Enhancing Cache Performance Based on Improved Average Access Time

Authors: Jasim. A. Ghaeb

Abstract:

A high performance computer includes a fast processor and millions bytes of memory. During the data processing, huge amount of information are shuffled between the memory and processor. Because of its small size and its effectiveness speed, cache has become a common feature of high performance computers. Enhancing cache performance proved to be essential in the speed up of cache-based computers. Most enhancement approaches can be classified as either software based or hardware controlled. The performance of the cache is quantified in terms of hit ratio or miss ratio. In this paper, we are optimizing the cache performance based on enhancing the cache hit ratio. The optimum cache performance is obtained by focusing on the cache hardware modification in the way to make a quick rejection to the missed line's tags from the hit-or miss comparison stage, and thus a low hit time for the wanted line in the cache is achieved. In the proposed technique which we called Even- Odd Tabulation (EOT), the cache lines come from the main memory into cache are classified in two types; even line's tags and odd line's tags depending on their Least Significant Bit (LSB). This division is exploited by EOT technique to reject the miss match line's tags in very low time compared to the time spent by the main comparator in the cache, giving an optimum hitting time for the wanted cache line. The high performance of EOT technique against the familiar mapping technique FAM is shown in the simulated results.

Keywords: Caches, Cache performance, Hit time, Cache hit ratio, Cache mapping, Cache memory.

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

References:

[1] U. Meyer, p. Sanders and j. Sibeyn, algorithms for memory hierarchies: advanced lectures, springer-verlag, berlin, heidelberg 2003.
[2] M. Kowarschik and C. Weiß, "An Overview of Cache Optimization Techniques and Cache-Aware Numerical Algorithms," Lecture Notes in Computer Science Vol. 2625, pp. 213-232, Springer, 2003.
[3] S. Mamagkakis, D. Atienza , C. Poucet , F. Catthoor , D. Soudris and J. M. Mendias, "Custom Design of Multi-Level Dynamic Memory Management Subsystem for Embedded Systems," Proceedings of the IEEE Workshop on Signal Processing Systems (SIPS'04), vol. 1, No. 1, 2004, pp. 170-175, New York: IEEE Press, 2004.
[4] C. Baloukas, et. al, "Optimization Methodology of Dynamic Data Structures Based on Genetic Algorithms for Multimedia Embedded Systems," Elsevier, the journal of systems and software, Vol. 82, pp.590-602, 2009.
[5] H. Eichenbaum, "Memory Systems," Wiley Interdisciplinary Reviews: Cognitive Science, 1: 478-490. doi: 10.1002/wcs.49, 2010.
[6] M. D. Hill and A. J. Smith, "Evaluating Associatively in CPU Caches," IEEE Transactions on Computers, Vol. 38(12), pp. 1612-1630, 1989.
[7] T. M. Chilimbi, M. D. Hill and James R. Larus, "Cache-Conscious Structure Layout," Proceedings of the ACM SIGPLAN Conference on programming language design and implementation, ISBN:1-58113-094- 5, PLDI ,1999.
[8] W. Stallings, Computer Organization and architecture, 7th Edition, Prentice Hall, 2006.
[9] S. I. Serhan and H. M. Abdel-Haq, "Improving Cache Memory Utilization," World academy of science, engineering and technology, Vol. 26, pp. 299-304, 2007.
[10] N. P. Topham and A. GonZalez, "Randomized Cache Placement for Eliminating Conflicts," IEEE Transactions on Computers, Vol. 48, No.2, pp. 185-192, 1999.
[11] J. H. Bae and C. M. Kyung, "A Supplementary Scheme for Reducing Cache Access Time," IEICE Trans. on inf. and systems, Vol. E79-d, No. 4, pp. 385-389, 1996.
[12] N. P. Jouppi, Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers, IEEE Proceeding, 17th Annual International Symposium on Computer Architecture, Seattle, WA, USA, pp. 364-373, 28-31 May 1990.
[13] S. J. E Wilton and N. P. Jouppi, "CACTI: An Enhanced Cache Access and Cycle Time Model," IEEE Transactions on solid state circuits, Vol. 31, No. 5, pp. 677-688, 1996.
[14] P.F. Lin, "A 0.8-V 128Kb Four-Way Set-Associative Two-Level CMOS Cache Memory Using Two-Stage Wordline/Bitline-oriented Tag- Compare (WLOTC/BLOTC) Scheme," IEEE Journal of Solid-State Circuits Vol. 37, No. 10, pp. 1307-1311, 2002.
[15] Ruud Van DerPas "Memory Hierarchy in Cache Based System," Sun Microsystems, Inc, part .No. 817-0742-10, 2002.
[16] P. Palsodkar, A. Deshmukh, P. Bajaj and A. G. Keskar, An Approach for Four Way Set Associative Multilevel CMOS Cache Memory, Lecture Notes in Computer Science, Vol. 4692, pp. 740-746, DOI: 10.1007/978-3-540-74819-9_91, 2007.
[17] J.B. Rothman and A.J. Smith, Sector cache design and performance, IEEE Proceedings. 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 2000. pp.124-133, San Francisco,CA,2000,doi: 10.1109/MASCOT.2000.876437.
[18] M. Spjuth, Refinement and Evaluation of the Elbow Cache, master's thesis, Department of computer systems, Uppsala University, Sweden, 2002.