Interleaving: a multithreading technique targeting multiprocessors and workstations

ABSTRACT

There is an increasing trend to use commodity microprocessors as the compute engines in large-scale multiprocessors. However, given that the majority of the microprocessors are sold in the workstation market, not in the multiprocessor market, it is only natural that architectural features that benefit only multiprocessors are less likely to be adopted in commodity microprocessors. In this paper, we explore multiple-context processors, an architectural technique proposed to hide the large memory latency in multiprocessors. We show that while current multiple-context designs work reasonably well for multiprocessors, they are ineffective in hiding the much shorter uniprocessor latencies using the limited parallelism found in workstation environments. We propose an alternative design that combines the best features of two existing approaches, and present simulation results that show it yields better performance for both multiprogrammed workloads on a workstation and parallel applications on a multiprocessor. By addressing the needs of the workstation environment, our proposal makes multiple contexts more attractive for commodity microprocessors.

REFERENCES

• 1: A. Agarwal, Performance Tradeoffs in Multithreaded Processors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.525-539, September 1992 [doi>10.1109/71.159037]
• 2: Cray Research, Incorporated. Cray T3D Technical Summary, October 1993.
• 3: David E. Culler , Michael Gunter , James C. Lee, Analysis of Multithreaded Microprocessors, University of California at Berkeley, Berkeley, CA, 1992
• 4: George E. Daddis Jr. and H. C. Tomg. The concurrent execution of multiple instruction streams on superscalar processors. In Proceedings of the 1991 International Conference on Parallel Processing, volume I, pages 76--83, 1991.
• 5: Helen Davis, Steven R. Goldschmidt, and John Hennessy. Multiprocessor simulation and tracing using Tango. In Proceedings of the 1991 International Conference on Parallel Processing, volume II, pages 99-107, August 1991.
• 6: Digital Equipment Corporation. DECChip 21064-AA RISC Microprocessor Preliminary Data Sheet, 1992.
• 7: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 8: Anoop Gupta , John Hennessy , Kourosh Gharachorloo , Todd Mowry , Wolf-Dietrich Weber, Comparative evaluation of latency reducing and tolerating techniques, Proceedings of the 18th annual international symposium on Computer architecture, p.254-263, May 27-30, 1991, Toronto, Ontario, Canada
• 9: Joseph Heinrich, MIPS R4000 user's manual, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 10: William Jaffe, Bob Miller, and Jeff Yetter. A 200 MFLOP precision architecture processor. In Hot Chips IV Symposium Record, pages 1.2.1-1.2.13, August 1992.
• 11: 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
• 12: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 13: Kiyoshi Kurihara, David Chaiken, and Anant Agarwal. Latency tolerance through multithreading in large-scale multiprocessors. In Proceedings of the International Symposium on Shared Memory Multiprocessing, pages 91-101, April 1991.
• 14: James Pierce Laudon, Architectural and implementation tradeoffs for multiple-context processors, Stanford University, Stanford, CA, 1995
• 15: James Laudon , Anoop Gupta , Mark Horowitz, Architectural and implementation tradeoffs in the design of multiple-context processors, Stanford University, Stanford, CA, 1992
• 16: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, Proceedings of the 17th annual international symposium on Computer Architecture, p.148-159, May 28-31, 1990, Seattle, Washington, United States
• 17: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 18: Peter R. Nuth , William J. Dally, A Mechanism for Efficient Context Switching, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.301-304, October 14-16, 1991
• 19: Amos R. Omondi. Design of a high performance instruction pipeline. Computer Systems Science and Engineering, 6(1): 13-29, January 1991.
• 20: R. Guru Prasadh and Chuan-lin Wu. A benchmark evaluation of a multi-threaded RISC processor architecture. In Proceedings of the 1991 International Conference on Parallel Processing, volume I, pages 84-91, 1991.
• 21: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 22: Burton J. Smith. Architecture and applications of the HEP multiprocessor computer system. SPIE, 298:241-248, 1981.
• 23: Michael David Smith. Support for Speculative Execution in High-Performance Processors. PhD thesis, Stanford University, Stanford, California, November 1992.
• 24: S. Peter Song and Marvin Denman. The PowerPC 604TM RISC microprocessor. Motorola Luncheon, iSCA '94, April 1994.
• 25: Josep Torrellas, Multiprocessor cache memory performance: characterization and optimization, Stanford University, Stanford, CA, 1992
• 26: W.-D. Weber , A. Gupta, Exploring the benefits of multiple hardware contexts in a multiprocessor architecture: preliminary results, Proceedings of the 16th annual international symposium on Computer architecture, p.273-280, April 1989, Jerusalem, Israel

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

Additional Classification:
  C. Computer Systems Organization

General Terms:
Design, Measurement, Performance, Theory