Determining possible event orders by analyzing sequential traces
David Helmbold, Charles E. McDowell, Jian-Zhong Wang, University of California, Santa Cruz. Computer Research Laboratory
University of California, Santa Cruz, Computer Research Laboratory, 1991 - Parallel programming (Computer science) - 28 pages
Abstract: "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 parellel 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."
6 pages matching race in Pt in this book
Results 1-3 of 6
What people are saying - Write a review
We haven't found any reviews in the usual places.
accesses algorithm Algorithm anonymous synchronization arcs assigned block B(r block B(s,s blocking event causal trace component-wise compute Conc corresponding history counting semaphores critical regions Definition determining event on semaphore event orderings events in tasks events performed feasible data race global trace happen concurrently IBM Parallel FORTRAN IBM-event implemented inferred program Initially input iterations Lemma non-determinacy non-determinate NP-complete number of events occur performed by task Post precede program execution race conditions race in Pt read in B(s,s report races representing a safe Request Processing respect to Pt rewinding algorithm run time analysis safe event history safe history Safe Order Relation safe partial order second Wait semaphore model Seq2 Seqj sequential event pairs shadowed with respect shared variable shown in Figure synchronization events Task A Task Task C Figure Theorem timestamps total order trace analyzer unordered sequential event variables read vectors computed Wait event Wait operation write