151. Coarse Grained Parallel Selection.
- Author
-
Boxer, Laurence
- Subjects
- *
PARALLEL computers , *DISTRIBUTION (Probability theory) , *CASE goods - Abstract
Several efficient, but non-optimal, solutions to the Selection Problem on coarse grained parallel computers have appeared in the literature. We consider the example of the Saukas-Song algorithm; we analyze it without expressing the running time in terms of communication rounds. This shows that while in the best case the Saukas-Song algorithm runs in asymptotically optimal time, in general it does not. We propose another algorithm for coarse grained selection that has optimal expected running time. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF