We are designing and prototyping a Java-based language called Deterministic Parallel Java, or DPJ.  Our near-term goal for DPJ is to provide a test bed for our research into deterministic-by-default programming models.  Our long-term goal is to provide a practical, usable parallel language.  Our current DPJ design has the following prominent features:

Core Deterministic Language

Fork-Join Parallelism:  Presently the language syntax supports fork-join parallelism (via foreach loops and cobegin blocks), though frameworks provide a way to add new control abstractions. Regions:  DPJ’s determinism checking is fundamentally based on the concept of a region, or collection of memory locations.  The programmer partitions the heap into regions by annotating classesClasses are parametric, so that the same class can be instantiated with different regions.

DPJ’s regions are hierarchical, and they support sophisticated and novel ways of naming sets of regions, in patterns such as updates through arrays of references and divide-and-conquer traversals.

Effect Summaries:  The DPJ programmer annotates methods with effect summaries stating which regions are read and written by a method.  The compiler uses the class types and method effect summaries to check that all concurrent (read, write) and (write, write) pairs of accesses to the same region are disjoint.

We have designed an interactive tool called DPJizer that automatically infers method effect summaries, given the region information.

Explicit Controlled Nondeterminism

DPJ supports explicit, controlled nondeterminism via parallel loops designated foreach_nd (where the “nd” is for “nondeterministic”) or parallel blocks designated cobegin_nd.  Nondeterminism occurs only where explicitly called for via an _nd construct, so the language is deterministic by default.  Further, the language enforces data race freedom and strong isolation, allowing modular reasoning about distinct parallel constructs, even if some are internally nondeterministic.  It limits the possible executions of a program to serializations of coarse-grain parallel constructs — foreach, cobegin, and atomic blocks.  This greatly reduces the interleavings that the programmer must reason about.

Object-Oriented Parallel Libraries and Frameworks

DPJ supports concurrent collections through a commutative annotation that tells the type system that a pair of methods may be safely run in parallel, even if those methods perform conflicting accesses to the same regions.

DPJ also supports object-oriented parallel frameworks, such as Java’s ParallelArray, through constrained effect polymorphism and other features.  If a parallel framework is correctly implemented, then DPJ can provide a determinism guarantee for the user code.

 

Deterministic Parallel Java:  Current Design

University of Illinois at Urbana-Champaign