[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

LRU stack processing

Published: 01 July 1975 Publication History

Abstract

Stack processing, and in particular stack processing for the least recently used replacement algorithms, may present computational problems when it is applied to a sequence of page references with many different pages. This paper describes a new technique for LRU stack processing that permits efficient processing of these sequences. An analysis of the algorithm and a comparison of its running times with those of the conventional stack processing algorithms are presented. Finally we discuss a multipass implementation, which was found necessary to process trace data from a large data base system.

References

[1]
R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger, "Evaluation Techniques for Storage Hierarchies," IBM Syst. J. 9, (1970).
[2]
I. L. Traiger and D. R. Slutz. "One-Pass Technique for the Evaluation of Memory Hierarchies," Research Report RJ 892, IBM Research Laboratory, San Jose, CA, July 28, 1971.
[3]
Private communication from H. Hempy of the IBM General Products Division Laboratory, Boulder, CO.
[4]
D. E. Knuth, Sorting and Searching; The Art of Computer Programming, Vol. 3, Addison-Wesley Publishing Co., Reading, MA, 1973.
[5]
D. E. Knuth, Fundamental Algorithms. The Art of Computer Programming, Vol. 1, Addison-Wesley Publishing Co., Inc., Reading, MA, 1968.

Cited By

View all
  • (2024)KosmoProceedings of the 22nd USENIX Conference on File and Storage Technologies10.5555/3650697.3650703(89-106)Online publication date: 27-Feb-2024
  • (2024)TTLs Matter: Efficient Cache Sizing with TTL-Aware Miss Ratio Curves and Working Set SizesProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650066(387-404)Online publication date: 22-Apr-2024
  • (2023)Increment - and - Freeze: Every Cache, Everywhere, All of the TimeProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591085(129-139)Online publication date: 17-Jun-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IBM Journal of Research and Development
IBM Journal of Research and Development  Volume 19, Issue 4
July 1975
91 pages

Publisher

IBM Corp.

United States

Publication History

Published: 01 July 1975
Revised: 10 March 1975
Received: 06 September 1974

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)KosmoProceedings of the 22nd USENIX Conference on File and Storage Technologies10.5555/3650697.3650703(89-106)Online publication date: 27-Feb-2024
  • (2024)TTLs Matter: Efficient Cache Sizing with TTL-Aware Miss Ratio Curves and Working Set SizesProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650066(387-404)Online publication date: 22-Apr-2024
  • (2023)Increment - and - Freeze: Every Cache, Everywhere, All of the TimeProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591085(129-139)Online publication date: 17-Jun-2023
  • (2021)Online Working Set Change Detection with Constant ComplexityProceedings of the International Symposium on Memory Systems10.1145/3488423.3519332(1-16)Online publication date: 27-Sep-2021
  • (2020)OSCAProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489200(785-798)Online publication date: 15-Jul-2020
  • (2020)A Locality Optimizer for Loop-dominated Applications Based on Reuse Distance AnalysisACM Transactions on Design Automation of Electronic Systems10.1145/339818925:6(1-26)Online publication date: 2-Sep-2020
  • (2020)PG2S+: Stack Distance Construction Using Popularity, Gap and Machine LearningProceedings of The Web Conference 202010.1145/3366423.3380176(973-983)Online publication date: 20-Apr-2020
  • (2020)MocktailsProceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture10.1109/ISCA45697.2020.00046(460-472)Online publication date: 30-May-2020
  • (2019)Directed Statistical Warming through Time TravelingProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358264(1037-1049)Online publication date: 12-Oct-2019
  • (2019)A fast analytical model of fully associative cachesProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314606(816-829)Online publication date: 8-Jun-2019
  • Show More Cited By

View Options

View options

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media