DLS: Directoryless Shared Last-level Cache

Daofu Liu, Yunji Chen, Qi Guo, Tianshi Chen, Ling Li, Qunfeng Dong, Weiwu Hu

TL;DR

This paper introduces DLS, a novel cache coherence protocol that eliminates the need for a directory in shared last-level caches. By leveraging the weak consistency model and a "self-suspicion + speculative execution" mechanism, DLS significantly reduces chip area, network traffic, and energy consumption while improving performance, all without requiring changes to existing software.

What Problem Does This Paper Address?

Modern multi-core processors rely on complex cache coherence protocols to ensure data consistency across multiple cores sharing memory. Directory-based protocols are the standard for this, but they come with significant drawbacks: the directory itself consumes substantial chip area, and the constant stream of "invalidation" and "acknowledgment" messages between cores and the directory creates network congestion, leading to performance degradation and increased energy usage. The authors argue that for practical parallel systems, which largely operate under a "weak consistency" model, this directory is an unnecessary overhead.

Methods

The core innovation of DLS is its complete removal of the directory. Instead of eagerly invalidating data in other cores' private caches (PCs) when a store operation occurs, DLS adopts a more relaxed approach. When a core performs a store that misses in its PC, the data isn't immediately broadcast. Instead, the change becomes visible to other cores only at their next synchronization point. At this synchronization, cores mark their shared (SHD) PC blocks as "suspicious" (SUS). If a load instruction later hits a SUS block, the core speculatively executes using the potentially stale data while simultaneously fetching the most up-to-date version from the last-level cache (LLC). This speculative execution, combined with the eventual retrieval of correct data, ensures correctness. This "self-suspicion + speculative execution" mechanism replaces the need for explicit invalidation messages.

Datasets

The experiments were conducted using the SPLASH-2 benchmark suite, a standard collection of parallel applications used for evaluating system performance. The paper lists ten specific benchmarks from this suite, along with their input data sizes. No new benchmarks were introduced.

Key Insights and Ideas

  • The Directory is an "Unnecessary Luxury": The central insight is that under the widely adopted weak consistency model, the strict requirement of immediate global visibility for store operations (enforced by directories) is overkill. Weak consistency allows for more relaxed ordering, making the directory's primary function redundant.
  • Synchronization as a Coherence Point: DLS cleverly uses synchronization points as natural moments to manage coherence. Instead of constant communication, cores self-police their shared blocks at these designated points.
  • Speculation Hides Latency: The speculative execution mechanism is key. It allows the processor to continue making progress even with potentially stale data, and the latency of fetching the correct data from the LLC often overlaps with this speculative work, mitigating performance penalties.
  • Compatibility is King: A major advantage highlighted is DLS's seamless compatibility with existing software. It doesn't require changes to programming languages or compilers, making it immediately applicable to legacy codebases.

Key Results

On a 16-core processor, DLS demonstrated significant improvements compared to the traditional MESI protocol with a full directory:

  • Performance: An average performance improvement of 11.08%, with a maximum of 28.34% on the "ocean-non" benchmark.
  • Network Traffic: A reduction of 28.83% in overall network traffic on average, and up to 81.92% for the "lu" benchmark.
  • Energy Consumption: A reduction of 15.65% in network energy consumption on average, with a maximum of 46.52% for the "barnes" benchmark.
  • Area Cost: Complete elimination of the chip area cost associated with the LLC directory.
  • Private Cache Performance: DLS actually reduced private cache (PC) miss rates across all evaluated benchmarks, a counter-intuitive but beneficial outcome attributed to its less aggressive invalidation policy.

Limitations and Future Work

  • Synchronization Dependency: The effectiveness of DLS relies heavily on the presence and proper use of synchronization points. The paper suggests that for optimal implementation, special synchronization instructions (like LL/SC) or hardware mechanisms might be beneficial, though it claims compatibility with normal load/store instructions.
  • Single-Threaded Performance: The paper notes that DLS does not affect the performance of single-threaded programs, as these typically operate on private memory regions that are already handled efficiently by other cache states.
  • Future Work: The authors suggest that DLS can be easily adapted to other directory-based protocols (like MSI and MOESI) by implementing the core modifications: enabling self-suspicion at synchronization and allowing SHD PC backups to coexist with EXC/MOD backups. The paper also briefly touches on cache value speculation as a related but orthogonal area.

Summary updated

Abstract

Directory-based protocols have been the de facto solution for maintaining cache coherence in shared-memory parallel systems comprising multi/many cores, where each store instruction is eagerly made globally visible by invalidating the private cache (PC) backups of other cores. Consequently, the directory not only consumes large chip area, but also incurs considerable energy consumption and performance degradation, due to the large number of Invalidation/Ack messages transferred in the interconnection network and resulting network congestion. In this paper, we reveal the interesting fact that the directory is actually an unnecessary luxury for practical parallel systems. Because of widely deployed software/hardware techniques involving instruction reordering, most (if not all) parallel systems work under the weak consistency model, where a remote store instruction is allowed to be invisible to a core before the next synchronization of the core, instead of being made visible eagerly by invalidating PC backups of other cores. Based on this key observation, we propose a lightweight novel scheme called {\em DLS (DirectoryLess Shared last-level cache)}, which completely removes the directory and Invalidation/Ack messages, and efficiently maintains cache coherence using a novel {\em self-suspicion + speculative execution} mechanism. Experimental results over SPLASH-2 benchmarks show that on a 16-core processor, DLS not only completely removes the chip area cost of the directory, but also improves processor performance by 11.08%, reduces overall network traffic by 28.83%, and reduces energy consumption of the network by 15.65% on average (compared with traditional MESI protocol with full directory). Moreover, DLS does not involve any modification to programming languages and compilers, and hence is seamlessly compatible with legacy codes.
BibTeX
@misc{liu2012dls,
  author = {Daofu Liu and Yunji Chen and Qi Guo and Tianshi Chen and Ling Li and Qunfeng Dong and Weiwu Hu},
  title = {{DLS: Directoryless Shared Last-level Cache}},
  year = {2012},
  eprint = {1206.4753},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1206.4753},
}

Loading related content...

Figure