The tasks with effects model for safe concurrency

Heumann, Stephen T.

Permalink

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

Description

Title

The tasks with effects model for safe concurrency

Author(s)

Heumann, Stephen T.

Issue Date

2016-07-11

Director of Research (if dissertation) or Advisor (if thesis)

Adve, Vikram

Doctoral Committee Chair(s)

Adve, Vikram

Committee Member(s)

• Adve, Sarita
• Padua, David
• Parthasarathy, Madhusudan
• Ceze, Luis

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• tasks with effects
• parallelism
• concurrency

Abstract

Today's state-of-the-art concurrent programming models either provide weak safety guarantees, making it easy to write code with subtle errors, or are limited in the class of programs that they can express. I believe that a concurrent programming model should offer strong safety guarantees such as data race freedom, atomicity, and optional determinism, while being flexible enough to express the wide range of uses for concurrency in realistic programs, and offering good performance and scalability. In my thesis research, I have defined a new concurrent programming model called tasks with effects (TWE) that is intended to fulfill these goals. The core unit of work in this model is a dynamically-created task. The model's key feature is that each task has programmer-specified effects, and a run-time scheduler is used to ensure that two tasks are run concurrently only if they have non-interfering effects. Through the combination of statically verifying the declared effects of tasks and using an effect-aware run-time scheduler, the TWE model is able to guarantee strong safety properties such as data race freedom and atomicity. I have implemented this programming model in a language called TWEJava and its accompanying runtime system. I have evaluated TWEJava's expressiveness by implementing several programs in it. This evaluation shows that it can express a variety of parallel and concurrent programs, including programs that combine unstructured concurrency driven by user input with structured parallelism for performance, a pattern that cannot be expressed by some more restrictive models for safe parallel programming. I describe the TWE programming model and provide a formal dynamic semantics for it. I also formalize the data flow analysis used to statically check effects in TWEJava programs. This analysis is used to ensure that the effect of each operation is included within the covering effect at that point in the program. The combination of these static checks with the dynamic semantics provided by the run-time system gives rise to the TWE model's strong safety guarantees. To make the TWE model usable, particularly for programs with many fine-grain tasks, a scalable, high-performance scheduler is crucial. I have designed a highly scalable scheduling algorithm for tasks with effects. It uses a tree structure corresponding to the hierarchical memory descriptions used in effect specifications, allowing scheduling operations for effects on separate parts of the tree to be performed concurrently and without explicitly checking such effects against each other. This allows for high scalability while preserving the expressiveness afforded by the hierarchical effect specifications. I describe the scalable scheduling algorithm in detail and prove that it correctly guarantees task isolation. I have evaluated this scheduler on six TWEJava programs, including programs using many fine-grain tasks. The evaluation shows that it gives significant speedups on all the programs, often comparable to versions of the programs with low-level synchronization and parallelism constructs that provide no safety guarantees. As originally defined, the TWE model could not express algorithms in which the side effects of each task are dependent on dynamic data structures and cannot be expressed statically. Existing systems that can handle such algorithms give substantially weaker safety guarantees than TWE. I developed an extension of the TWE model that enables it to be used for such algorithms. A new feature of the TWEJava language is defined to let programmers specify a set of object references that define some of the effects of a task, which can be added to dynamically as the task executes. The static covering effect checks used by TWE are extended to ensure they are still sound in the presence of such dynamic effect sets, and the formal dynamic semantics for the TWE model are extended to support these dynamic effects. I describe and implement a run-time system for handling these dynamic effects, including mechanisms to detect conflicts between dynamic effects and to abort and retry tasks when such conflicts arise. I show that this system can express parallel algorithms in which the effects of a task can only be expressed dynamically. Preliminary performance experiments show that my dynamic effect system can deliver self-relative speedups for certain benchmarks, but the current version of the system imposes substantial performance overheads. I believe that these overheads can be significantly reduced, making TWE practical to use for programs that require dynamic effects; this is a focus of my ongoing and future work.

Graduation Semester

2016-08

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2016 Stephen Thomas Heumann

Owning Collections