Abstract.
Consider the selection problem of determining the k th smallest element of a set of n elements. Under the CGM (coarse-grained multicomputer) model with p processors and O(n/p) local memory, we present a deterministic parallel algorithm for the selection problem that requires O( log p) communication rounds. Besides requiring a low number of communication rounds, the algorithm also attempts to minimize the total amount of data transmitted in each round (only O(p) except in the last round). In addition to showing theoretical complexities, we present very promising experimental results obtained on a parallel machine that show almost linear speedup, indicating the efficiency and scalability of the proposed algorithm.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received June 1, 1997; revised March 10, 1998.
Rights and permissions
About this article
Cite this article
Saukas, E., Song, S. A Note on Parallel Selection on Coarse-Grained Multicomputers . Algorithmica 24, 371–380 (1999). https://doi.org/10.1007/PL00008268
Issue Date:
DOI: https://doi.org/10.1007/PL00008268