Notification: Our email services are now fully restored after a brief, temporary outage caused by a denial-of-service (DoS) attack. If you sent an email on Dec 6 and haven't received a response, please resend your email.
CFP last date
20 December 2024
Reseach Article

Analysis and Predictability of Page Replacement Techniques towards Optimized Performance

Published on March 2012 by Debabrata Swain, Bancha Nidhi Dash, Debendra O Shamkuwar, Debabala Swain
International Conference on Recent Trends in Information Technology and Computer Science
Foundation of Computer Science USA
ICRTITCS - Number 3
March 2012
Authors: Debabrata Swain, Bancha Nidhi Dash, Debendra O Shamkuwar, Debabala Swain
7581d7dc-b59a-4770-83e7-f21dfe67d48d

Debabrata Swain, Bancha Nidhi Dash, Debendra O Shamkuwar, Debabala Swain . Analysis and Predictability of Page Replacement Techniques towards Optimized Performance. International Conference on Recent Trends in Information Technology and Computer Science. ICRTITCS, 3 (March 2012), 12-16.

@article{
author = { Debabrata Swain, Bancha Nidhi Dash, Debendra O Shamkuwar, Debabala Swain },
title = { Analysis and Predictability of Page Replacement Techniques towards Optimized Performance },
journal = { International Conference on Recent Trends in Information Technology and Computer Science },
issue_date = { March 2012 },
volume = { ICRTITCS },
number = { 3 },
month = { March },
year = { 2012 },
issn = 0975-8887,
pages = { 12-16 },
numpages = 5,
url = { /proceedings/icrtitcs/number3/5187-1019/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Conference on Recent Trends in Information Technology and Computer Science
%A Debabrata Swain
%A Bancha Nidhi Dash
%A Debendra O Shamkuwar
%A Debabala Swain
%T Analysis and Predictability of Page Replacement Techniques towards Optimized Performance
%J International Conference on Recent Trends in Information Technology and Computer Science
%@ 0975-8887
%V ICRTITCS
%N 3
%P 12-16
%D 2012
%I International Journal of Computer Applications
Abstract

Caching is a fundamental technique commonly employed to hide the latency gap between memory and the CPU by exploiting locality in memory accesses. On today’s architectures a cache miss may cost several hundred CPU cycles [1]. In a two-level memory hierarchy, a cache performs faster than auxiliary storage, but is more expensive. Cost concerns thus usually limit cache size to a fraction of the auxiliary memory’s size. This paper represents a comparative predictability about some of the traditional and new replacement techniques in contrast with OPTIMAL replacement technique.

References
  1. Relative Competitive Analysis of Cache Replacement Policies _Jan Reineke Daniel Grund, LCTES’08, June 12–13, 2008, Tucson, Arizona, USA. Copyrightc 2008 ACM
  2. Q. Yang, H. H. Zhang and H. Zhang, “Taylor Series Prediction: A Cache Replacement Policy Based on Second-Order Trend Analysis,” Proc. 34th Hawaii Conf. System Science, 2001.
  3. S.Hosseini-khayat, “On Optimal Replacement of Nonuniform Cache Objects,” IEEE Trans. Computers, vol. 49, no.8, Aug. 2000.
  4. Debabala Swain, Bijay K Paikray, Debabrata Swain,“AWRP: Adaptive Weight Ranking Policy for Improving Cache Performance”, Journal of Computing, vol-3, Issue-2, February 2011.
  5. S. Irani, “Page Replacement with Multi-Size Pages and Applications to Web Caching,” Proc.29th Ann, ACM symp. Theory of Computing, pp. 701-710, 1997.
  6. E. J. O’Neil, P. E. O’Neil, and G. Weikum, “an Optimality Proof of the LRU-K page Replacement Algorithm.” J.ACM, vol. 46, no.1, pp. 92-112, 1999. Figure 2: Performance Analysis of different techniques using Average Hit Ratio.
  7. G. Glass and P. Cao, “Adaptive Page Replacement Based on Memory Reference Behavior", proc ACM SIGMETRICS Conf.Measuring and Modeling of Computer Systems, May 1997, pp. 115-122
  8. S. Jihang and X. Zhang, “LIRS: An Efficient Low Inter Reference Recency Set Replacement Policy to Improve Buffer Cache Performance,” Proc. ACM Sigmetrics Conf., ACM Pres, pp. 31-42, 2002.
  9. N. Megiddo and D. S. Modha, “ARC: A Self-Tunning, Low Overhead Replacement Cache,”Proc.Usenix Conf. File and Storage Technologies (FAST 2003), Usenix, 2003, pp.115-130
  10. Y. Zhou and J. F. Philbin, “The Multi-Queue Replacement Algorithm for Second for Second-Level Buffer Caches,” Proc. Usenix Ann. Tech conf. (Usenix 2001), Usenix, 2001, pp. 91-104.
  11. Sorav Bansal and Dharmendra S. Modha, "CAR: Clock with Adaptive Replacement." USENIX File and Storage Technologies (FAST), March 31-April 2, 2004, San Francisco, CA.
  12. Mohamed Zahran. “Cache Replacement Policy Revisited,” In Proceedings of the 6th Workshop on Duplicating Decon-structing, and Debugging, San Diego, CA, USA, June 2007.
  13. J. L. Bentley, D. D. Sleator, R. E. Tarjan, and V. K. Wei, “A locally adaptive data compression scheme,” Comm. ACM, vol. 29, no. 4, pp. 320–330, 1986.
  14. D. Lee, J. Choi, J.-H. Kim, S. H. Noh, S. L. Min, Y. Cho, and C. S. Kim, “LRFU: A spectrum of policies that subsumes the least recently used and least frequently used policies,” IEEE Trans.Computers, vol. 50, no. 12, pp. 1352–1360, 2001.
  15. S. A. Johnson, B. McNutt, and R. Reich, “The making of a standard benchmark for open system storage,” J. Comput. Resource Management, no. 101, pp. 26–32, Winter 2001.
  16. C. Aggarwal, J. L. Wolf, and P. S. Yu. “Caching on the WorldWideWeb,” In IEEE Transactions on Knowledge and Data Engineering, vol. 11, pp. 94-107, 1999.
  17. Yannis Smaragdakis, Scott Kaplan, Paul Wilson, “The EELRU adaptive replacement algorithm”performance Evaluation, v.53 n.2, pp. 93-123, July 2003.
  18. D. Lee, J. Choi, J.-H. Kim, S. H. Noh, S. L. Min, Y. Cho, and C. S. Kim, “On the existence of a spectrum of policies that subsumes the least recently used (lru) and least frequently used (lfu) policies,” in Proc. ACM SIGMETRICS Conf., pp. 134–143, 1999.
  19. T. Johnson and D. Shasha, “2Q: A low overhead high performance buffer management replacement algorithm,” in Proc. VLDB Conf., pp. 297–306, 1994.
  20. S. Albers, S. Arora, and S. Khanna, “Page replacement for general caching problems,” Proceedings of the 10th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 31–40, 1999.
  21. A. S. Tanenbaum and A. S. Woodhull, Operating Systems: Design and Implementation. Prentice-Hall, 1997.
  22. J. E. G. Coffman and P. J. Denning, Operating Systems Theory Englewood Cliffs, NJ: Prentice-Hall, 1973.
  23. www.ecs.umass.edu/ece/koren/architecture, Computer Architecture Educational Tools.
  24. Kaveh Samiee, ”WRP: Weighting Replacement Policy to Improve Cache Performance”, International Journal of Hybrid Information Technology,Vol.2,No.2, April, 2009.
  25. Development of a Virtual Memory Simulator to Analyze the Goodness of Page Replacement Algorithms Fadi N. , Sibai, Maria Ma, David A. Lill
  26. The LRU-K Page Replacement Algorithm For Database Disk Buffering Elizabeth J. O’Neil 1, Patrick E. O’Neill, Gerhard Weikum2 SIGMOD 15193 AVaahin~ton, DC,USA @1993ACM.
  27. http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.set.cortexr/index.html
  28. L. A. Belady, A study of replacement algorithms for a virtual-storage computer, IBM Systems Journal, Volume 5, Issue 2, pp. 78–101 (1966).
Index Terms

Computer Science
Information Sciences

Keywords

Memory Management Cache Performance Replacement Policy Hit Ratio Analysis