  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.
