2009 Articles

A Determinizing Compiler

Vasudevan, Nalini; Edwards, Stephen A.

The advent of multicores mandates parallel programming. While parallelism presents a panoply of problems, few are as pernicious and prevalent as nondeterminism, in which the output of a program is affected by more than just its inputs, e.g., uncontrollable scheduling choices made by the operating system. A few parallel languages do guarantee determinism, but do so through draconian restrictions. It is time for a new era of bug-free parallel programming that will enable programmers to shift easily from sequential to parallel worlds.We propose a determinizing compiler: starting from a non-deterministic program, our compiler inserts just enough additional synchronization to guarantee deterministic behavior, even in the presence of nondeterministic scheduling choices. A brute-force solution would simply generate sequential code, but our compiler will strive to preserve parallelism to impose a minimal loss of performance.