A brief survey of papers on scheduling for pipelined processors

ABSTRACT

Most microprocessors introduced into the market in the past few years employ pipelining to enhance execution speed. Moreover, many of these processors use multiple pipelined functional units. This paper surveys several heuristics reported in the literature on the topic of code optimization and reordering for exploiting instruction level parallelism in pipelined processors. Five methods are described in detail and several others are briefly reviewed

REFERENCES

• 1: [Abrah88] Abraham, S., and Padmanabhan, K., "Instruction reorganization for a variable-length pipelined microprocessor," Proc. of the Intl. Conf. on Computer Design, New York, Oct. 1988.
• 2: [Arya85] Arya, S., "An optimal intruction scheduling model for a class of vector processors," IEEE Trans. on Computers, Vol. 34, No. 11, Nov. 1985.
• 3: [Bern88] Bernstein, D., "An improved approximation algorithm for scheduling pipelined machines," Proc. of the Intl. Conf. on Parallel Processing, St. Charles, Ill., Aug. 1988.
• 4: David Bernstein , Izidor Gertner, Scheduling expressions on a pipelined processor with a maximal delay of one cycle, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.57-66, Jan. 1989 [doi>10.1145/59287.59291]
• 5: David Bernstein , Micheal Rodeh , Izidor Gertner, Approximation algorithms for scheduling arithmetic expressions on pipelined machines, Journal of Algorithms, v.10 n.1, p.120-139, Mar. 1989 [doi>10.1016/0196-6774(89)90027-8]
• 6: David Bernstein , Michael Rodeh , Izidor Gertner, On the Complexity of Scheduling Problems for Parallel/Pipelined Machines, IEEE Transactions on Computers, v.38 n.9, p.1308-1313, September 1989 [doi>10.1109/12.29469]
• 7: [Bern90] Bernstein, D., Private communication.
• 8: Paul Chow, Mips-X RISC Microprocessor, Kluwer Academic Publishers, Norwell, MA, 1989
• 9: [Coff76] Coffman, E. G., Computer and job-shop scheduling theory. New York: Wiley, 1976.
• 10: [Elli85] Ellis, J. R., "Bulldog: A compiler for VLIW architectures," PhD Thesis, Yale U/DCS/RR-364, Yale University, Feb. 1985.
• 11: [Fish81] Fisher, J., "Trace Scheduling: A technique for global microcode compaction," IEEE Trans. on Computers, Vol. C-30, No. 7, July 1981.
• 12: 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
• 13: J. R. Goodman , W.-C. Hsu, Code scheduling and register allocation in large basic blocks, Proceedings of the 2nd international conference on Supercomputing, p.442-452, June 1988, St. Malo, France [doi>10.1145/55364.55407]
• 14: Thomas Karl Richard Gross, Code optimization of pipeline constraints, Stanford University, Stanford, CA, 1983
• 15: W. Helbig , V. Milutinovic, A DCFL E/D-MESFET GaAs Experimental RISC Machine, IEEE Transactions on Computers, v.38 n.2, p.263-274, February 1989 [doi>10.1109/12.16503]
• 16: 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]
• 17: [Hsu87] Hsu, W. C., "Register allocation and code scheduling for load/store architectures," Univ. of Wisconsin-Madison Tech. Report #722, Oct. 1987.
• 18: [Hu61] Hu, T. C., "Parallel sequencing and assembly line problems," Operations Research, Vol. 9, No. 6, 1961.
• 19: W. W. Hwu , P. P. Chang, Exploiting parallel microprocessor microarchitectures with a compiler code generator, Proceedings of the 15th Annual International Symposium on Computer architecture, p.45-53, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 20: P. P. Chang , W. W. Hwu, Trace selection for compiling large C application programs to microcode, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.21-29, November 28-December 02, 1988, San Diego, California, United States
• 21: W. W. Hwu , T. M. Conte , P. P. Chang, Comparing software and hardware schemes for reducing the cost of branches, Proceedings of the 16th annual international symposium on Computer architecture, p.224-233, April 1989, Jerusalem, Israel
• 22: [Krish90] Krishnamurthy, S. M., "Static scheduling of multi-cycle operations for a pipelined RISC processor," Scholarly Paper, Master's program, Clemson University, May 1990.
• 23: [Lawl87] Lawler, E., Lenstra, J. K., Martel, C., and Simmons, B., "Pipeline scheduling: A survey," IBM Research Report, RJ5738 (57717), July 1987.
• 24: Veljko Milutinovic , David Fura , Walter Helbig, An Introduction to GaAs Microprocessor Architecture for VLSI, Computer, v.19 n.3, p.30-42, March 1986 [doi>10.1109/MC.1986.1663177]
• 25: Veljko Milutinovic , Alex Silbey , David Fura , Kevin Kerin , Mark Bettinger , Walt Helbig , William Heagerty , Richard Zieger , Bob Schellack , Walt Curtice, Issues of Importance in Designing GaAs Microcomputer Systems, Computer, v.19 n.10, p.45-57, October 1986 [doi>10.1109/MC.1986.1663070]
• 26: Veljko Milutinovic , David Fura , Walter Helbig , Joseph Linn, Architecture/Compiler Synergism in GaAs Computer Systems, Computer, v.20 n.5, p.72-93, May 1987 [doi>10.1109/MC.1987.1663566]
• 27: 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
• 28: [Tie89] Tiemann, M. D., "The GNU Instruction Scheduler," CS343 course report, Stanford University, Jun. 1989.
• 29: [Youn85] Young, H., "Evaluation of a decoupled computer architecture and the design of a vector extension," Univ. of Wisconsin-Madison Tech. Report #603, July 1985.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Documentation, Management