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 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. Algorithms to generate, from the trace of an execution, those event orderings that can be relied on by the programmer are described. 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. This difficulty is mitigated by defining an inferred program based on the trace and original program, analyzing this inferred program, and showing how the inferred program relates to the original. The results of the algorithms can be used by other automated tools such as a data race detector or constraint checker