DETERMINING POSSIBLE EVENT ORDERS BY ANALYZING SEQUENTIAL TRACES

One of the fundamental problems encountered when debugging a parallel program is determining the possible orders in which events could have occurred. Various problems, such as data races and intermittent deadlo ck, arise when there is insufficient synchronization between the tasks in a parallel program. A sequential trace of an execution can be misl eading, as it implies additional event orderings, distorting the concu rrent nature of the computation. This paper describes algorithms to ge nerate, from the trace of an execution, those event orderings that can be relied on by the programmer. By its very nature, the information i n an execution trace pertains only to that execution of the program, a nd may not generalize to other executions. We mitigate this difficulty by defining an ''inferred program'' based on the trace and original p rogram, analyzing.this inferred program, and showing how the inferred program relates to the original. The results of our algorithms can be used by other automated tools such as a data race detector or constrai nt checker. The basic algorithms described here have been implemented in a working trace analyzer for IBM Parallel Fortran. The trace analyz er graphically presents the discovered event orderings and reports var ious potential data races in the subject program.