Article

Free access

Optimal software multicast in wormhole-routed multistage networks

Authors:

Lionel M. NiAuthors Info & Claims

Supercomputing '94: Proceedings of the 1994 ACM/IEEE conference on Supercomputing

Pages 703 - 712

Published: 14 November 1994 Publication History

Abstract

Multistage interconnection networks are a popular class of interconnection architecture for constructing scalable parallel computers (SPCs). The focus of this paper is on wormhole routed multistage networks supporting turnaround routing. Existing machines characterized by such a system model include the IBM SP-1, TMC CM-5, and Meiko CS-2.Efficient collective communication among processor nodes is critical to the performance of SPCs. A system-level multicast service, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is fundamental in supporting collective communication primitives including the application-level broadcast, reduction, and barrier synchronization. This paper addresses how to efficiently implement multicast services in wormhole-routed multistage networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. An optimal multicast algorithm is proposed. The results of implementations on a 64-node SP-1 show that the proposed algorithm significantly outperforms the application-level broadcast primitives provided by currently existing collective communication libraries including the public domain MPI.

References

[1]

Message Passing Interface Forum, "MPI: A Message-Passing Interface Standard," tech. rep., University of Tennessee, Mar. 1994.

Digital Library

[2]

H. Xu, P. K. McKinley, and L. M. Ni, "Efficient implementation of barrier synchronization in wormhole-routed hypercube multicomputers," Journal of Parallel and Distributed Computing, vol. 16, pp. 172 - 184, October 1992.

[3]

H. Xu, E. T. Kalns, P. K. McKinley, and L. M. Ni, "ComPaSS: A communication package for scalable software design," accepted to appear in Journal of Parallel and Distributed Computing, 1994.

Digital Library

[4]

P. K. McKinley, H. Xu, A. H. Esfahanian, and L. M. Ni, "Unicast-based multicast communication in wormhole-routed direct networks," in Proceedings of the 1992 International Conference on Parallel Processing, vol. II, pp. 10-19, Aug. 1992.

[5]

A. Bar-Noy, J. Bruck, C.-T. Ho, S. Kipnis, and B. Schieber, "Computing global combine operations in the multi-port postal model," in Proceedings of the fifth IEEE symposium on parallel and distributed processing, pp. 336-343, Dec. 1993.

[6]

D. F. Robinson, D. Judd, P. K. McKinley, and B. H. C. Cheng, "Efficient collective data distribution in all-port wormhole-routed hypercubes," in Proceedings of Supercomputing '93, pp. 792-801, Nov. 1993.

Digital Library

[7]

C.-T. Ho and M.-Y. Kao, "Optimal broadcast on hypercubes with wormhole and E-cube routings," in Proceedings of the 1993 International Conference on Parallel and Distributed Systems, pp. 694-697, 1992.

[8]

W. D. Gropp, E. Lusk, and A. Skjellum, Using MPI: Portable Parallel Programming with the Message-Passing Interface. MIT Press, 1994.

Digital Library

[9]

W. J. Dally and C. L. Seitz, "The torus routing chip," Journal of Distributed Computing, vol. 1, no. 3, pp. 187-196, 1986.

[10]

C. E. Leiserson et al., "The network architecture of the Connection Machine CM-5," in Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, (San Diego, CA.), pp. 272-285, Association for Computing Machinery, 1992.

Digital Library

[11]

Meiko Limited, Waltham, MA., Computing Surface: CS-2 Communications Networks, 1993.

[12]

C. B. Stunkel et al., "Architecture and implementation of Vulcan," in Proc. of the 8th International Parallel Processing Symposium, pp. 268-274, Apr. 1994.

Digital Library

[13]

L. M. Ni and P. K. McKinley, "A survey of wormhole routing techniques in direct networks," IEEE Computer, vol. 26, pp. 62 - 76, Feb. 1993.

Digital Library

[14]

C. E. Leiserson, "Fat-trees: Universal networks for hardware-efficient supercomputing," IEEE Transactions on Computers, vol. C-34, pp. 892-901, Oct. 1985.

Digital Library

[15]

L. M. Ni, Y. Gui, and S. Q. He, "Performance evaluation of multistage wormhole networks with turnaround routing," Tech. Rep. MSU-CPS-ACS-96, Michigan State University, July 1994.

[16]

H. Xu, Y.-D. Gui, and L. M. Ni, "Optimal software mulitcast in wormhole-routed multistage networks," Tech. Rep. MSU-CPS-ACS-91, Michigan State University, Mar. 1994.

[17]

W. Gropp, E. Lusk, and S. Pieper, "Users Guide for the ANL IBM SP-1 DRAFT," Tech. Rep. ANL/MCS-TM-00, Argonne National Laboratory, Feb. 1994.

[18]

W. Gropp and B. Smith, "Users manual for the Chameleon parallel programming tools," Tech. Rep. ANL-93/23, Argonne National Laboratory, June 1993.

[19]

