A type and effect system for deterministic parallel Java

Bocchino, Robert L., Adve, Vikram S., Dig, Danny, Adve, Sarita V., Heumann, Stephen, Komuravelli, Rakesh, Overbey, Jeffrey, Simmons, Patrick +2 more·2009·Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications
DOI 10.1145/1640089.1640097

Abstract

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 this paper, we 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. We describe an object-oriented type and effect system that provides several new capabilities over previous systems for expressing deterministic parallel algorithms.We also describe a language called Deterministic Parallel Java (DPJ) that incorporates the new type system features, and we show that a core subset of DPJ is sound. We describe an experimental validation showing thatDPJ 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).