Dthreads: Efficient Deterministic Multithreading

In one paragraph

Multithreaded programs are hard to debug because the same program and input can produce different results on different runs. Dthreads replaces the pthreads library so that every run with the same input behaves the same, even in the presence of data races and deadlocks, with no changes to the program. It turns threads into processes with private copy-on-write views of shared memory, tracks writes with ordinary virtual-memory protection, and commits each thread's updates in a fixed order at synchronization points. A side effect is that false sharing disappears. On most of the benchmarks evaluated it matched, and sometimes beat, pthreads, while the prior deterministic runtime ran several times slower.

Key ideas

• Threads as processes: each thread gets a private, copy-on-write mapping of shared memory, so its writes stay isolated until a deterministic commit.
• Deterministic commits: updates are merged in a fixed thread order at synchronization points, so interleavings cannot change the outcome. Determinism holds even with data races.
• Standard virtual-memory protection tracks which pages were written. No compiler, hardware, or program changes.
• Isolating each thread's writes eliminates false sharing as a by-product.

Results

• Outperforms CoreDet, the state-of-the-art deterministic runtime at the time, on 12 of 14 PARSEC and Phoenix benchmarks, by 14% to 11.2×. CoreDet was 3.5× slower on average and up to 8.4× slower than pthreads.
• Matches or exceeds pthreads on 8 of the 14 benchmarks, and runs nearly as fast on 9.