Files in this item



application/pdfA 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
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)

Item Statistics