Tiskin, Alexander (2010) Parallel selection by regular sampling. In: Guarracino, M. R. and Vivien, F. and Traff, J. L. and Cannataro, M. and Danelutto, M. and Hast, A. and Perla, F. and Knüpfer, A. and Di Martino, B. and Alexander, M., (eds.) Euro-Par 2010 - Parallel Processing. Lecture Notes in Computer Science (6272). Germany: Springer Verlag, pp. 393-399. ISBN 9783642152900

Full text not available from this repository.

Abstract

Bulk-synchronous parallelism (BSP) is a simple and efficient paradigm for parallel algorithm design and analysis. In this paper, we present a new simple deterministic BSP algorithm for the classical problem of selecting the k-th smallest element from an array of size n, for a given k, on a parallel computer with p processors. Our algorithm is based on the technique of regular sampling. It runs in optimal $O({{n}\over{p}})$ local computation and communication, and near-optimal O(loglogp) synchronisation. The algorithm is of theoretical interest, as it gives an improvement in the asymptotic synchronisation cost over its predecessors. It is also simple enough to be implementable.

Item Type:	Book Item
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Series Name:	Lecture Notes in Computer Science
Publisher:	Springer Verlag
Place of Publication:	Germany
ISBN:	9783642152900
Book Title:	Euro-Par 2010 - Parallel Processing
Editor:	Guarracino, M. R. and Vivien, F. and Traff, J. L. and Cannataro, M. and Danelutto, M. and Hast, A. and Perla, F. and Knüpfer, A. and Di Martino, B. and Alexander, M.
Date:	31 August 2010
Number:	6272
Page Range:	pp. 393-399
Identification Number:	10.1007/978-3-642-15291-7_36
Status:	Not Peer Reviewed
Publication Status:	Published
Conference Paper Type:	Paper
Related URLs:	Other Repository
URI:	http://wrap.warwick.ac.uk/id/eprint/47481

Request changes to a record

Actions (login required)

View Item