PaperlayerView exact revision on arXiv

Source-linked AI summary

An Imitation Learning Approach for Cache Replacement

Evan Zheran Liu, Milad Hashemi, Kevin Swersky, Parthasarathy Ranganathan, Junwhan Ahn

arXiv:2006.16239v2cs.LGcs.ARstat.ML

TL;DR

Cache replacement matters because cache hits are much faster than misses, yet choosing what to evict requires planning far ahead. PARROT imitates Belady’s optimal policy using only past accesses. It reports gains over evaluated baselines on CPU and web-search workloads, including a 61% web-search cache-hit-rate improvement over LRU.

  • Problem

    Cache replacement must choose which line to evict, but effective decisions require looking ahead across future accesses.

    Source: §1 · p. 1

  • Method

    PARROT uses imitation learning to train a policy conditioned on past accesses to approximate Belady’s future-informed eviction decisions.

    Source: §1 · p. 2

  • Results

    PARROT exceeds the state-of-the-art replacement policy’s hit rates on memory-intensive CPU benchmarks and improves web-search cache hit rates by 61% over LRU.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The released Gym environment frames cache replacement as a research benchmark with plentiful data and significant real-world impact.

    Source: §7 · p. 9

    The work does not explore production deployment, where policy memory and latency overheads remain concerns.

    Source: §7 · p. 9

Abstract

from arXiv · show

Program execution speed critically depends on increasing cache hits, as cache hits are orders of magnitude faster than misses. To increase cache hits, we focus on the problem of cache replacement: choosing which cache line to evict upon inserting a new line. This is challenging because it requires planning far ahead and currently there is no known practical solution. As a result, current replacement policies typically resort to heuristics designed for specific common access patterns, which fail on more diverse and complex access patterns. In contrast, we propose an imitation learning approach to automatically learn cache access patterns by leveraging Belady's, an oracle policy that computes the optimal eviction decision given the future cache accesses. While directly applying Belady's is infeasible since the future is unknown, we train a policy conditioned only on past accesses that accurately approximates Belady's even on diverse and complex access patterns, and call this approach Parrot. When evaluated on 13 of the most memory-intensive SPEC applications, Parrot increases cache miss rates by 20% over the current state of the art. In addition, on a large-scale web search benchmark, Parrot increases cache hit rates by 61% over a conventional LRU policy. We release a Gym environment to facilitate research in this area, as data is plentiful, and further advancements can have significant real-world impact.

1. Introduction

Cache replacement is a consequential eviction problem for which common heuristics cover only a narrow range of access patterns. PARROT uses imitation learning to approximate Belady’s from past accesses, with reported gains on CPU benchmarks and web search.

1. Introduction

  • Cache hits are orders of magnitude faster than misses, while simply increasing cache sizes is generally prohibitively expensive.Source: §1 · p. 1
  • Prior heuristics target common access patterns but perform poorly on programs with more diverse and complex patterns.Source: §1 · p. 2
  • PARROT learns a past-access-conditioned replacement policy by imitating Belady’s, an oracle that computes optimal evictions using future accesses.Source: §1 · p. 2
  • PARROT exceeds the state-of-the-art replacement policy’s hit rates by over 20% on memory-intensive CPU benchmarks and improves web-search cache hit rates by 61% over LRU.Source: §1 · p. 2
  • The paper frames cache replacement as an imitation-learning benchmark and releases a Gym environment for further research.Source: §1 · p. 2

2. Cache Preliminaries

A cache holds part of a larger memory so data can be accessed faster. In CPU caches, replacement chooses which resident line to evict when a full set needs space for a missed line.

2. Cache Preliminaries

  • CPU caches use cache lines, typically 64 bytes, as the minimum granularity of data access.Source: §2 · p. 2
  • A W-way set-associative cache has N sets, each holding W lines, and each line maps to one set.Source: §2 · p. 2
  • A cache hit occurs when requested data is cached; a miss requires retrieval from larger memory and may require evicting a line from a full set.Source: §2 · p. 2
  • Belady’s uses future reuse distances and evicts the line whose next access is furthest away.Source: §2 · p. 3

