4.2. CLASSIFICATION-BASED POLICIES 27
is aggressive and favors bypassing, and the second policy is conservative and favors caching.
Leeway uses Set Dueling [Qureshi et al., 2007] to choose between the two policies.
4.1.2 REUSE DISTANCE ORDERING
Keramidas et al. [2007] use reuse distance predictions to instead evict the line that is expected
to be reused furthest in the future. eir policy learns a reuse distance for each load instruction
(PC) and for each incoming line, it computes an estimated time of access (ETA), which is the
sum of the current time and the expected reuse interval. It then orders lines based on their ETA
and evicts the line with the largest ETA value.
To guard against cases where an ETA prediction is unavailable, this scheme also tracks
the line’s decay, which is an estimate of the amount of time that a line has remained unaccessed
in the cache, and it evicts a line if its decay interval is larger than its ETA.
More concretely, Figure 4.1 shows that the replacement policy has two candidates: (1) the
line with the largest ETA (the ETA line), and (2) the line with the largest Decay time (the LRU
line). e line with the largest of the two values is selected for eviction. us, the policy relies
on ETA when available and reverts to LRU otherwise.
case 1:
replacement = ETA
case 2:
replacement = LRU
t
decay
t
decay
Decay ETA
(distance to
next access)
past future
past future
time
clock
clock
Decay (LRU) ETA
Arrival of
a new miss
Figure 4.1: e ETA policy chooses between the line with the longest ETA or the one with the
largest decay; based on [Keramidas et al., 2007].
4.2 CLASSIFICATION-BASED POLICIES
Classification-based policies learn a binary classification of incoming lines: is a cache access likely
to result in a future hit or not? Cache-friendly lines—lines that are expected to result in cache
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.