More Web Proxy on the site http://driver.im/

article

Dynamic tracking of page miss ratio curve for memory management

Authors:

Jagadeesan Sundaresan,

Anand Raghuraman,

Sanjeev KumarAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 32, Issue 5

Pages 177 - 188

https://doi.org/10.1145/1037947.1024415

Published: 07 October 2004 Publication History

Abstract

Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this purpose. However, dynamically tracking MRC at run time is challenging in systems with virtual memory because not every memory reference passes through the operating system (OS).This paper proposes two methods to dynamically track MRC of applications at run time. The first method is using a hardware MRC monitor that can track MRC at fine time granularity. Our simulation results show that this monitor has negligible performance and energy overheads. The second method is an OS-only implementation that can track MRC at coarse time granularity. Our implementation results on Linux show that it adds only 7--10% overhead.We have also used the dynamic MRC to guide both memory allocation for multiprogramming systems and memory energy management. Our real system experiments on Linux with applications including Apache Web Server show that the MRC-directed memory allocation can speed up the applications' execution/response time by up to a factor of 5.86 and reduce the number of page faults by up to 63.1%. Our execution-driven simulation results with SPEC2000 benchmarks show that the MRC-directed memory energy management can improve the Energy * Delay metric by 27--58% over previously proposed static and dynamic schemes.

References

[1]

Apache web server. http://httpd.apache.org/test/flood.]]

[2]

Flood: A profile driven http load tester. http://httpd.apache.org/test/flood.]]

[3]

G. A. Abandah and E. S. Davidson. Configuration independent analysis for characterizing shared-memory applications. In IPPS-12, Mar 1998.]]

Digital Library

[4]

L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and zipf-like distributions: Evidence and implications. In INFOCOM (1), pages 126--134, 1999.]]

[5]

D. Brooks, V. Tiwari, and M. Martonosi. Wattch: A framework for architectural-level power analysis and optimizations. In ISCA-27, June 2000.]]

Digital Library

[6]

A. D. Brown and T. C. Mowry. Taming the memory hogs: Using compiler-inserted releases to manage physical memory intelligently. In OSDI, Oct 2000.]]

Digital Library

[7]

D. Burger, T. M. Austin, and S. Bennett. Evaluating future microprocessors: The simplescalar tool set. Technical Report CS-TR-1996-1308, Univ. of Wisconsin-Madison, 1996.]]

[8]

R. Carr and J. Hennessy. Wsclock --- a simple and efficient algorithm for virtual memory management. In SOSP, Dec. 1981.]]

Digital Library

[9]

F. Catthoor, S.Wuytack, E. Greef, F.Balasa, L.Nachtergaele, and A. Vandecappelle. Custom memory management methodology exploration of memory organization for embedded multimedia systems design. In Kluwer Academic Publishers, 1998.]]

Digital Library

[10]

J. S. Chase, D. C. Anderson, P. N. Thakar, A. Vahdat, and R. P. Doyle. Managing energy and server resources in hosting centres. In SOSP, pages 103--116, 2001.]]

Digital Library

[11]

W. Chu and H. Opderbeck. The page fault frequency replacement algorithm. In AFIPS Conf. Proc., 1972.]]

Digital Library

[12]

H. Custer. Inside Windows NT. Microsoft Press, Redmond, Washington, 2000.]]

Digital Library

[13]

V. Delaluz, M. Kandemir, and I. Kolcu. Automatic data migration for reducing energy consumption in multi-bank memory systems. In the 39th Design Automation Conference, June 2002.]]

Digital Library

[14]

V. Delaluz, M. Kandemir, N. Vijaykrishnan, and M. J. Irwin. Energy-oriented compiler optimizations for partitioned memory architectures. In International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, Nov 2000.]]

Digital Library

[15]

V. Delaluz, M. Kandemir, N. Vijaykrishnan, A. Sivasubramniam, and M. J. Irwin. Hardware and software techniques for controlling dram power modes. IEEE Transactions on Computers, 2001.]]

Digital Library

[16]

V. Delaluz, A. Sivasubramaniam, M. Kandemir, N. Vijaykrishnan, and M. J. Irwin. Scheduler-based dram energy management. In Proceedings of the 39th conference on Design automation, pages 697--702. ACM Press, 2002.]]

Digital Library

[17]

P. Denning. Thrashing: Its causes and prevention. In AFIPS Fall Joint Computer Conference, 1968.]]

[18]

P. J. Denning. Memory allocation in multiprogrammed computers. In Project MAC Computation Structures Group Memo, Mar 1966.]]

[19]

P. J. Denning. The working set model for program behavior. Commun. ACM, 11(5):323--333, May 1968.]]

Digital Library

[20]

J. B. Dennis. Program structure in a multi-access computer. Project MAC Tech Rep. MAC-TR-11, M.I.T, 1967.]]

Digital Library

[21]

M. Dillon. Design elements of the freebsd vm system. Daemon News, Jan 2001.]]

[22]

G. W. Dunlap, S. T. King, S. Cinar, M. A. Basrai, and P. M. Chen. ReVirt: Enabling intrusion analysis through virtual-machine logging and replay. In Proceedings of the 2002 Symposium on Operating Systems Design and Implementation (OSDI), 2002.]]

Digital Library

[23]

J. E. G. Coffman and J. Thomas A. Ryan. A study of storage partitioning using a mathematical model of locality. In Proceedings of the third symposium on Operating systems principles, page 122, 1971.]]

Digital Library

[24]

R. L. M. et al. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78--117, 1970.]]

Digital Library

[25]

X. Fan, C. S. Ellis, and A. R. Lebeck. Memory controller policies for dram power management. In ISLPED, Apr 2001.]]

Digital Library

[26]

D. Ferrari and Y.-Y. Yih. VSWS: The variable-interval sampled working set policy. IEEE Trans. on Software Engineering, SE-9, 1993.]]

[27]

R. K. Gupta and M. A. Franklin. Working set and page fault frequency replacement algorithms: A performance comparison. IEEE Transactions on Computers, C-27, 1978.]]

[28]

M. D. Hill. Aspects of cache memory and instruction buffer performance. Technical Report CSD-87-381, University of California, Berkeley, Nov. 1987.]]

Digital Library

[29]

M. D. Hill and A. J. Smith. Evaluating associativity in CPU caches. IEEE Transactions on Computers, 38(12), 1989.]]

Digital Library

[30]

H. Huang, P.Padmanabhan, and K. Shin. Design and implementation of power-aware virtual memory. In USENIX, 2003.]]

Digital Library

[31]

S. Jiang and X. Zhang. Tpf: A system thrashing protection facility. Software: Practice and Experience, 32:295--318, 2002.]]

Digital Library

[32]

M. T. Kandemir, N. Vijaykrishnan, M. J. Irwin, and W. Ye. Influence of compiler optimizations on system power. In Design Automation Conference, 2000.]]

Digital Library

[33]

S. F. Kaplan, L. A. McGeoch, and M. F. Cole. Adaptive caching for demand prepaging. In Proceedings of the third international symposium on Memory management, 2002.]]

Digital Library

[34]

M. Karlsson and P. Stenstrom. An analytical model of the working-set sizes in decision-support systems. In SIGMETRICS, pages 275--285, 2000.]]

Digital Library

[35]

L. J. Kenah and S. F. Bate. Vax/VMS Internals and Data Structures. Digital Press, Bedford, 1984.]]

Digital Library

[36]

J. Kim, J. Choi, J. Kim, S. Noh, S. Min, Y. Cho, and C. Kim. A low-overhead high-performance unified buffer management scheme that exploits sequential and looping references. OSDI, 2000.]]

Digital Library

[37]

Y. H. Kim, M. D. Hill, and D. A. Wood. Implementing stack simulation for highly-associative memories. In SIGMETRICS, 1991.]]

Digital Library

[38]

A. R. Lebeck, X. Fan, H. Zeng, and C. S. Ellis. Power aware page allocation. In ASPLOS, pages 105--116, 2000.]]

Digital Library

[39]

C. Lefurgy, K. Rajamani, F. Rawson, W. F. elter, M. Kistler, and T. W. Keller. Energy management for commercial servers. IEEE Computer, 36(12):39--48, December 2003.]]

Digital Library

[40]

K. Li. Ivy: A shared virtual memory system for parallel computing. In Proceedings of the 1988 International Conference on Parallel Processing, volume II Software, pages 94--101, Aug. 1988.]]

[41]

M. Malkawi and J. H. Patel. Compiler directed memory management policy for numerical programs. In SOSP, 1985.]]

Digital Library

[42]

M. Malkawi and J. H. Patel. Performance measurement of paging behavior in multiprogramming systems. In ISCA, 1986.]]

Digital Library

[43]

B. Moore. Taking the data center power and cooling challenge. Energy User News, August 27th, 2002.]]

[44]

R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka. Informed prefetching and caching. In the 15th SOSP, 1995.]]

Digital Library

[45]

S. P. Prasad Dabak, Milind Borate. Undocumented Windows NT. M&T Books, 1999.]]

Digital Library

[46]

A. Raghuraman. Miss-ratio curve directed memory management for high performance and low energy. UIUC, Master Thesis, 2003.]]

[47]

R. Rajkumar, C. Lee, J. Lehoczky, and D. Siewiorek. A resource allocation model for qos management. In IEEE Real-Time Systems Symposium, 1997.]]

Digital Library

[48]

R. Rajkumar, C. Lee, J. Lehoczky, and D. Siewiorek. Practical solutions for qos-based resource allocation problems. In IEEE Real-Time Systems Symposium, 1998.]]

Digital Library

[49]

Rambus. Rdram. http://www.rambus.com, 1999.]]

[50]

E. Rothberg, J. P. Singh, and A. Gupta. Working sets, cache sizes and node granularity issues for large-scale multiprocessors. In ISCA, 1993.]]

Digital Library

[51]

Y. Smaragdakis, S. Kaplan, and P. Wilson. EELRU: simple and effective adaptive page replacement. In SIGMETRICS, 1999.]]

Digital Library

[52]

B. J. Smith. A pipelined, shared resource MIMD computer. In Proceedings of International Conference on Parallel Proc essing, pages 6--8, 1978.]]

[53]

A. S. Tanenbaum. Modern Operating Systems. Prentice Hall, New Jersey, 1992.]]

Digital Library

[54]

D. Thiebaut, H. S. Stone, and J. L. Wolf. Improving disk cache hit-ratios through cache partitioning. IEEE Trans. Comput., 41(6):665--676, 1992.]]

Digital Library

[55]

R. van Riel. Page replacement in linux 2.4 memory management. USENIX Annual Technical Conference - FREENIX Track, 2001.]]

Digital Library

[56]

N. Vijaykrishnan, M. Kandemir, M. J. Irwin, H. S. Kim, and W. Ye. Energy-driven integrated hardware-software optimizations using simplepower. In ISCA-27, pages 95--106. ACM Press, 2000.]]

Digital Library

[57]

W.-H. Wang and J.-L. Baer. Efficient trace-driven simulation method for cache performance analysis. In SIGMETRICS, 1990.]]

Digital Library

[58]

P. R. Wilson, S. F. Kaplan, and Y. Smaragdakis. The case for compressed caching in virtual memory systems. In USENIX, 1999.]]

Digital Library

[59]

S. Woo, M. Ohara, E. Torrie, J.P.Singh, and A. Gupta. Methodological considerations and characterization of the splash-2 parallel application suite. In ISCA-23, May 1996.]]

Cited By

M. Mathew DS. Prado FZulian ÉWeis CGhaffar MJung MWehn N(2020)An Energy Efficient 3D-Heterogeneous Main Memory Architecture for Mobile DevicesProceedings of the International Symposium on Memory Systems10.1145/3422575.3422786(114-125)Online publication date: 28-Sep-2020
https://dl.acm.org/doi/10.1145/3422575.3422786
Saemundsson TBjornsson HChockler GVigfusson YLazowska ETerry DArpaci-Dusseau RGehrke J(2014)Dynamic Performance Profiling of Cloud CachesProceedings of the ACM Symposium on Cloud Computing10.1145/2670979.2671007(1-14)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2670979.2671007
ZHANG XLIU CLIU ZWANG D(2013)Improving Cache Partitioning Algorithms for Pseudo-LRU PoliciesIEICE Transactions on Information and Systems10.1587/transinf.E96.D.2514E96.D:12(2514-2523)Online publication date: 2013
https://doi.org/10.1587/transinf.E96.D.2514
Show More Cited By

