Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor

ABSTRACT

Simultaneous multithreading is a technique that permits multiple independent threads to issue multiple instructions each cycle. In previous work we demonstrated the performance potential of simultaneous multithreading, based on a somewhat idealized model. In this paper we show that the throughput gains from simultaneous multithreading can be achieved without extensive changes to a conventional wide-issue superscalar, either in hardware structures or sizes. We present an architecture for simultaneous multithreading that achieves three goals: (1) it minimizes the architectural impact on the conventional superscalar design, (2) it has minimal performance impact on a single thread executing alone, and (3) it achieves significant throughput gains when running multiple threads. Our simultaneous multithreading architecture achieves a throughput of 5.4 instructions per cycle, a 2.5-fold improvement over an unmodified superscalar with similar hardware resources. This speedup is enhanced by an advantage of multithreading previously unexploited in other architectures: the ability to favor for fetch and issue those threads most efficiently using the processor each cycle, thereby providing the "best" instructions to the processor.

REFERENCES

• 1: Anant Agarwal , Beng-Hong Lim , David Kranz , John Kubiatowicz, APRIL: a processor architecture for multiprocessing, Proceedings of the 17th annual international symposium on Computer Architecture, p.104-114, May 28-31, 1990, Seattle, Washington, United States
• 2: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• 3: Carl J. Beckmann , Constantine D. Polychronopoulos, Microarchitecture support for dynamic scheduling of acyclic task graphs, Proceedings of the 25th annual international symposium on Microarchitecture, p.140-148, December 01-04, 1992, Portland, Oregon, United States
• 4: B. Calder , D. Grunwald, Fast and accurate instruction fetch and branch prediction, Proceedings of the 21ST annual international symposium on Computer architecture, p.2-11, April 18-21, 1994, Chicago, Illinois, United States
• 5: 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
• 6: G.E. Daddis, Jr. and H.C. Tomg. The concurrent execution of multiple instruction streams on superscalar processors. In International Conference on Parallel Processing, pages I:76- 83, August 1991.
• 7: Kaivalya M. Dixit, New CPU benchmark suites from SPEC, Proceedings of the thirty-seventh international conference on COMPCON, p.305-310, January 1992, San Francisco, California, United States
• 8: J. Edmondson and R Rubinfield. An overview of the 21164 AXP microprocessor. In Hot Chips VI, pages 1-8, August 1994.
• 9: Marco Fillo , Stephen W. Keckler , William J. Dally , Nicholas P. Carter , Andrew Chang , Yevgeny Gurevich , Whay S. Lee, The M-Machine multicomputer, Proceedings of the 28th annual international symposium on Microarchitecture, p.146-156, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 10: R. Govindarajan , S. S. Nemawarkar , P. LeNir, Design and performance evaluation of a multithreaded architecture, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.298, January 22-25, 1995
• 11: Manu Gulati , Nader Bagherzadeh, Performance Study of a Multithreaded Superscalar Microprocessor, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.291, February 03-07, 1996
• 12: B.K. Gunther. Superscalarperformance in a multithreaded microprocessor. PhD thesis, University of Tasmania, December 1993.
• 13: Hiroaki Hirata , Kozo Kimura , Satoshi Nagamine , Yoshiyuki Mochizuki , Akio Nishimura , Yoshimori Nakase , Teiji Nishizawa, An elementary processor architecture with simultaneous instruction issuing from multiple threads, Proceedings of the 19th annual international symposium on Computer architecture, p.136-145, May 19-21, 1992, Queensland, Australia
• 14: Stephem W. Keckler , William J. Dally, Processor coupling: integrating compile time and runtime scheduling for parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.202-213, May 19-21, 1992, Queensland, Australia
• 15: James Laudon , Anoop Gupta , Mark Horowitz, Interleaving: a multithreading technique targeting multiprocessors and workstations, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.308-318, October 05-07, 1994, San Jose, California, United States
• 16: Yamin Li , Wanming Chu, The effects of STEF in finely parallel multithreaded processors, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.318, January 22-25, 1995
• 17: P. Geoffrey Lowney , Stefan M. Freudenberger , Thomas J. Karzes , W. D. Lichtenstein , Robert P. Nix , John S. O'Donnell , John Ruttenberg, The multiflow trace scheduling compiler, The Journal of Supercomputing, v.7 n.1-2, p.51-142, May 1993 [doi>10.1007/BF01205182]
• 18: S. McFarling. Combining branch predictors. TechnicalReport TN-36, DEC-WRL, June 1993.
• 19: R.G. Prasadh and C.-L. Wu. A benchmark evaluation of a multi-threaded RISC processor architecture. In International Conference on Parallel Processing, pages I:84-91, August 1991.
• 20: Microprocessor Report, October 24 1994.
• 21: Microprocessor Report, November 14 1994.
• 22: E.G. Sirer. Measuring limits of fine-grained parallelism. Senior Independent Work, Princeton University, June 1993.
• 23: B.J. Smith. Architecture and applications ofthe HEP multiprocessor computer system. In SPIE Real Time Signal Processing /V, pages 241-248, 1981.
• 24: M. D. Smith , M. Johnson , M. A. Horowitz, Limits on multiple instruction issue, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.290-302, April 03-06, 1989, Boston, Massachusetts, United States
• 25: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 26: Gurindar S. Sohi , Manoj Franklin, High-bandwidth data memory systems for superscalar processors, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.53-62, April 08-11, 1991, Santa Clara, California, United States
• 27: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 28: Wayne Yamamoto , Mario Nemirovsky, Increasing superscalar performance through multistreaming, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.49-58, June 27-29, 1995, Limassol, Cyprus
• 29: W. Yamamoto, M.J. Serrano, A.R. Talcott, R.C. Wood, and M. Nemirosky. Performance estimation of multistreamed, superscalar processors. In Twenty-Seventh Hawaii International Conference on System Sciences, pages I:195-204, January 1994.
• 30: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Management, Measurement