Dynamic tracking of page miss ratio curve for memory management

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. Abandah, Configuration Independent Analysis for Characterizing Shared-Memory Applications, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.485, March 30-April 03, 1998
• 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: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 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.
• 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: Richard W. Carr , John L. Hennessy, WSCLOCK—a simple and effective algorithm for virtual memory management, Proceedings of the eighth ACM symposium on Operating systems principles, p.87-95, December 14-16, 1981, Pacific Grove, California, United States
• 9: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 10: Jeffrey S. Chase , Darrell C. Anderson , Prachi N. Thakar , Amin M. Vahdat , Ronald P. Doyle, Managing energy and server resources in hosting centers, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 11: W. Chu and H. Opderbeck. The page fault frequency replacement algorithm. In AFIPS Conf. Proc., 1972.
• 12: Helen Custer, Inside Windows NT, Microcomputer Applications, Suisun City, CA, 1992
• 13: V. De La Luz , M. Kandemir , I. Kolcu, Automatic data migration for reducing energy consumption in multi-bank memory systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513973]
• 14: V. Delaluz , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Energy-oriented compiler optimizations for partitioned memory architectures, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.138-147, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354900]
• 15: Victor Delaluz , Mahmut Kandemir , N. Vijaykrishnan , Anand Sivasubramaniam , Mary Jane Irwin, Hardware and Software Techniques for Controlling DRAM Power Modes, IEEE Transactions on Computers, v.50 n.11, p.1154-1173, November 2001 [doi>10.1109/12.966492]
• 16: V. Delaluz , A. Sivasubramaniam , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Scheduler-based DRAM energy management, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514095]
• 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: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 20: J. B. Dennis, PROGRAM STRUCTURE IN A MULTI-ACCESS COMPUTER, Massachusetts Institute of Technology, Cambridge, MA, 1964
• 21: M. Dillon. Design elements of the freebsd vm system. Daemon News, Jan 2001.
• 22: George W. Dunlap , Samuel T. King , Sukru Cinar , Murtaza A. Basrai , Peter M. Chen, ReVirt: enabling intrusion analysis through virtual-machine logging and replay, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844148]
• 23: E. G. Coffman, Jr. , Thomas A. Ryan, Jr., A study of storage partitioning using a mathematical model of locality, Proceedings of the third ACM symposium on Operating systems principles, p.122, October 18-20, 1971, Palo Alto, California, United States [doi>10.1145/800212.806510]
• 24: R. L. M. et al. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78--117, 1970.
• 25: Xiaobo Fan , Carla Ellis , Alvin Lebeck, Memory controller policies for DRAM power management, Proceedings of the 2001 international symposium on Low power electronics and design, p.129-134, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383118]
• 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: Mark D Hill, Aspects of Cache Memory and Instruction, University of California at Berkeley, Berkeley, CA, 1987
• 29: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 30: H. Huang, P.Padmanabhan, and K. Shin. Design and implementation of power-aware virtual memory. In USENIX, 2003.
• 31: Song Jiang , Xiaodong Zhang, TPF: a dynamic system thrashing protection facility, Software—Practice & Experience, v.32 n.3, p.295-318, March 2002 [doi>10.1002/spe437]
• 32: M. Kandemir , N. Vijaykrishnan , M. J. Irwin , W. Ye, Influence of compiler optimizations on system power, Proceedings of the 37th conference on Design automation, p.304-307, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337425]
• 33: Scott F. Kaplan , Lyle A. McGeoch , Megan F. Cole, Adaptive caching for demand prepaging, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 34: Magnus Karlsson , Per Stenström, An analytical model of the working-set sizes in decision-support systems, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.275-285, June 18-21, 2000, Santa Clara, California, United States
• 35: Lawrence J. Kenah , Simon F. Bate, VAX/VMS internals and data structures, Digital Press, Newton, MA, 1984
• 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.
• 37: Yul H. Kim , Mark D. Hill , David A. Wood, Implementing stack simulation for highly-associative memories, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.212-213, May 21-24, 1991, San Diego, California, United States
• 38: Alvin R. Lebeck , Xiaobo Fan , Heng Zeng , Carla Ellis, Power aware page allocation, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.105-116, November 2000, Cambridge, Massachusetts, United States
• 39: Charles Lefurgy , Karthick Rajamani , Freeman Rawson , Wes Felter , Michael Kistler , Tom W. Keller, Energy Management for Commercial Servers, Computer, v.36 n.12, p.39-48, December 2003 [doi>10.1109/MC.2003.1250880]
• 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: Mohammad Malkawi , Janek Patel, Compiler directed memory management policy for numerical programs, Proceedings of the tenth ACM symposium on Operating systems principles, p.97-106, December 1985, Orcas Island, Washington, United States
• 42: M. I. Malkawi , J. H. Patel, Performance measurement of paging behavior in multiprogramming systems, Proceedings of the 13th annual international symposium on Computer architecture, p.111-118, June 02-05, 1986, Tokyo, Japan
• 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 , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 45: Prasad Dabak , Sandeep Phadke , Milind Borate, Undocumented Windows NT, John Wiley & Sons, Inc., New York, NY, 1999
• 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 , D. Siewiorek, A resource allocation model for QoS management, Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS '97), p.298, December 03-05, 1997
• 48: R. Rajkumar , C. Lee , J. P. Lehoczky , D. P. Siewiorek, Practical Solutions for QoS-Based Resource Allocation, Proceedings of the IEEE Real-Time Systems Symposium, p.296, December 02-04, 1998
• 49: Rambus. Rdram. http://www.rambus.com, 1999.
• 50: Edward Rothberg , Jaswinder Pal Singh , Anoop Gupta, Working sets, cache sizes, and node granularity issues for large-scale multiprocessors, Proceedings of the 20th annual international symposium on Computer architecture, p.14-26, May 16-19, 1993, San Diego, California, United States
• 51: Yannis Smaragdakis , Scott Kaplan , Paul Wilson, EELRU: simple and effective adaptive page replacement, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.122-133, May 01-04, 1999, Atlanta, Georgia, United States
• 52: B. J. Smith. A pipelined, shared resource MIMD computer. In Proceedings of International Conference on Parallel Proc essing, pages 6--8, 1978.
• 53: Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 54: Dominique Thiébaut , Harold S. Stone , Joel L. Wolf, Improving Disk Cache Hit-Ratios Through Cache Partitioning, IEEE Transactions on Computers, v.41 n.6, p.665-676, June 1992 [doi>10.1109/12.144619]
• 55: Rik van Riel, Page Replacement in Linux 2.4 Memory Management, Proceedings of the FREENIX Track: 2001 USENIX Annual Technical Conference, p.165-172, June 25-30, 2001
• 56: N. Vijaykrishnan , M. Kandemir , M. J. Irwin , H. S. Kim , W. Ye, Energy-driven integrated hardware-software optimizations using SimplePower, Proceedings of the 27th annual international symposium on Computer architecture, p.95-106, June 2000, Vancouver, British Columbia, Canada
• 57: Wen-Hann Wang , Jean-Loup Baer, Efficient trace-driven simulation method for cache performance analysis, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.27-36, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 58: P. R. Wilson, S. F. Kaplan, and Y. Smaragdakis. The case for compressed caching in virtual memory systems. In USENIX, 1999.
• 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.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Main memory

General Terms:
Algorithms, Management, Performance

Keywords:
memory management, power management, resource allocation