Parallel selection by regular sampling
Tiskin, Alexander (2010) Parallel selection by regular sampling. In: 16th International Euro-Par Conference on Parallel Processing, Ischia, Italy, August 31 - September 03 2010Full text not available from this repository.
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.
|Item Type:||Conference Item (Paper)|
|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|
|Editor:||DAmbra, P and Guarracino, M and Talia, D|
|Number of Pages:||7|
|Status:||Not Peer Reviewed|
|Conference Paper Type:||Paper|
|Title of Event:||16th International Euro-Par Conference on Parallel Processing|
|Type of Event:||Conference|
|Location of Event:||Ischia, Italy|
|Date(s) of Event:||August 31 - September 03 2010|
Actions (login required)