A Note on Parallel Selection on Coarse-Grained Multicomputers |
| |
Authors: | E L G Saukas S W Song |
| |
Affiliation: | Department of Computer Science, Institute of Mathematics and Statistics, University of S?o Paulo, S?o Paulo, SP 05508-900 Brazil., BR
|
| |
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.
Received June 1, 1997; revised March 10, 1998. |
| |
Keywords: | , Coarse-grained multicomputer, Parallel algorithm, Selection problem, |
本文献已被 SpringerLink 等数据库收录! |
|