SEED: scalable, efficient enforcement of dependences

ABSTRACT

Instruction issue logic is a critical component in modern high-performance out-of-order processors. The ever increasing latencies found in modern processors, mostly associated with memory accesses and longer pipelines, can be attenuated using large issue queues. Conventional designs rely on atomic wakeup-select cycles to ensure compact scheduling. These designs must aggressively utilize broadcasting, compaction, and heavily-ported structures that scale poorly in terms of both power consumption and access tim.To provide high scheduling flexibility and large instruction capacity without incurring prohibitive latency and energy overhead, we propose a novel scheme that uses an out-of-order, broadcast-free instruction wakeup block feeding an in-order scheduler. Multi-banked, index-based structures are used throughout this scheme to provide a high degree of scalability while achieving efficient dependence tracking, resulting in good overall performance and energy efficiency. We call this design "Scalable, Efficient Enforcement of Dependences (SEED)". We present a detailed design and analysis of SEED through an extensive evaluation. Compared to a conventional issue queue design, which is assumed favorably to scale in size without any impact on cycle time, the performance degradation of our design is 3% for both INT and FP suites of SPEC CPU2000. For such a small performance cost, SEED enjoys a 19% reduction in total chip power consumption for a 32-entry configuration. We also synthesize SEED and a conventional issue logic with 90nm standard cell logic. Synthesis results show that SEED can cycle twice the speed of a conventional issue logic of equivalent size. Cycling at the same frequency, SEED consumes ten times less dynamic power and five times less static power while achieving substantial area savings.

REFERENCES

• 1: Rajeev Balasubramonian , Sandhya Dwarkadas , David H. Albonesi, Reducing the complexity of the register file in dynamic superscalar processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 2: 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
• 3: Mary D. Brown , Jared Stark , Yale N. Patt, Select-free instruction scheduling logic, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 4: Ramon Canal , Antonio González, A low-complexity issue logic, Proceedings of the 14th international conference on Supercomputing, p.327-335, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335263]
• 5: D. G. Chinnery , K. Keutzer, Closing the gap between ASIC and custom: an ASIC perspective, Proceedings of the 37th conference on Design automation, p.637-642, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337602]
• 6: Compaq Computer Corporation. Alpha 21264/EV6 Microprocessor Hardware Reference Manual, Sept. 2000. Order number: DS-0027B-TE.
• 7: Dan Ernst , Andrew Hamel , Todd Austin, Cyclone: a broadcast-free dynamic instruction scheduler with selective replay, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 8: J. A. Farrell and T. C. Fischer. Issue logic for a 600-MHz Out-of-Order Execution Microprocessor. IEEE Journal of Solid-State Circuits, 33(5):707--712, May 1998.
• 9: Daniele Folegnani , Antonio González, Energy-effective issue logic, Proceedings of the 28th annual international symposium on Computer architecture, p.230-239, June 30-July 04, 2001, Göteborg, Sweden
• 10: Alok Garg , Fernando Castro , Michael Huang , Daniel Chaver , Luis Piñuel , Manuel Prieto, Substituting associative load queue with simple hash tables in out-of-order microprocessors, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165637]
• 11: Alok Garg , M. Wasiur Rashid , Michael Huang, Slackened Memory Dependence Enforcement: Combining Opportunistic Forwarding with Decoupled Verification, Proceedings of the 33rd annual international symposium on Computer Architecture, p.142-154, June 17-21, 2006
• 12: Kanad Ghose, Reducing energy requirements for instruction issue and dispatch in superscalar microprocessors (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.231-233, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344604]
• 13: Masahiro Goshima , Kengo Nishino , Toshiaki Kitamura , Yasuhiko Nakashima , Shinji Tomita , Shin-ichiro Mori, A high-speed dynamic instruction scheduling scheme for superscalar processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 14: Michael K. Gowan , Larry L. Biro , Daniel B. Jackson, Power considerations in the design of the Alpha 21264 microprocessor, Proceedings of the 35th annual conference on Design automation, p.726-731, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277226]
• 15: Michael Huang , Jose Renau , Josep Torrellas, Energy-efficient hybrid wakeup logic, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566456]
• 16: R. Huang, A. Garg, and M. Huang. Software-Hardware Cooperative Memory Disambiguation. In International Symposium on High-Performance Computer Architecture, pages 248--257, Feb. 2006.
• 17: Ilhyun Kim , Mikko H. Lipasti, Half-price architecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 18: Alvin R. Lebeck , Jinson Koppanalil , Tong Li , Jaidev Patwardhan , Eric Rotenberg, A large, fast instruction window for tolerating cache misses, Proceedings of the 29th annual international symposium on Computer architecture, p.59, May 25-29, 2002, Anchorage, Alaska
• 19: Pierre Michaud , André Seznec, Data-Flow Prescheduling for Large Instruction Windows in Out-of-Order Processors, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.27, January 20-24, 2001
• 20: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 21: Dmitry Ponomarev , Gurhan Kucuk , Kanad Ghose, Reducing power requirements of instruction scheduling through dynamic allocation of multiple datapath resources, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 22: Steven E. Raasch , Nathan L. Binkert , Steven K. Reinhardt, A scalable instruction queue design using dependence chains, Proceedings of the 29th annual international symposium on Computer architecture, p.318, May 25-29, 2002, Anchorage, Alaska
• 23: J. Renau et al. SESC simulator, January 2005. http://sesc.sourceforge.net.
• 24: Simha Sethumadhavan , Rajagopalan Desikan , Doug Burger , Charles R. Moore , Stephen W. Keckler, Scalable Hardware Memory Disambiguation for High ILP Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.399, December 03-05, 2003
• 25: P. Shivakumar and N. Jouppi. CACTI 3.0: An integrated cache timing, power and area model. Technical Report 2001/2, Compaq Computer Corporation, August 2001.
• 26: Synopsys Inc. Design Compiler Product Information, 2005. http://www.synopsys.com.
• 27: Synplicity Inc. SynplifyPro Product Information, 2005. http://www.synplicity.com.
• 28: J. Tendler, J. Dodson, J. Fields, H. Le, and B. Sinharoy. POWER4 System Microarchitecture. IBM Journal of Research and Development, 46(1):5--25, Jan. 2002.
• 29: Jessica H. Tseng , Krste Asanović, Banked multiported register files for high-frequency superscalar microprocessors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 30: Nicholas J. Wang , Justin Quek , Todd M. Rafacz , Sanjay J. patel, Characterizing the Effects of Transient Faults on a High-Performance Processor Pipeline, Proceedings of the 2004 International Conference on Dependable Systems and Networks (DSN'04), p.61, June 28-July 01, 2004
• 31: S. Weiss and J. Smith. Instruction Issue Logic in Pipelined Supercomputers. IEEE Transactions on Computers, 33(11):1013--1022, Nov. 1984.
• 32: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 33: V. Zyuban , P. Kogge, Optimization of high-performance superscalar architectures for energy efficiency, Proceedings of the 2000 international symposium on Low power electronics and design, p.84-89, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344522]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Microprocessors and microcomputers

General Terms:
Design

Keywords:
energy-efficient design, issue logic, scalability