Predictable Cache Coherence

@inproceedings{wu_25_ppp,
  author = {Zhuanhao Wu and Hiren Patel},
  booktitle = {{proceedings of IEEE Real-Time and Embedded Technology and
               Applications Symposium (RTAS)}},
  pages = {1–-11},
  numpages = {11},
  publisher = {IEEE},
  month = {may},
  doi = {10.1109/RTAS65571.2025.00019},
  title = {{Consistency-aware and Predictable Memory Processing for Safety-critical Out-of-order Multicores}},
  year = {2025}
}

We introduce an approach that facilitates predictable processing of multiple outstanding memory requests in safety-critical out-of-order multicores. A primary challenge addressed by this work is ensuring that multiple outstanding memory requests maintain a memory consistent model while minimizing a low worst-case latency. Adhering to a memory consistency model is crucial for ensuring the correctness of programs executed on such multicores. Our approach, termed predictable processing of multiple outstanding requests (PPP), leverages micro-architectural enhancements to tackle this challenge. Experimental results show that PPP delivers speedups of 2.07×, 2.79×, and 3.38× over serialization for 2, 4, and 8 cores, while maintaining the worst-case latency.

@inproceedings{wu_23_ditty_date,
  author = {Zhuanhao Wu and Marat Bekmyrza and Nachiket Kapre and Hiren Patel},
  booktitle = {{proceedings of IEEE Design Automation and Test in Europe (DATE)}},
  pages = {1–-6},
  numpages = {6},
  publisher = {IEEE},
  month = {apr},
  doi = {10.23919/DATE56975.2023.10136986},
  title = {{Ditty: Directory-based Cache Coherence for Multicore Safety-critical
           Systems}},
  year = {2023}
}

Ditty is a predictable directory-based cache co-herence mechanism for multicore safety-critical systems that guarantees a worst-case latency (WCL) on data accesses. Prior approaches for predictable cache coherence use a shared snooping bus to interconnect cores. This restricts the number of cores in the multicore to typically four or eight due to scalability concerns. Ditty takes a first step towards a scalable cache coherence mechanism that is predictable and one that can support a larger number of cores. In designing Ditty, we propose a coherence protocol and micro-architecture additions to deliver a WCL bound that is lower than a naive approach. Our WCL analysis reveals that the resulting bounds are comparable to state-of-the-art bus-based predictable coherence approaches. We prototype Ditty in hardware and empirically evaluate it on an FPGA. Our evaluation shows the observed WCL is within computed WCL bound for both the synthetic and SPLASH-3 benchmarks. We release our implementation to the public domain.

@inproceedings{tadepalli_23_pasoc,
  author = {Tadepalli, Susmita and Wu, Zhuanhao and Patel, Hiren},
  title = {PASoC: A Predictable Accelerator-Rich SoC},
  year = {2023},
  isbn = {9798400700491},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3576914.3587496},
  doi = {10.1145/3576914.3587496},
  booktitle = {Proceedings of Cyber-Physical Systems and Internet of Things Week
               2023},
  pages = {325–330},
  numpages = {6},
  keywords = {Hardware accelerators, Safety-critical systems, Predictability,
              SoCs},
  location = {San Antonio, TX, USA},
  series = {CPS-IoT Week '23}
}

We present a model of a predictable accelerator-rich system-on-chip (PASoC) for safety-critical systems. The PASoC allows the integration of multiple coherent agents to interact with each other over a shared memory bus. These agents can be a cluster of cache-coherent homogeneous cores, and fully or one-way coherent hardware accelerators. PASoC supports predictable cache coherence within the cluster of cores, and across agents. The former uses linear cache coherence, and the latter uses a modified version of predictable MSI. We analyze the per-request worst-case latency, a memory request from any of the agents can experience in the PASoC. Finally, we present some observations based on our analysis that can help in future designs of PASoCs.

Predictable hardware cache coherence is a viable shared data communication mechanism between cores for multicore real-time platforms. Prior works have established that predictable hardware cache coherence protocols offer significant performance advantages over alternative predictable data communication mechanisms while ensuring predictability. Unlike alternative predictable data communication mechanisms, designing predictable cache coherence protocols is nontrivial as it requires detailed understanding of the impact of different memory activity patterns to shared data for predictable and coherent data communication. Furthermore, designing predictable cache coherence protocols that deliver high average-case performance is even more challenging as it entails identifying opportunities such that a core’s access to a data is not stalled in the presence of interleaving memory activity from other cores to the same data. To this end, we present SYNTHIA, an open and automated tool for synthesizing predictable and high-performance snooping bus-based cache coherence protocols for multicore platforms deployed in real-time systems. SYNTHIA automates the complex analysis associated with designing predictable and high-performance cache coherence protocols, and constructs the complete protocol implementation (coherence states and transitions) that achieve predictability and performance. We use SYNTHIA to construct complete protocol implementations from simple specifications of common protocols (modified-shared-invalid (MSI), MESI, and MOESI protocols) and a predictable variant of the MESIF cache coherence protocol, which was recently found to be deployed in an existing multicore platform designed for real-time platforms. We validated the correctness, predictability, and performance guarantees of the generated protocol implementations from SYNTHIA using manually implemented versions, and a micro-architectural simulator.

