Reducing cache misses through programmable decoders

ABSTRACT

Level-one caches normally reside on a processor's critical path, which determines clock frequency. Therefore, fast access to level-one cache is important. Direct-mapped caches exhibit faster access time, but poor hit rates, compared with same sized set-associative caches because of nonuniform accesses to the cache sets. The nonuniform accesses generate more cache misses in some sets, while other sets are underutilized. We propose to increase the decoder length and, hence, reduce the accesses to heavily used sets without dynamically detecting the cache set usage information. We increase the access to the underutilized cache sets by incorporating a replacement policy into the cache design using programmable decoders. On average, the proposed techniques achieve as low a miss rate as a traditional 4-way cache on all 26 SPEC2K benchmarks for the instruction and data caches, respectively. This translates into an average IPC improvement of 21.5 and 42.4% for SPEC2K integer and floating-point benchmarks, respectively. The B-Cache consumes 10.5% more power per access, but exhibits a 12% total memory access-related energy savings as a result of the miss rate reductions, and, hence, the reduction to applications' execution time. Compared with previous techniques that aim at reducing the miss rate of direct-mapped caches, our technique requires only one cycle to access all cache hits and has the same access time of a direct-mapped cache.

REFERENCES

• 1: Anant Agarwal , Stephen D. Pudar, Column-associative caches: a technique for reducing the miss rate of direct-mapped caches, Proceedings of the 20th annual international symposium on Computer architecture, p.179-190, May 16-19, 1993, San Diego, California, United States
• 2: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 3: Amit Agarwal , Kaushik Roy , T. N. Vijaykumar, Exploring High Bandwidth Pipelined Cache Architecture for Scaled Technology, Proceedings of the conference on Design, Automation and Test in Europe, p.10778, March 03-07, 2003
• 4: Brian N. Bershad , Dennis Lee , Theodore H. Romer , J. Bradley Chen, Avoiding conflict misses dynamically in large direct-mapped caches, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.158-170, October 05-07, 1994, San Jose, California, United States
• 5: Burger, D. and Austin, T. M. 1997. The SimpleScalar Tool Set, Version 2.0. Univ. of Wisconsin-Madison Computer Sciences Dept. Technical Report #1342, June.
• 6: Cadence Corporation. http://www.cadence.com
• 7: B. Calder , D. Grunwald , J. Emer, Predictive sequential associative cache, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.244, February 03-07, 1996
• 8: Byung-Kwon Chung , Jih-Kwon Peir, LRU-based column-associative caches, ACM SIGARCH Computer Architecture News, v.26 n.2, p.9-17, May 1998 [doi>10.1145/278677.278689]
• 9: Malcolm C. Easton , Ronald Fagin, Cold-start vs. warm-start miss ratios, Communications of the ACM, v.21 n.10, p.866-872, Oct. 1978 [doi>10.1145/359619.359634]
• 10: Aristides Efthymiou , Jim D. Garside, An adaptive serial-parallel CAM architecture for low-power cache blocks, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566445]
• 11: Krisztián Flautner , Nam Sung Kim , Steve Martin , David Blaauw , Trevor Mudge, Drowsy caches: simple techniques for reducing leakage power, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 12: Kanad Ghose , Milind B. Kamble, Reducing power in superscalar processor caches using subbanking, multiple line buffers and bit-line segmentation, Proceedings of the 1999 international symposium on Low power electronics and design, p.70-75, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313860]
• 13: Tony Givargis, Improved indexing for cache miss reduction in embedded systems, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776052]
• 14: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 15: Toni Juan , Tomás Lang , Juan J. Navarro, The difference-bit cache, Proceedings of the 23rd annual international symposium on Computer architecture, p.114-120, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 16: Stefanos Kaxiras , Zhigang Hu , Margaret Martonosi, Cache decay: exploiting generational behavior to reduce cache leakage power, Proceedings of the 28th annual international symposium on Computer architecture, p.240-251, June 30-July 04, 2001, Göteborg, Sweden
• 17: Mazen Kharbutli , Keith Irwin , Yan Solihin , Jaejin Lee, Using Prime Numbers for Cache Indexing to Eliminate Conflict Misses, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.288, February 14-18, 2004 [doi>10.1109/HPCA.2004.10015]
• 18: R. E. Kessler , R. Jooss , A. Lebeck , M. D. Hill, Inexpensive implementations of set-associativity, Proceedings of the 16th annual international symposium on Computer architecture, p.131-139, April 1989, Jerusalem, Israel
• 19: Lishing Liu, Cache designs with partial address matching, Proceedings of the 27th annual international symposium on Microarchitecture, p.128-136, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192742]
• 20: Naffziger, S. D., Colon-Bonet, G., Fischer, T., Riedlinger, R., Sullivan, T. J., and Grutkowski, T. 2002. The implementation of the Itanium 2 microprocessor. IEEE Journal of Solid-State Circuits 37, 11.
• 21: Jih-Kwon Peir , Windsor W. Hsu , Honesty Young , Shauchi Ong, Improving cache performance with balanced tag and data paths, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.268-278, October 01-04, 1996, Cambridge, Massachusetts, United States
• 22: Jih-Kwon Peir , Yongjoon Lee , Windsor W. Hsu, Capturing dynamic memory reference behavior with adaptive cache topology, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.240-250, October 02-07, 1998, San Jose, California, United States
• 23: Reinmann, G. and Jouppi, N. P. 1999. CACTI2.0: An Integrated Cache Timing and Power Model. COMPAQ Western Research Lab.
• 24: Santhanam, S. et al. 1998. A low-cost, 300-MHz, RISC CPU with attached media processor. IEEE Journal of Solid-State Circuits 33, 11, 1829--1839.
• 25: André Seznec, A case for two-way skewed-associative caches, Proceedings of the 20th annual international symposium on Computer architecture, p.169-178, May 16-19, 1993, San Diego, California, United States
• 26: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 27: Standard Performance Evaluation Corporation. http://www.specbench.org/osg/cpu2000/.
• 28: Sun Microsystems, Inc. 2006. http://www.sun.com/servers/entry/v210/datasheet.pdf.
• 29: Weaver, C. T. Pre-compiled SPEC2000 Alpha Binaries. Available at: http://www.simplescalar.org.
• 30: Maurice V. Wilkes, The memory wall and the CMOS end-point, ACM SIGARCH Computer Architecture News, v.23 n.4, p.4-6, Sept. 1995 [doi>10.1145/218864.218865]
• 31: Wm. A. Wulf , Sally A. McKee, Hitting the memory wall: implications of the obvious, ACM SIGARCH Computer Architecture News, v.23 n.1, p.20-24, March 1995 [doi>10.1145/216585.216588]
• 32: Yoshimoto, M. et al. 1983. A divided word-line structure in the static RAM and its application to a 64k full CMOS RAM. IEEE J. Solid-State Circuits SC-21, 479--485.
• 33: Chuanjun Zhang, Balanced Cache: Reducing Conflict Misses of Direct-Mapped Caches, Proceedings of the 33rd annual international symposium on Computer Architecture, p.155-166, June 17-21, 2006
• 34: Chuanjun Zhang , Frank Vahid , Walid Najjar, A highly configurable cache architecture for embedded systems, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 35: Chuanjun Zhang , Frank Vahid , Jun Yang , Walid Najjar, A way-halting cache for low-energy high-performance systems, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.1, p.34-54, March 2005 [doi>10.1145/1061267.1061270]
• 36: Chenxi Zhang , Xiaodong Zhang , Yong Yan, Two Fast and High-Associativity Cache Schemes, IEEE Micro, v.17 n.5, p.40-49, September 1997 [doi>10.1109/40.621212]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Design, Experimentation, Performance

Keywords:
Cache, dynamic optimization, low power