Power efficient branch prediction through early identification of branch addresses

ABSTRACT

Ever increasing performance requirements have elevated deeply pipelined architectures to a standard even in the embedded processor domain, requiring the incorporation of dynamic branch prediction subsystems to hide the execution latency of control-altering instructions. In this paper a low power early branch identification technique which enables the design of extremely power-efficient branch predictors and BTBs is proposed. Through static extraction of program information regarding the distance to subsequent branches, this technique enables the calculation of the next branch address as soon as the direction of the current branch has been predicted. Early identification of branch addresses enables a complete elimination of the power hungry BTB lookups normally occurring at every execution cycle, as well as a just-in-time wake-up mechanism when accessing "hibernating" entries in complex predictors, switched to power-saving mode to reduce leakage power dissipation. A cost-efficient Branch Identification Unit (BIU) to calculate branch addresses is presented and analyzed in terms of power and timing characteristics. The effectiveness of the proposed BTB access policy and predictor wake-up mechanism is also confirmed by the simulation results of the SPECint 2000 and Media-bench benchmarks.

REFERENCES

• 1: 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
• 2: P. Petrov and A. Orailoglu. Low-power branch target buffer for application-speci c embedded processors. IEE Transactions on Computers &Digital Techniques, 152(4):482--488, July 2005.
• 3: M. Monchiero , G. Palermo , M. Sami , C. Silvano , V. Zaccaria , R. Zafalon, Low-power branch prediction techniques for VLIW architectures: a compiler-hints based approach, Integration, the VLSI Journal, v.38 n.3, p.515-524, January 2005 [doi>l0.1016/j.vlsi.2004.07.012]
• 4: Branch Predictor Prediction: A Power-Aware Branch Predictor for High-Performance Processors, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.458, September 16-18, 2002
• 5: Amirali Baniasadi , Andreas Moshovos, SEPAS: a highly accurate energy-efficient branch predictor, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013250]
• 6: Daniel Chaver , Luis Piñuel , Manuel Prieto , Francisco Tirado , Michael C. Huang, Branch prediction on demand: an energy-efficient solution, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871603]
• 7: 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
• 8: 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
• 9: 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
• 10: 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
• 11: 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
• 12: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• 13: S. McFarling. Combining branch predictors. Tech. Note TN-36, DEC WRL, June 1993.
• 14: 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
• 15: A. Srivastava and A. Eustace. ATOM: A system for building customized program analysis tools. Tech. report, Western Research Lab, March 1994.
• 16: 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]
• 17: P. Shivakumar and N. P. Jouppi. Cacti 3. 0:An integrated cache timing, power and area model. Tech. report, Western Research Lab, Aug. 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

General Terms:
Design, Performance

Keywords:
application-specific processors, dynamic branch prediction, low-power design