Critical-path-based message logging for incremental replay ofmessage-passing programs

摘要

Debugging long-running, nondeterministic message-passing parallelnprograms requires incremental replay, the ability to exactly replaynselected parts of an execution. To support incremental replay, we mustnlog enough messages and checkpoint processes often enough to allow anynrequested replay to complete quickly. We present an adaptive tracingnstrategy to keep the message-logging overhead down. We let the usernspecify a bound on the maximum time any replay request is allowed tontake. Our algorithm tracks what each process's critical path will benduring a replay and logs enough messages to ensure the critical pathnwill never exceed the bound. Overhead is kept low by not loggingnmessages that can be recomputed during a replay. Experiments indicatenthat we log about 0.1-5% of the messages while still providing anreasonable bound on any replay