Disciplined Shared Memory
Principal Investigators: Vikram Adve, Sarita Adve, Marc Snir
Shared memory parallel programming languages have been around for decades. Recent examples include C++ with threads or with the OpenMP parallel constructs, Java and C# — these languages support object-oriented programming, which is essential for their broad use. The use of a shared memory programming model facilitates the expression of many algorithms, but in its current incarnations, it does not offer adequate protection from program defects. Our goal is to develop disciplined shared memory models and languages that, to the extent possible, minimize concurrency related defects by design, without giving up the conveniences of modern object-oriented languages and the expressivity and performance of low-level programming.
Data-race-free — a fundamental discipline: There is broad consensus that data races are a fundamental source of concurrency related bugs in shared memory programs. Data races involve unsynchronized, conflicting accesses to memory, which result in unpredictable, schedule-dependent, and platform-dependent results. We believe that a fundamental requirement for safe shared memory programming is that races be avoided or detected, resulting in well-defined exceptions. Race avoidance or detection are the only practical ways of enforcing the safety of shared memory parallel code and of providing a feasible shared memory model. Debugging and testing of race-free programs is simpler since there are fewer interleaving sequences to consider — only the (possibly non-deterministic) interleaving of synchronization operations.
Determinism-by-default — a stronger discipline: A stronger requirement is that programs be deterministic (unless explicitly requested otherwise) so that, for each input, there is a unique output. While such a program may execute in parallel, the externally visible outcome is equivalent to that obtained in a well-specified sequential execution, and the relative timing of the executing threads cannot possibly affect the outcome. Programs satisfying this requirement have sequential semantics; for example, a well-tested sequential program parallelized using a "deterministic-by-default" programming model should not require any further testing. We believe that many transformative programs (where parallelism is used only for performance and is not part of the problem specification) can be expressed in deterministic terms. Nevertheless, non-deterministic behavior may be needed for the efficient implementation of some parallel algorithms. Our fundamental thesis is that client-side parallel programming must be deterministic by default. Non-deterministic behavior should occur only when explicitly non-deterministic constructs are used. All shared memory parallel code, whether deterministic or non-deterministic, must be data-race-free: unsynchronized conflicting accesses to shared memory must result in compile-time errors or run-time exceptions. Where possible, non-deterministic behavior should be encapsulated behind interfaces with well-defined contracts such that the rest of the program can be guaranteed deterministic as long as those contracts are satisfied.
Providing a parallel performance model: While we have argued for a sequential semantic model (by default) for easier reasoning, we believe that for robust performance, it is important for programmers to be exposed to a parallel performance model. For example, consider a language where the only explicitly parallel construct is a parallel loop, and where loop iterates are required to be independent. Although the loop has serial semantics, the user can analyze performance assuming that such a loop does execute in parallel. If the iterates are not independent, then an error will occur at compile time or an exception or warning will be raised at run-time (perhaps reverting to a sequential execution). In any case, the programmer is warned if the parallelism is not achieved. We can think of the explicitly parallel loop construct as an annotated loop where, in addition to specifying loop semantics, the programmer provides an indication of the expected execution model and the language implementation tries to deliver that model. Languages such as OpenMP already provide such annotations, as pragmas or directives. However, incorrect directives in OpenMP may cause data races; furthermore, the expressiveness of annotations that are, syntactically, comments, is limited. We believe that we need new programming constructs in the form of executable annotations.
To achieve the goals described in this section, we propose to add new programming constructs to existing popular object-oriented languages, such as Java, C# and C++. We believe that using such extended languages will provide an easier path to parallelism than using current languages or totally new languages. If parallelism is pursued using current languages, then it is achieved either by using explicit threading, or by adding directives and writing code in idioms that can be parallelized by the compiler. The former approach is bug-prone; the latter is platform-dependent. A totally new language presents an obvious porting barrier. Our preferred alternative is to add to a popular language sharing annotations and performance annotations — i.e. syntax extensions that do not affect the program semantics but can be used to check safety of sharing properties or that affect the performance model. With this approach, refactoring tools can support the porting of existing codes as a progressive annotation process and development tools can display a semantically equivalent program in the original language (Java, C# or C++), for debugging. The annotations are not specific to a platform; further, the investment in using them has a long-term payoff because they improve programmability, clarify design decisions, and reduce maintenance costs.
