article

On-line measurement of paging behavior by the multivalued MIN algorithm

Authors:

L. A. Belady,

F. P. PalerrnoAuthors Info & Claims

IBM Journal of Research and Development, Volume 18, Issue 1

Pages 2 - 19

https://doi.org/10.1147/rd.181.0002

Published: 01 January 1974 Publication History

Abstract

An algorithm is presented that extracts the sequence of minimum memory capacities (MMCs) from the sequence of page references generated by a program as it is executed in a demand paging environment. The new algorithm combines the advantages of existing approaches in that the MMC's are produced in a single pass, as is the output of the MIN algorithm for a single memory size, and the MMC sequence is identical to the optimum stack distances provided by the OPT algorithm, which requires two passes.

A hardware implementation is outlined as an extension to existing page management mechanisms. The resulting device could be used to produce continuously the MMC information, while the (paging) machine executes the program at essentially full speed. The paper also discusses the possible impact of the algorithm on the study of program behavior and on the development of space sharing (paging) algorithms. Finally, a proof is provided that the algorithm in fact produces an output identical to that of OPT.

References

[1]

R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger, "Evaluation Techniques for Storage Hierarchies," IBM Systems Journul 9, 2, 78 (1970).

Digital Library

Google Scholar

[2]

P. J. Denning, "Virtual Memory," Computing Surveys 2, 3, 153 (September 1970).

Digital Library

Google Scholar

[3]

L. A. Belady, "A Study of Replacement Algorithms for Virtual Storage Computers," IBM Systems Journal 5, 2, 178 (June 1966).

Digital Library

Google Scholar

[4]

F. R. A. Hopgood, Compiling Techniques, MacDonald, London, 1970, 96-99.

Google Scholar

[5]

D. Gries, Compiler Construction for Digital Computers, John Wiley and Sons, New York, 1972.

Crossref

Google Scholar

[6]

In 1970, J. Gecsei of IBM Systems Development Division, San Jose, developed a one-pass version of OPT yielding the approximate space-time behavior of programs.

Google Scholar

[7]

L. P. Honvitz, R. M. Karp, R. E. Miller, and S. Winograd, "Index Register Allocation," J. ACM 13, 1 (January 1966).

Crossref

Google Scholar

[8]

U. S. Patent 3, 577, 185, "On-line System for Measuring the Efficiency of Replacement Algorithms," issued to L. A. Belady.

Google Scholar

[9]

Sorting Techniques, IBM Data Processing Techniques, Form NR. C20-1639-0, 12-13, IBM Corporation, White Plains, N.Y.

Google Scholar

[10]

W. F. Beausoleil, D. T. Brown, and B. E. Phelps, "Magnetic Bubble Memory Organization," IBM J. Res. Develop. 16, 6, 587 (November 1972).

Google Scholar

Cited By

View all

Bender MDeLayo DKuszmaul BKuszmaul WWest EAgrawal KShun J(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
https://dl.acm.org/doi/10.1145/3558481.3591085
Song SKhan TShahri SSriraman ASoundararajan NSubramoney SJiménez DLitz HKasikci BSalapura VZahran MChong FTang L(2022)ThermometerProceedings of the 49th Annual International Symposium on Computer Architecture10.1145/3470496.3527430(742-756)Online publication date: 18-Jun-2022
https://dl.acm.org/doi/10.1145/3470496.3527430
Díaz JIbáñez PMonreal TViñals VLlabería J(2021)Near-optimal replacement policies for shared caches in multicore processorsThe Journal of Supercomputing10.1007/s11227-021-03736-177:10(11756-11785)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s11227-021-03736-1
Show More Cited By

Recommendations

Analysis of the paging behavior of UNIX

We analyze the paging behavior of several different versions of UNIX by recording traces of paging activity over time and writing programs to analyze the traces. We recorded periodic totals of paging events instead of individual paging events ...
Demand paging for OneNAND™ Flash eXecute-in-place
CODES+ISSS '06: Proceedings of the 4th international conference on Hardware/software codesign and system synthesis

NAND flash memory can provide cost-effective secondary storage in mobile embedded systems, but its lack of a random access capability means that code shadowing is generally required, taking up extra RAM space. Demand paging with NAND flash memory has ...
Energy-aware demand paging on NAND flash-based embedded storages
ISLPED '04: Proceedings of the 2004 international symposium on Low power electronics and design

The ever-increasing requirement for high-performance and huge-capacity memories of emerging embedded applications has led to the widespread adoption of SDRAM and NAND flash memory as main and secondary memories, respectively. In particular, the use of ...

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 18, Issue 1

January 1974

78 pages

ISSN:0018-8646

Issue’s Table of Contents

Publisher

IBM Corp.

United States

Publication History

Published: 01 January 1974

Received: 20 March 1973

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bender MDeLayo DKuszmaul BKuszmaul WWest EAgrawal KShun J(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
https://dl.acm.org/doi/10.1145/3558481.3591085
Song SKhan TShahri SSriraman ASoundararajan NSubramoney SJiménez DLitz HKasikci BSalapura VZahran MChong FTang L(2022)ThermometerProceedings of the 49th Annual International Symposium on Computer Architecture10.1145/3470496.3527430(742-756)Online publication date: 18-Jun-2022
https://dl.acm.org/doi/10.1145/3470496.3527430
Díaz JIbáñez PMonreal TViñals VLlabería J(2021)Near-optimal replacement policies for shared caches in multicore processorsThe Journal of Supercomputing10.1007/s11227-021-03736-177:10(11756-11785)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s11227-021-03736-1
Beckmann NGibbons PHaeupler BMcGuffey CScheideler CBerenbrink P(2019)Writeback-Aware Caching (Brief Announcement)The 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323169(345-347)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323169
Jain ALin C(2018)Rethinking belady's algorithm to accommodate prefetchingProceedings of the 45th Annual International Symposium on Computer Architecture10.1109/ISCA.2018.00020(110-123)Online publication date: 2-Jun-2018
https://dl.acm.org/doi/10.1109/ISCA.2018.00020
Bilardi GEkanadham KPattnaik PGiorgi RBecchi MPalumbo F(2017)Optimal On-Line Computation of Stack Distances for MIN and OPTProceedings of the Computing Frontiers Conference10.1145/3075564.3075571(237-246)Online publication date: 15-May-2017
https://dl.acm.org/doi/10.1145/3075564.3075571
Michaud P(2016)Some Mathematical Facts About Optimal Cache ReplacementACM Transactions on Architecture and Code Optimization10.1145/301799213:4(1-19)Online publication date: 16-Dec-2016
https://dl.acm.org/doi/10.1145/3017992
Jain ALin C(2016)Back to the futureACM SIGARCH Computer Architecture News10.1145/3007787.300114644:3(78-89)Online publication date: 18-Jun-2016
https://dl.acm.org/doi/10.1145/3007787.3001146
Jain ALin CMin SLoh G(2016)Back to the futureProceedings of the 43rd International Symposium on Computer Architecture10.1109/ISCA.2016.17(78-89)Online publication date: 18-Jun-2016
https://dl.acm.org/doi/10.1109/ISCA.2016.17
Choi ARuschitzka M(1993)Managing Locality SetsIEEE Transactions on Computers10.1109/12.20479242:2(190-204)Online publication date: 1-Feb-1993
https://dl.acm.org/doi/10.1109/12.204792
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.

Abstract

References

Cited By

Recommendations

Analysis of the paging behavior of UNIX

Demand paging for OneNAND™ Flash eXecute-in-place

Energy-aware demand paging on NAND flash-based embedded storages

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations