article

The EELRU adaptive replacement algorithm

Authors:

Yannis Smaragdakis,

Paul WilsonAuthors Info & Claims

Performance Evaluation, Volume 53, Issue 2

Pages 93 - 123

https://doi.org/10.1016/S0166-5316(02)00226-2

Published: 01 July 2003 Publication History

Abstract

The wide performance gap between processors and disks ensures that effective page replacement remains an important consideration in modern systems. This paper presents early eviction LRU (EELRU), an adaptive replacement algorithm. EELRU uses aggregate recency information to recognize the reference behavior of a workload and to adjust its speed of adaptation. An on-line cost/benefit analysis guides replacement decisions. This analysis is based on the LRU stack model (LRUSM) of program behavior. Essentially, EELRU is an on-line approximation of an optimal algorithm for the LRUSM. We prove that EELRU offers strong theoretical guarantees of performance relative to the LRU replacement algorithm. EELRU can never be more than a factor of 3 worse than LRU, while in a common best case it can be better than LRU by a large factor (proportional to the number of pages in memory).The goal of EELRU is to provide a simple replacement algorithm that adapts to reference patterns at all scales. Thus, EELRU should perform well for a wider range of programs and memory sizes than other algorithms. Practical experiments validate this claim. For a large number of programs and wide ranges of memory sizes, we show that EELRU outperforms LRU, typically reducing misses by 10-30%, and occasionally by much more--sometimes by a factor of 2-10. It rarely performs worse than LRU, and then only by a small amount.

References

[1]

{1} A.V. Aho, P.J. Denning, J.D. Ullman, Principles of optimal page replacement, J. ACM 18 (1971) 80-93.

Digital Library

[2]

{2} O. Babaoglu, D. Ferrari, Two-level replacement decisions in paging stores, IEEE Trans. Comput. 32 (12) 1983.

Digital Library

[3]

{3} M.H.J. Baylis, D.G. Fletcher, D.J. Howarth, Paging studies made on the ICT ATLAS computer, in: Information Processing, IFIP Congress Booklet, vol. D, 1968.

[4]

{4} P.J. Courtois, H. Vantilborgh, A decomposable model of program paging behavior, Acta Inform. 6 (1976) 251-275.

Digital Library

[5]

{5} P.J. Denning, Working sets past and present, IEEE Trans. Software Eng. 6 (1) (1980) 64-84.

Digital Library

[6]

{6} E.B. Fernandez, T. Lang, C. Wood, Effect of replacement algorithms on a paged buffer database system, IBM J. Res. Dev. 22 (2) (1978) 185-196.

Digital Library

[7]

{7} M.A. Franklin, R.K. Gupta, Computation of pf probabilities from program transition diagrams, Commun. ACM 17 (1974) 186-191.

Digital Library

[8]

{8} G. Glass, P. Cao, Adaptive page replacement based on memory reference behavior, in: Proceedings of ACM SIGMETRICS'97, 1997.

Digital Library

[9]

{9} S. Jiang, X. Zhang, LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance, in: Proceedings of ACM SIGMETRICS'02, 2002.

[10]

{10} A.R. Karlin, S.J. Phillips, P. Raghavan, Markov paging, in: Proceedings of the IEEE Symposium on the Foundations of Computer Science, FOCS, 1992, pp. 208-217.

[11]

{11} D.C. Lee, P.J. Crowley, J.L. Baer, T.E. Anderson, B.N. Bershad, Execution characteristics of desktop applications on windows NT, in: Proceedings of the International Symposium on Computer Architecture (ISCA)'98, 1998.

[12]

{12} R.L. Mattson, J. Gecsei, D.R. Slutz, I.L. Traiger, Evaluation techniques for storage hierarchies, IBM Syst. J. 9 (1970) 78-117.

Digital Library

[13]

{13} H. Muramatsu, H. Negishi, Page replacement algorithm for large-array manipulation, Software Practice Experience 10 (1980) 575-587.

[14]

{14} V. Phalke, Modeling and managing program references in a memory hierarchy, Ph.D. Dissertation, Rutgers University, 1995.

[15]

{15} D.D. Sleator, R.E. Tarjan, Amortized efficiency of list update and paging rules, Commun. ACM 28 (2) (1985) 202-208.

Digital Library

[16]

{16} Y. Smaragdakis, S.F. Kaplan, P. Wilson, EELRU: simple and effective adaptive page replacement, in: Proceedings of ACM SIGMETRICS'99, 1999.

[17]

{17} Y. Smaragdakis, P. Wilson, Performing replacement in modem pools, in: Proceedings of the 2000 USENIX Annual Technical Conference.

[18]

{18} J.R. Spirn, Distance string models for program behavior, Computer 9 (1976) 14-20.

Digital Library

[19]