3. Casting Cache Replacement as Imitation Learning

The paper formulates cache replacement as an episodic Markov decision process and trains a policy to imitate Belady’s using past accesses rather than future ones. The formulation highlights how much future information a constrained oracle needs to approach Belady’s performance.

3. Casting Cache Replacement as Imitation Learning

  • The state includes the current access, the cache lines in its set, and the history of past accesses; in practice, the policy conditions on the past H accesses.Source: §3 · p. 3
  • On misses the policy chooses a resident line to evict, while hits use a no-op; rewards are 1 for hits and 0 for misses.Source: §3 · p. 3
  • 80% of Belady’s infinite-window performance requires accurately computing reuse distances 2,600 accesses into the future.Source: Figure 2 · p. 3
  • The imitation-learning setup uses past cache accesses to train a policy that approximates Belady’s future-informed optimal policy at test time.Source: §3 · p. 3
  • A constrained Belady oracle observes exact reuse distances within its future window and assigns infinity beyond it; substantial future information is needed to match Belady’s performance.Source: §3 · p. 3

4. PARROT: Learning to Imitate Belady’s

PARROT learns cache replacement by imitating Belady’s oracle while conditioning on past accesses. The section describes its sequence model, training strategy, ranking objective, auxiliary reuse-distance task, and a smaller byte-based embedder.

4.1. Model and Training Overview

  • PARROT embeds each access, uses an LSTM and attention over past hidden states to score cached lines, then selects the line with the highest eviction probability.Training collects states and updates the policy to match Belady’s decisions on them.Source: §4.1 · p. 4

4.2. Avoiding Compounding Errors

  • DAgger collects training states under the learned policy to address compounding errors, periodically refreshing them every 5000 parameter updates.The first state collection follows the oracle because the initial learned policy is random.Source: §4.2 · p. 4

4.3. Ranking Loss

  • PARROT’s ranking loss uses reuse distance to supervise eviction rankings, penalizing probability on low-reuse-distance lines more heavily than on higher-distance lines.It leverages the oracle’s action distribution for more supervision than a simple log-likelihood behavior-cloning loss.Source: §4.3 · p. 5

4.4. Predicting Reuse Distance

  • A shared auxiliary head predicts each cache line’s log-reuse distance with mean-squared error, providing additional supervision through the shared network body.The paper’s stated intuition is that this task helps learn better representations in the rest of the network.Source: §4.4 · p. 5

4.5. Towards Practicality

  • A shared byte embedder reduces address-embedding storage to several kilobytes, though the paper frames direct Belady imitation as proof-of-concept and notes real-world use requires lower model size and latency.The full-sized model’s address embeddings can require tens of megabytes for programs with hundreds of thousands of unique addresses.Source: §4.5 · p. 5

5. Experiments

Across SPEC2006 and Web Search, PARROT improves cache-hit performance against established replacement policies, including Glider and LRU. Ablations show gains from reuse-distance prediction, on-policy training, and ranking loss, while performance gains from longer histories level off around 80 accesses.

5.1. Experimental Setup

  • Experiments test SPEC CPU2006 and Google Web Search at the last-level cache, compare PARROT variants with Glider, LRU, Belady’s, and nearest neighbors, and report raw and normalized hit rates.The study uses three cache levels, samples 64 sets for training data, and divides each sequence into 80% training, 10% validation, and 10% test.Source: §5.1 · pp. 5–6

5.2. Main Results

  • On Web Search, PARROT achieves a 61% higher normalized cache hit rate and 13.5% higher raw cache hit rate than LRU.The byte-embedder model averages 8% higher normalized cache hit rate than Glider; PARROT also maintains high hit rates on complex paths and unseen addresses.Source: §5.2 · pp. 6–7
  • 20% higher normalized cache hit rate on average than Glider across SPEC2006; PARROT beats Glider on 10 of 13 programs.Glider performs marginally better on the other three programs; Table 1 reports PARROT's average raw cache hit rate as 16% higher than LRU.Source: §5.2 · p. 6, Figure 5 · p. 7, Table 1 · p. 7

5.3. Ablations

  • Reuse-distance prediction raises normalized cache hit rates 16.8% over its ablation; auxiliary prediction outperforms using predicted distance directly for eviction.The authors hypothesize that ranking lines may be easier than accurately predicting each line’s reuse distance.Source: Figure 6 · p. 7, §5.3 · p. 7
  • On-policy training with DAgger improves normalized cache hit rate by 9.8% on average over off-policy training, though results vary by program.Off-policy training performs as well or better on mcf and Web Search, while on-policy training is crucial for some other programs.Source: Figure 7 · p. 8, §5.3 · p. 8
  • The ranking loss improves normalized cache hit rate by 3.5% on average over log-likelihood loss.It more heavily penalizes evicting lines with lower reuse distances, which lead to misses.Source: Figure 8 · p. 8, §5.3 · p. 8

5.4. History Length

  • Normalized cache hit rates improve as history grows through H=80, then additional accesses have little impact; Glider saturates around 30 accesses.The authors suggest end-to-end policy learning can leverage more past information than predicting whether a line is cache-friendly or cache-averse.Source: Figure 9 · p. 8, §5.4 · p. 8

6. Related Work

Prior cache-learning methods restrict eviction choices through heuristics or coarse classifications, while PARROT learns end-to-end with imitation learning. The paper’s imitation-learning setting also offers unusually direct access to its expert oracle and action distribution.

6. Related Work

  • Prior replacement methods use manually designed heuristics for selected access patterns, including recency and reuse-based rules.The cited examples include LRU and approaches based on counters or predicted zero-reuse instructions.Source: §6 · p. 8
  • Hawkeye and Glider classify lines as cache-friendly or cache-averse, then rely on a traditional heuristic to choose which line to evict.That reliance constrains their learnable policy class and can yield high miss rates for some access patterns.Source: §6 · p. 8
  • End-to-end imitation learning lets PARROT optimize over a highly expressive policy class, unlike prior methods that rely on a heuristic for final eviction decisions.The authors state that this enables high cache hit rates on complex and diverse access patterns.Source: §6 · pp. 8–9
  • PARROT’s imitation-learning expert, Belady’s, can be queried at any training state, and its action distribution is available for richer loss functions.The authors say arbitrary oracle queries let them avoid DAgger to address compounding errors.Source: §6 · p. 9

7. Conclusion and Future Directions

The paper establishes end-to-end imitation learning as a foundation for cache replacement and releases a Gym environment for further research. It identifies deployment costs and the lack of an optimal multi-level-cache policy as open boundaries.

7. Conclusion and Future Directions

  • The authors present end-to-end imitation learning as a foundation that bridges prior work and Belady’s, and say the approach can apply beyond CPU caches.They identify software caches as promising because they tolerate higher replacement latency and are easier to implement with complex policies.Source: §7 · p. 9
  • The work does not evaluate production deployment practicality, particularly the learned policy’s memory and latency overheads.The authors suggest model-size reduction and domains that tolerate greater latency and memory use as future directions.Source: §7 · p. 9
  • Belady’s is optimal for a single-level cache, but no optimal policy is known for multi-level caches common in CPUs and web services.The paper identifies hierarchical replacement as a research direction.Source: §7 · p. 9
  • The released Gym environment extends to hierarchical replacement, where reinforcement learning is needed because the optimal policy is unknown.The paper highlights delayed rewards, state-dependent action semantics, large address spaces, and diverse program access patterns as challenges.Source: §7 · p. 9
  • The paper releases code for PARROT and its cache-replacement Gym environment.The code is available in the Google Research repository.Source: §7 · p. 9

A. Architecture Details

The architecture embeds cache lines and past accesses, then uses attention to form a context for each line. Positional embeddings encode how far back accesses occurred, and the resulting line contexts can be computed in parallel.

