Information Technology Reference
In-Depth Information
ated in practice with a bit of work when creating
specialized algorithms. A prime example of this
approach is the EELRU algorithm, which we dis-
cuss next. EELRU (for “Early-Eviction LRU”) is
a well-known adaptive algorithm in the research
literature, with performance that matches LRU for
LRU-friendly workloads and significantly beats
LRU in several other instances.
A high-level version of the EELRU logic is:
well the behavior of a program that has a loop
touching i distinct pages.
If we know the histogram that best describes
the probabilities of program accesses, then we can
compute an optimal replacement algorithm for
this program (Wood, Fernandez, & Lang, 1983).
Specifically, if we pick two points e and l (for
“early” and “late” eviction point, respectively)
in the recency axis, with e less than and l greater
than the memory size, m, then the Wood et al.
technique yields a replacement algorithm that has
a hit ratio (i.e., proportion of accesses that are in
memory) of H(0,e) + (m - e)/(l - e) ∙ H(e,l), where
H(x,y), for x < y, is the probability that the page
accessed is among the y most recently accessed
but not among the x most recently accessed—i.e.,
H(x,y) is the sum of h(x+1), h(x+2), …, h(y).
EELRU is now simple to understand as an
algorithm adapting over a large number of com-
ponent algorithms that each pick a specific e and l
position. EELRU keeps a histogram of all program
accesses in the recent past, ordered by recency. For
each position i, the histogram records how many
recent hits were to the i-th most recently accessed
page. In this way, this past-behavior-histogram
can be used as the probability histogram h(i) of
future references. Based on the assumption that
the future will look like the past, recency-wise,
EELRU tries all its available combinations of e
and l points in the histogram and picks the one
that maximizes the sum H(0,e) + (m - e)/(l - e)
∙ H(e,l). In the case that the maximum value is
H(0,m), LRU is the best algorithm.
To reword this in terms of an ART, EELRU
keeps a window of k past misses and it checks (for
the program accesses during that time) whether the
algorithm that would have performed best is plain
LRU or any “early eviction” algorithm for a given
e and l value. (We slightly simplify the EELRU
logic, but not in important ways.) This is akin to
a (multiple) instantiation of an adaptive replace-
ment template ART
k
, which is much like ART
∞
,
but with only the last k misses taken into account.
If we view EELRU as a multiple instantiation of
•
Perform
LRU replacement unless many
references are to pages that were only re-
cently evicted.
If many references are to pages recently
•
evicted, enable “early evictions”: Pick an
optimal point e in the recency space and
evict the e-th most recently accessed page.
This informal strategy is clearly adaptive,
in the intuitive sense. EELRU is effectively
checking whether LRU performs well, and, if
not, it emulates an MRU-like algorithm. To be
more precise, the MRU-like algorithms belong
in a family of algorithms developed for a model
of program behavior called the “LRU stack
model”. The LRU stack model assumes that
programs behave as random processes with no
memory, but the random variable is not which
page address they access, but which page they
access in the
recency
(also called
reuse-distance
)
space. In this way, a program is modeled by a
histogram of probabilities, h(i), indicating how
likely it is for the program to next reference the
i-th most recently accessed page. That is, the
program's memory accesses are assumed to be
independent random actions, where on each
step of the execution the program randomly
decides on a number i, with probability h(i), and
then accesses the i-th most recently accessed
page (at the current moment). If we assume
that program locality is primarily determined
by loops, the LRU stack model is an excellent
model of program behavior, since a histogram
with a high probability for a certain i reflects
Search WWH ::
Custom Search