26 4. FINE-GRAINED REPLACEMENT POLICIES
We now discuss the different classes of Fine-Grained policies.
4.1 REUSE DISTANCE PREDICTION POLICIES
Policies based on reuse distance estimate the reuse distance of blocks, where reuse distance can be
defined in terms of the number of accesses or cycles between consecutive references to a block.
e perfect prediction of reuse distances would be sufficient to emulate Belady’s optimal solution,
but it is difficult to precisely predict reuse distances due to the high variation in reuse distance
values. erefore, realistic solutions estimate reuse distance distributions or other aggregate reuse
distance statistics.
4.1.1 EXPIRATION-BASED DEAD BLOCK PREDICTORS
Many dead block predictors use past evictions to estimate average reuse distance statistics, and
they evict lines that are not reused within their expected reuse distances [Abella et al., 2005,
Faldu and Grot, 2017, Hu et al., 2002, Kharbutli and Solihin, 2005, Liu et al., 2008, Takagi
and Hiraki, 2004].
Hu et al. learn the live time of cache blocks, where the live time is defined as the number of
cycles a block remains live in the cache [Hu et al., 2002]. When a block is inserted, its lifetime
is predicted to be similar to its last lifetime. If the block has stayed in the cache for twice its
lifetime without receiving a cache hit, the block is declared to be dead and is evicted from the
cache.
Abella et al., use a similar dead block prediction strategy to turn off L2 cache lines, but
instead of using the number of cycles, they define reuse distance in terms of the number of cache
accesses between consecutive references [Abella et al., 2005].
Kharbutli and Solihin [2005] use counters to track each cache line’s Access Interval, where
a line’s Access Interval is defined to be the number of other cache lines that were accessed be-
tween subsequent accesses to the line. Furthermore, they predict that a line is dead if its access
interval exceeds a certain threshold. e threshold is predicted by the access interval predictor
(AIP), which tracks the access intervals of all past evictions and remembers the maximum of all
such intervals in a PC-based table.
Faldu and Grot [2017] present the Leeway policy, which uses the notion of live distance—
the largest observed stack distance in a cache line’s lifetime—to identify dead blocks. A cache
block’s live distance is learned from the block’s previous generations, and when a block exceeds
its live distance, it is predicted to be dead. e live distances from past lifetimes are remembered
using a per-PC live distance predictor table (LDPT). e LDPT predicts live distances for
incoming blocks, and any block that has moved past its predicted live distance in an LRU stack
is predicted dead. To avoid the high variability in live distances across lifetimes and across blocks
accessed by the same PC, Leeway deploys two update policies that control the rate at which live
distance values in the LDPT are adjusted based on workload characteristics. e first policy
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.