Improving superscalar instruction dispatch and issue by exploiting dynamic code sequences

ABSTRACT

Superscalar processors currently have the potential to fetch multiple basic blocks per cycle by employing one of several recently proposed instruction fetch mechanisms. However, this increased fetch bandwidth cannot be exploited unless pipeline stages further downstream correspondingly improve. In particular, register renaming a large number of instructions per cycle is difficult. A large instruction window, needed to receive multiple basic blocks per cycle, will slow down dependence resolution and instruction issue. This paper addresses these and related issues by proposing (i) partitioning of the instruction window into multiple blocks, each holding a dynamic code sequence; (ii) logical partitioning of the register file into a global file and several local files, the latter holding registers local to a dynamic code sequence; (iii) the dynamic recording and reuse of register renaming information for registers local to a dynamic code sequence. Performance studies show these mechanisms improve performance over traditional superscalar processors by factors ranging from 1.5 to a little over 3 for the SPEC Integer programs. Next, it is observed that several of the loops in the benchmarks display vector-like behavior during execution, even if the static loop bodies are likely complex for compile-time vectorization. A dynamic loop vectorization mechanism that builds on top of the above mechanisms is briefly outlined. The mechanism vectorizes up to 60% of the dynamic instructions for some programs, albeit the average number of iterations per loop is quite small.

REFERENCES

• Aus92a: Todd M. Austin , Gurindar S. Sohi, Dynamic dependency analysis of ordinary programs, Proceedings of the 19th annual international symposium on Computer architecture, p.342-351, May 19-21, 1992, Queensland, Australia
• Bur96a: Doug Burger , James R. Goodman , Alain Kägi, Memory bandwidth limitations of future microprocessors, Proceedings of the 23rd annual international symposium on Computer architecture, p.78-89, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• Con95a: Thomas M. Conte , Kishore N. Menezes , Patrick M. Mills , Burzin A. Patel, Optimization of instruction fetch mechanisms for high issue rates, Proceedings of the 22nd annual international symposium on Computer architecture, p.333-344, June 22-24, 1995, S. Margherita Ligure, Italy
• Dit82a: David R. Ditzel , H. R. McLellan, Register allocation for free: The C machine stack cache, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.48-56, March 01-03, 1982, Palo Alto, California, United States
• Fra92a: Manoj Franklin , Gurindar S. Sohi, Register traffic analysis for streamlining inter-operation communication in fine-grain parallel processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.236-245, December 01-04, 1992, Portland, Oregon, United States
• Fra92b: Manoj Franklin , Gurindar S. Sohi, The expandable split window paradigm for exploiting fine-grain parallelsim, Proceedings of the 19th annual international symposium on Computer architecture, p.58-67, May 19-21, 1992, Queensland, Australia
• Fra93a: Manoj Franklin, The multiscalar architecture, University of Wisconsin at Madison, Madison, WI, 1993
• Fra94a: Manoj Franklin , Mark Smotherman, A fill-unit approach to multiple instruction issue, Proceedings of the 27th annual international symposium on Microarchitecture, p.162-171, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192748]
• Fra95a: Simonjit Dutta , Manoj Franklin, Control flow prediction with tree-like subgraphs for superscalar processors, Proceedings of the 28th annual international symposium on Microarchitecture, p.258-263, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• Hao96a: Eric Hao , Po-Yung Chang , Marius Evers , Yale N. Patt, Increasing the instruction fetch rate via block-structured instruction set architectures, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.191-200, December 02-04, 1996, Paris, France
• Hil84a: Mark D. Hill , Alan Jay Smith, Experimental evaluation of on-chip microprocessor cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.158-166, January 1984
• Hwu87a: W. W. Hwu and Y. N. Patt, "Design Choices for the HPSm Microprocessor Chip," in Proc. 20th Annual Hawaii International Conference on System Sciences, Kona, HI, January 1987.
• IBM90a: IBM, "Special Issue on the IBM RISC System/6000 Processor," IBM Journal of Research and Development, January 1990.
• Lam92a: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• Mel88a: S. W. Melvin , M. C. Shebanow , Y. N. Patt, Hardware support for large atomic units in dynamically scheduled machines, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.60-63, November 28-December 02, 1988, San Diego, California, United States
• Mit97a: Tulika Mitra. "Performance Evaluation of Improved Superscalar Issue Mechanisms," in M.E. Project Report, Dept. of Computer Science, Indian Institute of Science, January 1997.
• Pal96a: S. Palacharla. N. Jouppi, and J. E. Smith, "Quantifying the Complexity of Superscalar Processors," Univ. of Wisconsin-Madison Technical Report, vol. CS-T&96- 1328, November 1996, (Available at http:l/www.cs.wisc.edultrs.html; a version to appear in ISCA'97).
• Pat85a: Y. N. Patt , W. M. Hwu , M. Shebanow, HPS, a new microarchitecture: rationale and introduction, Proceedings of the 18th annual workshop on Microprogramming, p.103-108, December 03-06, 1985, Pacific Grove, California, United States
• Pat85b: Y. N. Patt , S. W. Melvin , W. M. Hwu , M. C. Shebanow, Critical issues regarding HPS, a high performance microarchitecture, Proceedings of the 18th annual workshop on Microprogramming, p.109-116, December 03-06, 1985, Pacific Grove, California, United States
• Rot96a: Eric Rotenberg , Steve Bennett , James E. Smith, Trace cache: a low latency approach to high bandwidth instruction fetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.24-35, December 02-04, 1996, Paris, France
• Rus78a: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• Smi84a: James E. Smith, Decoupled access/execute computer architectures, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.289-308, Nov. 1984 [doi>10.1145/357401.357403]
• Smo95a: Mark Smotherman , Manoj Franklin, Improving CISC instruction decoding performance using a fill unit, Proceedings of the 28th annual international symposium on Microarchitecture, p.219-229, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• Spr94a: Eric Sprangle , Yale Patt, Facilitating superscalar processing via a combined static/dynamic register renaming scheme, Proceedings of the 27th annual international symposium on Microarchitecture, p.143-147, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.197407]
• Tom67a: R. M. Tomasulo, "An Efficient Algorithm for Exploiting Multiple Arithmetic Units," IBM Journal of Research and Development, January 1967.
• Uht92a: Augustus K. Uht, Concurrency Extraction Via Hardware Methods Executing the Static Instruction Stream, IEEE Transactions on Computers, v.41 n.7, p.826-841, July 1992 [doi>10.1109/12.256451 ]
• Wal91a: David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
• Wei95a: S. Weiss, Implementation Register Interlocks in Parallel-Pipeline, Multiple Instruction Queue, Superscalar Processors, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.14, January 22-25, 1995
• Yeh93b: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States
• Yeh93a: Tse-Yu Yeh , Deborah T. Marr , Yale N. Patt, Increasing the instruction fetch rate via multiple branch prediction and a branch address cache, Proceedings of the 7th international conference on Supercomputing, p.67-76, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165956]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  C. Computer Systems Organization

General Terms:
Design, Experimentation, Measurement, Performance, Theory