Performance analysis of distributed applications using automatic classification of communication inefficiencies

ABSTRACT

We present a technique for performance analysis that helps users understand the communication behavior of their message passing applications. Our method automatically classifies individual communication operations and it reveals the cause of communication inefficiencies in the application. This classification allows the developer to focus quickly on the culprits of truly inefficient behavior, rather than manually foraging through massive amounts of performance data. Specifically, we trace the message operations of MPI applications and then classify each individual communication event using decision tree classification, a supervised learning technique. We train our decision tree using microbenchmarks that demonstrate both efficient and inefficient communication. Since our technique adapts to the target system's configuration through these microbenchmarks, we can simultaneously automate the performance analysis process and improve classification accuracy. Our experiments on four applications demonstrate that our technique can improve the accuracy of performance analysis, and dramatically reduce the amount of data that users must encounter

REFERENCES

• 1: 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
• 2: D. Bailey, E. Barszez et al., "The NAS Parallel Benchmarks (94)," NASA Ames Research Center, RNR Technical Report RNR-94-007, 1994.
• 3: Maria Calzarossa , Luisa Massari , Alessandro Merlo , Mario Pantano , Daniele Tessera, Medea: A Tool for Workload Characterization of Parallel Systems, IEEE Parallel & Distributed Technology: Systems & Technology, v.3 n.4, p.72-80, December 1995 [doi>10.1109/88.473615]
• 4: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 5: Ian Foster, Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 6: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 7: J.A. Gannon, K.J. Williams et ai., "Using perturbation tracking to compensate for intrusion in message-passing systems," Prec. 14th Int'l Conf. Distributed Computing Systems, 1994, pp. 414-21.
• 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: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI (2nd ed.): portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1999
• 10: 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]
• 11: Minwen Ji , Edward W. Felten , Kai Li, Performance measurements for multithreaded programs, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.161-170, June 22-26, 1998, Madison, Wisconsin, United States
• 12: Wenke Lee , Salvatore J. Stolfo , Kui W. Mok, Mining in a data-flow environment: experience in network intrusion detection, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.114-124, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312212]
• 13: Wagner Meira, Jr. , Thomas J. LeBlanc , Alexandros Poulos, Waiting time analysis and performance visualization in Carnival, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.1-10, May 22-23, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/238020.238023]
• 14: 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]
• 15: 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]
• 16: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 17: Ramakrishnan Rajamony , Alan L. Cox, Performance debugging shared memory parallel programs using run-time dependence analysis, ACM SIGMETRICS Performance Evaluation Review, v.25 n.1, p.75-87, June 1997
• 18: D.A. Reed, R.A. Aydt et al., "An Overview of the Pablo Performance Analysis Environment," Department of Computer Science, University of Illinois, 1304 West Springfield Avenue, Urbana, IL 61801 1992.
• 19: D.A. Reed, O.Y. Nickolayev, and P.C. Roth, "Real-Time Statistical Clustering and for Event Trace Reduction," Z Supercomputing Applications and High-Performance Computing, 11(2): 144-59, 1997.
• 20: Sekhar R. Sarukkai , Jerry Yan , Jacob K. Gotwals, Normalized performance indices for message passing parallel programs, Proceedings of the 8th international conference on Supercomputing, p.323-332, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181548]
• 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 W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
• 23: J. Stasko, J. Domingue et al., Eds., Software Visualization: Programming as a Multimedia Experience,. Cambridge, MA: MIT Press, 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Design, Measurement, Performance, Theory