A type and effect system for deterministic parallel java

Robert L. Bocchino, Vikram S. Adve, Danny Dig, Sarita V. Adve, Stephen Heumann, Rakesh Komuravelli, Jeffrey Overbey, Patrick Simmons, Hyojin Sung, Mohsen Vakilian

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)97-116
Number of pages20
JournalACM SIGPLAN Notices
Issue number10
StatePublished - Oct 2009


  • Commutativity
  • Determinism
  • Deterministic parallelism
  • Effect systems
  • Effects

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'A type and effect system for deterministic parallel java'. Together they form a unique fingerprint.

Cite this