B. P. Miller
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.
- 1.R.M. Balzer, "EXDAMS - EXtendable Debugging and Monitoring System," Proc. of AFI?S Spring Joint Computer Conf. 34 pp. 567- 580 (1969).Google Scholar
- 2.K. Cooper, K. Kennedy, and L. Torczon, "The Impact of Interprocess Analysis and Optimization in the Rn programming Environment,'' ACM Trans. on Prog. Lang. and Syst. 8(4)pp. 491-523 (October 1986). Google ScholarDigital Library
- 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).Google Scholar
- 4.B. Randell, P. A. Lee, and P. C. Treleaven, "Reliability Issues in Computing System Design," Computing Surveys 10(2)pp. 123-165 (June 1978). Google ScholarDigital Library
- 5.R. Curtis and L. Witfie, "BUGNET: A Debugging System for Parallel Programming Environment," Proc. of the 3rd International Conf. on Distributed Computing Systems, pp. 394-399 Denver, (August 1982).Google Scholar
- 6.R.D. Schiffenbaur, "Interactive Debugging in a Distributed Programs," M.S. Thesis, EECS Tech Report MIT/LCS/TR-264, M.I.T., (August 1981). Google ScholarDigital Library
- 7.T.J. LeBlanc and J. M. Mellor-Crummey, "Debugging Parallel Programs with Instant Replay," IEEE Trans. on Computers C-36(4) pp. 471-482 (April 1987). Google ScholarDigital Library
- 8.E. Dijkstra, "Guarded Commands, Nondeterminacy and Formal Derivation of Programs," Comm. of ACM 18(8) pp. 453-457 (1975). Google ScholarDigital Library
- 9.P.C. Bates and J. C. Wile&n, "High Level Debugging of Distributed Systems: the Behavioral Abstraction Approach," J. Systems and Softwares 4(3) pp. 255-264 (December 1983).Google ScholarDigital Library
- 10.B. Bruegge and P. Hibbard, "Generalized Path Expressions: A High Level Debugging Mechanism," Proc. of the SIGSOFT/SIGPLAN Syrup. on High-Level Debugging, pp. 34-44 Pacific Grove, Calif., (August 1983). Google ScholarDigital Library
- 11.F. Baiardi, N. De Francesco, and G. Vaglini, "Development of a Debugger for a Concurrent Language," IEEE Trans. on Software Engineering SE-12(4) pp. 547-553 (April 1986). Google ScholarDigital Library
- 12.R. Snodgrass, "Monitoring Distributed Systems: A Relational Approach," Ph.D. Thesis, Carnegie-Mellon University, (December 1982). Google ScholarDigital Library
- 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).Google ScholarDigital Library
- 14.J.R. Allen 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).Google Scholar
- 15.J.R. Allen and K. Kennedy, "Automatic Loop Interchange," Proc. of the SIGPLAN 84 Symposium on Compiler Construction, pp. 233- 246 Montreal, Canada, (June 1984). Google ScholarDigital Library
- 16.K, J. Ottenstein and L. M. Ottenstein, "The Program Dependency Graph In A Software Development Environment," SIGPLAN Notices 19(5) pp. 177-184 ACM, (May 1984). Google ScholarDigital Library
- 17.J. Ferrante, K. Ottenstein, and J. Warren, "The Program Dependence Graph and Its Use in Optimization," ACM Trans. on Prog. Lang. and Syst. 9(3) pp. 319-349 (July 1987). Google ScholarDigital Library
- 18.S. Horwitz, J. Prins, and T. Reps, "Integrating non-interfering versions of programs," Proc. of the SIGPLAN 88 Symposium on Principles of Programming Languages, pp. 133-145 San Diego, CA, (January 1988). Google ScholarDigital Library
- 19.M. Weiser, "Programmers Use Slices When Debugging," Communication, of the ACM 25(7)(July 1982). Google ScholarDigital Library
- 20.M. Weiser, "Program Slicing," IEEE Trans. on Software Engineering SE-10(4)(July 1984).Google ScholarDigital Library
- 21.J.M. Barth, "A practical interprocedural data flow analysis algorithm,'' Communications of the ACM 21(9) pp. 724-736 (September 19'78). Google ScholarDigital Library
- 22.J.P. Banning, "An efficient way to find the side effects of procedure calls and the aliases of variables," Proc. of the SiGPLAN 79 Symposium on Principles of Programming Languages, pp. 29-41 San Antonio, TX, (lanuary I979). Google ScholarDigital Library
- 23.E. Myers, "A precise inter-procedural data flow algorithm," Proc. of the SIGPLAN 81 Symposium on Principles of Programming Languages, pp. 219-230 Williamsburg, VA, (January 1981). Google ScholarDigital Library
- 24.B.P. Miller and J. D. Choi, "Breakpoints and Halting in Distributed Programs," Proc. of the 8th International Conf. on Distributed Computing Systems, San Jose, CA, (June 1988).Google Scholar
- 25.L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM 21(7)pp. 558-565 (July 1978). Google ScholarDigital Library
- 26.. Gray, "Notes on Database Operating Systems," Lecture Notes in omputer Science 60: Operating Systems, R. Bayer, R. M. Graham, and G. Seegmuller, Eds., pp. 393481 Springer-Vefiag, Berlin, (1978), Google ScholarDigital Library
- 27.D, R, Cheriton and W. Zwaenepoel, "The Distributed V kernel and its Performance for Disldess Workstations," Proc. of the 9th SOSP, Operating Systems Review 17(5) pp. 129-140 (November 1983), Google ScholarDigital Library
- 28.C. Ruggieri and T. P. Murtagh, "Lifetime Analysis of Dynamically Allocated Objects," Proc. of the SIGPLAN 88 Symposium on Principles of Programming Languages, pp. 285-293 San Diego, CA, (January 1988). Google ScholarDigital Library
- 29.S. Horwitz, P. Pfeiffer, and T. ReDs, "Dependence Analysis for Pointer Variables," Computer Sciences Tech Report (in preparation), Univ. of Wisconsin- Madison, (1988).Google Scholar
Index Terms
- A mechanism for efficient debugging of parallel programs
Recommendations
A mechanism for efficient debugging of parallel programs
Proceedings of the SIGPLAN '88 conference on Programming language design and implementationThis 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 ...
A mechanism for efficient debugging of parallel programs
Special issue: Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on parallel and distributed debuggingThis 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 ...
A mechanism for efficient debugging of parallel programs
PADD '88: Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debuggingThis 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 ...
Comments