Scheduling expressions on a pipelined processor with a maximal delay of one cycle

ABSTRACT

Consider a pipelined machine that can issue instructions every machine cycle. Sometimes, an instruction that uses the result of the instruction preceding it in a pipe must be delayed to ensure that a program computes a right value. We assume that issuing of such instructions is delayed by at most one machine cycle. For such a machine model, given an unbounded number of machine registers and memory locations, an algorithm to find a shortest schedule of the given expression is presented and analyzed. The proposed algorithm is a modification of Coffman-Graham's algorithm [7], which provides an optimal solution to the problem of scheduling tasks on two parallel processors.

REFERENCES

• 1: A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
• 2: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 3: 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]
• 4: BRUNO, J., JONES, J. W., AND SO, K. Deterministic scheduling with pipelined processors. IEEE Trans. Comput. C-29, 4 (Apr. 1980), 308-316.
• 5: John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976 [doi>10.1145/321958.321971]
• 6: COFFMA~, E.G. Computer and Job-Shop Scheduling Theory. John Wiley and Sons, New York, 1976.
• 7: COFFMAN, E. G., JR., AND GRAHAM, R.L. Optimal scheduling for two-processor systems. Acta Inf. I (1972), 200-213.
• 8: Harold N. Gabow, An Almost-Linear Algorithm for Two-Processor Scheduling, Journal of the ACM (JACM), v.29 n.3, p.766-780, July 1982 [doi>10.1145/322326.322335]
• 9: Harold N. Gabow , Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.246-251, December 1983 [doi>10.1145/800061.808753]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: 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
• 12: 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]
• 13: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 14: Manolis G. H. Katevenis, Reduced instruction set computer architectures for VLSI, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 15: Manolis G.H. Katevenis , Robert W. Sherburne, Jr. , David A. Patterson , Carlo H. Séquin, The RISC II micro-architecture, Advances in VLSI and Computer Systems, v.1 n.2, p.138-152, Fall 1984
• 16: KOGGE, P. M. The Architecture of Pipelined Computers. McGraw-Hill, New York, 1981.
• 17: James R. Larus , Paul N. Hilfinger, Register allocation in the SPUR Lisp compiler, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.255-263, June 25-27, 1986, Palo Alto, California, United States
• 18: LI, H.F. Scheduling trees in parallel/pipelined processing environments. IEEE Trans. Comput. C-26, 11 (Nov. 1977), 1101-1112.
• 19: 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]
• 20: RADIN, G. The 801 minicomputer. IBM J. Res. Dev. 27, 3 (May 1983), 237-246.
• 21: SETm, R. Scheduling graphs on two processors. SIAM J. Comput. 5, i (Mar. 1976), 73-82.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Pipeline processors**

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Hierarchical design**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Performance