Scalable Task Scheduling and Synchronization Using Hierarchical Effects

Stephen T. Heumann, Alexandros Tzannes, Vikram S. Adve

Research output: Contribution to journalConference articlepeer-review


Several concurrent programming models that give strong safety guarantees employ effect specifications that indicate what effects on shared state a piece of code may perform. These specifications can be much more expressive than traditional synchronization mechanisms like locks, and they are amenable to static and/or dynamic checking approaches for ensuring safety properties. The Tasks With Effects (TWE) programming model uses dynamic checking to give nearly the strongest safety guarantees of any existing shared memory language while providing the flexibility to express both structured and unstructured concurrency. Like several other systems, TWE's effect specifications use hierarchical memory regions, which can naturally model nested and modular data structures and allow effects to be expressed at different levels of granularity in different parts of a program. To implement a programming model like TWE with high performance, particularly for programs with many fine-grain tasks, the run-time task scheduler must employ an algorithm that can enforce task isolation (mutual exclusion of tasks with conflicting effects) with low overhead and high scalability. This paper describes such an algorithm for TWE. It uses a scheduling tree designed to take advantage of the hierarchical structure of TWE effects, obtaining two key properties that lead to high scalability: (a) effects need to be compared only for ancestor and descendant nodes in the tree, and not any other nodes, and (b) the scheduler can use fine-grain locking of tree nodes to enable highly concurrent scheduling operations. We prove formally that the algorithm guarantees task isolation. Experimental results with a range of programs show that the algorithm provides very good scalability, even with fine-grain tasks.

Original languageEnglish (US)
Article number7429300
Pages (from-to)125-137
Number of pages13
JournalParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
StatePublished - Jan 1 2015
Event24th International Conference on Parallel Architecture and Compilation, PACT 2015 - San Francisco, United States
Duration: Oct 18 2015Oct 21 2015


  • Hierarchical effects
  • Task isolation
  • Task scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Scalable Task Scheduling and Synchronization Using Hierarchical Effects'. Together they form a unique fingerprint.

Cite this