Debugging Concurrent Processes: A Case Study

Abstract

We present a case study that illustrates a method of debugging concurrent processes in a parallel programming environment. It uses a new approach called speculative replay to reconstruct the behavior of a program from the histories of its individual processes. Known time dependencies between events in different processes are used to divide the histories into dependence blocks. A graphical representation called a concurrency map displays possibilities for concurrency among processes. The replay technique preserves the known dependencies and compares the process histories generated during replay with those that were logged during the original program execution. If a process generates a replay history that does not match its original history, replay backs up. An alternative ordering of events is created and tested to see if it produces process histories that match the original histories. Successively more controlled replay sequences are generated, by introducing additional dependencies. We describe ongoing work on tools that will control replay without reconstructing the entire space of possible event orderings.