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.



  • thumnail for vasudevan2009determinizing.pdf vasudevan2009determinizing.pdf application/pdf 21.8 KB Download File

More About This Work

Academic Units
Computer Science
Published Here
August 23, 2011


ACM SIGPLAN 2009 Conference on Programming Language Design and Implementation, Dublin, Ireland, June 15-20, 2009: Fun Ideas and Thoughts Session