CATCH: a mechanism for dynamically detecting Cache-Content-Duplication and its application to instruction caches

ABSTRACT

Cache-Content-Duplication (CCD) occurs when there is a miss for a block in a cache and the entire content of the missed block is already in the cache in a block with a different tag. Caches aware of content-duplication can have lower miss rates by allowing only blocks with unique content to enter a cache. This work examines the potential of CCD for instruction caches. We show that CCD is a frequent phenomenon and that an idealized duplication-detection mechanism for instruction caches has the potential to increase performance of an out-of-order processor, with a 2-way eight instruction per block 16KB instruction cache, often by more than 5% and up to 20%. This work also proposes CATCH, a hardware based mechanism for dynamically detecting CCD. Experimental results for an out-of-order processor show that a CATCH with a 2.32KB cost usually captures 60% or more of the CCD's idealized potential.

REFERENCES

• 1: Michael Behar , Avi Mendelson , Avinoam Kolodny, Trace Cache Sampling Filter, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.255-266, September 17-21, 2005 [doi>10.1109/PACT.2005.38]
• 2: Árpád Beszédes , Rudolf Ferenc , Tibor Gyimóthy , André Dolenc , Konsta Karsisto, Survey of code-size reduction methods, ACM Computing Surveys (CSUR), v.35 n.3, p.223-267, September 2003 [doi>10.1145/937503.937504]
• 3: D. Burger and T. Austin. The SimpleScalar tool set: Version 2.0. Technical Report 1342, University of Wisconsin-Madison, June 1997.
• 4: Thomas M. Conte , Kishore N. Menezes , Patrick M. Mills , Burzin A. Patel, Optimization of instruction fetch mechanisms for high issue rates, Proceedings of the 22nd annual international symposium on Computer architecture, p.333-344, June 22-24, 1995, S. Margherita Ligure, Italy
• 5: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 6: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 7: F. Douglis. The Compression Cache: Using On-line Compression to Extend Physical Memory. In USENIX, January 1993.
• 8: Norman P. Jouppi, Retrospective: improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, 25 years of the international symposia on Computer architecture (selected papers), p.71-73, June 27-July 02, 1998, Barcelona, Spain [doi>10.1145/285930.285958]
• 9: Raghavan Komondoor , Susan Horwitz, Using Slicing to Identify Duplication in Source Code, Proceedings of the 8th International Symposium on Static Analysis, p.40-56, July 16-18, 2001
• 10: Charles Lefurgy , Peter Bird , I-Cheng Chen , Trevor Mudge, Improving code density using compression techniques, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.194-203, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 11: Resit Sendag , Peng-fei Chuang , David J. Lilja, Address Correlation: Exceeding the Limits of Locality, IEEE Computer Architecture Letters, v.2 n.1, p.3, January 2003 [doi>10.1109/L-CA.2003.3]
• 12: 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]
• 13: Youtao Zhang , Jun Yang , Rajiv Gupta, Frequent value locality and value-centric data cache design, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.150-159, November 2000, Cambridge, Massachusetts, United States

INDEX TERMS

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

General Terms:
Design, Experimentation, Performance