MRNet: A Software-Based Multicast/Reduction Network for Scalable Tools

ABSTRACT

We present MRNet, a software-based multicast/reduction network for building scalable performance and system administration tools. MRNet supports multiple simultaneous, asynchronous collective communication operations. MRNet is flexible, allowing tool builders to tailor its process network topology to suit their tool's requirements and the underlying system's capabilities. MRNet is extensible, allowing tool builders to incorporate custom data reductions to augment its collection of built-in reductions. We evaluated MRNet in a simple test tool and also integrated into an existing, real-world performance tool with up to 512 tool back-ends. In the real-world tool, we used MRNet not only for multicast and simple data reductions but also with custom histogram and clock skew detection reductions. In our experiments, the MRNet-based tools showed significantly better performance than the tools without MRNet for average message latency and throughput, overall tool start-up latency, and performance data processing throughput.

REFERENCES

• 1: [1] Advanced Simulation and Computing program, National Nuclear Security Administration, United States of America Department of Energy. ¿http://www.nnsa.doe.gov/asc/home.htm¿, February 6, 2003.
• 2: Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model for parallel computation, Journal of Parallel and Distributed Computing, v.44 n.1, p.71-79, July 10, 1997 [doi>10.1006/jpdc.1997.1346]
• 3: [3] Susanne M. Balle. Personal communication, November 2002.
• 4: Susanne M. Balle , Bevin R. Brett , Chih-Ping Chen , David LaFrance-Linden, A New Approach to Parallel Debugger Architecture, Proceedings of the 6th International Conference on Applied Parallel Computing Advanced Scientific Computing, p.139-149, June 15-18, 2002
• 5: [5] M. Bernaschi and G. Iannello. Collective Communication Operations: Experimental Results vs. Theory. Concurrency: Practice and Experience 10, 5, April 1998, pp. 359-386.
• 6: Peter N. Brown , Robert D. Falgout , Jim E. Jones, Semicoarsening Multigrid on Distributed Memory Machines, SIAM Journal on Scientific Computing, v.21 n.5, p.1823-1834, April 2000 [doi>10.1137/S1064827598339141]
• 7: [7] Center for Computational Research, University at Buffalo, The State University of New York. ¿http://www.ccr.buffalo.edu¿, February 6, 2003.
• 8: David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996 [doi>10.1145/240455.240477]
• 9: [9] Earth Simulator Center. ¿http://www.es.jamstec.go.jp¿, February 6, 2003.
• 10: [10] Etnus LLC, "TotalView User's Guide", Document version 6.0.0-1, January 2003. ¿http://www.etnus.com¿
• 11: D. A. Evensky , A. C. Gentile , L. J. Camp , R. C. Armstrong, Lilith: Scalable Execution of User Code for Distributed Computing, Proceedings of the 6th IEEE International Symposium on High Performance Distributed Computing, p.305, August 05-08, 1997
• 12: [12] D.A. Evensky. Personal communication, November 2001.
• 13: [13] Forecast Systems Laboratory, National Oceanic and Atmospheric Administration. ¿http://hpcs.fsl.noaa.gov¿, Feb 6, 2003.
• 14: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 15: J. K. Hollingsworth , O. Niam , B. P. Miller , Zhichen Xu , M. J. R. Goncalves , Ling Zheng, MDL: A Language And Compiler For Dynamic Program Instrumentation, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.201, November 11-15, 1997
• 16: Richard M. Karp , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser, Optimal broadcast and summation in the LogP model, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.142-153, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165250]
• 17: Thilo Kielmann , Rutger F. H. Hofman , Henri E. Bal , Aske Plaat , Raoul A. F. Bhoedjang, MagPIe: MPI's collective communication operations for clustered wide area systems, ACM SIGPLAN Notices, v.34 n.8, p.131-140, Aug. 1999
• 18: [18] Lawrence Livermore National Laboratory. Multiprogrammatic Capability Cluster. ¿http://www.llnl.gov/linux/mcr¿, February 6, 2003.
• 19: [19] Lawrence Livermore National Laboratory. Using ASCI Blue Pacific. ¿http://www.llnl.gov/asci/platforms/bluepac¿, February 13, 2003.
• 20: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 21: [21] M.L. Massie, B.N. Chun, and D.E. Culler. The Ganglia Distributed Monitoring System: Design, Implementation, and Experience. University of California, Berkeley Technical Report, ¿http://ganglia.sourceforge.net/talks/parallel_computi ng/ganglia-twocol.pdf¿, February 2003.
• 22: [22] Message Passing Interface Forum. MPI: A Message Passing Interface Standard. International Journal of Supercomputing Applications 8, 3/4, Fall/Winter 1994.
• 23: Barton P. Miller , Mark D. Callaghan , Jonathan M. Cargille , Jeffrey K. Hollingsworth , R. Bruce Irvin , Karen L. Karavanic , Krishna Kunchithapadam , Tia Newhall, The Paradyn Parallel Performance Measurement Tool, Computer, v.28 n.11, p.37-46, November 1995 [doi>10.1109/2.471178]
• 24: Ambuj Shatdal , Jeffrey F. Naughton, Adaptive parallel aggregation algorithms, ACM SIGMOD Record, v.24 n.2, p.104-114, May 1995
• 25: Matthew J. Sottile , Ronald G. Minnich, Supermon: A High-Speed Cluster Monitoring System, Proceedings of the IEEE International Conference on Cluster Computing, p.39, September 23-26, 2002
• 26: [26] UoE HPCX Ltd. ¿http://www.hpcx.ac.uk¿, February 6, 2003.
• 27: Sathish S. Vadhiyar , Graham E. Fagg , Jack Dongarra, Automatically tuned collective communications, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.3-es, November 04-10, 2000, Dallas, Texas, United States
• 28: Abdul Waheed , Diane T. Rover , Jeffrey K. Hollingsworth, Modeling and Evaluating Design Alternatives for an On-Line Instrumentation System: A Case Study, IEEE Transactions on Software Engineering, v.24 n.6, p.451-470, June 1998 [doi>10.1109/32.689402]

INDEX TERMS

Keywords:
Scalability, tools, multicast, reduction, aggregation