November 05, 2009
A Type and Effect System for Deterministic Parallel Java
A novel type and effect system, together
with a language called DPJ, enforces deterministic semantics
Today's shared-memory parallel programming models are complex and error-prone. While many parallel programs are intended to be deterministic, unanticipated thread interleavings can lead to subtle bugs and nondeterministic semantics.
In A Type and Effect System for Deterministic Parallel Java, Robert L. Bocchino Jr.,Vikram S. Adve, Danny Dig, Sarita V. Adve, Stephen Heumann, Rakesh Komuravelli, Jeffrey Overbey, Patrick Simmons, Hyojin Sung, and Mohsen Vakilian demonstrate that a practical type and effect system can simplify parallel programming by guaranteeing deterministic semantics with modular, compile-time type checking even in a rich, concurrent object-oriented language such as Java. They describe an object-oriented type and effect system that provides several new capabilities over previous systems for expressing deterministic parallel algorithms.
They also describe a language called Deterministic Parallel Java (DPJ) that incorporates the new type system features, and show that a core subset of DPJ is sound. The present an experimental validation showing that DPJ can express a wide range of realistic parallel programs; that the new type system features are useful for such programs; and that the parallel programs exhibit good performance gains (coming close to or beating equivalent, nondeterministic multithreaded programs where those are available).
