Abstract
Program execution speed critically depends on increasing cache hits, as cachehits are orders of magnitude faster than misses. To increase cache hits, wefocus on the problem of cache replacement: choosing which cache line to evictupon inserting a new line. This is challenging because it requires planning farahead and currently there is no known practical solution. As a result, currentreplacement policies typically resort to heuristics designed for specificcommon access patterns, which fail on more diverse and complex access patterns.In contrast, we propose an imitation learning approach to automatically learncache access patterns by leveraging Belady's, an oracle policy that computesthe optimal eviction decision given the future cache accesses. While directlyapplying Belady's is infeasible since the future is unknown, we train a policyconditioned only on past accesses that accurately approximates Belady's even ondiverse and complex access patterns, and call this approach Parrot. Whenevaluated on 13 of the most memory-intensive SPEC applications, Parrotincreases cache miss rates by 20% over the current state of the art. Inaddition, on a large-scale web search benchmark, Parrot increases cache hitrates by 61% over a conventional LRU policy. We release a Gym environment tofacilitate research in this area, as data is plentiful, and furtheradvancements can have significant real-world impact.