A mechanism for efficient debugging of parallel programs

ABSTRACT

This paper addresses the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors (SMMP). We describe the use of flowback analysis to provide information on causal relationships between events in a program's execution without re-executing the program for debugging. We introduce a mechanism called incremental tracing that, by using semantic analyses of the debugged program, makes the flowback analysis practical with only a small amount of trace generated during execution. We extend flowback analysis to apply to parallel programs and describe a method to detect race conditions in the interactions of the co-operating processes.

REFERENCES

• 1: R.M. Balzer, "EXDAMS - EXtendable Debugging and Monitoring System," Proc. of AFIPS Spring Joint Computer Conf. 34 pp. 567- 580 (1969).
• 2: Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986 [doi>10.1145/6465.6489]
• 3: K. Kennedy, "A Survey of Data-flow Analysis Techniques," Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds., pp. 5-54 Prentice-Hall, Englewood Cliffs, N,J., (1981).
• 4: B. Randell , P. Lee , P. C. Treleaven, Reliability Issues in Computing System Design, ACM Computing Surveys (CSUR), v.10 n.2, p.123-165, June 1978 [doi>10.1145/356725.356729]
• 5: R. Curtis and L. Withe, "BUGNET: A Debugging System for Parallel Programming Environment," Proc. of the 3rd International Conf. on Distributed Computing Systems, pp. 394-399 Denver, (August 1982).
• 6: R. D. Schiffenbauer, INTERACTIVE DEBUGGING IN A DISTRIBUTED COMPUTATIONAL, Massachusetts Institute of Technology, Cambridge, MA, 1981
• 7: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging parallel programs with instant replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• 8: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 9: P.C. Bates and J, C. Wileden, "High Level Debugging of Distributed Systems: the Behavioral Abstraction Approach," J. Systems and Softwares 4(3) pp. 255-264 (December 1983).
• 10: Bernd Bruegge , Peter Hibbard, Generalized path expressions: A high level debugging mechanism (Preliminary Draft), Proceedings of the ACM SIGSOFT/SIGPLAN software engineering symposium on High-level debugging, p.34-44, January 1983 [doi>10.1145/800007.808006]
• 11: F Baiardi , N DeFrancesco , G Vaglini, Development of a debugger for a concurrent language, IEEE Transactions on Software Engineering, v.12 n.4, p.547-553, April 1986
• 12: Richard Thomas Snodgrass, Monitoring distributed systems: a relational approach, 1982
• 13: D.J. Kuck, Y. Muraoka, and S. C. Chen, "On the Number of Operations Simultaneously Executable in FORTRAN-like Programs and Their Speed-up," IEEE Trans. on Computers, pp. 1293-1310 (December 1972).
• 14: J. R. Alien and K. Kennedy, "PFC: A Program to Convert FOR- TRAN to Parallel Form," TR 82-6, Dept. of Math. Sciences, Rice University, Houston, Texas, (March 1982).
• 15: John R. Allen , Ken Kennedy, Automatic loop interchange, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.233-246, June 17-22, 1984, Montreal, Canada
• 16: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• 17: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 18: S. Horwitz , J. Prins , T. Reps, Integrating non-intering versions of programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-145, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73572]
• 19: Mark Weiser, Programmers use slices when debugging, Communications of the ACM, v.25 n.7, p.446-452, July 1982 [doi>10.1145/358557.358577]
• 20: M. Weiser, "Program Slicing," IEEE Trans. on Software Engineering SE-10(4)(July 1984).
• 21: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• 22: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 23: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 24: B. P, Miller and J. D. Choi, "Bre, aklx~ints and Halting in Distributed Programs," Pro~. of the 8th International Conf. on Distributed Computing Systems, San Jose, CA, 0tree 1988).
• 25: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 26: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 27: David R. Cheriton , Willy Zwaenepoel, The distributed V kernel and its performance for diskless workstations, Proceedings of the ninth ACM symposium on Operating systems principles, p.129-140, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 28: C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
• 29: S. Horwitz, P. Pfeiffer, and T. Reps, "Dependence Analysis for Pointer Variables," Computer Sciences Tech Report (in preparation), Univ. of Wisconsin - Madison, (1988).

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.1 PROGRAMMING TECHNIQUES

General Terms:
Languages, Performance