Managing Static (Leakage) Power - Computer Architecture Techniques for Power-Efficiency - page 142

Access Interval M : Miss H : Hit

M HH H H H M

Live time Dead time TIME

NEW Last

Access

NEW

Generation Generation

1.0

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.0

FIGURE 5.4: Generational behavior of cache lines (top). Dead time as a percentage of total time in the
cache. Reproduced from [ 127 ]. Copyright 2001 IEEE.

data, and the reason why unknown references in trace sampling have a very high miss rate, is
that (on average) the dead time of cache lines by far exceeds their live time . 7 Adaptedfrom[ 127 ]
the graph in Figure 5.4 shows that total dead time (for all cache lines) accounts for about 80%
of the total time, on average, for the SPEC2000 benchmarks. This fundamental characteristic
is exactly what cache decay tries to exploit.
Cache decay tries to guess whether a cache line is live at any particular point in time. It
does this by measuring elapsed time since the last access to the cache line. Since the cache line
is accessed only during its live time—which is typically short—it follows that the inter-access
time between two consecutive accesses should be particularly short. It is easy then to guess
when a cache line is not in its live time: if sufficient time has passed without an intervening
access then most likely the cache line has entered its dead time and awaits eviction.
This approach is supported by data showing that the distribution of the inter-access
time intervals, measured in cycles , is—for all practical purposes— bimodal . Figure 5.5 shows
the distributions for three of the SPEC2000 benchmarks, gcc, compress, and vortex. The
vast majority of the inter-access times are clustered around very small values (few hundreds
of cycles or less), while a single cumulative bar at the far right represents the very large
inter-access intervals. The middle parts of the graphs are practically empty. Similar inter-access
time distributions are typical for many programs.

7 So, for a number of unknown references, starting at a random point in the trace, it is unlikely to catch most of
them in their live time. It follows that the majority will be cold misses!