IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

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

Show simple item record

Bookmark or cite this item: http://hdl.handle.net/2142/11519

Files in this item

File Description Format
PDF A Type and Effe ... ect-Oriented Languages.pdf (236KB) (no description provided) PDF
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
Subject(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.
Issue Date: 2009-02
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/11519
Other Identifier(s): UIUCDCS-R-2009-3032
Rights 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).
Date Available in IDEALS: 2009-04-23
 

This item appears in the following Collection(s)

Show simple item record

Item Statistics

  • Total Downloads: 339
  • Downloads this Month: 2
  • Downloads Today: 0

Browse

My Account

Information

Access Key