Amittai F. Aviram
Ph.D. thesis advised by Bryan Ford
September 20, 2012
Abstract:
Researchers widely agree that determinism in parallel programs is desirable.
Although experimental parallel programming languages have long featured
deterministic semantics, in mainstream parallel environments, developers
still build on non-deterministic constructs such as mutexes, leading to time-
or schedule-dependent heisenbugs. To make deterministic programming more
accessible, we introduce DOMP, a deterministic extension to OpenMP, preserving
the familiarity of traditional languages such as C and Fortran, and
maintaining source-compatibility with much of the existing OpenMP standard. Our
analysis of parallel idioms used in 35 popular benchmarks suggests that the
idioms used most often (89% of instances in the analyzed code) are either
already expressible in OpenMP’s deterministic subset (74%), or merely lack more
general reduction (12%) or pipeline (3%) constructs. DOMP broadens OpenMP’s
deterministic subset with generalized reductions, and implements an efficient
deterministic runtime that acts as a drop-in replacement for Gnu’s widely used
conventional OpenMP support library GOMP, on mainstream Unix platforms. We
evaluate DOMP with several existing OpenMP benchmarks, each requiring under 50
source line changes and a majority requiring none, as well as several
benchmarks we ported to OpenMP/DOMP. We find DOMP’s efficiency and scalability
comparable to GOMP in 7 of 11 benchmarks, suggesting that a deterministic
model for mainstream parallel programming may be well within reach.