A Type and Effect System for Deterministic Parallelism in Object-Oriented Languages

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

Permalink

https://hdl.handle.net/2142/11519 Copy

Description

Title

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)

• parallel systems
• programming languages
• object-oriented languages

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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11519

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections