Data cache management using frequency-based replacement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Data cache management using frequency-based replacement

Full text

Pdf (991 KB)

Source

Joint International Conference on Measurement and Modeling of Computer Systems archive
Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems table of contents

Univ. of Colorado, Boulder, Colorado, United States

Pages: 134 - 142

Year of Publication: 1990

ISBN:0-89791-359-0

Also published in ...

Authors

John T. Robinson	IBM Research Division, T.J. Watson Research Center, P. O. Box 704, Yorktown Heights, NY
Murthy V. Devarakonda	IBM Research Division, T.J. Watson Research Center, P. O. Box 704, Yorktown Heights, NY

Sponsor

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 142, Citation Count: 72

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/98457.98523 What is a DOI?

ABSTRACT

We propose a new frequency-based replacement algorithm for managing caches used for disk blocks by a file system, database management system, or disk control unit, which we refer to here as data caches. Previously, LRU replacement has usually been used for such caches. We describe a replacement algorithm based on the concept of maintaining reference counts in which locality has been “factored out”. In this algorithm replacement choices are made using a combination of reference frequency and block age. Simulation results based on traces of file system and I/O activity from actual systems show that this algorithm can offer up to 34% performance improvement over LRU replacement, where the improvement is expressed as the fraction of the performance gain achieved between LRU replacement and the theoretically optimal policy in which the reference string must be known in advance. Furthermore, the implementation complexity and efficiency of this algorithm is comparable to one using LRU replacement.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BOZM89	G. P. Bozman, VM/XA SP2 minidisk cache, IBM Systems Journal, v.28 n.1, p.165-174, 1989
	COFF73	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	DEVA88	Murthy V.-S. Devarakonda , R. K. Iyer, File usage analysis and resource usage prediction: a measurement-based study, 1988
	DEVA90	Devarakonda, M. Analysis of file cache replacement algorithms using UNIX traces, Res. report RC15410, IBM Research Div., T. J. Watson Res. Ctr., Yorktown Hts., NY, 1990.
	EFFE84	Wolfgang Effelsberg , Theo Haerder, Principles of database buffer management, ACM Transactions on Database Systems (TODS), v.9 n.4, p.560-595, Dec. 1984 [doi>10.1145/1994.2022]
	OUST85	John K. Ousterhout , Hervé Da Costa , David Harrison , John A. Kunze , Mike Kupfer , James G. Thompson, A trace-driven analysis of the UNIX 4.2 BSD file system, Proceedings of the tenth ACM symposium on Operating systems principles, p.15-24, December 1985, Orcas Island, Washington, United States
	SMIT82	Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
	SMIT85	Alan J. Smith, Disk cache—miss ratio analysis and design considerations, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.161-203, Aug. 1985 [doi>10.1145/3959.3961]

