The Library
Parallel selection by regular sampling
Tools
Tiskin, Alexander (2010) Parallel selection by regular sampling. In: 16th International Euro-Par Conference on Parallel Processing, Ischia, Italy, August 31 - September 03 2010 doi:10.1007/978-3-642-15291-7_36
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
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 | ||||
Editor: | DAmbra, P and Guarracino, M and Talia, D | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Number of Pages: | 7 | ||||
DOI: | 10.1007/978-3-642-15291-7_36 | ||||
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 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |