Abstract   In  this  paper,  we  present  a  new  block  replacement  policy  in  which  we  proposed  a  new  efficient  algorithm  for  combining  two  important  policies  Least  Recently  Use d  (LRU)  and  Least  Frequently  Used  (LFU).  The  implem entation  of  the  proposed policy is simple. It requires limited calc ulations to determine the victim block. We proposed  our models to implement  LRU  and  LFU  policies.  The  new  policy  gives  each  blo ck  in  cache  two weighing  values  corresponding  to  LRU  and  LFU  policies.  Then  a  simple  algorithm  is  used  to  get  th e  overall  value  for  each  block.  A  comprehensive  com parison  is  made  between  our  Policy  and  LRU,  First  In  First  Out  (FIF O),  V-WAY,  and  Combined  LRU  and  LFU  (CRF)  policies.   Experimental  results show that the LR+5LF replacement policy  significantly reduces the number of cache misses. W e modified simple scalar  simulator  version  3  under  Linux  Ubuntu  9.04  and  we  used  speccpu2000  benchmark  to  simulate  this  policy.  The  results  of  simulations  showed,  that  giving  higher  weighing  to  LFU  policy  gives  this  policy  best  performance  chara cteristics  over  other  policies. Substantial improvement on miss rate was  achieved on instruction level 1 cache and at level 2 cache memory. 

References

[1] Alghazo J., Akaaboune A., and Botros N., SF0 LRU Cache Replacement Algorithm, in Proceedings of International Workshop on Memory Technology Design and Testing , USA, pp. 19024, 2004.

[2] Belady A., A Study of Replacement Algorithms for Virtual0Storage Computers, Computer Journal of IBM Systems , vol. 5, no. 2, pp. 780 101, 1966.

[3] Hennessy J. and Patterson D., Computer Architecture A Quantitative Approach , Morgan Kaufmann Publishers, 2007.

[4] Jamil T. and Stacpoole R., Cache Memories, IEEE Potentials , vol. 19, no. 2, pp. 24029, 2000.

[5] Kampe M., Stenstrom P., and Dubois M., Self0 Correcting LRU Replacement Policies, in Proceedings of the 1 st Conference on Computing Frontiers , USA, pp. 1810191, 2004.

[6] Kaushik R. and Govindarajan R., Emulating Optimal Replacement with Shepherd Cache, in Proceedings of the 40 th International Symposium on Microarchitecture , Chicago, pp. 4450454, 2007.

[7] Lee D., Choi J., Kim J., Noh S., Min S., Cho Y., and Kim C., LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies, IEEE Transaction on Computers , vol. 50, no. 12, pp. 135201361, 2001.

[8] Mattson L., Gecsei J., Slutz R., and Traiger L., Evaluation Techniques for Storage Hierarchies, Computer Journal of IBM Systems , vol. 9, no. 2, pp. 780117, 1970.

[9] Megiddo N. and Modha D., ARC: A Self0 Tuning, Low Overhead Replacement Cache, in Proceedings of the 2 nd USENIX Symposium on File and Storage Technologies , USA, pp. 1150 130, 2003.

[10] Qureshi K., Aamer J., Yale N., Patt C., Steely J., and Joel E., Adaptive Insertion Policies for High0Performance Caching, in Proceedings of the 34 th International Symp-osium on Computer Architecture , USA, pp. 3810391, 2007.

[11] Qureshi K., Thompson D., and Patt N., The V0 Way Cache: Demand Based Associativity via Global Replacement, in Proceedings of the 32 th International Symposium on Computer Architecture , USA, pp. 5440555, 2005.

[12] Simple Scalar, LLC, available at: http://www.simplescalar.com/, last visited 2010.

[13] Stallings W., Computer Organization and Architecture , Prentice Hall, 2006.

[14] Standard Performance Evaluation Corporation , available at: http://www.spec.org/, last visited 2010.

[15] Wong A. and Baer L., Modified LRU Policies for Improving Second0Level Cache Behavior, in Proceedings of 6 th International Symposium on High-Performance Computer Architecture , France, pp. 49060, 2000.

[16] Yoon J., Min L., and Cho Y., Buffer Cache Management: Predicting the Future from the Past, in Proceedings of International Symposium on Parallel Architecture Algorithms and Networks , Philippines, pp. 92097, 2002.

[17] Zhansheng L., Dawei L., and Huijuan B., CRFP: A Novel Adaptive Replacement Policy Combined the LRU and LFU Policies, in Proceedings of IEEE 8 th International Conference on Computer and Information Technology Workshops , Sydney, pp. 72079, 2008. Adwan AbdelFattah is an assistant professor at the Computer Science Department of the Arab American University of Jenin, Palestine. Previously, he worked at Philadelphia and Zarqa Private University. He received his PhD from the National Technical University of Ukraine in 1996. His research interests include computer networks, computer architecture, cryptography, networks security, authentication and digital signa ture. Aiman Abu Samra is an IEEE and computer society member. He received his PhD from the National Technical University of Ukraine in 1996. Currently, he is an assistant professor at the Computer Engineering Department at the Islamic University of Gaza, Palestine. His research interests include computer architecture, computer networks and software engineering. He managed several funded projects in cooperation with industr y. He teaches several courses on computer architecture and computer networks.