Parallelism Without Concurrency

The widespread deployment of parallel machines -- from multicores to supercomputers -- has made it critical to develop simple approaches to programming them. Significant progress has been made in simplifying parallel programming by developing programming models to support parallelism without concurrency, that is, without the nondeterminacies in the logic of programs caused by the relative and nondeterministic timing of communicating processes. Yet most parallel programs in practice are concurrent, and hence, nondeterministic, leading to code that can only be programmed and understood by experts. This research project aims to understand how parallel computers can be made easier to use by the vast majority of programmers by developing software technology that enables deterministic parallel computing.

The project takes a holistic view of the problem from the key perspectives of programming linguistics, software systems, algorithmic analysis, and absolute performance. It acknowledges the reality that parallel programming cannot be fully deterministic at every level of abstraction. It is pursuing three key strategies for dealing with concurrency: encapsulating concurrency so that it is hidden by layered abstractions at appropriate abstraction levels, avoiding concurrency by restructuring programs to employ deterministic approaches, and managing concurrency when it is impractical to either encapsulate or avoid concurrency completely. Among the specific techniques being studied are commutative building blocks, deterministic nonassociative reducers, deterministic pipelined parallelism, deterministic interfaces, and generalized race detection for detecting invariant races. The project is developing open-source libraries, tools, and runtime extensions integrated into a multicore-software platform, as well as a problem-based benchmark suite to compare approaches.