Instruction packing: Toward fast and energy-efficient instruction scheduling

ABSTRACT

Traditional dynamic scheduler designs use one issue queue entry per instruction, regardless of the actual number of operands actively involved in the wakeup process. We propose Instruction Packing---a novel microarchitectural technique that reduces both delay and power consumption of the issue queue by sharing the associative part of an issue queue entry between two instructions, each with, at most, one nonready register source operand at the time of dispatch. Our results show that this technique results in 40% reduction of the IQ power and 14% reduction in scheduling delay with negligible IPC degradations.

REFERENCES

• 1: Jaume Abella , Antonio Gonzalez, Low-Complexity Distributed Issue Queue, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.73, February 14-18, 2004 [doi>10.1109/HPCA.2004.10013]
• 2: Aneesh Aggarwal , Manoj Franklin , Oguz Ergin, Defining Wakeup Width for Efficient Dynamic Scheduling, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.36-41, October 11-13, 2004
• 3: Anne Bracy , Prashant Prahlad , Amir Roth, Dataflow Mini-Graphs: Amplifying Superscalar Capacity and Bandwidth, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.18-29, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.15]
• 4: 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
• 5: Edward Brekelbaum , Jeff Rupley , Chris Wilkerson , Bryan Black, Hierarchical Scheduling Windows, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 6: Burger, D. and Austin, T. M. 1997. The simpleScalar tool set: Version 2.0. Technical Report, Department of CS, Univ. of Wisconsin-Madison, June and documentation for all Simple Scaler releases.
• 7: Alper Buyuktosunoglu , David Albonesi , Stanley Schuster , David Brooks , Pradip Bose , Peter Cook, A circuit level implementation of an adaptive issue queue for power-aware microprocessors, Proceedings of the 11th Great Lakes symposium on VLSI, p.73-78, March 2001, West Lafayette, Indiana, United States [doi>10.1145/368122.368807]
• 8: Alper Buyuktosunoglu , Tejas Karkhanis , David H. Albonesi , Pradip Bose, Energy efficient co-adaptive instruction fetch and issue, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 9: 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]
• 10: Ramon Canal , Antonio González, Reducing the complexity of the issue logic, Proceedings of the 15th international conference on Supercomputing, p.312-320, June 2001, Sorrento, Italy [doi>10.1145/377792.377854]
• 11: Compaq Computer Cor. 1999. Alpha. 21264 Microprocessor hardware reference manual. July.
• 12: Adrian Cristal , Daniel Ortega , Josep Llosa , Mateo Valero, Out-of-Order Commit Processors, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.48, February 14-18, 2004 [doi>10.1109/HPCA.2004.10008]
• 13: Todd E. Ehrhart , Sanjay J. Patel, Reducing the Scheduling Critical Cycle Using Wakeup Prediction, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.222, February 14-18, 2004 [doi>10.1109/HPCA.2004.10016]
• 14: Dan Ernst , Todd Austin, Efficient dynamic scheduling through tag elimination, Proceedings of the 29th annual international symposium on Computer architecture, p.37, May 25-29, 2002, Anchorage, Alaska
• 15: Ernst, D. and Austin, T. 2003a. Practical selective replay for reduced-tag schedulers. In Proceedings of the 2nd Workshop on Duplicating, Deconstructing, and Debunking, June.
• 16: 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
• 17: 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
• 18: Jie S. Hu , N. Vijaykrishnan , Mary Jane Irwin, Exploring Wakeup-Free Instruction Scheduling, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.232, February 14-18, 2004 [doi>10.1109/HPCA.2004.10014]
• 19: 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]
• 20: 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]
• 21: 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
• 22: Ilhyun Kim , Mikko H. Lipasti, Macro-op Scheduling: Relaxing Scheduling Loop Constraints, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.277, December 03-05, 2003
• 23: Ilhyun Kim , Mikko H. Lipasti, Understanding Scheduling Replay Schemes, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.198, February 14-18, 2004 [doi>10.1109/HPCA.2004.10011]
• 24: 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
• 25: Yongxiang Liu , Anahita Shayesteh , Gokhan Memik , Glenn Reinman, Scaling the issue window with look-ahead latency prediction, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006240]
• 26: 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
• 27: Merchant, A. and Sager, D. 2001. US patent #6,212,626, assigned to Intel Corp., Computer processor having a checker. April.
• 28: 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
• 29: 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
• 30: Dmitry V. Ponomarev , Gurhan Kucuk , Oguz Ergin , Kanad Ghose , Peter M. Kogge, Energy-efficient issue queue design, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.5, p.789-800, October 2003 [doi>10.1109/TVLSI.2003.814321]
• 31: Energy Efficient Comparators for Superscalar Datapaths, IEEE Transactions on Computers, v.53 n.7, p.892-904, July 2004 [doi>10.1109/TC.2004.29]
• 32: 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
• 33: Sharkey, J. and Ponomarev, D. 2005a. Instruction recirculation: Eliminating counting logic in wakeup-free schedulers. In Proceedings of the Euro-Par Conference.
• 34: Sharkey, J. and Ponomarev, D. 2005b. Non-uniform instruction scheduling. In Proceedings of the Euro-Par Conference.
• 35: Joseph J. Sharkey , Dmitry V. Ponomarev , Kanad Ghose , Oguz Ergin, Instruction packing: reducing power and delay of the dynamic scheduling logic, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA [doi>10.1145/1077603.1077613]
• 36: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 37: Srikanth T. Srinivasan , Ravi Rajwar , Haitham Akkary , Amit Gandhi , Mike Upton, Continual flow pipelines, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 38: Jared Stark , Mary D. Brown , Yale N. Patt, On pipelining dynamic instruction scheduling logic, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.57-66, December 2000, Monterey, California, United States [doi>10.1145/360128.360136]
• 39: Wilcox, K. et al. 1999. Alpha processors: A history of power issues and a look to the future. In Cool-Chips Tutorial, November.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Performance

Keywords:
Issue queue, instruction packing, low power