Multi-protocol active messages on a cluster of SMP's

ABSTRACT

Clusters of multiprocessors, or Clumps, promise to be the supercomputers of the future, but obtaining high performance on these architectures requires an understanding of interactions between the multiple levels of interconnection. In this paper, we present the first multi-protocol implementation of a lightweight message layer---a version of Active Messages-II running on a cluster of Sun Enterprise 5000 servers connected with Myrinet. This research brings together several pieces of high-performance interconnection technology: bus backplanes for symmetric multiprocessors, low-latency networks for connections between machines, and simple, user-level primitives for communication. The paper describes the shared memory message-passing protocol and analyzes the multi-protocol implementation with both microbenchmarks and Split-C applications. Three aspects of the communication layer are critical to performance: the overhead of cache-coherence mechanisms, the method of managing concurrent access, and the cost of accessing state with the slower protocol. Through the use of an adaptive polling strategy, the multi-protocol implementation limits performance interactions between the protocols, delivering up to 160 MB/s of bandwidth with 3.6 microsecond end-to-end latency. Applications within an SMP benefit from this fast communication, running up to 75% faster than on a network of uniprocessor workstations. Applications running on the entire Clump are limited by the balance of NIC's to processors in our system, and are typically slower than on the NOW. These results illustrate several potential pitfalls for the Clumps architecture.

REFERENCES

• 1: Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.95-105, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215427]
• 2: Accelerated Strategic Computing Initiative, a program of the Department of Energy. Information is available via http://www.llnl.gov/asci-alliances/.
• 3: D. A. Bader, J. JáJá, "SIMPLE: A Methodology for Programming High Performance Algorithms on Clusters of Symmetric Multiprocessors (SMP's)," preliminary version, May 1997, available via http://www.umiacs.umd.edu/research/EXPAR.
• 4: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• 5: Eric A. Brewer , Bradley C. Kuszmaul, How to Get Good Performance from the CM-5 Data Network, Proceedings of the 8th International Symposium on Parallel Processing, p.858-867, April 01, 1994
• 6: R. Butler, E. Lusk, "Monitors, Message, and Clusters: the p4 Parallel Programming System," available via http://www.mcs.anl.gov/home/lusk/p4/p4-paper/paper.html.
• 7: B. N. Chun, A. M. Mainwaring, D. E. Culler, "A General-Purpose Protocol Architecture for a Low-Latency, Multi-gigabit System Area Network," Proceedings of Hot Interconnects V, Stanford, California, August 1997.
• 8: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 9: 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
• 10: David E. Culler , Lok Tin Liu , Richard P. Martin , Chad O. Yoshikawa, Assessing Fast Network Interfaces, IEEE Micro, v.16 n.1, p.35-43, February 1996 [doi>10.1109/40.482310]
• 11: S. J. Fink, S. B. Baden, "Non-Uniform Partitioning of Finite Difference Methods Running on SMP Clusters," submitted for publication, available via http://www-cse.ucsd.edu/users/baden/MT.html.
• 12: S. J. Fink, S. B. Baden, "Runtime Support for Multi-Tier Programming of Block-Structured Applications on SMP Clusters," submitted for publication, available via http://www-cse.ucsd.edu/users/baden/MT.html.
• 13: Ian Foster , Carl Kesselman , Steven Tuecke, The Nexus approach to integrating multithreading and communication, Journal of Parallel and Distributed Computing, v.37 n.1, p.70-82, Aug. 25, 1996 [doi>10.1006/jpdc.1996.0108]
• 14: Ian Foster , Jonathan Geisler , Carl Kesselman , Steven Tuecke, Managing multiple communication methods in high-performance networked computing systems, Journal of Parallel and Distributed Computing, v.40 n.1, p.35-48, Jan. 10, 1997 [doi>10.1006/jpdc.1996.1266]
• 15: W. W. Gropp , E. L. Lusk, A taxonomy of programming models for symmetric multiprocessors and SMP clusters, Proceedings of the conference on Programming Models for Massively Parallel Computers, p.2, October 09-12, 1995
• 16: Matthew Haines , David Cronk , Piyush Mehrotra, On the design of Chant: a talking threads package, Proceedings of the 1994 conference on Supercomputing, p.350-359, December 1994, Washington, D.C., United States
• 17: Dongming Jiang , Hongzhang Shan , Jaswinder Pal Singh, Application restructuring and performance portability on shared virtual memory and hardware-coherent multiprocessors, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.217-229, June 18-21, 1997, Las Vegas, Nevada, United States
• 18: B.-H. Lim, P. Heidelberger, P. Pattnaik, M. Snir, "Message Proxies for Efficient, Protected Communication on SMP Clusters," IBM Almaden Research Report #RC 20522 (90972), August 1996.
• 19: L. T. Liu, D. E. Culler, "Evaluation of the Intel Paragon on Active Message Communication," Proceedings of Intel Supercomputer Users Group Conference, June 1995, also available via http://now.CS.Berkeley.EDU.
• 20: S. S. Lumetta, D. E. Culler, "Managing Concurrent Access for Shared Memory Active Messages," U. C. Berkeley Technical Report in preparation.
• 21: Alan Mainwaring , David Culler, Active Message Applications Programming Interface, University of California at Berkeley, Berkeley, CA, 1996
• 22: R. Martin, "HPAM: an Active Message Layer for a Network of HP Workstations," Proceedings of Hot Interconnects II, Stanford, California, August 1994, pp. 40-58.
• 23: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 24: S. S. Mukherjee, M. D. Hill, "A Case for Making Network Interfaces Less Peripheral," Proceedings of Hot Interconnects V, Stanford, California, August 1997.
• 25: R. H. Saavedra , R. S. Gaines , M. J. Carlton, Micro benchmark analysis of the KSR1, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.202-213, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169695]
• 26: Klaus E. Schauser , Chris J. Scheiman, Experience with active messages on the Meiko CS-2, Proceedings of the 9th International Symposium on Parallel Processing, p.140-149, April 25-28, 1995
• 27: A. Singhal, D. Broniarczyk, F. Cerauskis, J. Price, L. Yuan, C. Cheng, D. Doblar, S. Fosth, N. Agarwal, K. Harvey, E. Hagersten, B. Liencres, "Gigaplane: A High Performance Bus for Large SMPs," Proceedings of Hot Interconnects IV, Stanford, California, August 1996, pp. 41-52
• 28: Lewis W. Tucker , Alan Mainwaring, CMMD: active messages on the CM-5, Parallel Computing, v.20 n.4, p.481-496, April 1994 [doi>10.1016/0167-8191(94)90024-8]
• 29: T. von Eicken, V. Avula, A. Basu, V. Buch, "Low-latency Communication over ATM Networks Using Active Messages," Proceedings of Hot Interconnects II, Stanford, California, August 1994, pp. 60-71.
• 30: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 31: Paul R. Woodward, Perspectives on Supercomputing: Three Decades of Change, Computer, v.29 n.10, p.99-111, October 1996 [doi>10.1109/2.539728]
• 32: Donald Yeung , John Kubiatowicz , Anant Agarwal, MGS: a multigrain shared memory system, Proceedings of the 23rd annual international symposium on Computer architecture, p.44-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States