The Library
Parallel selection by regular sampling
Tools
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
PDF
fulltext5.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (140Kb) |
Official URL: http://dx.doi.org/10.1007/978-3-642-15291-7_36
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, Engineering and Medicine > 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. | ||||
Official Date: | 31 August 2010 | ||||
Dates: |
|
||||
Number: | 6272 | ||||
Page Range: | pp. 393-399 | ||||
DOI: | 10.1007/978-3-642-15291-7_36 | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 21 December 2015 | ||||
Conference Paper Type: | Paper |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |