Improving Latency Tolerance of Multithreading through Decoupling

ABSTRACT

The increasing hardware complexity of dynamically scheduled superscalar processors may compromise the scalability of this organization to make an efficient use of future increases in transistor budget. SMT processors, designed over a superscalar core, are therefore directly concerned by this problem. This work presents and evaluates a novel processor microarchitecture which combines two paradigms: simultaneous multithreading and access/execute decoupling. Since its decoupled units issue instructions in-order, this architecture is significantly less complex, in terms of critical path delays, than a centralized out-of-order design, and it is more effective for future growth in issue-width and clock speed. We investigate how both techniques complement each other. Since decoupling features an excellent memory latency hiding efficiency, the large amount of parallelism exploited by multithreading may be used to hide the latency of functional units and keep them fully utilized. Our study shows that, by adding decoupling to a multithreaded architecture, fewer threads are needed to achieve maximum throughput. Therefore, in addition to the obvious hardware complexity reduction, it places lower demands on the memory system. Since one of the problems of multithreading is the degradation of the memory system performance, both in terms of miss latency and bandwidth requirements, this improvement becomes critical for high miss latencies, where bandwidth might become a bottleneck. Finally, although it may seem rather surprising, our study reveals that multithreading by itself exhibits little memory latency tolerance. Our results suggest that most of the latency hiding effectiveness of SMT architectures comes from the dynamic scheduling. On the other hand, decoupling is very effective at hiding memory latency. An increase in the cache miss penalty from 1 to 32 cycles reduces the performance of a 4-context multithreaded decoupled processor by less than 2 percent. For the nondecoupled multithreaded processor, the loss of performance is about 23 percent.

REFERENCES