A. Architecture Details

  • The model is implemented in PyTorch and optimized with Adam.Source: A. Architecture Details · p. 12
  • Memory addresses and cache lines share a trained address embedder, while PCs are embedded similarly; unseen test addresses map to a special UNK embedding.The full-sized model trains unique embeddings for addresses observed during training.Source: A. Architecture Details · p. 12
  • For each cache line, the model attends over hidden states representing the past H accesses to compute a line-specific context.The line embeddings serve as queries, and the hidden states concatenated with positional embeddings serve as keys.Source: A. Architecture Details · p. 12
  • Positional embeddings are concatenated with LSTM hidden states to encode each access’s distance in the past; the authors found this helped optimization.The learned attention matrix maps the concatenated hidden states and positional embeddings, and line contexts can be computed in parallel.Source: A. Architecture Details · p. 12

B.1. Detailed Results

The detailed results compare PARROT’s eviction decisions with Belady’s and show that agreement and the significance of decision errors vary across programs. Similar hit rates can accompany different accuracy and reuse-distance-gap patterns.

B.1. Detailed Results

  • The study reports top-1 and top-5 accuracy and reuse distance gap as additional metrics for examining PARROT’s decisions.Source: §B.1 · p. 12
  • Top-1 and top-5 accuracy measure whether Belady’s optimal eviction is among PARROT’s highest-probability choices; reuse distance gap measures the difference in reuse distance.Table 2 reports mean top-1/5 accuracy and reuse distance gap, averaged over three seeds with single standard deviation intervals.Source: §B.1 · p. 12, Table 2 · p. 13
  • Over 75% top-1 accuracy and close to 100% top-5 accuracy occur in mcf, libquantum, and lbm, while other programs can have lower accuracy despite similar normalized hit rates.The authors caution that top-K accuracy is imperfect because several lines may have reuse distances close to the optimal line’s.Source: §B.1 · p. 12
  • A reuse distance gap of hundreds of accesses can occur in omnetpp without a miss, while slightly earlier eviction more often causes misses in mcf.The passage relates this difference to program access patterns despite similar normalized and raw cache hit rates.Source: §B.1 · pp. 12–13

B.2. Hyperparameters

The final experiments used shared hyperparameter values across programs, with selected parameters tuned exclusively on omnetpp’s validation set. History length was varied separately in its dedicated experiments.

B.2. Hyperparameters

  • The same hyperparameter values were used across all final experiments and five evaluated programs, except that history length varied in its dedicated experiments.The programs were omnetpp, mcf, libq, lbm, and Web Search.Source: §B.2 · p. 13
  • The reported configuration includes learning rate and recollection-frequency choices, embedding dimensions and vocabulary size, LSTM hidden size, and seven tested history lengths.The listed history lengths are 20, 40, 60, 80, 100, 120, and 140.Source: §B.2 · p. 13
  • Hyperparameters tuned for the experiments were selected exclusively using the omnetpp validation set.Most parameters were set to reasonable values without further changes.Source: §B.2 · p. 13

B.3. Program Details

Program details document cache-access counts and unique address and PC coverage across train and test splits. Some test-time addresses and PCs were unseen in training, and data came from 64 randomly selected last-level cache sets.

B.3. Program Details

  • Some programs contain test-time addresses and PCs absent from training, requiring the replacement policy to generalize to unseen inputs.Table 3 reports unseen address and PC counts and the share of test accesses associated with them.Source: §B.3 · p. 13, Table 3 · p. 14
  • Each program’s last-level cache accesses were collected over 50 seconds and split into 80% training, 10% validation, and 10% test data.Access totals varied because programs differed in L1 and L2 cacheability, reflecting different program behaviors.Source: §B.3 · p. 13

B.4. Randomly Chosen Cache Sets

  • The evaluation collected last-level cache accesses from 64 randomly chosen cache sets.The selected set identifiers are listed in the passage.Source: §B.4 · p. 13

Related papers

Loading 2006.16239v2…