Vikram S. Adve University of Illinois @ Urbana
Most new consumer computers today contain at least two cores, high-end ones have as many as eight, and major vendor road-maps foresee hundreds of cores. To exploit this processing power, parallel computing, once a narrow specialty, must become mainstream. Parallel programming, however, is notoriously difficult. To avoid an expensive decline in programmer productivity, programming languages, libraries, and tools must make parallel programming nearly as easy as sequential programming. One powerful way to achieve this goal will be to enable a deterministic style of parallel programming, meaning that a program is guaranteed to produce the same output whenever it is run with a particular input. Determinism eliminates the hardest problems of parallel programming such as data races and deadlocks. Most importantly, it makes quality assurance easier because only one execution for each input must be tested and because errors are easier to reproduce. While deterministic programming models exist, they have limited expressivity and do not handle most programs written in widely-used languages such as Java and C#.
This research is developing simple, expressive language and runtime mechanisms for deterministic parallelism, using a thread-parallel style with aliasing of mutable objects. The design combines recent advances in type systems for declaring and checking memory regions and effects, falling back on runtime speculation in cases that are burdensome or impossible to express using the type system. The project is also developing mechanisms to allow ``locally non-deterministic'' constructs such as associative reductions and commutative data structure updates. Finally, the project will develop experience with writing realistic parallel programs in a deterministic style, to answer many practical questions about the expressivity, ease-of-use, and performance implications of the deterministic language features.
