09/01/1991 09:00 AM
Computer Science
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 deadlock, arise when there is insufficient synchronization between the tasks in a parallel program. A sequential trace of an execution can be misleading, as it implies additional event orderings, distorting the concurrent nature of the computation. This paper describes algorithms which generate those event orderings which can be relied on by the programmer from the trace of an execution. By its very nature, the information in an execution trace pertains only to that execution of the program, and may not generalize to other executions. We tackle this difficulty in a systematic way: defining an \"inferred program\" based on the trace and original program, analyze this inferred program, and prove a relationship between the inferred program and the original. The results of our algorithms can be used by other automated tools such as a data race detector or constraint checker. The basic algorithms described here have been implemented in a working trace analyzer for IBM Parallel Fortran. The trace analyzer graphically presents the discovered event orderings and reports various potential data races in the subject program.
