An instruction reoderer for pipelined computers

ABSTRACT

In paper [19], we proposed an algorithm to reorder the straight line instruction streams for pipelined computers. In this paper, we extend the algorithm to handle streams with branches and loops as well. The input is the intermediate code of a compiler and is represented by the data control dependence graph(DCG). The DCG is preprocessed to construct a branch nest tree which is related to the structure of the branches and loops within the instruction streams. A priority list is then constructed for scheduling the nodes. The algorithm finds a most suitable slot for each node of the DCG.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: S. Arya, An Optimal Instruction-Scheduling Models for Class of Vectors Processor, IEEE Transactions on Computers, V-34(11), p981-995, Nov. 1985
• 3: 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
• 4: J. J. Dongarra and A. R. Hinds, Unrolling Loops in TORTRAN, Sojtware Praticce and Experience, V-9(3), Mar. 1979
• 5: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 6: Philip B. Gibbons , Steven S. Muchnick, Efficient instruction scheduling for a pipelined architecture, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.11-16, June 25-27, 1986, Palo Alto, California, United States
• 7: Thomas R. Gross , John L. Hennessy, Optimizing delayed branches, Proceedings of the 15th annual workshop on Microprogramming, p.114-120, October 05-07, 1982, Palo Alto, California, United States
• 8: T. R. Gross, Code Optimization of Pipeline Constraints, Technique Report No. 255, Computer System Laboratory, Dept. of Electric Engineering and Conputer Science, Stanford University, Dec. 1983
• 9: 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]
• 10: 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
• 11: Manolis G. H. Katevenis, Reduced instruction set computer architectures for VLSI, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 12: P. M. Kogge, The Architecture of Pipelined Computers, Hemisphere Publishing Corporation, 1981
• 13: E. Lawler, J. K. Lenstra, C. Martel, and B. Simons, Pipeline Scheduling: A Survey, IBM Research Report, RJ5738 (57717), July 15, 1987
• 14: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• 15: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 16: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• 17: B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, Proceedings of the 9th annual symposium on Computer Architecture, p.131-139, April 26-29, 1982, Austin, Texas, United States
• 18: 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
• 19: J.-J. Shieh , C. Papachristou, On reordering instruction streams for pipelined computers, Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture, p.199-206, August 14-16, 1989, Dublin, Ireland
• 20: 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
• 21: J. E. Thomton, Parallel Operation in Control Data 6600, Proc. of Fall Joint Computer Conference, Part 2, V-26, p33-40, 1964
• 22: R. M. Tomasulo, An Efficient Algorithm for Exploiting Multiple Arithmetic Units, IBM Journal, p25-33, Jan. 1967
• 23: Jack Walicki , John D. Laughlin, Operation scheduling in reconfigurable, multifunction pipelines, Proceedings of the 20th annual workshop on Microprogramming, p.80-87, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255319]