Coarse Grained Parallel Selection
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.
References
- 1. , Practical algorithms for selection on coarse-grained parallel computers, IEEE Transactions on Parallel and Distributed Systems 8(8) (1997) 813–824. Crossref, ISI, Google Scholar
- 2. , An improved, randomized algorithm for parallel selection with an experimental study, Journal of Parallel and Distributed Computing 64(9) (2004) 1051–1059. Crossref, ISI, Google Scholar
- 3. , Bounds for selection, Journal of Computer and System Sciences 7 (1973) 448–461. Crossref, Google Scholar
- 4. , Coarse grained gather and scatter operations with applications, Journal of Parallel and Distributed Computing 64(11) (2004) 1297–1310. Crossref, ISI, Google Scholar
- 5. , Scalable parallel algorithms for geometric pattern recognition, Journal of Parallel and Distributed Computing 58 (1999) 466–486. Crossref, ISI, Google Scholar
- 6. , Scalable parallel geometric algorithms for multicomputers, Int. Journal of Computational Geometry and Applications 6 (1996) 379–400. Link, ISI, Google Scholar
- 7. , Parallel selection algorithms for CGM and BSP models with application to sorting, Information Processing Society of Japan Journal 41(5) (2000) 1500–1508. Google Scholar
- 8. , Architecture independent parallel selection with applications to parallel priority queues, Theoretical Computer Science 301 (2003) 119–142. Crossref, ISI, Google Scholar
- 9. , Parallel algorithms for selection on the BSP and BSP models, Systems and Computers in Japan 33(12) (2002) 97–107. Crossref, Google Scholar
- 10. , Algorithms Sequential and Parallel, A Unified Approach, 3rd edn. (Cengage Learning, Boston, 2013). Google Scholar
- 11. , Parallel Algorithms for Regular Architectures: Meshes and Pyramids (The MIT Press, Cambridge, MA, 1996). Google Scholar
- 12. , Mathematical Statistics and Data Analysis, 2nd edn. (International Thomson Publishing, Belmont, CA, 1995). Google Scholar
- 13. , A note on parallel selection on coarse-grained multicomputers, Algorithmica 24 (1999) 371–380. Crossref, ISI, Google Scholar
- 14. ,
Parallel selection by regular sampling , Euro-Par 2010, Part II, P. D’AmbraM. GuarracinoD. Talia (eds.),LNCS , 6272 (Springer-Verlag, Berlin/Heidelberg, 2010), pp. 393–399. Crossref, Google Scholar


