Predictable Shared Last-level Caches

@inproceedings{wang_25_parp,
  author = {Xinzhe Wang and Rodolfo Pellizzoni 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.00020},
  title = {{ParRP: Enabling Space Isolation in Caches with Shared Data}},
  year = {2025}
}

This work presents an approach to isolate cache space while supporting shared data. Enabling shared data caching is challenging because it causes interference making it unsuitable for real-time multicores. Unlike prior works, we aim to introduce isolation, but our approach enables caching of shared data, and promotes isolated cache analysis for individual cores. The crux behind our approach is that shared data isolation can be achieved by partitioning the replacement information instead of the cache's data storage. Consequently, this work introduces ParRP, a novel hardware cache partitioning scheme for realtime cache-coherent multicores. Our evaluation using the gem5 simulator shows that, by providing isolation for shared data, the worst-case execution time of multi-threaded tasks can be lower by 2.4× at the cost of a 16.5% decrease in average-case performance.

@article{wu_24_tecs,
  author = {Zhuanhao Wu and Anirudh Mohan Kaushik and Hiren Patel},
  journal = {ACM Transactions on Embedded Computing Systems},
  volume = {23},
  number = {6},
  pages = {1--30},
  publisher = {ACM},
  month = {sep},
  doi = {10.1145/3687308},
  title = {{High Performance and Predictable Shared Last-level Cache for Safety-Critical Systems}},
  year = {2024}
}

We propose ZeroCost-LLC (ZCLLC), a novel shared inclusive last-level cache (LLC) design for timing predictable multi-core platforms that offers lower worst-case latency (WCL) when compared with a traditional shared inclusive LLC design. ZCLLC achieves low WCL by eliminating certain memory operations in the form of cache line invalidations across the cache hierarchy that are a consequence of a core’s memory request that misses in the cache hierarchy and when there is no vacant entry in the LLC to accommodate the fetched data for this request. In addition to low WCL, ZCLLC offers performance benefits in the form of additional caching capacity and unlike state-of-the-art approaches, ZCLLC does not impose any constraints on its usage across multiple cores. In this work, we describe the impact of LLC cache line invalidations on the WCL and systematically build solutions to eliminate these invalidations resulting in ZCLLC. We also present ZCLLC-OPT, an optimized variant of ZCLLC that offers lower WCL and improved average-case performance over ZCLLC. We apply optimizations to the shared bus arbitration mechanism and extend the micro-architecture of ZCLLC to allow for overlapping memory requests to the main memory. Our analysis reveals that the analytical WCL of a memory request under ZCLLC-OPT is 87.0%, 93.8%, and 97.1% lower than that under state-of-the-art LLC partition sharing techniques for 2, 4, and 8 cores, respectively. ZCLLC-OPT shows average-case performance speedups of 1.89×, 3.36×, and 6.24× compared with the state-of-the-art LLC partition sharing techniques for 2, 4, and 8 cores, respectively. When compared with the original ZCLLC that does not have any optimizations, ZCLLC-OPT shows lower analytical WCLs that are 76.5%, 82.6%, and 86.2% lower compared with ZCLLC-NORMAL for 2, 4, and 8 cores, respectively.

@inproceedings{wang_24_excl,
  author = {Xinzhe Wang and Zhuanhao Wu and Rodolfo Pellizzoni 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/RTAS61025.2024.00023},
  title = {{Exclusive Hierarchies for Predictable Sharing in Last-level Cache}},
  year = {2024}
}

This work presents an approach to use a last-level cache (LLC) in a memory hierarchy for cache-coherent real-time multicores that delivers a low worst-case latency (WCL) and higher performance than all of its counterparts. Our approach relies on the key observation that an exclusive memory hierarchy, by definition, eliminates back invalidations, which are one of the largest contributors to the WCL when using inclusive memory hierarchies. However, to the best of our knowledge, there are no prior efforts that ensure the predictability of exclusive hierarchies for cache-coherent multicores. Consequently, in this work, we propose PECC, a predictable exclusive cache coherence mechanism, that achieves a lower average data access latency while providing a low WCL bound that scales linearly in the number of cores. Our evaluation shows that PECC reduces the bound by 6% and improves the average performance by 2.33× over the predictable solution with an inclusive LLC.

@inproceedings{wu_23_zcllc_rtas,
  author = {Zhuanhao Wu and Anirudh M. Kaushik and Hiren Patel},
  booktitle = {{proceedings of IEEE Real-Time and Embedded Technology and
               Applications Symposium (RTAS)}},
  pages = {249-261},
  numpages = {11},
  publisher = {IEEE},
  month = {may},
  doi = {10.1109/RTAS58335.2023.00027},
  title = {{ZeroCost-LLC: Shared LLCs at No Cost to WCL}},
  year = {2023}
}

ZeroCost-LLC (ZCLLC) is a shared inclusive lastlevel cache (LLC) architecture for predictable multicore platforms that does not incur additional cost to the worst-case latency (WCL) of memory requests when compared to the memory hierarchy without an LLC. Thus, the WCL remains the same as without an LLC in the memory hierarchy, but with the performance benefits of having an LLC, in the form of additional caching capacity. ZCLLC achieves this by eliminating all cache line invalidations, and proactively updating the main memory with cache lines to preserve an important vacancy invariant. Furthermore, ZCLLC does not impose any constraints on the way the LLC is used unlike other approaches such as LLC partitioning. Our analysis reveals that the WCL is 55.6%, 68.0%, and 80.2% lower, and the performance is 2.4%, 7.2%, and 25.6% better than the state-of-the-art LLC partition sharing techniques for 2, 4, and 8 cores, respectively.

@inproceedings{wu_22_llc_dac,
  author = {Zhuanhao Wu and Hiren Patel},
  booktitle = {{proceedings of IEEE Design Automation Conference (DAC)}},
  pages = {1273–1278},
  numpages = {6},
  publisher = {IEEE},
  title = {{Predictable Sharing of Last-level Cache Partitions for Multi-core
           Safety-critical Systems}},
  year = {2022},
  doi = {10.1145/3489517.3530614}
}

Last-level cache (LLC) partitioning is a technique to provide temporal isolation and low worst-case latency (WCL) bounds when cores access the shared LLC in multicore safety-critical systems. A typical approach to cache partitioning involves allocating a separate partition to a distinct core. A central criticism of this approach is its poor utilization of cache storage. Today's trend of integrating a larger number of cores exacerbates this issue such that we are forced to consider shared LLC partitions for effective deployments. This work presents an approach to share LLC partitions among multiple cores while being able to provide low WCL bounds.