Cache decay: exploiting generational behavior to reduce cache leakage power

ABSTRACT

Power dissipation is increasingly important in CPUs ranging from those intended for mobile use, all the way up to high-performance processors for high-end servers. While the bulk of the power dissipated is dynamic switching power, leakage power is also beginning to be a concern. Chipmakers expect that in future chip generations, leakage's proportion of total chip power will increase significantly.

This paper examines methods for reducing leakage power within the cache memories of the CPU. Because caches comprise much of a CPU chip's area and transistor counts, they are reasonable targets for attacking leakage. We discuss policies and implementations for reducing cache leakage by invalidating and “turning off” cache lines when they hold data not likely to be reused. In particular, our approach is targeted at the generational nature of cache line usage. That is, cache lines typically have a flurry of frequent use when first brought into the cache, and then have a period of “dead time” before they are evicted. By devising effective, low-power ways of deducing dead time, our results show that in many cases we can reduce LI cache leakage energy by 4x in SPEC2000 applications without impacting performance. Because our decay-based techniques have notions of competitive on-line algorithms at their roots, their energy usage can be theoretically bounded at within a factor of two of the optimal oracle-based policy. We also examine adaptive decay-based policies that make energy-minimizing policy choices on a per-application basis by choosing appropriate decay intervals individually for each cache line. Our proposed adaptive policies effectively reduce LI cache leakage energy by 5x for the SPEC2000 with only negligible degradations in performance.

REFERENCES

