RELATIONSHIPS BETWEEN REGULAR AND IRREGULAR COLLECTIVE COMMUNICATION OPERATIONS ON CLUSTERED MULTIPROCESSORS
Abstract
We characterize collective communication operations on (clustered) multiprocessor systems in terms of their communication volume, and arrive at useful relationships between regular and irregular operations over sets of processors and sets of cluster-nodes, respectively. We show that regular problems over sets of processors induce corresponding irregular problems over sets of nodes. We hereby identify a symmetric variant of the personalized all-to-all communication problem that might be worth studying in its own right, and discuss an algorithm for solving this problem. From a simple algorithm for the regular all-gather problem over sets of processors, we derive an algorithm for the irregular all-gather problem over both sets of processors and sets of nodes. For communication libraries like MPI, the relationships emphasize the need for efficient algorithms for the irregular collective communication operations.
References
- Journal of Parallel and Distributed Computing 66(1), 1 (2006). Crossref, ISI, Google Scholar
- Discrete Applied Mathematics 100(2), 1 (2000), DOI: 10.1016/S0166-218X(99)00155-9. Crossref, ISI, Google Scholar
- International Journal of Foundations of Computer Science 16(2), 195 (2005), DOI: 10.1142/S0129054105002942. Link, ISI, Google Scholar
-
W. J. Dally and B. Towles , Principles and Practices of Interconnection Networks ( Morgan Kaufmann Publishers , 2004 ) . Google Scholar N. T. Karonis , Exploiting hierarchy in parallel computer networks to optimize collective operation performance, 14th International Parallel and Distributed Processing Symposium (IPDPS 2000) (2000) pp. 377–386. Google Scholar- Journal of Parallel and Distributed Computing 63(5), 551 (2003), DOI: 10.1016/S0743-7315(03)00002-9. Crossref, ISI, Google Scholar
- Parallel Computing 27(11), 1431 (2001), DOI: 10.1016/S0167-8191(01)00098-9. Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 62, 1493 (2002). Crossref, ISI, Google Scholar
- Parallel Processing Letters 8(1), 83 (1998), DOI: 10.1142/S0129626498000110. Link, ISI, Google Scholar
- Cluster Computing 10(2), 127 (2007), DOI: 10.1007/s10586-007-0012-0. Crossref, ISI, Google Scholar
H. Ritzdorf and J. L. Träff , Collective operations in NEC's high-performance MPI libraries, International Parallel and Distributed Processing Symposium (IPDPS 2006) (2006) p. 100. Google ScholarP. Sanders and J. L. Träff , The hierarchical factor algorithm for all-to-all communication, Euro-Par 2002 Parallel Processing2400,Lecture Notes in Computer Science (Springer, 2002) pp. 799–803. Google Scholar-
M. Snir , MPI - The Complete Reference , 2nd edn. 1 ( The MPI Core, MIT Press , 1998 ) . Google Scholar - International Journal on High Performance Computing Applications 19, 49 (2004), DOI: 10.1177/1094342005051521. Crossref, ISI, Google Scholar
J. L. Träff , Hierarchical gather/scatter algorithms with graceful degradation, International Parallel and Distributed Processing Symposium (IPDPS 2004) (2004) p. 80. Google ScholarJ. L. Träff , Efficient allgather for regular SMP-clusters, Recent Advances in Parallel Virtual Machine and Message Passing Interface. 13th European PVM/MPI Users' Group Meeting4192,Lecture Notes in Computer Science (Springer, 2006) pp. 58–65. Google ScholarJ. L. Träff , A simple, pipelined algorithm for large, irregular all-gather problems, Recent Advances in Parallel Virtual Machine and Message Passing Interface. 15th European PVM/MPI Users' Group Meeting5205,Lecture Notes in Computer Science (Springer, 2008) pp. 84–93. Google Scholar