CITED BY 72

	Anthony K. H. Tung , Y. C. Tay , Hongjun Lu, BROOM: buffer replacement using online optimization by mining, Proceedings of the seventh international conference on Information and knowledge management, p.185-192, November 02-07, 1998, Bethesda, Maryland, United States
	Miguel Castro , Atul Adya , Barbara Liskov , Andrew C. Meyers, HAC: hybrid adaptive caching for distributed storage systems, ACM SIGOPS Operating Systems Review, v.31 n.5, p.102-115, Dec. 1997
	Yul H. Kim , Mark D. Hill , David A. Wood, Implementing stack simulation for highly-associative memories, ACM SIGMETRICS Performance Evaluation Review, v.19 n.1, p.212-213, May 1991
	Donghee Lee , Jongmoo Choi , Jong-Hun Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies, ACM SIGMETRICS Performance Evaluation Review, v.27 n.1, p.134-143, June 1999
	Vidyadhar Phalke , Bhaskarpillai Gopinath, An inter-reference gap model for temporal locality in program behavior, ACM SIGMETRICS Performance Evaluation Review, v.23 n.1, p.291-300, May 1995
	Song Jiang , Xiaodong Zhang, LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance, ACM SIGMETRICS Performance Evaluation Review, v.30 n.1, June 2002
	Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, ACM SIGMOD Record, v.22 n.2, p.297-306, June 1, 1993
	Zhifeng Chen , Yan Zhang , Yuanyuan Zhou , Heidi Scott , Berni Schiefer, Empirical evaluation of multi-level buffer cache collaboration for storage systems, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
	Windsor W. Hsu , Alan Jay Smith , Honesty C. Young, I/O reference behavior of production database workloads and the TPC benchmarks—an analysis at the logical level, ACM Transactions on Database Systems (TODS), v.26 n.1, p.96-143, March 2001
	Scott F. Kaplan , Yannis Smaragdakis , Paul R. Wilson, Trace reduction for virtual memory simulations, ACM SIGMETRICS Performance Evaluation Review, v.27 n.1, p.47-58, June 1999
	Scott F. Kaplan , Yannis Smaragdakis , Paul R. Wilson, Flexible reference trace reduction for VM simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.1, p.1-38, January 2003
	Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Eun-Yong Ha , Yookun Cho, Design, Implementation, and Performance Evaluation of a Detection-Based Adaptive Block Replacement Scheme, IEEE Transactions on Computers, v.51 n.7, p.793-800, July 2002
	Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Effective “static-graph” reorganization to improve locality in garbage-collected systems, ACM SIGPLAN Notices, v.26 n.6, p.177-191, June 1991
	William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Ganesh Santhanakrishnan , Ahmed Amer , Panos K. Chrysanthis , Dan Li, GD-GhOST: a goal-oriented self-tuning caching algorithm, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	D. Lee , J. Choi , J. H. Kim , S. H. Noh , S. L. Min , Y. Cho , C. S. Kim, LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies, IEEE Transactions on Computers, v.50 n.12, p.1352-1361, December 2001
	Alexander Thomasian , Chang Liu, Disk scheduling policies with lookahead, ACM SIGMETRICS Performance Evaluation Review, v.30 n.2, September 2002
	Christopher R. LaRosa , Mark W. Bailey, A docked-aware storage architecture for mobile computing, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy
	Dimitrios Katsaros , Yannis Manolopoulos, Caching in Web memory hierarchies, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	H. Seok Jeon , Sam H. Noh, A database disk buffer management algorithm based on prefetching, Proceedings of the seventh international conference on Information and knowledge management, p.167-174, November 02-07, 1998, Bethesda, Maryland, United States
	Prabuddha Biswas, Issues in cache management algorithms for commercial software systems, Proceedings of the 1st international workshop on Software and performance, p.76-77, October 12-16, 1998, Santa Fe, New Mexico, United States
	Vidyadhar Phalke , B. Gopinath, Compression-Based Program Characterization for Improving Cache Memory Performance, IEEE Transactions on Computers, v.46 n.11, p.1174-1186, November 1997
	D. M. Nicol , A. G. Greenberg , B. D. Lubachevsky, Massively Parallel Algorithms for Trace-Driven Cache Simulations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.849-859, August 1994
	Li Chen , Song Wang , Elke A. Rundensteiner, Replacement strategies for XQuery caching systems, Data & Knowledge Engineering, v.49 n.2, p.145-175, May 2004
	Masamichi Takagi , Kei Hiraki, Inter-reference gap distribution replacement: an improved replacement algorithm for set-associative caches, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Ming-Kuan Liu , Fei-Yue Wang , Daniel Dajun Zeng, Web caching: a way to improve web QoS, Journal of Computer Science and Technology, v.19 n.2, p.113-127, March 2004
	Yannis Smaragdakis, General adaptive replacement policies, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Nimrod Megiddo , Dharmendra S. Modha, Outperforming LRU with an Adaptive Replacement Cache Algorithm, Computer, v.37 n.4, p.58-65, April 2004
	Yuanyuan Zhou , Zhifeng Chen , Kai Li, Second-Level Buffer Cache Management, IEEE Transactions on Parallel and Distributed Systems, v.15 n.6, p.505-519, June 2004
	Ali R. Butt , Chris Gniady , Y. Charlie Hu, The performance impact of kernel prefetching on buffer cache replacement algorithms, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
	Song Jiang , Xiaodong Zhang, Making LRU Friendly to Weak Locality Workloads: A Novel Replacement Algorithm to Improve Buffer Cache Performance, IEEE Transactions on Computers, v.54 n.8, p.939-952, August 2005
	Ganesh Santhanakrishnan , Ahmed Amer , Panos K. Chrysanthis, Towards universal mobile caching, Proceedings of the 4th ACM international workshop on Data engineering for wireless and mobile access, June 12-12, 2005, Baltimore, MD, USA
	Tiziano Fagni , Raffaele Perego , Fabrizio Silvestri , Salvatore Orlando, Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data, ACM Transactions on Information Systems (TOIS), v.24 n.1, p.51-78, January 2006
	Ramakrishna Karedla , J. Spencer Love , Bradley G. Wherry, Caching strategies to improve disk system performance, Computer, v.27 n.3, p.38-46, March 1994
	Y. C. Tay , Min Zou, A page fault equation for modeling the effect of memory size, Performance Evaluation, v.63 n.2, p.99-130, February 2006
	Li Chen , Song Wang , Elizabeth Cash , Burke Ryder , Ian Hobbs , Elke A. Rundensteiner, A fine-grained replacement strategy for XML query cache, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA
	Rachid El Abdouni Khayari, Design and evaluation of web proxies by leveraging self-similarity of web traffic, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.12, p.1952-1973, 24 August 2006
	Binny S. Gill, On multi-level exclusive caching: offline optimality and why promotions are better than demotions, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-17, February 26-29, 2008, San Jose, California
	Henrique Andrade , Tahsin Kurc , Alan Sussman , Joel Saltz, Active semantic caching to optimize multidimensional data analysis in parallel and distributed environments, Parallel Computing, v.33 n.7-8, p.497-520, August, 2007
	Haakon Dybdahl , Per Stenström , Lasse Natvig, An LRU-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches, Proceedings of the 2006 workshop on MEmory performance: DEaling with Applications, systems and architectures, p.45-52, September 16-20, 2006, Seattle, Washington
	Michael Behar , Avi Mendelson , Avinoam Kolodny, Trace cache sampling filter, ACM Transactions on Computer Systems (TOCS), v.25 n.1, p.3-es, February 2007
	Jochen Hollmann , Anders Ardö , Per Stenström, Effectiveness of caching in a distributed digital library system, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.7, p.403-416, July, 2007
	Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001
	Jong Min Kim , Jongmoo Choi , Jesung Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, A low-overhead high-performance unified buffer management scheme that exploits sequential and looping references, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.9-9, October 22-25, 2000, San Diego, California
	Nathan C. Burnett , John Bent , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Exploiting Gray-Box Knowledge of Buffer-Cache Management, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.29-44, June 10-15, 2002
	Theodore M. Wong , John Wilkes, My Cache or Yours? Making Storage More Exclusive, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.161-175, June 10-15, 2002
	Michael B. Nielsen , Ola Nilsson , Andreas Söderström , Ken Museth, Out-of-core and compressed level set methods, ACM Transactions on Graphics (TOG), v.26 n.4, p.16-es, October 2007
	H. Seok Jeon , Sam H. Noh, Dynamic buffer cache management scheme based on simple and aggressive prefetching, Proceedings of the 4th conference on 4th Annual Linux Showcase & Conference, Atlanta, p.3-3, October 10-14, 2000, Atlanta, Georgia
	Carlos Maltzahn , Kathy J. Richardson , Dirk Grunwald, Reducing the disk I/O of web proxy server caches, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.17-17, June 06-11, 1999, Monterey, California
	Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Yookun Cho, An implementation study of a detection-based adaptive block replacement scheme, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.18-18, June 06-11, 1999, Monterey, California
	Moinuddin K. Qureshi , Aamer Jaleel , Yale N. Patt , Simon C. Steely , Joel Emer, Adaptive insertion policies for high performance caching, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
	Hyung Rai Oh , Hwangjun Song, A Novel Dynamic and Scalable Caching Algorithm of Proxy Server for Multimedia Objects, Journal of VLSI Signal Processing Systems, v.46 n.2-3, p.103-112, March 2007
	Nimrod Megiddo , Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
	Sorav Bansal , Dharmendra S. Modha, CAR: Clock with Adaptive Replacement, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
	John T. Robinson , Murthy V. Devarakonda, Note on a problem with Reed and Long's FBR results, ACM SIGOPS Operating Systems Review, v.31 n.1, p.3-4, Jan. 1997
	Chee Yong Chan , Beng Chin Ooi , Hongjun Lu, Extensible Buffer Management of Indexes, Proceedings of the 18th International Conference on Very Large Data Bases, p.444-454, August 23-27, 1992
	Kurt P. Brown , Michael J. Carey , Miron Livny, Managing Memory to Meet Multiclass Workload Response Time Goals, Proceedings of the 19th International Conference on Very Large Data Bases, p.328-341, August 24-27, 1993
	Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
	Konstantinos Stathatos , Nick Roussopoulos , John S. Baras, Adaptive Data Broadcast in Hybrid Networks, Proceedings of the 23rd International Conference on Very Large Data Bases, p.326-335, August 25-29, 1997
	Andreas Gerndt , Bernd Hentschel , Marc Wolter , Torsten Kuhlen , Christian Bischof, VIRACOCHA: An Efficient Parallelization Framework for Large-Scale CFD Post-Processing in Virtual Environments, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.50, November 06-12, 2004
	Benjamin Reed , Darrell D. E. Long, Analysis of caching algorithms for distributed file systems, ACM SIGOPS Operating Systems Review, v.30 n.3, p.12-21, July 1996
	Paul R. Wilson, Some issues and strategies in heap management and memory hierarchies, ACM SIGPLAN Notices, v.26 n.3, p.45-52, March 1991
	Hui Chen , Yang Xiao , Xuemin (Sherman) Shen, Update-Based Cache Access and Replacement in Wireless Data Access, IEEE Transactions on Mobile Computing, v.5 n.12, p.1734-1748, December 2006
	Ali R. Butt , Chris Gniady , Y. Charlie Hu, The Performance Impact of Kernel Prefetching on Buffer Cache Replacement Algorithms, IEEE Transactions on Computers, v.56 n.7, p.889-908, July 2007
	Li Ou , Xubin He , Jizhong Han, An efficient design for fast memory registration in RDMA, Journal of Network and Computer Applications, v.32 n.3, p.642-651, May, 2009
	Haakon Dybdahl , Per Stenström , Lasse Natvig, An LRU-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches, ACM SIGARCH Computer Architecture News, v.35 n.4, September 2007
	Christian A. Lang , Bishwaranjan Bhattacharjee , Tim Malkemus , Kwai Wong, Increasing buffer-locality for multiple index based scans through intelligent placement and index scan speed control, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Xubin (Ben) He , Li Ou , Martha J. Kosa , Stephen L. Scott , Christian Engelmann, A unified multiple-level cache for high performance storage systems, International Journal of High Performance Computing and Networking, v.5 n.1/2, p.97-109, November 2007
	Hui Chen , Yang Xiao, On-Bound Selection Cache Replacement Policy for Wireless Data Access, IEEE Transactions on Computers, v.56 n.12, p.1597-1611, December 2007
	Han-Lin Li , Chia-Lin Yang , Hung-Wei Tseng, Energy-aware flash memory management in virtual memory system, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.8, p.952-964, August 2008
	Andhi Janapsatya , Sri Parameswaran , Aleksandar Ignjatović, HitME: low power Hit MEmory buffer for embedded systems, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Chuanjun Zhang , Bing Xue, Divide-and-conquer: a bubble replacement for low level caches, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA