page 1  (11 pages)
2to next section

Computing Reachable States of

Parallel Programs

David P. Helmbold

Charles E. McDowell

July 8, 1992

Board of Studies in Computer and Information Sciences
University of California at Santa Cruz
Santa Cruz, CA 95064


A concurrency history graph is a representation of the reachable states of a parallel program, A new abstraction for representing the state of a parallel program is presented. This new abstraction is more general than previous work by the authors. At the same time, the new abstraction makes it possible to produce concurrency history graphs that require much less storage than that suggested by a simple worst case complexity analysis. Concurrency history graphs based on this new abstraction form the foundation upon which a static analysis tool capable of detecting race conditions in parallel programs is being built.

keywords: parallel processing, debugging, static program analysis