An architecture for optimal all-to-all personalized communication

ABSTRACT

In all-to-all personalized communication (AAPC), every node of a parallel system sends a potentially unique packet to every other node. AAPC is an important primitive operation for modern parallel compilers, since it is used to redistribute data structures during parallel computations. As an extremely dense communication pattern, AAPC causes congestion in many types of networks and therefore executes very poorly on general purpose, asynchronous message passsing routers. We present and evaluate a network architecture that executes all-to-all communication optimally on a two-dimensional torus. The router combines optimal partitions of the AAPC step with a self-synchronizing switching mechanism integrated into a conventional wormhole router. Optimality is achieved by routing along shortest paths while fully utilizing all links. A simple hardware addition for synchronized message switching can guarantee optimal AAPC routing in many existing network architectures. The flexible communication agent of the iWarp VLSI component allowed us to implement an efficient prototype for the evaluation of the hardware complexity as well as possible software overheads. The measured performance on an 8 × 8 torus exceeded 2 GigaBytes/sec or 80% of the limit set by the raw speed of the interconnects. We make a quantitative comparison of the AAPC router with a conventional message passing system. The potential gain of such a router for larger parallel programs is illustrated with the example of a two-dimensional Fast Fourier Transform.

REFERENCES

• 1: ADAMS, D. Cray T3D System Architecture Overview. Tech. rep., Cray Research Inc., September 1993. Revision 1.C.
• 2: Amotz Bar-Noy , Shlomo Kipnis, Designing broadcasting algorithms in the postal model for message-passing systems, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.13-22, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140903]
• 3: Pablo E. Berman , Luis Gravano , Gustavo D. Pifarré , Jorge L. C. Sanz, Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.3-12, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140902]
• 4: BOKHARI, S. Multiphase complete exchange on a circuit switched hypercube. Tech. Rep. 91-5, ICASE, January 1991.
• 5: BOKHARI, S. H., AND BERRYMAN, H. Complete Exchange on a Circuit Switched Mesh. In Proc. Scalable High Performance Computing Conference (Williamsburg, VA, April 1992), pp. 300--306.
• 6: S. Borkar , R. Cohn , G. Cox , S. Gleason , T. Gross, Warp: an integrated solution of high-speed parallel computing, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.330-339, November 12-17, 1988, Orlando, Florida, United States
• 7: Shekhar Borkar , Robert Cohn , George Cox , Thomas Gross , H. T. Kung , Monica Lam , Margie Levine , Brian Moore , Wire Moore , Craig Peterson , Jim Susman , Jim Sutton , John Urbanski , Jon Webb, Supporting systolic and memory communication in iWarp, Proceedings of the 17th annual international symposium on Computer Architecture, p.70-81, May 28-31, 1990, Seattle, Washington, United States
• 8: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 9: Anja Feldmann , Thomas M. Stricker , Thomas E. Warfel, Supporting sets of arbitrary connections on iWarp through communication context switches, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.203-212, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165257]
• 10: HIGH PERFORMANCE FORTRAN FORUM. High Performance Fortran Language Specification Version 1.0., May 1993.
• 11: HINRICHS, S. Compiler Resource Management for Connection-Based Communication. Internal document, 1994.
• 12: Susan Hinrichs , Corey Kosak , David R. O''Hallaron , Thomas M. Stricker , Riichiro Take, An Architecture for Optimal All-to-All Personalized Communication, Carnegie Mellon University, Pittsburgh, PA, 1994
• 13: HORIE, T., AND HAYASHI, K. All-to-All Personalized Communication on a Wrap-around Mesh. In Proceedings of CAP Workshop (Canberra, Austrailia, November 1991 ).
• 14: Takeshi Horie , Hiroaki Ishihata , Morio Ikesaka, Design and Implementation of an Interconnection Network for the AP1000, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information Processing '92, Volume 1, p.555-561, September 07-11, 1992
• 15: INTEL CORP. Paragon X/PS Product Overview, March 1991.
• 16: S. Lennart Johnsson , Ching-Tien Ho, Optimum Broadcasting and Personalized Communication in Hypercubes, IEEE Transactions on Computers, v.38 n.9, p.1249-1268, September 1989 [doi>10.1109/12.29465]
• 17: Charles E. Leiserson , Zahi S. Abuhamdeh , David C. Douglas , Carl R. Feynman , Mahesh N. Ganmukhi , Jeffrey V. Hill , Daniel Hillis , Bradley C. Kuszmaul , Margaret A. St. Pierre , David S. Wells , Monica C. Wong , Shaw-Wen Yang , Robert Zak, The network architecture of the Connection Machine CM-5 (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.272-285, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141883]
• 18: THE MESSAGE PASSING INTERFACE FORUM. Draft Document for a Standard Message Passing Interface, November 1993.
• 19: SCOTT, D. S. Efficient AII-to-AH Communication Patterns in Hypercube and Mesh Topologies. In The Sixth Distributed Memory Computing Conference Proceedings (1991 ), pp. 398- 403.
• 20: Marc Snir, Scalable parallel computing: the IBM 9076 scalable POWERparallel 1, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.42, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165236]
• 21: James M. Stichnoth , David O'Hallaron , Thomas R. Gross, Generating communication for array statements: design, implementation, and evaluation, Journal of Parallel and Distributed Computing, v.21 n.1, p.150-159, April 1994 [doi>10.1006/jpdc.1994.1048]
• 22: STRICKER, T. Message Routing on Irregular 2D-Meshes and Tori. In Proceedings of the 6th Distributed Memory Computing Conference (Portland, OR, Apr. 1991 ), pp, 170-177. Also appeared as Technical Report CMU-CS-91-109, Carnegie Mellon School of Computer Science.
• 23: STmCKER, T., STICHNOTH, J., O'HALLARON, D., HtNmCttS, S., AND GROSS, T. Decoupling Communication Services of Compiled Parallel Programs. Tech. Rep. CMU-CS-94-139, Carnegie Mellon University, School of Computer Science, 1994.
• 24: Jaspal Subhlok , James M. Stichnoth , David R. O'Hallaron , Thomas Gross, Exploiting task and data parallelism on a multicomputer, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.13-22, May 19-22, 1993, San Diego, California, United States
• 25: V. S. Sunderam, PVM: a framework for parallel distributed computing, Concurrency: Practice and Experience, v.2 n.4, p.315-339, Dec. 1990 [doi>10.1002/cpe.4330020404]
• 26: TAKE, R. A Routing Method for All-to-all Burst on Hypercube Networks. In Proc. 35th National Conference of Information Processing SocietyofJapan(1987), pp. 151-152. In Japanese.
• 27: Riichirou Take , Yasuo Noguchi , Haruo Yokota, An architecture for parallel database computing, Proceedings of the world transputer user group (WOTUG) conference on Transputing '91, p.1-14, May 1991, Sunnyvale, California, United States
• 28: VARVARIGOS, E. A., AND BERTSEKAS, D. P. Communication algorithms for isotropic tasks in hypercubes and wraparound meshes. Parallel Computing 18 (1992), 1233-1257.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Algorithms, Measurement, Performance, Theory, Verification