Cache Memory: An Analysis on Replacement Algorithms and Optimization Techniques.

Qaisar Javaid; AYESHA ZAFAR; Muhammad Awais; Munam Ali Shah

Author(s)

Qaisar Javaid Department of Computer Science & Software Engineering, International Islamic University, Islamabad, Pakistan

AYESHA ZAFAR Department of Computer Science, COMSATS Institute of Information Technology, Islamabad, Pakistan

Muhammad Awais Department of Computer Science, COMSATS Institute of Information Technology, Islamabad, Pakistan

Munam Ali Shah Department of Computer Science, COMSATS Institute of Information Technology, Islamabad, Pakistan

Abstract

Caching strategies can improve the overall performance of a system by allowing the fast processor and slow memory to at a same pace. One important factor in caching is the replacement policy.Advancement in technology results in evolution of a huge number of techniques and algorithms implemented to improve cache performance. In this paper, analysis is done on different cache optimization techniques as well as replacement algorithms. Furthermore this paper presents a comprehensive statistical comparison of cache optimization techniques.To the best of our knowledge there is no numerical measure which can tell us the rating of specific cache optimization technique. We tried to come up with such a numerical figure. By statistical comparison we find out which technique is more consistent among all others. For said purpose we calculated mean and CV (Coefficient of Variation). CV tells us about which technique is more consistent. Comparative analysis of different techniques shows that victim cache has more consistent technique among all.

Publication Details

Page(s) 831-840

DOI DOI not available

Published Journal: Mehran University Research Journal of Engineering and Technology, Volume: 36, Issue: 4, Year: 2017

Request the full text from PASTIC

Keywords

optimization, Cache Hti, Threshold, Cache Miss, Miss Latency, Recency

References

Gagged , G.,Paresh , R.,Madarkar , J., “Survey on Chavan, A.S.,Nayak , K.R.,Vora , K.D.,Purohit , M.D.,Chawan , P.M., 2011.“A Comparison of Page Replacement Algorithms”,International Journal of Engineering and Technology, Volume3, No. 2 171 -174

Bansal , S.,Modha , D.S., 2004.Clock with Adaptive Replacement”,Proceedings of 3rd USENIX Conference on File and Storage Technologies 4 187 -200

Megiddo , N.,Modha , D.S., 2004.Outperforming LRU with an Adaptive Replacement Cache Algorithm”,Computer 37 58 -65

Megiddo , N.,Modha , D.S.,A SimpleAdaptive Cache Algorithm Outperforms,LRU, 2003.,IBM Research Report, Computer Science -

Butt , A.R.,Gniady , C.,Hu , Y.C., 2005.The Performance Impact of Kernel Prefetching on Buffer Cache Replacement Algorithms”,ACM SIGMETRICS Performance Evaluation Review 37 157 -168

October,Janapsatya , A.,Ignjatoviae , A.,Peddersen , J.,Parameswaran , S.,DuelingCLOCK, 2010.Adaptive Cache Replacement Policy Based on The CLOCK Algorithm”,Proceedings of Conference on Design, Automation and Test in Europe 36 920 -925

Bhattacharjee , A.,Debnath , B.K., 2005.“A New Web Cache Replacement Algorithm”,Proceedings of IEEE Conference on Pacific Rim Conference on Communications, Computers and Signal Processing 420 -423

Gao , H.,Wilkerson , C., 2010.“A Dueling Segmented LRU Replacement Algorithm with Adaptive Bypassing”,1st JILP Worshop on Computer Architecture Competitions: Cache Replacement Championship -

Morales , K.,Lee , B.K., 2012.Fixed Segmented LRU Cache Replacement Scheme with Selective Caching”,IEEE Proceedings of 31st International Conference on Performance Computing and Communications 199 -200

Abdel F.A. , and Samra,A.A., 2012.Least Recently Plus Five Least Frequently Replacement Policy (LR+5LF )”,International Arabic Journal of Information Technology 9 16 -21

Wang , Q.,“WLRU CPU Cache ReplacementAlgorithm”,DoctoralDissertation, 2006., -

Ding , X.,Wang , K.,Zhang, 2011.ULCC: A UserLevel Facility for Optimizing Shared Cache Performance on Multicores”,ACM Sigplan Notices 46 103 -112

