An empirical study of decentralized ILP execution models

ABSTRACT

Recent fascination for dynamic scheduling as a means for exploiting instruction-level parallelism has introduced significant interest in the scalability aspects of dynamic scheduling hardware. In order to overcome the scalability problems of centralized hardware schedulers, many decentralized execution models are being proposed and investigated recently. The crux of all these models is to split the instruction window across multiple processing elements (PEs) that do independent, scheduling of instructions. The decentralized execution models proposed so far can be grouped under 3 categories, based on the criterion used for assigning an instruction to a particular PE. They are: (i) execution unit dependence based decentralization (EDD), (ii) control dependence based decentralization (CDD), and (iii) data dependence based decentralization (DDD). This paper investigates the performance aspects of these three decentralization approaches. Using a suite of important benchmarks and realistic system parameters, we examine performance differences resulting from the type of partitioning as well as from specific implementation issues such as the type of PE interconnect.We found that with a ring-type PE interconnect, the DDD approach performs the best when the number of PEs is moderate, and that the CDD approach performs best when the number of PEs is large. The currently used approach---EDD---does not perform well for any configuration. With a realistic crossbar, performance does not increase with the number of PEs for any of the partitioning approaches. The results give insight into the best way to use the transistor budget available for implementing the instruction window.

REFERENCES

• 1: 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
• 2: P. G. Emma, Understanding some simple processor-performance limits, IBM Journal of Research and Development, v.41 n.3, p.215-232, May 1997
• 3: 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
• 4: Manoj Franklin, The multiscalar architecture, University of Wisconsin at Madison, Madison, WI, 1993
• 5: 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
• 6: G. A. Kemp and M. Franklin, "PEWs: A Decentralized Dynamic Scheduler for ILP Processing," Proc. International Conference on Parallel Processing (ICPP), Vol. I, pp. 239-246, 1996.
• 7: Daniel Leibholz , Rahul Razdan, The Alpha 21264: A 500 MHz Out-of-Order Execution Microprocessor, Proceedings of the 42nd IEEE International Computer Conference, p.28, February 23-26, 1997
• 8: Stephen Melvin , Yale Patt, Exploiting fine-grained parallelism through a combination of hardware and software techniques, Proceedings of the 18th annual international symposium on Computer architecture, p.287-296, May 27-30, 1991, Toronto, Ontario, Canada
• 9: Ravi Nair , Martin E. Hopkins, Exploiting instruction level parallelism in processors by caching scheduled groups, Proceedings of the 24th annual international symposium on Computer architecture, p.13-25, June 01-04, 1997, Denver, Colorado, United States
• 10: 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
• 11: N. Ranganathan and M. Franklin, "Complexity~ Effective PEWs Microarchitecture," (to appear in) Microprocessors and Microsystems.
• 12: 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
• 13: 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
• 14: 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
• 15: Krishna K. Sundararaman , Manoj Franklin, Multiscalar Execution along a Single Flow of Control, Proceedings of the international Conference on Parallel Processing, p.106-113, August 11-15, 1997
• 16: R. M. Tomasulo, "An Efficient Algorithm for Exploiting Multiple Arithmetic Units," IBM Journal of Research and Development, pp. 25-33, January 1967.
• 17: Jenn-Yuan Tsai , Pen-Chung Yew, The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.35, October 20-23, 1996
• 18: 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
• 19: Sriram Vajapeyam , Tulika Mitra, Improving superscalar instruction dispatch and issue by exploiting dynamic code sequences, Proceedings of the 24th annual international symposium on Computer architecture, p.1-12, June 01-04, 1997, Denver, Colorado, United States
• 20: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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

Keywords:
control dependence, data dependence, decentralization, dynamic scheduling, execution unit dependence, hardware window, instruction-level parallelism, speculative execution