Lune

Abstract

Modern computers heavily rely on caches as one of the means to achieve higher performance. As a result, cache management has been the topic of extensive research. Compared to cache replacement and prefetching, cache indexing has re-ceived far less interest over the years. Being in the critical path, a good cache index function must exhibit a high performance while having a minimal computational delay. Previous indexing schemes fall short of these requirements, having either moderate performance or a prohibitively expensive delay. We propose ENTROPyINDEX, an entropy-based cache indexing scheme that can deliver superior performance while maintaining a minimal computational cost. ENTROPyINDEX is based on the idea of constructing the index function dynamically at runtime using the address bits with the highest entropy (randomness) to maximize the balance of the cache access distribution. The entropy of the address bits is measured by determining which bits change between two subsequent cache misses. ENTROPyINDEX periodically compares the entropy of different bits and selects the ones that change the most. This dynamic selection scheme allows ENTROPyINDEX to adapt to different types of applications. Our experimental results show that ENTROPyINDEX outper-forms previous indexing schemes both with and without hardware prefetching. For SPEC 2006, SPEC 2017, PARSEC 3.0 and GAP benchmarks without prefetching, ENTROPyINDEX delivers a geometric mean IPC improvement of 3.39% (with the highest being 52.2%), compared to a 1.74% improvement of the state-of-the-art index function (PRIME) and a 1.76% improvement of a commercialized indexing scheme (XORHASH) over the baseline power-of-two modulo scheme. With prefetching, ENTROPyINDEX is the only indexing scheme with a substantial performance gain of 1.42% (with the highest being 30.1 %), compared to a 0.41 % improvement of Prime and a 0.49% improvement of Xorhash over the same baseline. For non-uniform applications and no-prefetching, ENTROPyINDEX gives an IPC speed up of 5.58%, compared to a 2.26% speed up of Prime and a 2.23% speed up of Xorhash. For non-uniform applications with prefetching, the IPC speed up of ENTROPyINDEX is 2.08%, compared to a 0.35% speed up of Prime and a 0.53% speed up of Xorhash. For CVP workloads without prefetching, ENTROPyINDEX delivers a speed up of 3.04% over the baseline compared to a 1.52% of Prime and a 2.04% of Xorhash. For CVP workloads with prefetching, ENTROPyINDEX improves the IPC by 1.60%, compared to 0.63% of Prime and 1.07% of Xorhash.

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.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Principled Design of Indexing Functions for Memory Coloring cites Page Size Aware Cache Prefetching
  • Principled Design of Indexing Functions for Memory Coloring cites Effective Mimicry of Belady's MIN Policy
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Principled Design of Indexing Functions for Memory ColoringStephan Dübler, Jana Hofmann, Boris Köpf, Stavros VolosUSENIX Security 2026

Builds on5

  1. A hierarchical neural model of data prefetchingZhan Shi, Akanksha Jain, Kevin Swersky, Milad Hashemi et al.ASPLOS 2021 · 100 citations
  2. Designing a Cost-Effective Cache Replacement Policy using Machine LearningSubhash Sethumurugan, Jieming Yin, John SartoriHPCA 2021 · 81 citations
  3. Effective Mimicry of Belady's MIN PolicyIshan Shah, Akanksha Jain, Calvin LinHPCA 2022 · 44 citations
  4. Ripple: Profile-Guided Instruction Cache Replacement for Data Center ApplicationsTanvir Ahmed Khan, Dexin Zhang, Akshitha Sriraman, Joseph Devietti et al.ISCA 2021 · 33 citations
  5. Page Size Aware Cache PrefetchingGeorgios Vavouliotis, Gino Chacon, Lluc Alvarez, Paul V. Gratz et al.MICRO 2022 · 24 citations

Related papers

  1. A Cost-Effective Entangling Prefetcher for InstructionsAlberto Ros, Alexandra JimboreanISCA 2021 · 31 citations
  2. R-Max: Extending BéLáDy's MIN with Prefetching to Bound Realistic Cache PerformanceLei Wang, Chia-Hang Lee, Maccoy Merrell, Gino Chacon et al.ISCA 2026
  3. Scatter and Split Securely: Defeating Cache Contention and Occupancy AttacksLukas Giner, Stefan Steinegger, Antoon Purnal, Maria Eichlseder et al.S&P 2023
  4. ClepsydraCache - Preventing Cache Attacks with Time-Based EvictionsJan Philipp Thoma, Christian Niesler, Dominic A. Funke, Gregor Leander et al.USENIX Security 2023
  5. Evaluating Persistent Memory Range Indexes: Part TwoYuliang He, Duo Lu, Kaisong Huang, Tianzheng WangVLDB 2022 · 26 citations
Dusk over the sea between two cliffs drawn in fine vertical lines