A Formally Verified Foundation for Compositional Heterogeneous Coherence
An Qi Zhang, Andrés Goens, Daniel J. Sorin, Vijay Nagarajan
Abstract
Modern processors integrate heterogeneous devices to expose unified shared memory. Yet, the de-facto design pattern used to compose their disparate coherence protocols lacks a formal foundation. This leaves the door open for subtle consistency bugs, in a critical gap between practice and correctness. This paper provides the first formal, machine-checked proof that a de-facto design pattern, which we call the Principle of Synchronous Propagation, is correct. Leveraging a new unifying abstraction for coherence protocols, our central theorem (machine checked in Lean) proves that Synchronous Propagation is sufficient to guarantee the Compound Memory Consistency Model for a wide class of protocols. Our work provides long-needed assurance for current designs and delivers a reusable, compositional framework for verifying future heterogeneous systems.
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.
Lineage
- vCXLGen: Automated Synthesis and Verification of CXL Bridges for Heterogeneous Architectures cites HieraGen: Automated Generation of Concurrent, Hierarchical Cache Coherence Protocols
- vCXLGen: Automated Synthesis and Verification of CXL Bridges for Heterogeneous Architectures cites HeteroGen: Automatic Synthesis of Heterogeneous Cache Coherence Protocols
- vCXLGen: Automated Synthesis and Verification of CXL Bridges for Heterogeneous Architectures cites Compound Memory Models
- HeteroGen: Automatic Synthesis of Heterogeneous Cache Coherence Protocols cites HieraGen: Automated Generation of Concurrent, Hierarchical Cache Coherence Protocols
- Compound Memory Models cites HeteroGen: Automatic Synthesis of Heterogeneous Cache Coherence Protocols
- Hemiola: A DSL and Verification Tools to Guide Design and Proof of Hierarchical Cache-Coherence Protocols cites HieraGen: Automated Generation of Concurrent, Hierarchical Cache Coherence Protocols
Builds on6
- HieraGen: Automated Generation of Concurrent, Hierarchical Cache Coherence ProtocolsNicolai Oswald, Vijay Nagarajan, Daniel J. SorinISCA 2020 · 15 citations
- HeteroGen: Automatic Synthesis of Heterogeneous Cache Coherence ProtocolsNicolai Oswald, Vijay Nagarajan, Daniel J. Sorin, Vasilis Gavrielatos et al.HPCA 2022 · 15 citations
- Compound Memory ModelsAndrés Goens, Soham Chakraborty, Susmit Sarkar, Sukarn Agarwal et al.PLDI 2023 · 11 citations
- Hemiola: A DSL and Verification Tools to Guide Design and Proof of Hierarchical Cache-Coherence ProtocolsJoonwon Choi, Adam Chlipala, ArvindCAV 2022 · 9 citations
- vCXLGen: Automated Synthesis and Verification of CXL Bridges for Heterogeneous ArchitecturesAnatole Lefort, Julian Pritzi, Nicolò Carpentieri, David Schall et al.ASPLOS 2026 · 2 citations
Related papers
- CAAT: consistency as a theoryThomas Haas, Roland Meyer, Hernán Ponce de LeónOOPSLA 2022 · 11 citations
- Checking Data-Race Freedom of GPU Kernels, CompositionallyTiago Cogumbreiro, Julien Lange, Dennis Liew Zhen Rong, Hannah ZicarelliCAV 2021 · 17 citations
- Sharding the State Machine: Automated Modular Reasoning for Complex Concurrent SystemsTravis Hance, Yi Zhou, Andrea Lattuada, Reto Achermann et al.OSDI 2023 · 18 citations
- C³: CXL Coherence Controllers for Heterogeneous ArchitecturesAnatole Lefort, David Schall, Nicolò Carpentieri, Julian Pritzi et al.HPCA 2026 · 1 citation
- Sequential reasoning for optimizing compilers under weak memory concurrencyMinki Cho, Sung-Hwan Lee, Dongjae Lee, Chung-Kil Hur et al.PLDI 2022 · 11 citations
