Skewed caches from a low-power perspective

ABSTRACT

The common approach to reduce cache conflicts is to increase the associativity. From a dynamic power perspective this associativity comes at a high cost. In this paper we present miss ratio performance and a dynamic power comparison for set-associative caches, a skewed cache and also for a new organization proposed,the elbow cache. The elbow cache extends the skewed cache organization with a relocation strategy for conflicting blocks. We show that these skewed designs significantly reduce the conflict problems while consuming p to 56% less dynamic power than a comparably performing 8-way set associative cache. We believe this to be the strongest case in favor of skewed caches presented so far

REFERENCES

• 1: Sun's Niagara Pours on the Cores.Microprocessor Report Newsletter,September 2004.
• 2: Jaume Abella , Antonio González, Power Efficient Data Cache Designs, Proceedings of the 21st International Conference on Computer Design, p.8, October 13-15, 2003
• 3: 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
• 4: David H. Albonesi, Selective cache ways: on-demand cache resource allocation, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.248-259, November 16-18, 1999, Haifa, Israel
• 5: Brannon Batson , T. N. Vijaykumar, Reactive-Associative Caches, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.49-60, September 08-12, 2001
• 6: L. A. Belady. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal, 5:78--101, 1966.
• 7: Nikolaos Bellas , Ibrahim Hajj , Constantine Polychronopoulos, Using dynamic cache management techniques to reduce energy in a high-performance processor, Proceedings of the 1999 international symposium on Low power electronics and design, p.64-69, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313856]
• 8: François Bodin , André Seznec, Skewed Associativity Improves Program Performance and Enhances Predictability, IEEE Transactions on Computers, v.46 n.5, p.530-544, May 1997 [doi>10.1109/12.589219]
• 9: Magnus Ekman , Per Stenström , Fredrik Dahlgren, TLB and snoop energy-reduction using virtual caches in low-power chip-multiprocessors, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566471]
• 10: Andrew Erlichson , Basem A. Nayfeh , Jaswinder P. Singh , Kunle Olukotun, The benefits of clustering in shared address space multiprocessors: an applications-driven investigation, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.60-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224397]
• 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, p.148, May 25-29, 2002, Anchorage, Alaska
• 12: R. Heald, K. Shin, V. Reddy, I.-F. Kao, M. Khan, W. L. Lynch,G. Lauterbach, and J. Petolino. 64kB Sum-Addressed-Memory Cache with 1.6ns Cycle and 2.6ns Latency.IEEE Journal of Solid-State Circuits 33, page 1682--1689, 1998.
• 13: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
• 14: J. Jalminger and P. Stenström. Improvements of Energy-Efficiency in Off-Chip Caches by Selective Prefetching. Microprocessors and Microsystems, 2001.
• 15: Nigel Topham , Antonio González, Randomized Cache Placement for Eliminating Conflicts, IEEE Transactions on Computers, v.48 n.2, p.185-192, February 1999 [doi>10.1109/12.752660]
• 16: M. Karlsson and E. Hagersten. Timestamp-based Selective Cache Allocation. In Proceedings of the Workshop on Memory Performance Issues, June 2001. held in conjunction with the 28th International Symposium on Computer Architecture (ISCA28).
• 17: Martin Karlsson , Kevin E. Moore , Erik Hagersten , David A. Wood, Memory System Behavior of Java-Based Middleware, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.217, February 08-12, 2003
• 18: 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
• 19: 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]
• 20: Johnson Kin , Munish Gupta , William H. Mangione-Smith, The filter cache: an energy efficient memory structure, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.184-193, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 21: Jack L. Lo , Luiz André Barroso , Susan J. Eggers , Kourosh Gharachorloo , Henry M. Levy , Sujay S. Parekh, An analysis of database workload performance on simultaneous multithreaded processors, Proceedings of the 25th annual international symposium on Computer architecture, p.39-50, June 27-July 02, 1998, Barcelona, Spain
• 22: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 23: Michael D. Powell , Amit Agarwal , T. N. Vijaykumar , Babak Falsafi , Kaushik Roy, Reducing set-associative cache energy via way-prediction and selective direct-mapping, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 24: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 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: A. Seznec. A new case for skewed-associativity. Internal Publication No 1114, IRISA-INRIA, July 1997.
• 27: André Seznec , François Bodin, Skewed-associative Caches, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.304-316, June 14-17, 1993
• 28: P. Shivakumar and N. Jouppi. CACTI 3.0 An integrated Cache Timing, Power and Area Model. Technical Report 2001/2, DEC Western Research Lab, 2001.
• 29: 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
• 30: Hans Vandierendonck and Koen De Bosschere. Trade-offs for Skewed-Associative Caches. In Parallel Computing (PARCO), September 2003.
• 31: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 32: S. Wilton and N. Jouppi. An enhanced access and cycle time model for on-chip caches, 1994.
• 33: Se-Hyun Yang , Babak Falsafi , Michael D. Powell , Kaushik Roy , T. N. Vijaykumar, An Integrated Circuit/Architecture Approach to Reducing Leakage in Deep-Submicron High-Performance I-Caches, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.147, January 20-24, 2001
• 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: Michael Zhang and Krste Asanovic. Highly-Associative Caches for Low-Power Processors. In Proceedings of Kool Chips Workshop held in conjunction with International Symposium on Microarchitecture (MICRO-33), Monterey, CA, December, 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.m Miscellaneous

General Terms:
Performance

Keywords:
CAT, elbow, low-power, skewed caches