Reconciling Predictability and Coherent Caching

Ayoosh Bansal, Jayati Singh, Yifan Hao, Jen-Yang Wen, Renato Mancuso, Marco Caccamo

TL;DR

This paper introduces a novel memory type, Inner-Non-Cacheable, Outer-Cacheable (INC-OC), that allows applications to selectively bypass private L1 caches and cache data only in shared L2/L3 caches. This approach eliminates cache coherence overheads for critical data, significantly reducing worst-case execution time (WCET) variability in real-time systems without a substantial impact on average performance.

What Problem Does This Paper Address?

Modern real-time and cyber-physical systems demand predictable response times. While multi-core processors offer immense computational power, they introduce significant unpredictability, particularly due to cache coherence mechanisms. When multiple cores access shared data, maintaining consistency across their private caches (L1) requires complex protocols. These protocols, often proprietary and not optimized for worst-case scenarios, introduce variable latencies that make WCET analysis extremely challenging. This unpredictability hinders the design and certification of safety-critical real-time systems.

Methods

The core contribution is the Inner-Non-Cacheable, Outer-Cacheable (INC-OC) memory type. This memory type is configured at the page granularity. Data marked as INC-OC is prevented from being cached in private L1 caches but is allowed to be cached in shared L2/L3 caches. By ensuring that shared data resides only in shared cache levels, the need for explicit cache coherence protocols between private caches is eliminated. This effectively makes accesses to INC-OC data predictable, as they bypass the variable latencies associated with coherence operations. The authors implemented this concept within the gem5 architectural simulator, modifying the memory subsystem and cache controllers to recognize and handle this new memory type.

Datasets

The paper does not explicitly mention specific datasets for training. For evaluation, they used:

  • Custom Scenarios and Microbenchmarks: Designed to isolate specific behaviors like dirty misses and lock contention.
  • SPLASH2 Benchmarks: A suite of parallel applications used to evaluate the performance of the proposed INC-OC memory type in a full system simulation.

Key Insights and Ideas

  • Cache Coherence is a Major Predictability Bottleneck: The paper strongly emphasizes that the variability introduced by cache coherence protocols is a primary obstacle to achieving predictable WCET in multi-core real-time systems.
  • Bypassing Private Caches Solves the Problem: The key insight is that by forcing shared data into shared caches (and out of private L1s), the complex and unpredictable coherence machinery can be entirely bypassed for that data.
  • Application-Level Control is Crucial: The solution relies on giving developers or compilers the ability to explicitly designate memory regions as INC-OC, allowing them to make informed trade-offs between average performance and worst-case predictability.
  • Minimal Hardware/OS Changes: The proposed INC-OC memory type leverages existing ISA features (like page table attributes) and requires only modest modifications to cache controllers and OS memory management, making it potentially practical to implement.

Key Results

  • 52% Reduction in Worst-Case Write Latency: For a specific dirty miss scenario (a write request to a line in the Modified state in another L1 cache), INC-OC reduced the worst-case latency by 52%.
  • 74% Reduction in Total Write Request Time: In a scenario with four cores simultaneously writing to the same address, INC-OC reduced the total time by 74%.
  • Lock Acquisition Latency Reduced: For synchronization primitives like spinlocks, INC-OC significantly reduced average acquisition latency, as the overhead of maintaining coherence was removed.
  • Minimal Impact on Average Performance: When applied selectively ("Program Aware INC-OC"), the proposed technique showed near-identical performance to the normal cacheable memory baseline across SPLASH2 benchmarks, with INC-OC accesses being a very small percentage of total accesses.
  • "Blind" INC-OC Allocation is Detrimental: Applying INC-OC to all shared memory without careful selection ("Blind INC-OC") resulted in up to 5.7x higher execution times, highlighting the importance of precise application-level control.

Limitations and Future Work

  • Manual Refinement Required: The "Program Aware INC-OC" approach, which yields good results, requires manual identification of shared memory regions by developers. The authors suggest that this process could potentially be automated at compile-time.
  • Platform Dependency: The exact applicability and benefits of INC-OC depend on the specific cache hierarchy, coherence protocol, and memory type support of the target hardware. Some platforms might simplify INC-OC support, reducing its effectiveness.
  • Shared Cache Bandwidth Contention: While INC-OC eliminates coherence overhead, it can increase contention on shared L2/L3 cache bandwidth. This is a known issue that has been studied in prior work.
  • Limited Evaluation of Application Models: The paper acknowledges that the impact of INC-OC on specific application models like non-blocking algorithms or data streaming models was not fully evaluated due to platform and benchmark limitations. Future work could explore these areas.
  • Security Implications: The authors note that expanding user-space control over hardware memory types has security implications that need careful consideration.

Summary updated

Abstract

Real-time systems are required to respond to their physical environment within predictable time. While multi-core platforms provide incredible computational power and throughput, they also introduce new sources of unpredictability. For parallel applications with data shared across multiple cores, overhead to maintain data coherence is a major cause of execution time variability. This source of variability can be eliminated by application level control for limiting data caching at different levels of the cache hierarchy. This removes the requirement of explicit coherence machinery for selected data. We show that such control can reduce the worst case write request latency on shared data by 52%. Benchmark evaluations show that proposed technique has a minimal impact on average performance.
BibTeX
@inproceedings{bansal2020reconciling,
  author = {Ayoosh Bansal and Jayati Singh and Yifan Hao and Jen-Yang Wen and Renato Mancuso and Marco Caccamo},
  title = {{Reconciling Predictability and Coherent Caching}},
  booktitle = {MECO},
  year = {2020},
  url = {https://openreview.net/forum?id=RNELCRV9ViI},
}
Figure