A Type and Effect System for Deterministic Parallelism in Object-Oriented Languages
Author(s)
Bocchino, Robert L., Jr.
Adve, Vikram S.
Dig, Danny
Heumann, Stephen
Komuravelli, Rakesh
Overbey, Jeffrey
Simmons, Patrick
Sung, Hyojin
Vakilian, Mohsen
Issue Date
2009-02
Keyword(s)
Computer science
Abstract
We describe a type and effect system for ensuring deterministic semantics in a concurrent object-oriented language. Our system provides several new capabilities over previous work, including support for linear arrays (important in parallel update traversals), flexible effect specifications and subtyping (important for, e.g., tree-based algorithms), dynamic partitioning into subarrays (important for divide-and-conquer algorithms), and a novel invocation effect for handling higher-level commutative operations such as set insert. We informally describe the key type system features, formally define a core subset of our system, and explain the steps leading to the key soundness result, i.e., that the type and effect annotations allow us to reason soundly about parallel noninterference between sections of code. Finally, we describe our experience with using the system to express realistic parallel algorithms, which validates the importance of the new type system features.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
