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. 1.T.E. Anderson and E.D. Lazowska, "Quartz: A Tool for Tuning Parallel Program Performance," Prec. 1990 SIGMETRICS Conf. Measurement and Modeling Computer Systems, 1990, PiT. 115-25.
2. 2.D. Bailey, E. Barszez et al., "The NAS Parallel Benchmarks (94)," NASA Ames Research Center, RNR Technical Report RNR-94-007, 1994.
3. 3.M. Calzarossa, L. Massari et al., "Medea: A Tool for Workload Characterization of Parallel Systems," IEEE Parallel & Distributed Technology, 3(4):72-80, 1995.
4. 4.U.M. Fayyad, G. Piatetsky-Shapiro et al., Eds., Advances in knowledge discovery and data mining. Menlo Park, CA: AAAI Press: MIT Press, 1996, pp. xiv, 611.
5. 5.I. Foster, Designing and building parallel programs: concepts and tools for parallel software engineering. Reading, MA: Addison-Wesley, 1995.
6. 6.I. Foster and C. Kesselman, Eds., The Grid: blueprint for a new computing infrastructure. San Francisco: Morgan Kaufmann Publishers, 1999, pp. xxiv, 677.
7. 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. 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. 9.W. Gropp, E. Lusk, and A. Skjellum, Using MPI: portable parallel programming with the message.passing interface, 2nd ed. Cambridge, MA: MIT Press, 1999.
10. 10.M.T. Heath, A.D. Malony, and D.T. Rover, "Parallel performance visualization: from practice to theory," IEEE Parallel & Distributed Technology: Systems & Applications, 3(4):44-60, 1995.
11. 11.M. Ji, E.W. Felten, and K. Li, "Performance Measurements for Multithreaded Programs," Prec. 1998 ACM Int'l Conf. Measurement and Modeling of Computer Systems, SIGMETRICS 98, 1998, pp. 161-70.
12. 12.W. Lee, S. J.Stolfo, and K. W.Mok, "Mining in a dataflow environment: experience in network intrusion detection," Prec. Fifth ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining, 1999, pp. 114-24.
13. 13.W. Meira, Jr; T.J. LeB!anc, and A. Poulos, "Waiting Time Analysis and Performance Visualization in Carnival," Prec. ACM SIGMETRICS Syrup. on Parallel and Distributed Tools, 1996, pp. 1-10.
14. 14.B.P. Miller, M.D. Callaghan et al., "The Paradyn parallel performance measurement tool," IEEE Computer, 28(11):37-46, 1995.
15. 15.A.A. Mirin, R.H. Cohen et al., "Very High Resolution Simulation of Compressible Turbulence on the IBM-SP System," Prec. SC99, 1999.
16. 16.J.R. Quinlan, C4.5: programs for machine learning. San Mateo, CA: Morgan Kaufmann Publishers, 1993.
17. 17.R. Rajamony and A.L. Cox, "Performance debugging shared memory parallel programs using run-time dependence analysis," Performance Evaluation Review (Prec. 1997 ACM lnt'l Conf. Measurement and Modeling of Computer Systems, SIGMETRICS 97), 25(1):75-87, 1997.
18. 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. 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. 20.S.R. Sarukkai, J. Yah, and J.K. Gotwals, "Normalized performance indices for message passing parallel programs," Prec. 8th ACM Int'l Conf. Supercomputing, 1994, pp. 323-32.
21. 21.S. Shende, A.D. Malony et al., "Portable profiling and tracing for parallel, scientific applications using C++," Prec. SIGMETRICS Symp. Parallel and Distributed Tools (SPDT), 1998, pp. 134-45.
22. 22.M. Snir, S. Otto et al., Eds., MP1-the complete reference, 2nd ed. Cambridge, MA: MIT Press, 1998.
23. 23.J. Stasko, J. Domingue et al., Eds., Software Visualization: Programming as a Multimedia Experience,. Cambridge, MA: MIT Press, 1998.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

  • Dependable and fault-tolerant systems and networks

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Supervised learning

        • Supervised learning by classification

    • Machine learning approaches

      • Classification and regression trees

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network performance evaluation

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles