Normalized performance indices for message passing parallel programs

ABSTRACT

Existing tools for locating performance bottlenecks of message passing parallel programs either provide visualizations or profiles of program executions only; they do not highlight the cause of poor program performance. From the perspective of the application, the location and cause of performance problems in terms of procedures, processors and data structures are all important. Identifying the cause of poor performance necessitates the need to expose how well the underlying algorithm has been mapped onto the parallel machine. In this paper, we present a suite of normalized performance indices that provide a convenient mechanism for focusing on a location with poor performance. These indices are complemented by additional indices that highlight the cause of the performance failure in terms of processors, procedures and data structure interactions. With the help of examples from the NAS benchmark suite, we show that the automatically generated indices help detect potential causes of poor performance. These indices are generated from execution traces (augmented with data structure information) obtained from monitoring program executions on the Intel iPSC/860.

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: David Bailey, John Barton, Thomas lasinski and Horst Simon, " The NAS Parallel Benchmarks," Report RNR-91.002, NASA Ames Research Center, January 1991.
• 3: S. H. Bokhari, " Communication Overhead on the Intel iPSC/860 Hypercube," 1CASE Interim Report 10, May 1990.
• 4: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 5: Dennis Gannon , Jenq Kuen Lee , Bruce Shei , Sekhar R. Sarukkai , Srinivas Narayana , Neelakantan Sundaresan , Daya Atapattu , François Bodin, Sigma II: A Tool Kit for Building Parallelizing Compilers and Performance Analysis Systems, Proceedings of the IFIP WG 10.3 Workshop on Programming Environments for Parallel Computing, p.17-36, April 06-08, 1992
• 6: S. L. Graham, P.B. Kessler and M. K. McKusick," An Execution Profiler for Modular Programs," Software Practice and Experience, August 1983.
• 7: Michael T. Heath , Jennifer A. Etheridge, Visualizing the Performance of Parallel Programs, IEEE Software, v.8 n.5, p.29-39, September 1991 [doi>10.1109/52.84214]
• 8: Jeffrey K. Hollingsworth , Barton P. Miller, Dynamic control of performance monitoring on large scale parallel systems, Proceedings of the 7th international conference on Supercomputing, p.185-194, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165969]
• 9: Eileen Kraemer , John T. Stasko, The visualization of parallel systems: an overview, Journal of Parallel and Distributed Computing, v.18 n.2, p.105-117, June 1993 [doi>10.1006/jpdc.1993.1050]
• 10: Margaret Martonosi , Anoop Gupta , Thomas Anderson, MemSpy: analyzing memory system bottlenecks in programs, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-12, June 01-05, 1992, Newport, Rhode Island, United States
• 11: B. P. Miller , M. Clark , J. Hollingsworth , S. Kierstead , S. S. Lim , T. Torzewski, IPS-2: The Second Generation of a Parallel Program Measurement System, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.206-217, April 1990 [doi>10.1109/71.80132]
• 12: Sekhar R. Sarukkai , Dennis Gannon, SIEVE: a performance debugging environment for parallel programs, Journal of Parallel and Distributed Computing, v.18 n.2, p.147-168, June 1993 [doi>10.1006/jpdc.1993.1053]
• 13: Sekhar R. Sarukkai , Doug Kimelman , Larry Rudolph, A methodology for visualizing performance of loosely synchronous programs, Journal of Parallel and Distributed Computing, v.18 n.2, p.242-251, June 1993 [doi>10.1006/jpdc.1993.1060]
• 14: Sekhar It. Sarukkai and Jerry Yah, "Integration of Perturbation Compensation and Application Monitoring Tools for Message Passing Parallel Porgrams," Submitted to 1EEE Transactions on Parallel and Distributed Systems
• 15: Sekhar R. Sarukkai and Jacob Gotwals, " Analysing Data Structure Movements in Message Passing Parallel Programs," Indiana University Technical Report # 402, March 1994.
• 16: Jerry Yan, "Performance Tuning with AIMS - An Automated Instrumentation and Monitoring System for Multieomputers," Proceedings of the 27tn Hawaii International Conference on System Sciences, Hawaii, January 1994.
• 17: "UNICOS Performance Utilities Reference Manual," Cray Research Inc., 1991.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES

General Terms:
Measurement, Performance, Theory