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: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationOOPSLA 2009 - 24th Annual ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, OOPSLA 2009
Pages97-116
Number of pages20
DOIs
StatePublished - 2009
EventOOPSLA 2009 - 24th Annual ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, OOPSLA 2009 - Orlando, FL, United States
Duration: Oct 25 2009Oct 29 2009

Publication series

NameProceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, OOPSLA

Conference

ConferenceOOPSLA 2009 - 24th Annual ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, OOPSLA 2009
Country/TerritoryUnited States
CityOrlando, FL
Period10/25/0910/29/09

Keywords

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

ASJC Scopus subject areas

  • Software

Fingerprint

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

Cite this