Efficient instruction scheduling for a pipelined architecture

ABSTRACT

As part of an effort to develop an optimizing compiler for a pipelined architecture, a code reorganization algorithm has been developed that significantly reduces the number of runtime pipeline interlocks. In a pass after code generation, the algorithm uses a dag representation to heuristically schedule the instructions in each basic block.Previous algorithms for reducing pipeline interlocks have had worst-case runtimes of at least O (n4). By using a dag representation which prevents scheduling deadlocks and a selection method that requires no lookahead, the resulting algorithm reorganizes instructions almost as effectively in practice, while having an O (n2) worst-case runtime.

REFERENCES

• Ary83: Arya, S. Optimal Instruction Scheduling for a Class of Vector Processors: An Integer Programming Approach. Tech. Rept. CRL-TR-19-83, Computer Research Laboratory, the Univ. of Michigan, Ann Arbor, April 1983.
• Aus82: Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
• Con67: Conway, R.W., W.L. Maxwell & L.W. Miller, Theory of Scheduling, Addison-Wesley, Reading, MA, 1967.
• Cou86: Deborah S. Coutant, Retargetable high-level alias analysis, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-118, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512654]
• Dav81: Davidson, S., D. Landskov, B.D. Shriver & P.W. Mallett. Some Experiments in Local Microcode Compaction for Horizontal Machines. 1EEE Trans. on Computers, Vol. C-30, No. 7, July 1981, pp. 460 - 477.
• Fis81: Fisher, j.A. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Trans. on Computers, Vol. C-30, No. 7, July 1981, pp. 478 - 490.
• Gro83: Gross, T.R. Code Optimization of Pipeline Constraints. Tech. Rept. 83-255, Computer Systems Lab., Stanford Univ., Dec. 1983.
• Hen81: Hennessy, J.L. Symbolic Debugging of Optimized Code, ACM Trans. on Prog. Lang. and Sys., Vol. 3, No. 1, Jan. 1981, pp. 200 - 206.
• Hen83: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• Joh86: Mark S. Johnson , Terrence C. Miller, Effectiveness of a machine-level, global optimizer, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.99-108, June 25-27, 1986, Palo Alto, California, United States
• Knu68: Knuth, D.E. Fundamental Algorithms, Addison- Wesley, Reading, MA, p. 258.
• Kog81: Kogge, P.M. The Architecture of Pipelined Computers, McGraw-Hill, New York, 1981.
• Rym82: James W. Rymarczyk, Coding guidelines for pipelined processors, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.12-19, March 01-03, 1982, Palo Alto, California, United States
• Sit78: Sites, R.L. Instruction Ordering for the Cray-1 Computer. Tech. Rept. 78-CS-023, Univ. of California, San Diego, July 1978.
• Spi71: Spillman, Thomas C., Exposing Side-Effects in a PldI Optimizing Compiler, Information Processing 81, North:Holland, 1972, pp. 376 - 381.
• Tho64: Thornton, J.E. Parallel Operation in the Control Data 6600, Proc. Fall Joint Comp. Conf., Part 2, Vol. 26, 1964, pp. 33 -40.
• Tok81: Tokoru, M., E. Tamura & T. Takizuka. Optimization of Microprograms. IEEE Trans. on Computers, Vol. C-30, No. 7, July 1981, pp. 491 - 504.
• Tom67: Tomasulo, R.M. An Efficient Algorithm for Exploiting Multiple Arithmetic Units, IBM J. of Res. and Devt., Vol. 11, No. 1, Jan. 1967, pp. 25 - 33.
• Veg82: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982
• Zel84: Zellweger, P.T. lnteractiv~ Source-Level Debugging of Optimized Programs, Research Report CSL-84-5, Xerox Palo Alto Research Center, Palo Alto, CA, May 1984.

INDEX TERMS

Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Styles (e.g., parallel, pipeline, special-purpose)

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Pipeline processors**

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Code generation; Compilers
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Performance, Theory