Paper Info
Title
Parallel selection by regular sampling
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/p) local computation and communication, and near-optimal O(log log p) 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.
Year
Venue
Keywords
2010
Euro-Par (2)
parallel computer,new simple deterministic bsp,asymptotic synchronisation cost,p processor,parallel algorithm design,optimal o,near-optimal o,regular sampling,classical problem,bulk-synchronous parallelism,log log p,parallel selection,parallel algorithm,bulk synchronous parallel
DocType
Volume
ISSN
Conference
6272
0302-9743
ISBN
Citations 
PageRank 
3-642-15290-2
1
0.44
References 
Authors
17
1
Name
Order
Citations
PageRank
Alexander Tiskin122015.50