Optimal chaining in expression trees

ABSTRACT

Chaining is the ability to pipeline two or more vector instructions on Cray-1 like machines. We show how to optimally use this feature to compute (vector) expression trees, in the context of automatic code-generation. We present a linear-time scheduling algorithm for finding an optimal order of evaluation for a machine with a bounded number of registers.

REFERENCES

• A: Arya, S., "An optimal instructionscheduling model for a class of vector processors", IEEE Transactions on Cornputers, Vol. C-34, No. 11, (November 1985), 981-995.
• AJ: 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]
• AJU: 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]
• BJPR: David Bernstein , Ron Y. Pinter , Michael Rodeh, Optimal scheduling of arithmetic operations in parallel with memory access (preliminary version), Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.325-333, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318662]
• BJR: Bernstein, D., Jaffe, J.M., and Rodeh, M., "Scheduling arithmetic and load operations in parallel with no spilling", in preparation.
• BS: 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]
• C: Cray-I Hardware Reference Manual, Cray Research inc., Cray-I Comput. Syst. Publ. 2240004 (May 1979).
• HB: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• R: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• SU: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]

INDEX TERMS

Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Styles (e.g., parallel, pipeline, special-purpose)
      B.5.2 Design Aids
          Subjects: Optimization

  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Performance, Theory, Verification