A programming model for deterministic task parallelism

Polyvios Pratikakis, Hans Vandierendonck, Spyros Lyberis, Dimitrios S. NikolopoulosMSPC 2011 · DOI

TL;DR

This paper proposes a new programming model for multicore processors that aims to simplify parallel programming by restricting how tasks communicate and by managing memory access deterministically. The goal is to achieve predictable, race-free execution equivalent to sequential code, even on hardware without cache coherency.

What Problem Does This Paper Address?

Modern multicore processors are becoming increasingly complex, with a growing number of cores. This leads to challenges in maintaining efficient cache coherency protocols, making shared memory programming difficult and error-prone. Programmers struggle to reason about the myriad of potential thread interleavings and interactions, leading to subtle bugs that are hard to reproduce and debug. Furthermore, as hardware increasingly relaxes cache coherency, programmers must manually manage data transfers, adding complexity. This paper addresses the need for a programming model that simplifies parallel programming, guarantees deterministic execution, and efficiently handles memory on modern multicore architectures, especially those with relaxed or absent cache coherency.

Methods

The proposed model introduces two key ideas:

  • Restricted Task Communication: Programs are structured as a hierarchy of recursive, atomic tasks. Crucially, tasks cannot communicate with each other during their execution. Communication is limited to spawning child tasks and waiting for their completion.
  • Region-Based Memory Footprinting and Exclusive Access: Each task explicitly declares its memory footprint (the objects or regions it will access). The runtime system guarantees that a task has exclusive access to its declared memory during its execution. This eliminates the need for traditional cache coherency protocols.

A runtime system is described that transparently handles data transfers between cores based on these memory footprints. It detects ordering dependencies among tasks accessing the same memory and resolves them deterministically, ensuring that the parallel execution is equivalent to its sequential counterpart. The model leverages region-based memory management to handle dynamic data structures and optimize for locality.

Datasets

Not discussed in the paper. The paper focuses on a conceptual programming model and its formalization, with a small illustrative example rather than empirical evaluation on large datasets.

Key Insights and Ideas

  • Determinism as a First-Class Citizen: The core insight is that by restricting communication and enforcing exclusive memory access per task, deterministic execution can be guaranteed. This is a significant departure from many existing multithreaded models where non-determinism is a common challenge.
  • Decoupling Parallelism from Cache Coherency: The model effectively sidesteps the complexities of cache coherency by ensuring that only one task accesses a given piece of memory at a time. This makes it suitable for a wider range of hardware, including those without hardware cache coherency.
  • Task Footprinting for Efficient Runtime: Requiring tasks to declare their memory footprint allows the runtime to precisely manage data transfers and dependencies, leading to potentially efficient execution without the overhead of global shared memory management.
  • Hierarchical and Recursive Task Structure: The model supports nested parallelism, allowing for a natural decomposition of problems into smaller, independent tasks, similar to Cilk.

Key Results

The paper presents a formalization of a simplified version of the programming model and provides a proof sketch for sequential equivalence. This means that any program written in this model is guaranteed to produce the same result as its sequential version, and its execution is deterministic. While a preliminary implementation is mentioned as performing comparably to Cilk++, specific quantitative results are not detailed in this position paper.

Limitations and Future Work

  • Object Granularity: The model requires tasks to operate on whole objects or regions, which might be restrictive for certain fine-grained operations. The authors note this requirement is more fitting for type-safe languages and that their current implementation is in C.
  • Formalism Simplification: The determinism proof is presented for a simplified version of the model, omitting region-based memory management for clarity.
  • Scalability of Runtime: While the model aims for scalability, the paper doesn't deeply explore the performance characteristics of the runtime system on large-scale systems.

Future work would likely involve a full implementation and empirical evaluation of the proposed model and its runtime system, exploring its performance on various multicore architectures and workloads. Further research could also investigate how to relax the object-granularity constraint while maintaining determinism.

Summary updated

BibTeX
@inproceedings{pratikakis2011programming,
  author = {Polyvios Pratikakis and Hans Vandierendonck and Spyros Lyberis and Dimitrios S. Nikolopoulos},
  title = {{A programming model for deterministic task parallelism}},
  booktitle = {MSPC},
  year = {2011},
  doi = {10.1145/1988915.1988918},
}
Figure