Towards High Performance Determinism for Multithreaded Programs

The emergence of multi-core commodity processors, and more recently accelerators, has brought about a resurgence of interest in parallel programming. With that renewed interest comes a concern amongst practitioners and researchers that traditional models of parallel programming come at the cost of significantly increased complexity. Part of this complexity comes from nondeterminism and its impact on program testing, debugging and overall reasoning. To combat this, deterministic multithreading systems have been introduced at both the hardware and software layers to enhance repeatability of a computation. Despite initial research on determinism, the systems that enforce this property still show significant performance degradation. In this thesis, we describe several approaches to tackling these performance pathologies. We start by attacking the performance overhead caused by enforcing a deterministic memory model, by using a kernel-level multi-version concurrency control system for main memory segments. We next introduce a new deterministic threading library to make better use of the new memory model. And our final system uses speculation to attack the total order bottleneck in all prior deterministic systems.