World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

RELATIONSHIPS BETWEEN REGULAR AND IRREGULAR COLLECTIVE COMMUNICATION OPERATIONS ON CLUSTERED MULTIPROCESSORS

    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

    • D. T. Alfredo Goldman and Joseph G. Peters, Journal of Parallel and Distributed Computing 66(1), 1 (2006). Crossref, ISIGoogle Scholar
    • A. Bar-Noy, S. Kipnis and B. Schieber, Discrete Applied Mathematics 100(2), 1 (2000), DOI: 10.1016/S0166-218X(99)00155-9. Crossref, ISIGoogle Scholar
    • F. Cappelloet al., International Journal of Foundations of Computer Science 16(2), 195 (2005), DOI: 10.1142/S0129054105002942. Link, ISIGoogle Scholar
    • W. J.   Dally and B.   Towles , Principles and Practices of Interconnection Networks ( Morgan Kaufmann Publishers , 2004 ) . Google Scholar
    • N. T. Karoniset al., 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
    • N. T. Karonis, B. R. Toonen and I. T. Foster, Journal of Parallel and Distributed Computing 63(5), 551 (2003), DOI: 10.1016/S0743-7315(03)00002-9. Crossref, ISIGoogle Scholar
    • T. Kielmannet al., Parallel Computing 27(11), 1431 (2001), DOI: 10.1016/S0167-8191(01)00098-9. Crossref, ISIGoogle Scholar
    • W. Liu, C.-L. Wang and V. K. Prasanna, Journal of Parallel and Distributed Computing 62, 1493 (2002). Crossref, ISIGoogle Scholar
    • A. Michail, Parallel Processing Letters 8(1), 83 (1998), DOI: 10.1142/S0129626498000110. Link, ISIGoogle Scholar
    • J. Pješivac-Grbovićet al., Cluster Computing 10(2), 127 (2007), DOI: 10.1007/s10586-007-0012-0. Crossref, ISIGoogle 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 Scholar
    • P. 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 et al. , MPI - The Complete Reference , 2nd edn.   1 ( The MPI Core, MIT Press , 1998 ) . Google Scholar
    • R. Thakur, W. D. Gropp and R. Rabenseifner, International Journal on High Performance Computing Applications 19, 49 (2004), DOI: 10.1177/1094342005051521. Crossref, ISIGoogle Scholar
    • J. L. Träff, Hierarchical gather/scatter algorithms with graceful degradation, International Parallel and Distributed Processing Symposium (IPDPS 2004) (2004) p. 80. Google Scholar
    • J. 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 Scholar
    • J. L. Träffet al., 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