{19} E. Torng, A unified analysis of paging and caching, Algorithmica 20 (1998) 175-200.

[20]

{20} R. Turner, H. Levy, Segmented FIFO page replacement, in: Proceedings of ACM SIGMETRICS'81, 1981.

Digital Library

[21]

{21} P.R. Wilson, S. Kakkad, S.S. Mukherjee, Anomalies and adaptation in the analysis and development of prefetching policies, J. Syst. Software 27 (2) (1994) 147-153.

[22]

{22} C. Wood, E.B. Fernandez, T. Lang, Minimization of demand paging for the LRU stack model of program behavior, Inform. Process. Lett. 16 (1983) 99-104.

Cited By

Tan JZhang TLi FChen JZheng QZhang PQiao HShi YCao WZhang R(2019)iBTuneProceedings of the VLDB Endowment10.14778/3339490.333950312:10(1221-1234)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.14778/3339490.3339503
Waldspurger CPark NGarthwaite AAhmad ISchindler JZadok E(2015)Efficient MRC construction with SHARDSProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750490(95-110)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.5555/2750482.2750490
Olorode ONourani M(2015)Improving Performance in Sub-Block Caches with Optimized Replacement PoliciesACM Journal on Emerging Technologies in Computing Systems10.1145/266812711:4(1-22)Online publication date: 27-Apr-2015
https://dl.acm.org/doi/10.1145/2668127
Show More Cited By

Index Terms

The EELRU adaptive replacement algorithm
1. Hardware
  1. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

General adaptive replacement policies
ISMM '04: Proceedings of the 4th international symposium on Memory management

We propose a general scheme for creating adaptive replacement policies with good performance and strong theoretical guarantees. Specifically, we show how to combine any two existing replacement policies so that the resulting policy provably can never ...
Approximating the optimal replacement algorithm
CF '04: Proceedings of the 1st conference on Computing frontiers

LRU is the de facto standard page replacement strategy. It is well-known, however, that there are many situations where LRU behaves far from optimal. We present a replacement policy that approximates the optimal algorithm OPT more closely by predicting ...
Page Size Aware Cache Prefetching
MICRO '22: Proceedings of the 55th Annual IEEE/ACM International Symposium on Microarchitecture

The increase in working set sizes of contemporary applications outpaces the growth in cache sizes, resulting in frequent main memory accesses that deteriorate system performance due to the disparity between processor and memory speeds. Prefetching ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Performance Evaluation

Performance Evaluation Volume 53, Issue 2

July 2003

67 pages

ISSN:0166-5316

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 July 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tan JZhang TLi FChen JZheng QZhang PQiao HShi YCao WZhang R(2019)iBTuneProceedings of the VLDB Endowment10.14778/3339490.333950312:10(1221-1234)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.14778/3339490.3339503
Waldspurger CPark NGarthwaite AAhmad ISchindler JZadok E(2015)Efficient MRC construction with SHARDSProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750490(95-110)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.5555/2750482.2750490
Olorode ONourani M(2015)Improving Performance in Sub-Block Caches with Optimized Replacement PoliciesACM Journal on Emerging Technologies in Computing Systems10.1145/266812711:4(1-22)Online publication date: 27-Apr-2015
https://dl.acm.org/doi/10.1145/2668127
Brock JGu XBao BDing C(2013)PacmanACM SIGPLAN Notices10.1145/2555670.246648248:11(39-50)Online publication date: 20-Jun-2013
https://dl.acm.org/doi/10.1145/2555670.2466482
Brock JGu XBao BDing CCheng PPetrank E(2013)PacmanProceedings of the 2013 international symposium on memory management10.1145/2491894.2466482(39-50)Online publication date: 20-Jun-2013
https://dl.acm.org/doi/10.1145/2491894.2466482
Brock JGu XBao BDing CCheng PPetrank E(2013)PacmanProceedings of the 2013 international symposium on memory management10.1145/2464157.2466482(39-50)Online publication date: 20-Jun-2013
https://dl.acm.org/doi/10.1145/2464157.2466482
Moruz GNegoescu A(2012)Outperforming LRU via competitive analysis on parametrized inputs for pagingProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095248(1669-1680)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095248
Gu XDing C(2012)A generalized theory of collaborative cachingACM SIGPLAN Notices10.1145/2426642.225901247:11(109-120)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.1145/2426642.2259012
Gu XDing CVechev MMcKinley K(2012)A generalized theory of collaborative cachingProceedings of the 2012 international symposium on Memory Management10.1145/2258996.2259012(109-120)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.1145/2258996.2259012
Hertz MKane SKeudel EBai TDing CGu XBard J(2011)Waste not, want notACM SIGPLAN Notices10.1145/2076022.199348746:11(65-76)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2076022.1993487
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents