English: Description of the Mockingjay Cache Replacement Algorithm. Described in detail in the paper "Effective Mimicry of Belady’s MIN Policy" By "Ishan Shah", "Akanksha Jain", "Calvin Lin", published in HPCA 2022.

The Sampled Cache stores a history of past accesses to unique addresses, along with the PC and timestamp of the last request, this is only done for a limited number of sets. Once a new access for an address already present arrives, the reuse distance and old PC are sent to train the Reuse Distance Predictor using Temporal Difference Learning. This stores the predicted reuse distances for a cache line given the last PC that accessed it.

The ETR counters store the predicted reuse distance for a given line in all sets, and is updated with every access. All values are decremented with every access.

On a cache miss, the line with the highest absolute ETR in the set is evicted, meaning that we evict the line that is predicted to be reused furthest in the future, or the line that has been predicted to be reused furthest in the past (and hasn't been).