• 1: A. Berrached, L.D. Coraor, and PT. Hulina, "A Decoupled Access/Execute Architecture for Efficient Access of Structured Data," Proc. 26th Hawai Int'l Conf. System Sciences, vol. 1, pp. 438447, Jan. 1993.
• 2: Peter L. Bird , Alasdair Rawsthorne , Nigel P. Topham, The effectiveness of decoupling, Proceedings of the 7th international conference on Supercomputing, p.47-56, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165952]
• 3: Ramon Canal , Joan-Manuel Parcerisa , Antonio Gonzalez, A Cost-Effective Clustered Architecture, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.160, October 12-16, 1999
• 4: G.E. Daddis and H.C. Torng, "The Concurrent Execution of Multiple Execution Streams on Superscalar Processors," Proc. Int'l Conf. Parallel Processing, pp. 76-83, Aug. 1991.
• 5: Digital Equipment Corp., Alpha 21164 Microprocessor Hardware Reference Manual, Or. Num. EC-QAEQB-TE, Maynard, Mass., Apr. 1995.
• 6: Keith I. Farkas , Paul Chow , Norman P. Jouppi , Zvonko Vranesic, The multicluster architecture: reducing cycle time through partitioning, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.149-159, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 7: J. R. Goodman , Jian-tu Hsieh , Koujuch Liou , Andrew R. Pleszkun , P. B. Schechter , Honesty C. Young, PIPE: a VLSI decoupled architecture, Proceedings of the 12th annual international symposium on Computer architecture, p.20-27, June 17-19, 1985, Boston, Massachusetts, United States
• 8: L. Gwennap, "Intel's P6 Uses Decoupled Superscalar Design," Microprocessor Report, vol. 9, no. 2, pp. 9-15, Feb. 1995.
• 9: L Gwennap, 'Digital 21264 Sets New Standard," Microprocessor Report, vol. 10, no. 14, Oct. 1996.
• 10: 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
• 11: Peter Yan-Tek Hsu, Designing the TFP Microprocessor, IEEE Micro, v.14 n.2, p.23-33, April 1994 [doi>10.1109/40.272835]
• 12: M. Johnson, Superscalar Microprocessor Design. Englewood Cliffs, N.J.: Prentice Hall, 1991.
• 13: G. P. Jones , Nigel P. Topham, A Limitation Study into Access Decoupling, Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.1102-1111, August 26-29, 1997
• 14: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 15: G.A. Kemp and lvi Franklin," PEWs: A Decentralized Dynamic Scheduler for ILP Processing," Proc. Intl Con,! Parallel Processing, vol. 1, pp. 239-246, 1996.
• 16: 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
• 17: A. Kumar, "The HP-PA8000 RISC CPU: A High Performance Outof-Order Processor," Proc. Hot Chips VIII, pp. 9-20, Aug. 1996.
• 18: L. Kurian , P. T. Hulina , L. D. Coraor, Memory Latency Effects in Decoupled Architectures, IEEE Transactions on Computers, v.43 n.10, p.1129-1139, October 1994 [doi>10.1109/12.324539]
• 19: D. Levitan , T. Thomas , P. Tu, The PowerPC 620 microprocessor: a high performance superscalar RISC microprocessor, Proceedings of the 40th IEEE Computer Society International Conference, p.285, March 05-09, 1995
• 20: Joan-Manuel Parcerisa , Antonio González, The Latency Hiding Effectiveness of Decoupled Access/Execute Processors, Proceedings of the 24th Conference on EUROMICRO, p.10293, August 25-27, 1998
• 21: 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
• 22: Subbarao Palacharla , J. E. Smith, Decoupling integer execution in superscalar processors, Proceedings of the 28th annual international symposium on Microarchitecture, p.285-290, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 23: AR. Pleszkun and E.S. Davidson, "Structured Memory Access Architecture," Proc. 1983 Int'l Conf. Parallel Processing, pp. 461-471, Aug. 1983.
• 24: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 25: S. Subramanya Sastry , Subbarao Palacharla , James E. Smith, Exploiting idle floating-point resources for integer execution, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.118-129, June 17-19, 1998, Montreal, Quebec, Canada
• 26: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 27: 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]
• 28: J. E. Smith , G. E. Dermer , B. D. Vanderwarn , S. D. Klinger , C. M. Rozewski, The ZS-1 central processor, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.199-204, October 1987, Palo Alto, California, United States
• 29: James E. Smith , Andrew R. Pleszkun, Implementation of precise interrupts in pipelined processors, Proceedings of the 12th annual international symposium on Computer architecture, p.36-44, June 17-19, 1985, Boston, Massachusetts, United States
• 30: James E. Smith , Shlomo Weiss , Nicholas Y. Pang, A simulation study of decoupled architecture computers, IEEE Transactions on Computers, v.35 n.8, p.692-702, Aug. 1986 [doi>10.1109/TC.1986.1676820]
• 31: 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
• 32: 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
• 33: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 34: Standard Performance Evaluation Corp., SPEC Newsletter, Fairfax, Va., Sept. 1995.
• 35: R.M. Tomasulo. "An Efficient Algorithm for Exploiting Multiple Arithmetic Units," IBM J. Research and Development, vol. 11, no. 1, pp. 25-33, Jan. 1967,
• 36: Nigel Topham , Alasdair Rawsthorne , Callum McLean , Muriel Mewissen , Peter Bird, Compiling and optimizing for decoupled architectures, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.40-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224301]
• 37: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 38: 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
• 39: Gary Tyson , Matthew Farrens , Andrew R. Pleszkun, MISC: a Multiple Instruction Stream Computer, Proceedings of the 25th annual international symposium on Microarchitecture, p.193-196, December 01-04, 1992, Portland, Oregon, United States
• 40: Wm. A. Wulf, Evaluation of the WM architecture, Proceedings of the 19th annual international symposium on Computer architecture, p.382-390, May 19-21, 1992, Queensland, Australia
• 41: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 42: Yinong Zhang , George B. Adams, III, Performance modeling and code partitioning for the DS architecture, Proceedings of the 25th annual international symposium on Computer architecture, p.293-304, June 27-July 02, 1998, Barcelona, Spain

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General
      C.1.3 Other Architecture Styles

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Access/execute decoupling, simultaneous multithreading, latency hiding, instruction-level parallelism, hardware complexity.