12/01/1989 09:00 AM
Computer Science
In a parallel system, events can occur concurrently. However, programmers are often forced to rely on misleading sequential traces for information about their program\'s behavior. We present a series of algorithms which extract ordering information from a sequential trace with anonymous semaphore- style synchronization. We view a program execution as a partial ordering of events, and define which executions are consistent with a given trace. Although it is generally not possible to determine which of the consistent executions occurred, we define the notion of ``safe orderings\'\' which can be relied on regardless of which execution generated the trace. The main results of the paper are algorithms which determine many of the ``safe orderings\'\'. The first algorithm starts from a sequential trace and creates a partially ordered canonical execution. The second algorithm strips away the ordering relationships particular to the canonical execution, so that the resulting partial order is safe. The third algorithm increases the amount of ordering information while maintaining a safe partial order. All three algorithms are accompanied by proofs of correctness. Finally, an algorithm is presented to detect critical regions, to distinguish unordered sequential events from concurrent events.