Philip B. Gibbons
Steven S. Muchnick
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.
- 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.Google Scholar
- Aus82 Auslander, M. & M. Hopkins. An Overview of the PL.8 Compiler. Proc. ACM SIGPLAN Syrup. on Compiler Construction, Boston, June 1982, pp. 22 - 31. Google ScholarDigital Library
- Con67 Conway, R.W., W.L. Maxwell & L.W. Miller, Theory of Scheduling, Addison-Wesley, Reading, MA, 1967.Google Scholar
- Cou86 Coutant, D.S. Retargetable High-Level Alias Analysis, Proc. ACM Syrup. on Princ. of Prog. Lang., St. Petersburg Beach, FL, January 1986, pp. 110- 118. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Gro83 Gross, T.R. Code Optimization of Pipeline Constraints. Tech. Rept. 83-255, Computer Systems Lab., Stanford Univ., Dec. 1983.Google Scholar
- 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.Google Scholar
- Hen83 Hennessy, J.L. & T.R. Gross. Postpass Code Optimization of Pipeline Constraints. ACM Trans. on Prog. Lang. and Sys, Vol. 5, No. 3, July 1983, pp. 422- 448. Google ScholarDigital Library
- Joh86 johnson, M.S. & T.C. Miller. Effectiveness of a Machine-Level, Global Optimizer, Proc. of the SIGPLAN '86 Conf. on Comp. Constr., June 1986. Google ScholarDigital Library
- Knu68 Knuth, D.E. Fundamental Algorithms, Addison- Wesley, Reading, MA, p. 258.Google Scholar
- Kog81 Kogge, P.M. The Architecture of Pipelined Computers, McGraw-Hill, New York, 1981.Google Scholar
- Rym82 Rymarczyk, J.W. Coding Guidelines for Pipelined Processors, Proc. of the Symp. on Arch. Supt. for Prog. Lang. and Oper. Syst., Palo Alto, CA, March 1982, pp. 12- 19. Google ScholarDigital Library
- Sit78 Sites, R.L. Instruction Ordering for the Cray-1 Computer. Tech. Rept. 78-CS-023, Univ. of California, San Diego, July 1978.Google Scholar
- Spi71 Spillman, Thomas C., Exposing Side-Effects in a PldI Optimizing Compiler, Information Processing 81, North:Holland, 1972, pp. 376 - 381.Google Scholar
- Tho64 Thornton, J.E. Parallel Operation in the Control Data 6600, Proc. Fall Joint Comp. Conf., Part 2, Vol. 26, 1964, pp. 33 -40.Google Scholar
- Tok81 Tokoru, M., E. Tamura & T. Takizuka. Optimization of Microprograms. IEEE Trans. on Computers, Vol. C-30, No. 7, July 1981, pp. 491 - 504.Google Scholar
- 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.Google ScholarDigital Library
- Veg82 Vegdahl, S. Local Code Generation and Compaction in Optimizing Microcode Compilers, Ph.D. thesis, Carnegie-Mellon Univ., De~. 1982. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Efficient instruction scheduling for a pipelined architecture
Recommendations
Efficient instruction scheduling for a pipelined architecture
SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler constructionAs 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 ...
Efficient instruction scheduling for a pipelined architecture
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A SelectionAs 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 ...
Comments