Coarse grained parallel selection

DOI10.1142/S0129626421500031zbMATH Open1490.68294arXiv1712.00870OpenAlexW3132738721MaRDI QIDQ5087083FDOQ5087083

Authors: Laurence Boxer 

Publication date: 8 July 2022

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

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.

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

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

zbMATH Keywords

uniform distributionselection problemChebyshev's inequalitycoarse-grained multicomputer

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS
• Time bounds for selection
• Coarse grained gather and scatter operations with applications
• An improved, randomized algorithm for parallel selection with an experimental study
• Architecture independent parallel selection with applications to parallel priority queues
• Scalable parallel algorithms for geometric pattern recognition

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)