Improving Cache Memory Utilization

Authors: Sami I. Serhan, Hamed M. Abdel-Haq

Abstract:

In this paper, an efficient technique is proposed to manage the cache memory. The proposed technique introduces some modifications on the well-known set associative mapping technique. This modification requires a little alteration in the structure of the cache memory and on the way by which it can be referenced. The proposed alteration leads to increase the set size virtually and consequently to improve the performance and the utilization of the cache memory. The current mapping techniques have accomplished good results. In fact, there are still different cases in which cache memory lines are left empty and not used, whereas two or more processes overwrite the lines of each other, instead of using those empty lines. The proposed algorithm aims at finding an efficient way to deal with such problem.

Keywords: Modified Set Associative Mapping, Locality of Reference, Miss Ratio, Hit Ratio, Cache Memory, Clustered Behavior, Index Address, Tag Field, Status Field, and Complement of Index Address.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078211

References:

[1] Mathias Spjuth, Martin Karlsson and Erik, "Cache Memory Design Trade-offs for Current and Emerging Workloads". Licentiate Thesis 2003-009, Department of Information Technology, Uppsala University, September 2003.
[2] M.D. Hill. "Aspects of cache Memory and Instruction Buffer Performance",A PhD thesis presented to the University of California, Berkeley 1987.
[3] A. Agarwal and S.D. Puadar, "Column-Associative Caches: A Technique for Reducing the Miss Ratio of Direct-Mapped Caches", In Proceedings of the 20th International Symposium on Computer Architecture, UK, pages 179-190, May 1993.
[4] A.Seznec and F. Bodin, "Skewed-associative caches", In Proceedings of PARLE '93, Munich, pages 305-316, June 1993.
[5] Ramachandran S. 1999, An algorithmic theory of caches http://216.239.51.100/search?q=cache:KmPHLKLvJlkC:supertech.lcs.mit.edu/~sridhar/thesis.ps+%22cache+model%22&hl=en&ie=UTF-8.
[6] A.Seznec, "A New Case for Skewed-Associativity", A technical Report No. 1114, IRISA-INRIA, Campus de Beaulieu, July 1997.
[7] M. Spjuth, "Refinement and Evaluation of the Elbow Cache", Master's thesis, School of Engineering, Uppsala University, Sweden, April 2002.
[8] L. Barroso, K. Gharachorloo, R. McNamara, A. Nowatzyk, S. Qadeer, B. Sano, S. Smith, R. Stets, and B. Verghese, "Piranha: A scalable World Academy of Science, Engineering and Technology 2 2007303 Architecture Based on Single-Chip Multiprocessing", In Proceeding of the 27th Annual ISCA, USA, pages 149-160, 2000.
[9] A. Seznec, "A Case for Two-way Skewed Associative Caches", In Proceedings of the 20th International Symposium on Computer Architecture, USA , pages 169-178, May 1993.
[10] Yu Y. , K. Beyls and E. H. D'Hollander , "Visualizing the Impact of the Cache on Program Execution", http://citeseer.nj.nec.com/502364.html, 2001.
[11] Nagel P. Topham and Antoio GonZalez, "Randomized Cache Placement for Eliminating Conflicts", IEEE Transactions on Computers, Vol. 48, No.2, pages 185-192, 1999.
[12] Hans Vandierendonck and Koen De Bosschere, "Trade-offs for Skewed- Associative Caches", Proceedings of the International Conference in Parallel Computing (PARCO), Germany, pages 467- 474, September 2003.
[13] William Stallings, Computer Organization and Architecture, seventh edition, Prentice Hall, 2006.
[14] Barry Wilkinson, Computer Architecture, second edition, Prentice Hall, 1996.
[15] Linda Null and Julia Lobur, The essentials of Computer Organization and Architecture, second edition, Jones and Bartlett, 2006.