• 1: J.-L. Baer , W.-H. Wang, On the inclusion properties for multi-level cache hierarchies, Proceedings of the 15th Annual International Symposium on Computer architecture, p.73-80, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 2: Shekhar Borkar, Design Challenges of Technology Scaling, IEEE Micro, v.19 n.4, p.23-29, July 1999 [doi>10.1109/40.782564]
• 3: William J. Bowhill , Shane L. Bell , Bradley J. Benschneider , Andrew J. Black , Sharon M. Britton , Ruben W. Castelino , Dale R. Donchin , John H. Edmondson , Harry R. Fair , Paul E. Gronowski , Anil K. Jain , Patricia L. Kroesen , Marc E. Lamere , Bruce J. Loughlin , Shekhar Mehata , Sribalan Santhanam , Timothy A. Shedd , Stephen C. Thierauf , Robert O. Mueller , Ronald P. Preston , Michael J. Smith, Circuit implementation of a 300-MHz 64-bit second-generation CMOS Alpha CPU, Digital Technical Journal, v.7 n.1, p.100-118, Jan. 1995
• 4: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 5: D. Burger, T. M. Austin, and S. Bennett. Evaluating future microprocessors: the SimpleScalar tool set. Tecfi. Report TR-1308, Univ. of Wisconsin-Madison Computer Sciences Dept., July 1996.
• 6: D. Burger, J. Goodman, and A. Kagi. The declining effectiveness of dynamic caching for general-purpose microprocessors. Tech. Report TR- 1216, Univ. of Wisconsin-Madison Computer Sciences Dept.
• 7: Zhanping Chen , Mark Johnson , Liqiong Wei , Kaushik Roy, Estimation of standby leakage power in CMOS circuits considering accurate modeling of transistor stacks, Proceedings of the 1998 international symposium on Low power electronics and design, p.239-244, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280917]
• 8: Jeffrey Dean , James E. Hicks , Carl A. Waldspurger , William E. Weihl , George Chrysos, ProfileMe: hardware support for instruction-level profiling on out-of-order processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.292-302, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 9: L. Gwennap. Digital 21264 sets new standard. Microprocessor Report, pages 11-16, Oct. 28, 1996.
• 10: Hsien-Hsin S. Lee , Gary S. Tyson , Matthew K. Farrens, Eager writeback - a technique for improving bandwidth utilization, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.11-21, December 2000, Monterey, California, United States [doi>10.1145/360128.360132]
• 11: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 12: IBM Corp. Personal communication. November, 2000.
• 13: Intel Corp. Intel architecture optimization manual.
• 14: J. Adam Butts , Gurindar S. Sohi, A static power model for architects, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.191-201, December 2000, Monterey, California, United States [doi>10.1145/360128.360148]
• 15: Teresa L. Johnson , Daniel A. Connors , Matthew C. Merten , Wen-mei W. Hwu, Run-Time Cache Bypassing, IEEE Transactions on Computers, v.48 n.12, p.1338-1354, December 1999 [doi>10.1109/12.817393]
• 16: Milind B. Kamble , Kanad Ghose, Analytical energy dissipation models for low-power caches, Proceedings of the 1997 international symposium on Low power electronics and design, p.143-148, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263310]
• 17: Anna R. Karlin , Kai Li , Mark S. Manasse , Susan Owicki, Empirical studies of competitve spinning for a shared-memory multiprocessor, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.41-55, October 13-16, 1991, Pacific Grove, California, United States
• 18: S. Kaxiras and C. Young. Coherence communication prediction in shared-memory multiprocessors. In Proc. HPCA-6, Jan. 2000.
• 19: Tracy Kimbrel , Anna R. Karlin, Near-Optimal Parallel Prefetching and Caching, SIAM Journal on Computing, v.29 n.4, p.1051-1082, Feb. 2000 to March 2000 [doi>10.1137/S0097539797326976]
• 20: An-Chow Lai , Babak Falsafi, Selective, accurate, and timely self-invalidation using last-touch prediction, Proceedings of the 27th annual international symposium on Computer architecture, p.139-148, June 2000, Vancouver, British Columbia, Canada
• 21: Alvin R. Lebeck , David A. Wood, Dynamic self-invalidation: reducing coherence overhead in shared-memory multiprocessors, Proceedings of the 22nd annual international symposium on Computer architecture, p.48-59, June 22-24, 1995, S. Margherita Ligure, Italy
• 22: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 23: 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
• 24: Michael Powell , Se-Hyun Yang , Babak Falsafi , Kaushik Roy , T. N. Vijaykumar, Gated-Vdd: a circuit technique to reduce leakage in deep-submicron cache memories, Proceedings of the 2000 international symposium on Low power electronics and design, p.90-95, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344526]
• 25: Theodore H. Romer , Wayne H. Ohlrich , Anna R. Karlin , Brian N. Bershad, Reducing TLB and memory overhead using online superpage promotion, Proceedings of the 22nd annual international symposium on Computer architecture, p.176-187, June 22-24, 1995, S. Margherita Ligure, Italy
• 26: S. Sair and M. Charney. Memory behavior of the SPEC2000 benchmark suite. Technical report, IBM, 2000.
• 27: Semiconductor Industry Association. The International Technology Roadmap for Semiconductors, 1999. hnp://www.semichips.org.
• 28: William Stallings, Operating systems, Macmillan Publishing Co., Inc., Indianapolis, IN, 1992
• 29: The Standard Performance Evaluation Corporation. WWW Site. http://www.spec.org, Dec. 2000.
• 30: U.S. Environmental Protection Agency. Energy Star Program web page. http://www.epa.gov/energystar/.
• 31: Z. Wang , K. S. McKinley , A. L. Rosenberg, Improving Replacement Decisions in Set-Associative Caches TITLE2:, University of Massachusetts, Amherst, MA, 2001
• 32: Kenneth M. Wilson , Kunle Olukotun, Designing high bandwidth on-chip caches, Proceedings of the 24th annual international symposium on Computer architecture, p.121-132, June 01-04, 1997, Denver, Colorado, United States
• 33: David A. Wood , Mark D. Hill , R. E. Kessler, A model for estimating trace-sample miss ratios, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.79-89, May 21-24, 1991, San Diego, California, United States
• 34: 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
• 35: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States
• 36: Marco Zagha , Brond Larson , Steve Turner , Marty Itzkowitz, Performance analysis using the MIPS R10000 performance counters, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.16-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369059]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization

General Terms:
Design, Experimentation, Measurement, Performance, Theory