Optimal tracing and replay for debugging message-passing parallel programs

A common debugging strategy involves re-executing a program (on a given input) over and over, each time gaining more information about bugs. Such techniques can fail on message-passing parallel programs. Because of variations in message latencies and process scheduling, different runs on the given input may produce different results. This non-repeatability is a serious debugging problem, since,an execution cannot always be reproduced to track down bugs. This paper presents a technique for tracing and replaying message-passing pro-grams for debugging. Our technique is optimal in the common case,and has good performance in the worst case. By m,aking run-time tracing decisions, we trace only a fraction of the total number of messages, g,aining two orders of magnitude reduction over traditional tech-niques which trace every message. Experiments indicate that only 1 % of the messages often need be ~aced. These traces,are sufficient to provide replay, allowing an execu-tion to be reproduced any number of times for debugging. Our work is novel in that we use run-time decisions to detect,and trace only those messages that introduce non-determinacy. With our strategy, large reductions in trace size allow long-running programs to be replayed that were previously unmanageable. In addition, the reduced tracing requirements alleviate tracing bottlenecks, allow-ing executions to be debugged with substantially lower execution-time overhead. 1