Parallel Program Debugging With Flowback Analysis

This thesis describes the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors. The goal of the debugging system is to present to the programmer a graphical view of the dynamic program dependences while keeping the execution-time overhead low. We first describe the use of flowback analysis to provide information on causal relationship between events in a program�s execution without re-executing the entire program for debugging. Execution time overhead is kept low by recording only a small amount of trace during a program�s execution. We use semantic analysis and a technique called incremental tracing to keep the time and space overhead low. As part of the semantic analysis, we use a static program dependence graph structure that reduces the amount of work done at compile time and takes advantage of the dynamic information produced during execution time. The cornerstone of the incremental tracing concept is to generate a coarse trace during execution and fill incrementally, during the interactive portion of the debugging session, the gap between the information gathered in the coarse trace and the information needed to do flowback analysis using the coarse trace. Then, we describe how to extend flowback analysis to parallel programs. Flowback analysis can span process boundaries: i.e. the most recent modification to a shared variable might be traced to a different process than the one that contains the current reference. The static and dynamic program dependence graphs of the individual processes are tied together with synchronization and data dependence information to form complete graphs that represent the entire program. Finally, we describe the implementation of a prototype debugging system (called PPD) and provide performance measurements of the various parts of PPD. We describe the code-generation techniques for separate compilation used by PPD compiler. In general, the performance measurements of PPD have demonstrated the feasibility of our ideas and directions for debugging parallel programs