Implementing branch-predictor decay using quasi-static memory cells

ABSTRACT

With semiconductor technology advancing toward deep submicron, leakage energy is of increasing concern, especially for large on-chip array structures such as caches and branch predictors. Recent work has suggested that larger, aggressive branch predictors can and should be used in order to improve microprocessor performance. A further consideration is that more aggressive branch predictors, especially multiported predictors for multiple branch prediction, may be thermal hot spots, thus further increasing leakage. Moreover, as the branch predictor holds state that is transient and predictive, elements can be discarded without adverse effect. For these reasons, it is natural to consider applying decay techniques---already shown to reduce leakage energy for caches---to branch-prediction structures.Due to the structural difference between caches and branch predictors, applying decay techniques to branch predictors is not straightforward. This paper explores the strategies for exploiting spatial and temporal locality to make decay effective for bimodal, gshare, and hybrid predictors, as well as the branch target buffer (BTB). Furthermore, the predictive behavior of branch predictors steers them towards decay based not on state-preserving, static storage cells, but rather quasi-static, dynamic storage cells. This paper will examine the results of implementing decaying branch-predictor structures with dynamic---appropriately, decaying---cells rather than the standard static SRAM cell.Overall, this paper demonstrates that decay techniques can apply to more than just caches, with the branch predictor and BTB as an example. We show decay can either be implemented at the architectural level, or with a wholesale replacement of static storage cells with quasi-static storage cells, which naturally implement decay. More importantly, decay techniques can be applied and should be applied to other such transient and/or predictive structures.

REFERENCES

