Macro-op Scheduling: Relaxing Scheduling Loop Constraints

ABSTRACT

Ensuring back-to-back execution of dependent instructionsin a conventional out-of-order processor requiresscheduling logic that wakes up and selects instructions atthe same rate as they are executed. To sustain high performance,integer ALU instructions typically have single-cyclelatency, consequently requiring scheduling logic withthe same single-cycle latency. Prior proposals have advocatedthe use of speculation in either the wakeup or selectphases to enable pipelining of scheduling logic to achievehigher clock frequency. In contrast, this paper proposesmacro-op scheduling, which systematically removesinstructions with single-cycle latency from the machine bycombining them into macro-ops, and performs nonspeculativepipelined scheduling of multi-cycle operations. Macro-opscheduling also increases the effective size of the schedulingwindow by enabling multiple instructions to occupy asingle issue queue entry. We demonstrate that pipelined 2-cyclemacro-op scheduling performs comparably or evenbetter than atomic scheduling or prior proposals for select-freescheduling.

REFERENCES

• 1: Eric Borch , Srilatha Manne , Joel Emer , Eric Tune, Loose Loops Sink Chips, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.299, February 02-06, 2002
• 2: [2] G. Hinton et al., The microarchitecture of the Pentium 4 processor, Intel Technology Journal Q1, 2001.
• 3: M. S. Hrishikesh , Doug Burger , Norman P. Jouppi , Stephen W. Keckler , Keith I. Farkas , Premkishore Shivakumar, The optimal logic depth per pipeline stage is 6 to 8 FO4 inverter delays, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 4: Dan Ernst , Todd Austin, Efficient dynamic scheduling through tag elimination, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 5: 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
• 6: [6] K. Diefendorff, K7 challenges Intel, Microprocessor Report, Vol. 12, No. 14, 1998.
• 7: 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]
• 8: 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
• 9: 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
• 10: 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, May 25-29, 2002, Anchorage, Alaska
• 11: 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
• 12: 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
• 13: [13] D. C. Burger and T. M. Austin, The Simplescalar tool set, version 2.0, Technical Report CS-TR-97-1342, University of Wisconsin, Madison, 1997.
• 14: [14] A. Kleinosowski, J. Flynn, N. Meares and D. J. Lilja, Adapting the SPEC2000 benchmarks suite for simulation-based computer architecture research, Workshop on Workload Characterization in International Conference on Computer Design, 2000.
• 15: [15] Compaq Computer Corporation, Alpha 21264 microprocessor hardware reference manual, 1999.
• 16: Ho-Seop Kim , James E. Smith, An instruction set and microarchitecture for instruction level distributed processing, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 17: Peter Y. T. Hsu , Joseph T. Rahmeh , Edward S. Davidson , Jacob A. Abraham, TIDBITS: speedup via time-delay bit-slicing in ALU design for VLSI technology, Proceedings of the 12th annual international symposium on Computer architecture, p.29-35, June 17-19, 1985, Boston, Massachusetts, United States
• 18: [18] S. Gochman et al., The Intel Pentium M processor: Microarchitecture and performance, Intel Technology Journal vol. 7, issue 2, 2003.
• 19: 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]
• 20: 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, May 25-29, 2002, Anchorage, Alaska
• 21: Q. Jacobson , J. E. Smith, Instruction Pre-Processing in Trace Processors, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.125, January 09-12, 1999
• 22: Yuan Chou , John Paul Shen, Instruction path coprocessors, Proceedings of the 27th annual international symposium on Computer architecture, p.270-281, June 2000, Vancouver, British Columbia, Canada
• 23: Daniel Holmes Friendly , Sanjay Jeram Patel , Yale N. Patt, Putting the fill unit to work: dynamic optimizations for trace cache microprocessors, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.173-181, November 1998, Dallas, Texas, United States
• 24: Nadeem Malik , Richard J. Eickemeyer , Stamatis Vassiliadis, Interlock collapsing ALU for increased instruction-level parallelism, Proceedings of the 25th annual international symposium on Microarchitecture, p.149-157, December 01-04, 1992, Portland, Oregon, United States
• 25: Yiannakis Sazeides , Stamatis Vassiliadis , James E. Smith, The performance potential of data dependence speculation & collapsing, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.238-247, December 02-04, 1996, Paris, France

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Macro and assembly languages
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Algorithms, Performance