Efficient Deterministic Multithreading Without Global Barriers

Multithreaded programs execute nondeterministically on conventional architectures and operating systems. This com-plicates many tasks, including debugging and testing. Deter-ministic multithreading (DMT) makes the output of a mul-tithreaded program depend on its inputs only, which can totally solve the above problem. However, current DMT im-plementations suffer from a common inefficiency: they use frequent global barriers to enforce a deterministic ordering on memory accesses. In this paper, we eliminate that in-efficiency using an execution model we call deterministic lazy release consistency (DLRC). Our execution model uses the Kendo algorithm to enforce a deterministic ordering on synchronization, and it uses a deterministic version of the lazy release consistency memory model to propagate mem-ory updates across threads. Our approach guarantees that programs execute deterministically even when they contain data races. We implemented a DMT system based on these ideas (RFDet) and evaluated it using 17 parallel applica-tions. Our implementation targets C/C++ programs that use POSIX threads. Results show that RFDet gains nearly 2x speedup compared with DThreads—a start-of-the-art DMT system