• 1: Amit Agarwal , Hai Li , Kaushik Roy, DRG-cache: a data retention gated-ground cache for low power, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514037]
• 2: Navid Azizi , Andreas Moshovos , Farid N. Najm, Low-leakage asymmetric-cell SRAM, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566422]
• 3: Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States [doi>10.1145/360128.360153]
• 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: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 6: Po-Ying Chang , Eric Hao , Yale N. Patt, Alternative implementations of hybrid branch predictors, Proceedings of the 28th annual international symposium on Microarchitecture, p.252-257, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 7: Diefendorff, K. 1999. Pentium III = Pentium II + SSE. Microprocessor Report.
• 8: P. W. Diodato , Y.-H. Wong , C.-T Liu , K.-H. Lee , R. Dail , W. S. Lindenberger , A. C.. .. Dumbri , M. V. Depaolis , J. T. Clemens , W. W. Troutman , K. Noda , J. M. Drynan , M. Nakamae, Merged Dram-Logic In The Year 2001, Proceedings of the 1998 IEEE International Workshop on Memory Technology, Design and Testing, p.24, August 24-25, 1998
• 9: Diodato, P. et al. 2001. Embedded DRAM: An element and circuit evaluation. In IEEE Custom Integrated Circuits Conference.
• 10: Diodato, P. W. 2001. Personal communication.
• 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: Gwennap, L. 1996. Digital 21264 sets new standard. Microprocessor Report, 11--16.
• 13: Hanamura, S. et al. 1987. A 256K CMOS SRAM with internal refresh. In The 1987 IEEE International Solid-State Circuits Conference.
• 14: Static Energy Reduction Techniques for Microprocessor Caches, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.276, September 23-26, 2001
• 15: Seongmoo Heo , Kenneth Barr , Mark Hampton , Krste Asanović, Dynamic fine-grain leakage reduction using leakage-biased bitlines, Proceedings of the 29th annual international symposium on Computer architecture, p.137, May 25-29, 2002, Anchorage, Alaska
• 16: Holgate, R. W. and Ibbett, R. N. 1980. An analysis of instruction fetching strategies in pipelined computers. IEEE Transactions on Computers C-29, 4 (Apr.), 325--329.
• 17: Applying Decay Strategies to Branch Predictors for Leakage Energy Savings, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.442, September 16-18, 2002
• 18: Zhigang Hu , Philo Juang , Phil Diodato , Stefanos Kaxiras , Kevin Skadron , Margaret Martonosi , Douglas W. Clark, Managing leakage for transient data: decay and quasi-static 4T memory cells, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566423]
• 19: Zhigang Hu , Philo Juang , Kevin Skadron , Douglas W. Clark , Margaret Martonosi, Applying Decay Strategies to Branch Predictors for Leakage Energy Savings, University of Virginia, Charlottesville, VA, 2001
• 20: Zhigang Hu , Stefanos Kaxiras , Margaret Martonosi, Let caches decay: reducing leakage energy via exploitation of cache generational behavior, ACM Transactions on Computer Systems (TOCS), v.20 n.2, p.161-190, May 2002 [doi>10.1145/507052.507055]
• 21: Hu, Z., Kaxiras, S., and Martonosi, M. 2003. Timekeeping techniques for predicting and optimizing memory behavior. In The 2003 IEEE International Solid-State Circuits Conference.
• 22: 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]
• 23: Daniel A. Jiménez , Stephen W. Keckler , Calvin Lin, The impact of delay on the design of branch predictors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.67-76, December 2000, Monterey, California, United States [doi>10.1145/360128.360137]
• 24: Juang, P. et al. 2002. Implementing decay techniques using 4T quasi-static memory cells. Comput. Arch. Lett.
• 25: Stefanos Kaxiras , Zhigang Hu , Girija J. Narlikar , Rae McLellan, Cache-Line Decay: A Mechanism to Reduce Cache Leakage Power, Proceedings of the First International Workshop on Power-Aware Computer Systems-Revised Papers, p.82-96, November 12, 2000
• 26: 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
• 27: Ali Keshavarzi , Kaushik Roy , Charles F. Hawkins, Intrinsic Leakage in Low-Power Deep Submicron CMOS ICs, Proceedings of the IEEE International Test Conference, p.146-155, November 03-05, 1997
• 28: An-Chow Lai , Cem Fide , Babak Falsafi, Dead-block prediction & dead-block correlating prefetchers, Proceedings of the 28th annual international symposium on Computer architecture, p.144-154, June 30-July 04, 2001, Göteborg, Sweden
• 29: L. Li , Ismail Kadayif , Yuh-Fang Tsai , Narayanan Vijaykrishnan , Mahmut T. Kandemir , Mary Jane Irwin , Anand Sivasubramaniam, Leakage Energy Management in Cache Hierarchies, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.131-140, September 22-25, 2002
• 30: Yingmin Li , Dharmesh Parikh , Yan Zhang , Karthik Sankaranarayanan , Mircea Stan , Kevin Skadron, State-Preserving vs. Non-State-Preserving Leakage Control in Caches, Proceedings of the conference on Design, automation and test in Europe, p.10022, February 16-20, 2004
• 31: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 32: Losq, J. J. 1982. Generalized history table for branch prediction. IBM Tech. Discl. Bull. 25, 1 (June), 99--101.
• 33: Lyons, R. et al. 1987. CMOS static memory with a new four-transistor memory cell. In Proceedings of the 1987 Stanford Conference On Advanced Research in VLSI. 111--132.
• 34: McFarling, S. 1993. Combining branch predictors. Tech. Note TN-36, DEC WRL.
• 35: Noda, K. et al. 1998. A 1.9 μm2 loadless CMOS four-transistor SRAM cell in a 0.18 μm logic technology. IEDM Tech. Dig., 847--850.
• 36: Dharmesh Parikh , Kevin Skadron , Yan Zhang , Marco Barcella , Mircea R. Stan, Power Issues Related to Branch Prediction, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.233, February 02-06, 2002
• 37: 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]
• 38: Roy, K. 1998. Leakage power reduction in low-voltage CMOS designs. In Proceedings of the International Conference on Electronics, Circuits, and Systems. 167--73.
• 39: Karthik Sankaranarayanan , Kevin Skadron, Profile-based adaptation for cache decay, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.3, p.305-322, September 2004 [doi>10.1145/1022969.1022972]
• 40: Schuster, S., Terman, L., and Franch, R. 1987. A 4-device CMOS static RAM cell using sub-threshold conduction. In Symposium on VLSI Technology, Systems, and Applications.
• 41: Semiconductor Industry Association. 2001. From website: The international technology roadmap for semiconductors. Available at http://public.itrs.net/Files/2001ITRS/Home.htm.
• 42: André Seznec , Stephen Felix , Venkata Krishnan , Yiannakis Sazeides, Design tradeoffs for the Alpha EV8 conditional branch predictor, Proceedings of the 29th annual international symposium on Computer architecture, p.295, May 25-29, 2002, Anchorage, Alaska
• 43: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 44: Song, P. 1997. UltraSparc-3 aims at MP servers. Microprocessor Report, 29--34.
• 45: The Standard Performance Evaluation Corporation. 2000. Available at http://www.spec.org.
• 46: Velusamy, S. et al. 2002. Adaptive cache decay using formal feedback control. In Proceedings of the 2002 Workshop on Memory Performance Issues. In conjunction with ISCA-29).
• 47: Wayne Wolf, Modern VLSI design (2nd ed.): systems on silicon, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 48: Se-Hyun Yang , Babak Falsafi , Michael D. Powell , T. N. Vijaykumar, Exploiting Choice in Resizable Cache Design to Optimize Deep-Submicron Processor Energy-Delay, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.151, February 02-06, 2002
• 49: 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
• 50: W. Zhang , J. S. Hu , V. Degalahal , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Compiler-directed instruction cache leakage optimization, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 51: Huiyang Zhou , Mark C. Toburen , Eric Rotenberg , Thomas M. Conte, Adaptive mode control: A static-power-efficient cache design, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.347-372, August 2003 [doi>10.1145/860176.860181]
• 52: Huiyang Zhou , Mark C. Toburen , Eric Rotenberg , Thomas M. Conte, Adaptive Mode Control: A Static-Power-Efficient Cache Design, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.61, September 08-12, 2001

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories

General Terms:
Design, Performance

Keywords:
Energy aware computing