Scheduling time-critical instructions on RISC machines

ABSTRACT

An instruction or a set of instructions can be considered time critical if their execution is required to free up a resource. Time critical instructions might be used to make shared resources such as registers more quickly available for reuse; or they might be used for real time computations, portions of which are critical for the operation of some piece of equipment. In this paper we present a polynomial time algorithm for optimally scheduling instructions with or without time critical constraints on RISC machines such as the IBM 801, the Berkeley RISC machine, and the HP Precision Architecture. We also show that in the absence of time critical constraints, the greedy algorithm always produces a schedule for a target machine with multiple identical pipelines that has a length less than twice that of an optimal schedule. The behavior of the greedy algorithm is of interest because, as we show, the instruction scheduling problem becomes NP-hard for arbitrary length pipelines, even when the basic block of code being input consists of only several independent streams of straight-line code, and there are no time-critical constraints. Finally, we present the first correct proofs that the problem becomes NP-hard even for small pipelines, no time-critical constraints, and input of several independent streams of straight-line code if there is only a single register or if there is a bus constraint.

REFERENCES

• 1: Alexander Aiken , Alexandru Nicolau, Loop Quantization: an Analysis and Algorithm, Cornell University, Ithaca, NY, 1987
• 2: F. Allen, B. Rosen, and K. Zadeck (eds), "Optimization in Compilers', MIT Pzess, to appear.
• 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: 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: J. Bruno, J.W. Jones iII, and K. So, "Deterlninistic scheduling with pipelined processors", 1EEE Trans. Computers, C-29, (1980), 308-316.
• 7: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 8: J.A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction", IEEE Trans. on Computers, Vo}. C-30, No. 7, (July, 1981) 478-490.
• 9: Harold N. Gabow, Scheduling Uet systems on two uniform processors and length two pipelines, SIAM Journal on Computing, v.17 n.4, p.810-829, August 1988 [doi>10.1137/0217051]
• 10: 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
• 11: R. L. Graham, "Bounds for Certain Multiprocessor Anomalies", Bell System Technical Journal, 45, (1966), 1563-158 ~.
• 12: John L. Hennessy , Thomas R. Gross, Code generation and reorganization in the presence of pipeline constraints, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.120-127, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582166]
• 13: 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]
• 14: J. Hennessy, N. Jouppi, J. Gill, F. Baskett., A. Strong, T. Gross, C. Rowen, and J. Leonard, "The MIPS Machine", Proc. 1EEE Coupcon, San Francisco, CA, (Feb. 1982), 2-7.
• 15: Manolis G. H. Katevenis, Reduced instruction set computer architectures for VLSI, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 16: E. Lawler, J.K. Lenstra, C. Martel, B. Simons, and L. Stockmeyer, "Pipeline Scheduling: A Survey", Technical Report, RJ 5738, IBM Research Division, San Jose, CA., (1987).
• 17: Joseph Y-T. Leung , Oliver Vornberger , James D. Witthoff, On some variants of the bandwidth minimization problem, SIAM Journal on Computing, v.13 n.3, p.650-667, August 1984 [doi>10.1137/0213040]
• 18: A. Nicolau, Loop quantization of unwinding done right, Proceedings of the 1st International Conference on Supercomputing, p.294-308, March 1988, Athens, Greece
• 19: Krishna SSV. Palem, On the Complexity of Precedence Constrained Scheduling, University of Texas at Austin, Austin, TX, 1986
• 20: K. Palem and B. Simons, "Algorithms for Optimal Instruction Scheduling on Pipelines", Confidential Technical Report, RJ 6592, IBM Research Division, San Jose, CA, (1988).
• 21: C. Papadimitriou and M. Yannakakis, "Scheduling interval-ordered tasks", SlAM J. Compnt., 8, (1979), 405-409.
• 22: David A. Patterson, Reduced instruction set computers, Communications of the ACM, v.28 n.1, p.8-21, Jan. 1985 [doi>10.1145/2465.214917]
• 23: G. Radin, "The 801 Minicomputer~, IBM J. Res. Dev. ,77, (1983), 237-246.
• 24: Richard O Simpson, The IBM RT personal computer, BYTE, v.11 n.11, p.43-78, Oct. 1986
• 25: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

          Nouns: RISC**

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms