Adaptive Replacement Algorithm Templates and EELRU - Advanced Operating Systems and Kernel Applications - page 274

some programs—nine of them here—for which
EELRU, on average, provides no benefit, and
only five of those incur more than 5% detriment.
Furthermore, for those five programs, the detri-
ment is never more than 10%. In contrast, twelve
of these programs enjoy an improvement of more
than 10%, up to 89%, of the possible improve-
ment over LRU. On balance, EELRU yields a
modest detriment in some cases in exchange for
a substantial improvement for others.
Although Table 1 shows means, you may be
concerned that there are worst cases in which
EELRU performs far worse than LRU. Table
2 shows, for each program, the raw increase in
misses that occurs at the memory size for which
EELRU's performance is worst in comparison
to LRU.
For Table 2, positive values imply more misses
for EELRU than LRU. We first see that, at worst,
the increase in the raw number of misses is only
16.38%. For most programs, the worst case is no
worse than 10%, and for a few programs, the worst
case is either a modest detriment (less than 2%) or
an improvement (up to -8.86%). Even for a poor
combination of application and memory size, the
adaptivity of EELRU avoids substantial harm.

already applied them to different domains, includ-
ing hardware caching.

referenceS

Jiang, S. (2009). Swap Token: Rethink the Appli-
cation of the LRU Principle on Paging to Remove
System Thrashing. In Y. Wiseman & S. Jiang,
(Eds.), The Handbook of Advanced Operating
Systems and Kernel Applications: Techniques and
Technologies . Hershey, PA: IGI Global.

Lee, D., Choi, J., Kim, J.-H., Noh, S. H., Min, S.
L., Cho, Y., & Kim, C. S. (2001). LRFU: A spec-
trum of policies that subsumes the least recently
used and least frequently used policies . IEEE
Transactions on Computers , 50 (12), 1352-1361.
doi:10.1109/TC.2001.970573

Megiddo, N., & Modha, D. S. (2003). ARC: A
self-tuning, low overhead replacement cache.
In Proc. File and Storage Technologies (FAST) .
USENIX Association.

Robertson, J., & Devarakonda, M. (1990). Data
cache management using frequency-based re-
placement. In Proc. SIGMETRICS Conference on
Measurement and Modeling of computer systems .
New York: ACM Press.

concluSion

Smaragdakis, Y. (2004). General Adaptive Re-
placement Policies. Proc. International Sympo-
sium on Memory Management (pp. 108-119). New
York: ACM Press.

We presented the idea of adaptive replacement
algorithms created by instantiating general
“adaptive replacement templates” (ARTs). ARTs
are very attractive because of their generality
and theoretical guarantees regardless of which
algorithms are adapted over. Importantly, ARTs
can lead to specialized, efficient instantiations,
when the algorithm designers understand well
the properties of the component algorithms. We
demonstrated how the EELRU algorithm from
the research literature can be thought of as an
optimized multiple instantiation of an ART, and
its performance in practice. We believe thatARTs,
rather than EELRU itself, are a very promising
idea for future replacement policies, and we have

Smaragdakis, Y., Kaplan, S., & Wilson, P. (2003).
The EELRU Adaptive Replacement Algo-
rithm. Performance Evaluation , 53 (2), 93-123.
doi:10.1016/S0166-5316(02)00226-2

Subramanian, R., Smaragdakis, Y., & Loh, G.
(2006). Adaptive Caches: Effective Shaping of
Cache Behavior to Workloads. In Proc. Interna-
tional Symposium on Microarchitecture (MICRO)
(pp. 385-386). Washington, DC: IEEE Computer
Society.