A type and effect system for deterministic parallel Java
Robert L. Bocchino, Vikram Adve, Danny Dig et al. · ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA) · 2009
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).
Cited by 265 works. doi:10.1145/1640089.1640097
Authors
- Robert L. Bocchino
- Vikram Adve
- Danny Dig
- Sarita V. Adve
- Stephen T. Heumann
- Rakesh Komuravelli
- Jeffrey L. Overbey
- Patrick Simmons
- Hyojin Sung
- Mohsen Vakilian
References
- Cilk
- Separation logic: a logic for shared mutable data structures
- X10
- Polymorphic effect systems
- Ownership types for safe programming
- STAMP: Stanford Transactional Applications for Multi-Processing
- Ownership types for flexible alias protection
- Resources, concurrency, and local reasoning
- Optimistic parallelism requires abstractions
- Checking interference with fractional permissions