This work presents MapleBoard: a set of opensource hardware tools to implement predictable cache coherence protocols in hardware. MapleBoard consists of the following: (1) a novel domain-specific language (DSL) for specifying coherence protocols and synthesizing the corresponding hardware; and, (2) a real-time multicore hardware platform that seamlessly integrates the coherence protocols synthesized from the DSL. This platform has a memory hierarchy, a real-time bus interconnect between cores, and various predictable arbiters. As a demonstration of MapleBoard's efficacy, we explore hardware implementations of data bus organizations, and their impact on the worstcase communication latency (WCL). An important discovery we make is that a dedicated data bus (DDB) organization that allows bidirectional data communication offers lower analytical WCL bounds than any state-of-the-art predictable cache coherence protocols. The analytical WCL bounds are improved by 84%, 90% and 94% for 2-core, 4-core and 8-core systems respectively compared to prior works. We synthesize MapleBoard on the Xilinx Virtex Ultrascale+ VCU1525 board, and validate using both synthetic workloads and SPLASH-2 benchmark suite.

Predictable hardware cache coherence is an attractive data communication mechanism between safety-critical tasks deployed on real-time multi-core platforms due to its predictability and high-performance benefits. However, from a worst-case analysis standpoint, alternative data communication mechanisms appear in favorable light for adoption in real-time multi-core platforms. This is because alternative data communication mechanisms such as cache bypassing offer tighter worstcase latency (WCL) bounds for memory requests compared to predictable hardware cache coherence mechanisms. We present a systematic approach towards designing predictable cache coherence mechanisms that offer tight WCL and high-performance. Our approach consists of a formal framework that concisely captures the key reasons behind the high WCL in existing predictable cache coherence mechanisms. Guided by this formal framework, we describe one technique that employs micro-architectural extensions and protocol changes to achieve tight WCL and high-performance. We apply this technique to two existing cache coherence mechanisms. Our evaluation shows that the new cache coherence mechanisms resulting from our technique have the same tight WCL as alternative mechanisms, and still maintain a significant average-case performance advantage (up to 5× speedup) over the alternative mechanisms.

We present SYNTHIA, an open and automated tool for synthesizing predictable and high-performance snooping bus-based cache coherence protocols for multi-core processors in multi-processor system-on-chips (MPSoCs) deployed in real-time systems. SYNTHIA automates the complex analysis associated with designing predictable and high-performance cache coherence protocols, and constructs new states (transient states) and corresponding transitions that achieve predictability and performance. We use SYNTHIA to construct complete protocol implementations from simple specifications of common protocols (MSI, MESI, and MOESI protocols). We validated the correctness, predictability, and performance guarantees of the generated protocol implementations from SYNTHIA using manually implemented versions, and a micro-architectural simulator.

We present CARP, a predictable and high-performance data communication mechanism for multi-core mixed-criticality systems (MCS). CARP is realized as a hardware cache coherence protocol that enables communication between critical and non-critical tasks while ensuring that non-critical tasks do not interfere with the safety requirements of critical tasks. The key novelty of CARP is that it is criticality-aware, and hence, handles communication patterns between critical and non-critical tasks appropriately. We derive the analytical worst-case latency bounds for requests using CARP and note that the observed per-request latencies are within the analytical worst-case latency bounds. We compare CARP against prior data communication mechanisms using synthetic and SPLASH-2 benchmarks. Our evaluation shows that CARP improves the average-case performance of MCS compared to prior data communication mechanisms, while maintaining the safety requirements of critical tasks.

Emerging embedded systems deployed in the automotive and avionics domains execute applications with different criticalities, comprising what is known as Mixed Criticality Systems (MCS). Applications in MCS often share data between tasks (coming from sensors for instance). Data sharing is challenging because it can lead to increased response times or even unpredictable behaviors if not carefully addressed. Therefore, several prior works in MCS either assumed that tasks do not share data or disallowed it by design. Recent solutions attempt to mitigate the effects of data sharing, albeit by introducing new restrictions on the system either by prohibiting applications from caching shared data or prohibiting the operating system from running tasks with shared data in parallel. We find these solutions also to have limited applicability as they deteriorate system schedulability and prohibit simultaneous access to shared data. In this paper, we propose PENDULUM: a time-based cache coherence protocol to enable simultaneous and predictable access to shared data in MCS. Our evaluation shows that PENDULUM, achieves flexibility and better performance compared to existing solutions, while maintaining system predictability.

This work addresses the challenge of allowing simultaneous and predictable accesses to shared data on multicore systems. We propose a predictable cache coherence protocol, which mandates the use of certain invariants to ensure predictability. In particular, we enforce these invariants by augmenting the classic modify-share-invalid (MSI) protocol with transient coherence states, and minimal architectural changes. This allows us to derive worst-case latency bounds on predictable MSI (PMSI) protocol. Our analysis shows that while the arbitration latency scales linearly, the coherence latency scales quadratically with the number of cores, which emphasizes that importance of accounting for cache coherence effects on latency bounds. We implement PMSI in gem5, and execute SPLASH-2 and synthetic workloads. Results show that our approach is always within the analytical worst-case latency bounds, and that PMSI improves averagecase performance by up to 4 over the next best predictable alternative. PMSI has average slowdowns of 1.45 and 1.46 compared to MSI and MESI protocols, respectively.