  Memory-intensive workloads operate on massive amounts of data that cannot be
captured by last-level caches (LLCs) of modern processors. Consequently,
processors encounter frequent off-chip misses, and hence, lose a significant
performance potential. One way to reduce the number of off-chip misses is
through using a well-behaved replacement policy in the LLC. Existing processors
employ a variation of least recently used (LRU) policy to determine a victim
for replacement. Unfortunately, there is a large gap between what LRU offers
and that of Belady's MIN, which is the optimal replacement policy. Belady's MIN
requires selecting a victim with the longest reuse distance, and hence, is
unfeasible due to the need to know the future. Consequently, Belady-inspired
replacement polices use Belady's MIN to derive an indicator to help them choose
a victim for replacement.
  In this work, we show that the indicator that is used in the state-of-the-art
Belady-inspired replacement policy is not decisive in picking a victim in a
considerable number of cases, and hence, the policy has to rely on a standard
metric (e.g., recency or frequency) to pick a victim, which is inefficient. We
observe that there exist strong correlations among the hit counts of cache
blocks in the same region of memory when Belady's MIN is the replacement
policy. Taking advantage of this observation, we propose an expected-hit-count
indicator for the memory regions and use it to improve the victim selection
mechanism of Belady-inspired replacement policies when the main indicator is
not decisive. Our proposal offers a 5.2\% performance improvement over the
baseline LRU and outperforms Hawkeye, which is the state-of-the-art replacement
policy.
