On reordering instruction streams for pipelined computers

ABSTRACT

This paper describes a method to reorder the straight line instruction streams for pipelined computers which have one instruction issue unit but may contain multiple function units. The objective is to make the most efficient usage of the pipelines within the computer system. The input to the scheduler is the intermediate code of a compiler, and is represented by a data dependence graph (DDG). The scheduler is a kind of list scheduler. The data dependence and the pipeline effect of the function units within the system have been considered for finding a most suitable time slot for each node during reordering time. The scheduler has been implemented and several scientific application programs have been tested. The results show that in most of the cases the scheduler will achieve the optimal result. The average instruction issue rate is over 96%. As a comparison, the issue rate of an ordinary compiler is only 22%; and the issue rate of a compiler with the effect of pipeline but without reordering the instruction stream is about 45%.

REFERENCES

• Aho-86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Arya85: Arya, S." An Optimal Instruction - Scheduling Models for Class of Vectors Processor", IEEE Transactions on Computers, V-34(11), p981-995, Nov. 1985
• Ausl82: 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
• Brow84: D. R. K. Brownrigg, The weighted median filter, Communications of the ACM, v.27 n.8, p.807-818, Aug 1984 [doi>10.1145/358198.358222]
• Brun80: Bruno, J., Jones, J. W. and So, K.,' Deterministic Scheduling with Pipelined Processors", IEEE Transactions on Computers, C-29(4), p308 316, Apr. 1980
• Bucy80: Bucy, R. S. and Senne, K. D.," Nonlinear Filtering Algorithms for Vector Machines,", Computers and Mathematics, V-6(3), p317-338, 1980
• Burd85: Burden, R. L. and Faires, J. D., Numerical Analysis, Prindle, Weber and Schmidt, Boston, 1985
• Dong79: Dongarra, J. J. and Hinds, A. R.," Unrolling Loops in TORTRAN,", Software Praticce and Experience, V-9(3), Mar. 1979
• Elli86: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• Gibb86: 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
• Gonz77: Mario J. Gonzalez, Jr., Deterministic Processor Scheduling, ACM Computing Surveys (CSUR), v.9 n.3, p.173-204, Sept. 1977 [doi>10.1145/356698.356700]
• Gros83: Gross, T. R., Code Optimization of Pipeline Constraints, Technique Report No. 255, Computer System Laboratory, Dept. of Electric Engineering and Conputer Science, Stanford University, Dec. 1983
• Henn83: 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]
• John86: 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
• Kasa84: Kasahara, H. and Narita, S.,"" Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Proccessing", IEEE Transactions on Computers, C-33(11), p1023-1029, Nov. 1984
• Kate85: Manolis G. H. Katevenis, Reduced instruction set computer architectures for VLSI, Massachusetts Institute of Technology, Cambridge, MA, 1985
• Kogg81: Kogge, P. M.", The Architecture of Pipelined Computers, Hemisphere Publishing Corporation, 1981
• Kuck81: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• Lawl87: Lawler, E., Lenstra, J. K., Martel, C. and Simons, B.," Pipeline Scheduling: A Survey", IBM Research Report, RJ5738 (57717), July 15, 1987
• Padu86: 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]
• Poly88: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• Rau-81: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• Rau-82: 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
• Ryma82: 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
• Sahn84: Sahni, S.," Scheduling Multipipeline and Multiprocessor Computers', IEEE Transactions on Computers, C-30(1), p637-645, Jul. 1984
• Shie89: Shieh, J. J. and Papachristou, C.," A Mapping Strategy for Multiprocessor Systems", To be published.
• Thom64: Thornton, J. E.," Parallel Operation in Control Data 6600,", Proc. of Fall Joint Computer Conference, Part 2, V-26, p33-40, 1964
• Toma67: Tomasulo, R. M., " An Efficient Algorithm for Exploiting Multiple Arithmetic Units", IBM Journal, p25-33, Jan. 1967
• Wali87: 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]
• Wedi82: Robert G. Wedig, Dynamic detection of concurrency in DEL instruction streams, Stanford University, Stanford, CA, 1982

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers
      B.1.5 Microcode Applications
          Subjects: Special-purpose**

General Terms:
Algorithms, Design, Languages