Low level scheduling using the hierarchical task graph

ABSTRACT

This paper introduces a new efficient instruction scheduling algorithm that can schedule across basic blocks. Scheduling globally, across basic blocks, is done by using an extension of the control flow graph (CFG) that combines both data and control dependence constraints. It organizes control flow into a hierarchy of dags and includes dataflow edges that cross basic blocks. We assume a type of extended CFG called the hierarchical task graph (HTG). Previously, the HTG has been used to describe the functional parallelism of programs at medium or higher levels of parallelism. Here we use the HTG to assist in finding parallelism at the instruction level. The new generation of superscalar RISC chips must keep their pipelines full and maximize multiple issue for maximum performance. This means that scheduling across basic blocks is becoming increasingly important. The HTG data structure simplifies the task of scheduling instructions across basic blocks.

REFERENCES

• AHU74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• BWH: Buxbaum, M., D. Wallace and P. Hohensee, "A RISC Vectorization Algorithm," to appear.
• E86: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• F81: Fisher, J., "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, Vol. C-30, No. 7, July 1981, pp. 478-490.
• GP90: Girkar, M. and C. Polychronopoulos, "A Universal Intermediate Representation for Parallel Programs Based on Control and Data Dependences," Technical Report 1046, Center for Supercomputing Research and Development, Univ. of Illinois at Urbana-Champaign, 1990.
• GP92: M. Girkar , C. D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.166-178, March 1992 [doi>10.1109/71.127258]
• PS90: Krishna Palem , Barbara Simons, Scheduling time-critical instructions on RISC machines, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.270-280, December 1989, San Francisco, California, United States [doi>10.1145/96709.96737]
• P91: Constantine D. Polychronopoulos, The hierarchical task graph and its use in auto-scheduling, Proceedings of the 5th international conference on Supercomputing, p.252-263, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109089]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Performance, Verification