Lune

OOPSLA2021Top-tier venue

Specifying and testing GPU workgroup progress models

Tyler Sorensen, Lucas F. Salvador, Harmit Raval, Hugues Evrard, John Wickerson, Margaret Martonosi, Alastair F. Donaldson

Abstract

As GPU availability has increased and programming support has matured, a wider variety of applications are being ported to these platforms. Many parallel applications contain fine-grained synchronization idioms; as such, their correct execution depends on a degree of relative forward progress between threads (or thread groups). Unfortunately, many GPU programming specifications (e.g. Vulkan and Metal) say almost nothing about relative forward progress guarantees between workgroups. Although prior work has proposed a spectrum of plausible progress models for GPUs, cross-vendor specifications have yet to commit to any model.

This work is a collection of tools and experimental data to aid specification designers when considering forward progress guarantees in programming frameworks. As a foundation, we formalize a small parallel programming language that captures the essence of fine-grained synchronization. We then provide a means of formally specifying a progress model, and develop a termination oracle that decides whether a given program is guaranteed to eventually terminate with respect to a given progress model. Next, we formalize a set of constraints that describe concurrent programs that require forward progress to terminate. This allows us to synthesize a large set of 483 progress litmus tests. Combined with the termination oracle, we can determine the expected status of each litmus test -i.e. whether it is guaranteed to eventually terminate -under various progress models. We present a large experimental campaign running the litmus tests across 8 GPUs from 5 different vendors. Our results highlight that GPUs have significantly different termination behaviors under our test suite. Most notably, we find that Apple and ARM GPUs do not support the linear occupancy-bound model, an intuitive progress model defined by prior work that has been hypothesized to describe the workgroup schedulers of existing GPUs.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Recurrence Sets for Proving Fair Non-termination under Axiomatic Memory Consistency Models cites Towards Unified Analysis of GPU Consistency
  • Recurrence Sets for Proving Fair Non-termination under Axiomatic Memory Consistency Models cites Making weak memory models fair
  • Kuiper: Correct and Efficient GPU Programming with Dependent Types and Separation Logic cites Towards Unified Analysis of GPU Consistency
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. High-Performance GPU-to-CPU Transpilation and Optimization via High-Level Parallel ConstructsWilliam S. Moses, Ivan R. Ivanov, Jens Domke, Toshio Endo et al.PPoPP 2023 · 27 citations
  2. Towards Unified Analysis of GPU ConsistencyHaining Tong, Natalia Gavrilenko, Hernán Ponce de León, Keijo HeljankoASPLOS 2024 · 5 citations
  3. Taking Back Control in an Intermediate Representation for GPU ComputingVasileios Klimis, Jack Clark, Alan Baker, David Neto et al.POPL 2023 · 5 citations
  4. Recurrence Sets for Proving Fair Non-termination under Axiomatic Memory Consistency ModelsThomas Haas, Roland Meyer, Hernán Ponce de León, Andrés Lomelí GarduñoPOPL 2026 · 2 citations
  5. Kuiper: Correct and Efficient GPU Programming with Dependent Types and Separation LogicGuido Martínez, Bastian Köpcke, Jonás Fiala, Gabriel Ebner et al.PLDI 2026 · 2 citations

Builds on2

  1. Making weak memory models fairOri Lahav, Egor Namakonov, Jonas Oberhauser, Anton Podkopaev et al.OOPSLA 2021 · 21 citations
  2. Independent Forward Progress of Work-groupsAlexandru Dutu, Matthew D. Sinclair, Bradford M. Beckmann, David A. Wood et al.ISCA 2020 · 5 citations

Related papers

  1. SIMT-Step Execution: A Flexible Operational Semantics for GPU Subgroup BehaviorZheyuan Chen, Naomi Rehman, Guido Martínez, Tyler SorensenPLDI 2026 · 2 citations
  2. sfGPUMC: A Stateless Model Checker for GPU Weak Memory ConcurrencySoham Chakraborty, S. Krishna, Andreas Pavlogiannis, Omkar TuppeCAV 2025 · 2 citations
  3. Uniformity Analysis in the WebGPU Shading LanguageJames Lee-Jones, John Wickerson, Alastair F. DonaldsonPLDI 2026 · 1 citation
  4. Foundations of empirical memory consistency testingJake Kirkham, Tyler Sorensen, Esin Tureci, Margaret MartonosiOOPSLA 2020 · 7 citations
  5. Descend: A Safe GPU Systems Programming LanguageBastian Köpcke, Sergei Gorlatch, Michel SteuwerPLDI 2024 · 7 citations
Dusk over the sea between two cliffs drawn in fine vertical lines