Dynamic statistical profiling of communication activity in distributed applications

ABSTRACT

Performance analysis of communication activity for a terascale application with traditional message tracing can be overwhelming in terms of overhead, perturbation, and storage. We propose a novel alternative that enables dynamic statistical profiling of an application's communication activity using message sampling. We have implemented an operational prototype, named PHOTON, and our evidence shows that this new approach can provide an accurate, low-overhead, tractable alternative for performance analysis of communication activity. PHOTON consists of two components: a Message Passing Interface (MPI) profiling layer that implements sampling and analysis, and a modified MPI runtime that appends a small but necessary amount of information to individual messages. More importantly, this alternative enables an assortment of runtime analysis techniques so that, in contrast to post-mortem, trace-based techniques, the raw performance data can be jettisoned immediately after analysis. Our investigation shows that message sampling can reduce overhead to imperceptible levels for many applications. Experiments on several applications demonstrate the viability of this approach. For example, with one application, our technique reduced the analysis overhead from 154% for traditional tracing to 6% for statistical profiling. We also evaluate different sampling techniques in this framework. The coverage of the sample space provided by purely random sampling is superior to counter- and timer-based sampling. Also, PHOTON's design reveals that frugal modifications to the MPI runtime system could facilitate such techniques on production computing systems, and it suggests that this sampling technique could execute continuously for long-running applications.

REFERENCES

• 1: George S. Almasi , Cǎlin Caşcaval , José G. Castaños , Monty Denneau , Wilm Donath , Maria Eleftheriou , Mark Giampapa , Howard Ho , Derek Lieber , José E. Moreira , Dennis Newns , Marc Snir , Henry S. Warren, Jr., Demonstrating the scalability of a molecular dynamics application on a Petaflop computer, Proceedings of the 15th international conference on Supercomputing, p.393-406, June 2001, Sorrento, Italy [doi>10.1145/377792.377896]
• 2: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.357-390, Nov. 1997 [doi>10.1145/265924.265925]
• 3: Thomas E. Anderson , Edward D. Lazowska, Quartz: a tool for tuning parallel program performance, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.115-125, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 4: Robert Bosch , Chris Stolte , Diane Tang , John Gerth , Mendel Rosenblum , Pat Hanrahan, Rivet: a flexible environment for computer systems visualization, ACM SIGGRAPH Computer Graphics, v.34 n.1, February 2000 [doi>10.1145/604446.604455]
• 5: 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]
• 6: Jordi Caubet , Judit Gimenez , Jesús Labarta , Luiz De Rose , Jeffrey S. Vetter, A Dynamic Tracing Mechanism for Performance Analysis of OpenMP Applications, Proceedings of the International Workshop on OpenMP Applications and Tools: OpenMP Shared Memory Parallel Programming, p.53-67, July 30-31, 2001
• 7: Kimberly C. Claffy , George C. Polyzos , Hans-Werner Braun, Application of sampling methodologies to network traffic characterization, Conference proceedings on Communications architectures, protocols and applications, p.194-203, September 13-17, 1993, San Francisco, California, United States
• 8: G. A. Geist, M. T. Heath et al., "A Users' Guide to PICL - A Portable Instrumented Communication Library," Oak Ridge National Laboratory, P.O.Box 2009, Bldg. 9207-A, Oak Ridge, TN 37831-8083 1991.
• 9: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• 10: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI (2nd ed.): portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1999
• 11: W. D. Gropp, E. Lusk, and D. Swider, "Improving the Performance of MPI Derived Datatypes," Proc. MPI Developers and Users Conference (MPIDC), 1999.
• 12: W. Gu, G. Eisenhauer et al., "Falcon: On-line Monitoring and Steering of Parallel Programs," Concurrency: Practice and Experience, 10(9):699-736, 1998.
• 13: Michael T. Heath , Allen D. Malony , Diane T. Rover, Parallel Performance Visualization: From Practice to Theory, IEEE Parallel & Distributed Technology: Systems & Technology, v.3 n.4, p.44-60, December 1995 [doi>10.1109/88.473613]
• 14: Jay Hoeflinger , Bob Kuhn , Wolfgang E. Nagel , Paul Petersen , Hrabri Rajic , Sanjiv Shah , Jeffrey S. Vetter , Michael Voss , Renee Woo, An Integrated Performance Visualizer for MPI/OpenMP Programs, Proceedings of the International Workshop on OpenMP Applications and Tools: OpenMP Shared Memory Parallel Programming, p.40-52, July 30-31, 2001
• 15: Adolfy Hoisie , Olaf Lubeck , Harvey Wasserman , Fabrizio Petrini , Hank Alme, A General Predictive Performance Model for Wavefront Algorithms on Clusters of SMPs, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.219, August 21-24, 2000
• 16: K. R. Koch, R. S. Baker, and R. E. Alcouffe, "Solution of the First-Order Form of the 3-D Discrete Ordinates Equation on a Massively Parallel Processor," Trans. Amer. Nuc. Soc., 65(198), 1992.
• 17: J. Labarta, S. Girona et al., "DiP: A Parallel Program Development Environment," CEPBA, Barcelona, Spain 1996.
• 18: A. D. Malony , D. A. Reed, Visualizing parallel computer system performance, Instrumentation for future parallel computing systems, ACM Press, New York, NY, 1989 [doi>10.1145/75705.75709]
• 19: A. A. Mirin , R. H. Cohen , B. C. Curtis , W. P. Dannevik , A. M. Dimits , M. A. Duchaineau , D. E. Eliason , D. R. Schikore , S. E. Anderson , D. H. Porter , P. R. Woodward , L. J. Shieh , S. W. White, Very high resolution simulation of compressible turbulence on the IBM-SP system, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.70-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331601]
• 20: D. A. Reed, P. C. Roth et al., "Scalable performance analysis: the Pablo performance analysis environment," Proc. Scalable Parallel Libraries Conf., 1994, pp. 104-13.
• 21: Sameer Shende , Allen D. Malony , Janice Cuny , Peter Beckman , Steve Karmesin , Kathleen Lindlan, Portable profiling and tracing for parallel, scientific applications using C++, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.134-145, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281049]
• 22: Marc Snir , Steve Otto, MPI-The Complete Reference: The MPI Core, MIT Press, Cambridge, MA, 1998
• 23: John T. Stasko , Marc H. Brown , Blaine A. Price, Software Visualization, MIT Press, Cambridge, MA, 1997
• 24: Jeffrey Vetter, Performance analysis of distributed applications using automatic classification of communication inefficiencies, Proceedings of the 14th international conference on Supercomputing, p.245-254, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335255]
• 25: Jeffrey S. Vetter , Frank Mueller, Communication Characteristics of Large-Scale Scientific Applications for Contemporary Cluster Architectures, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.96, April 15-19, 2002
• 26: C. Eric Wu , Anthony Bolmarcich , Marc Snir , David Wootton , Farid Parpia , Anthony Chan , Ewing Lusk , William Gropp, From trace generation to visualization: a performance framework for distributed parallel systems, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.50-es, November 04-10, 2000, Dallas, Texas, United States