H. Franke, "MPI-F: An MPI implementation for IBM SP-1," Feb. 1994. Available on anonymous ftp from info.mcs.anl.gov.

Cited By

Varavithya VMohapatra P(1999)Asynchronous Tree-Based Multicasting in Wormhole-Switched MINsIEEE Transactions on Parallel and Distributed Systems10.1109/71.80957410:11(1159-1178)Online publication date: 1-Nov-1999
https://dl.acm.org/doi/10.1109/71.809574
Sivaram RPanda DStunkel C(1998)Efficient Broadcast and Multicast on Multistage Interconnection Networks Using Multiport EncodingIEEE Transactions on Parallel and Distributed Systems10.1109/71.7305299:10(1004-1028)Online publication date: 1-Oct-1998
https://dl.acm.org/doi/10.1109/71.730529
Sivaram RStunkel CPanda D(1997)A Reliable Hardware Barrier Synchronization SchemeProceedings of the 11th International Symposium on Parallel Processing10.5555/645607.661666(274-280)Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.5555/645607.661666
Show More Cited By

Optimal software multicast in wormhole-routed multistage networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Optimal Software Multicast in Wormhole-Routed Multistage Networks

Multistage interconnection networks are a popular class of interconnection architecture for constructing scalable parallel computers (SPCs). The focus of this paper is on the multistage network system which supports wormhole routed turnaround routing. ...
Efficient software multicast in wormhole-routed unidirectional multistage networks
SPDP '95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing

A system-level multicast service, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is fundamental in supporting collective communication primitives including the application-level broadcast, ...
Communication modeling of multicast in all-port wormhole-routed NoCs

Multicast is one of the most frequently used collective communication operations in multi-core SoC platforms. Bus as the traditional interconnect architecture for SoC development has been highly efficient in delivering multicast messages. Since the bus ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Supercomputing '94: Proceedings of the 1994 ACM/IEEE conference on Supercomputing

November 1994

840 pages

ISBN:0818666056

Conference Chair:
Gary M. Johnson
George Mason University

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 14 November 1994

Check for updates

Qualifiers

Article

Conference

SC '94

Sponsor:

SIGARCH
IEEE-CS

SC '94: International Conference for High Performance Computing, Networking, Storage and Analysis

November 14 - 18, 1994

Washington, D.C.

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
109
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)7

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Varavithya VMohapatra P(1999)Asynchronous Tree-Based Multicasting in Wormhole-Switched MINsIEEE Transactions on Parallel and Distributed Systems10.1109/71.80957410:11(1159-1178)Online publication date: 1-Nov-1999
https://dl.acm.org/doi/10.1109/71.809574
Sivaram RPanda DStunkel C(1998)Efficient Broadcast and Multicast on Multistage Interconnection Networks Using Multiport EncodingIEEE Transactions on Parallel and Distributed Systems10.1109/71.7305299:10(1004-1028)Online publication date: 1-Oct-1998
https://dl.acm.org/doi/10.1109/71.730529
Sivaram RStunkel CPanda D(1997)A Reliable Hardware Barrier Synchronization SchemeProceedings of the 11th International Symposium on Parallel Processing10.5555/645607.661666(274-280)Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.5555/645607.661666
Nupairoj NNi LPark JChoi H(1997)Architecture-Dependent Tuning of the Parameterized Communication Model for Optimal MulticastingProceedings of the 11th International Symposium on Parallel Processing10.5555/645607.661656(578-582)Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.5555/645607.661656
Birchler BEsfahanian ATorng E(1997)Sufficient Conditions for Optimal Multicast CommunicationProceedings of the international Conference on Parallel Processing10.5555/645533.656509Online publication date: 11-Aug-1997
https://dl.acm.org/doi/10.5555/645533.656509
Park JYoon H(1997)Performance Analysis of Multistage Interconnection Networks using a Multicast AlgorithmProceedings of the High-Performance Computing on the Information Superhighway, HPC-Asia '9710.5555/523549.822921Online publication date: 28-Apr-1997
https://dl.acm.org/doi/10.5555/523549.822921
Stunkel CSivaram RPanda D(1997)Implementing multidestination worms in switch-based parallel systemsACM SIGARCH Computer Architecture News10.1145/384286.26412925:2(50-61)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/384286.264129
Stunkel CSivaram RPanda DPleszkun AMudge T(1997)Implementing multidestination worms in switch-based parallel systemsProceedings of the 24th annual international symposium on Computer architecture10.1145/264107.264129(50-61)Online publication date: 1-Jun-1997
https://dl.acm.org/doi/10.1145/264107.264129
Ni LGui YMoore S(1997)Performance Evaluation of Switch-Based Wormhole NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/71.5982748:5(462-474)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1109/71.598274
Yang Y(1996)A Class of Interconnection Networks for MulticastingProceedings of the 10th International Parallel Processing Symposium10.5555/645606.661164(796-802)Online publication date: 15-Apr-1996
https://dl.acm.org/doi/10.5555/645606.661164

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents