Optimal tracing and replay for debugging shared-memory parallel programs

Execution replay is a crucial part of debugging. Because explicitly parallel shared-memory programs can be nondeterministic, a tool is required that traces executions so they can be replayed for debugging. We present an adaptive tracing strategy that is optimal and records the minimal number of shared-memory references required to exactly replay executions. Our algorithm makes runtime tracing decisions by detecting and tracing a certain type of race condition on-the-fly. Unlike past schemes, we make no assumptions about the execution'scorrectness (it need not be race free). Experiments show that only 0.01-2% of the shared-memory references are usually traced, a 2-4 order of magnitude reduction over past techniques which trace every access.