Threads Should Not Play Dice: Determinism and Bug Avoidance for Multithreaded Programs

Current shared memory multicore and multiprocessor systems are
nondeterministic. Each time these systems execute a multithreaded application, even if supplied with the same input, they can produce a different output. This frustrates debugging and limits the ability to properly test multithreaded code, becoming a major stumbling block to the much-needed widespread adoption of parallel programming.

In this talk I will present fully deterministic shared memory
multiprocessing (DMP). The behavior of an arbitrary multithreaded
program on a DMP system is only a function of its inputs. Previous
approaches to coping with nondeterminism in multithreaded programs have focused on replay, a technique useful only for debugging. In contrast, while DMP systems are directly useful for debugging by offering repeatability by default, we argue that parallel programs should execute deterministically in the field as well. This has the potential to make testing more assuring and increase the reliability of deployed multithreaded software. We propose a range of approaches to enforcing determinism and discuss their implementation trade-offs. We show that determinism can be provided with little performance cost using our architecture proposals on future hardware.

Building on similar architecture support, I will then describe an
approach to dynamically avoiding concurrency bugs in the field. Our proposal, called Atom-Aid, dynamically detects when an atomicity violation is likely to happen and adjusts thread interleavings as to hide the bug. Atom-Aid does not change program semantics nor adversely affecting performance.
Luis Ceze is an Assistant Professor in the Computer Science and
Engineering Department at the University of Washington. His research focuses on computer architecture, compiler, programming models and OS to improve the programmability and reliability of multiprocessor systems. He has co-authored over 30 papers in these areas, and had three papers selected as IEEE Micro Top Picks. He participated in the Blue Gene, Cyclops, and PERCS projects at IBM and is a recipient of several IBM awards, including an IBM PhD Fellowship. He obtained his PhD in Computer Science from UIUC in 2007 and has received awards for research and academic accomplishments, including the Ross Martin Award
for Outstanding Research Achievement in the College of Engineering, the David Kuck Outstanding PhD Thesis Award, and NSF CAREER Award. He recently co-founded a startup company where he is a part-time consultant.