Coarse grained parallel selection

DOI10.1142/S0129626421500031MaRDI QIDQ5087083zbMATH OpenOpenAlexFDO

Authors Laurence Boxer

Publication date 8 July 2022

Published in Parallel Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.00870

zbMATH Keywords

uniform distributionselection problemChebyshev's inequalitycoarse-grained multicomputer

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10)

Abstract: We analyze the running time of the Saukas-Song algorithm for selection on a coarse grained multicomputer 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 other algorithms for coarse grained selection that have optimal expected running time.

Recommendations

• scientific article; zbMATH DE number 2079315
• Optimal parallel selection
• scientific article; zbMATH DE number 4082988
• An optimally efficient selection algorithm
• scientific article; zbMATH DE number 4213428

Cites work

• scientific article; zbMATH DE number 824933 (Why is no real title available?)
• An improved, randomized algorithm for parallel selection with an experimental study
• Architecture independent parallel selection with applications to parallel priority queues
• Coarse grained gather and scatter operations with applications
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS
• Scalable parallel algorithms for geometric pattern recognition
• Time bounds for selection

Cited in

(2)

• A Greedy Strategy for Coarse-Grid Selection
• Coarse grained gather and scatter operations with applications

This page was built for publication: Coarse grained parallel selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5087083)