Sandberg , A.,Eklöv , D.,Hagersten, 2010.Reducing Cache Pollution Through Detection and Elimination of Non-Temporal Memory Accesses”,Proceedings of IEEE Conference on High Performance Computing, Networking, Storage and Analysis 1 -11

2003., 64 -76

Beckmann , N.,Sanchez , D, 2013.Jigsaw: Scalable Software-Defined Caches”,Proceedings of IEEE 22nd International Conference on Parallel Architectures and Compilation Techniques 213 -224

Kim , C.,Burger , D.,Keckler , S.W., 2002.An Adaptive, Non-Uniform Cache Structure for Wire-Delay Dominated On-Chip Caches”,ACM Sigplan Notices 10 211 -222

Wang , Z.,McKinley , K.S.,Rosenberg , A.L.,Weems , C.C., 2002.Using the Compiler to Improve Cache Replacement Decisions”,Proceedings of IEEE International Conference on Parallel Architectures and Compilation Techniques 199 -208

Calder , B.,Grunwald , D.,Emer, 1996.,Proceedings of IEEE 2nd International Symposium on High-Performance Computer Architecture 244 -253

VanderWiel , S.,Lilja , D.J., 1996.A Survey of Data Prefetching Techniques”,Proceedings of the 23rd International Symposium on Computer Architecture -

Huang , C.C.,Nagarajan, 2014.Increasing Cache Capacity via Critical-Words-Only Cache”,Proceedings of IEEE 32nd International Conference on Computer Design (ICCD) 125 -132

Sawant , R.,Ramaprasad , B.H.,Govindwar , S.,Mothe, 2010.“Memory Hierarchies-Basic Design and Optimization Techniques Survey on Memory Hierarchies - Basic Design, -

Agarwal , A.,Pudar,Column-AssociativeCaches,ACM, 1993.Caches A Technique for Reducing the Miss Rate of Direct-Mapped”, 21 179 -190

Batson , B.,Vijaykumar , T.N., 2001.Reactive-Associative Caches”,Proceedings of IEEE International Conference on Parallel Architectures and Compilation Techniques 49 -60

Stiliadis , D.,Varma , A., 1997.Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches”,IEEE Transactions on Computers 46 603 -610

Bershad , B.N.,Lee , D.,Romer , T.H.,Chen , J.B., 1994.Avoiding Conflict Misses Dynamically in Large DirectMapped Caches”,ACM SIGPLAN Notices 11 158 -170

Ramaswamy , S.,Yalamanchili , S., 2007.,Proceedings of IEEE 25th International Conference on Computer Design (ICCD) 47 -54

Calder, B., Grunwald, D., and Emer, J.,”Predictive Sequential Associative Cache”, Proceedings of IEEE 2nd International Symposium on High-Performance Computer Architecture, pp. 244-253, 1996.

VanderWiel, S., and Lilja, D.J., “A Survey of Data Prefetching Techniques”, Proceedings of the 23rd International Symposium on Computer Architecture, 1996.

Huang, C.C., and Nagarajan, V., “Increasing Cache Capacity via Critical-Words-Only Cache”, Proceedings of IEEE 32nd International Conference on Computer Design (ICCD), pp. 125-132, 2014.

Sawant, R., Ramaprasad, B.H., Govindwar, S., and Mothe, N., “Memory Hierarchies-Basic Design and Optimization Techniques Survey on Memory Hierarchies – Basic Design and Cache Optimization Techniques”, 2010.

Agarwal, A., and Pudar, S.D., “Column-Associative Caches: Caches A Technique for Reducing the Miss Rate of Direct-Mapped”, ACM, Volume 21, No. 2, pp. 179-190, 1993.

Batson, B., and Vijaykumar, T.N., “Reactive-Associative Caches”, Proceedings of IEEE International Conference on Parallel Architectures and Compilation Techniques, pp. 49-60, 2001.

Stiliadis, D., and Varma, A., “Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches”, IEEE Transactions on Computers, Volume 46, No. 5, pp. 603–610, 1997.

Bershad, B.N., Lee, D., Romer, T.H., and Chen, J.B., “Avoiding Conflict Misses Dynamically in Large Direct- Mapped Caches”, ACM SIGPLAN Notices, Volume 29, No. 11, pp. 158-170, 1994.

Ramaswamy, S., and Yalamanchili, S., “Improving Cache Efficiency via Resizing + Remapping”, Proceedings of IEEE 25th International Conference on Computer Design (ICCD), pp. 47–54, 2007.