Index Terms

Dynamic tracking of page miss ratio curve for memory management
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Main memory

Recommendations

Dynamic tracking of page miss ratio curve for memory management
ASPLOS '04

Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this ...
Dynamic tracking of page miss ratio curve for memory management
ASPLOS XI: Proceedings of the 11th international conference on Architectural support for programming languages and operating systems

Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this ...
Dynamic tracking of page miss ratio curve for memory management
ASPLOS '04

Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 32, Issue 5

ASPLOS 2004

December 2004

283 pages

ISSN:0163-5964

DOI:10.1145/1037947

Issue’s Table of Contents

ASPLOS XI: Proceedings of the 11th international conference on Architectural support for programming languages and operating systems
October 2004
296 pages
ISBN:1581138040
DOI:10.1145/1024393
General Chair:
Shubu Mukherjee
Intel Corporation
,
Program Chair:
Kathryn S. McKinley
University of Texas at Austin

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 October 2004

Published in SIGARCH Volume 32, Issue 5

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

226
Total Citations
View Citations
2,451
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)13

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

M. Mathew DS. Prado FZulian ÉWeis CGhaffar MJung MWehn N(2020)An Energy Efficient 3D-Heterogeneous Main Memory Architecture for Mobile DevicesProceedings of the International Symposium on Memory Systems10.1145/3422575.3422786(114-125)Online publication date: 28-Sep-2020
https://dl.acm.org/doi/10.1145/3422575.3422786
Saemundsson TBjornsson HChockler GVigfusson YLazowska ETerry DArpaci-Dusseau RGehrke J(2014)Dynamic Performance Profiling of Cloud CachesProceedings of the ACM Symposium on Cloud Computing10.1145/2670979.2671007(1-14)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2670979.2671007
ZHANG XLIU CLIU ZWANG D(2013)Improving Cache Partitioning Algorithms for Pseudo-LRU PoliciesIEICE Transactions on Information and Systems10.1587/transinf.E96.D.2514E96.D:12(2514-2523)Online publication date: 2013
https://doi.org/10.1587/transinf.E96.D.2514
Khargharia BYousif M(2012)Autonomic Energy/Performance Optimizations for Memory in ServersEnergy‐Efficient Distributed Computing Systems10.1002/9781118342015.ch14(377-394)Online publication date: 30-Jul-2012
https://doi.org/10.1002/9781118342015.ch14
Sultan SShakiba KLee AChen PStumm M(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
https://dl.acm.org/doi/10.1145/3627703.3650066
Maruf HWang HDhanotia AWeiner JAgarwal NBhattacharya PPetersen CChowdhury MKanaujia SChauhan PAamodt TJerger NSwift M(2023)TPP: Transparent Page Placement for CXL-Enabled Tiered-MemoryProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582063(742-755)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3582016.3582063
Li PGuo YGu YWolf FShende SCulhane CAlam SJagode H(2022)Predicting reuse interval for optimized web cachingProceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis10.5555/3571885.3571999(1-15)Online publication date: 13-Nov-2022
https://dl.acm.org/doi/10.5555/3571885.3571999
Seering JKairam S(2022)Who Moderates on Twitch and What Do They Do?Proceedings of the ACM on Human-Computer Interaction10.1145/35675687:GROUP(1-18)Online publication date: 29-Dec-2022
https://dl.acm.org/doi/10.1145/3567568
Li PGuo YGu Y(2022)Predicting Reuse Interval for Optimized Web Caching: An LSTM-Based Machine Learning ApproachSC22: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41404.2022.00091(1-15)Online publication date: Nov-2022
https://doi.org/10.1109/SC41404.2022.00091
Gokul Vasan LF. Zulian ÉWeis CJung MWehn N(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
https://dl.acm.org/doi/10.1145/3488423.3519332
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents