Optimal scheduling of arithmetic operations in parallel with memory access (preliminary version)

ABSTRACT

We propose a new machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units. For this model, the evaluation of expression trees is considered. An efficient algorithm to produce an optimal order of evaluation is described and analyzed. For a tree with n vertices the algorithm runs in time &Ogr;(n log2n). If the arithmetic operations have at most two arguments, the complexity goes down to &Ogr;(n logn).

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: 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]
• 3: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 4: [4] Knuth, D. E., The art of computer programming: Sorting and Searching (Vol. 31), Addison-Wesley, Reading, MA, 1973.
• 5: [5] Li, H. F., "Scheduling trees in parallel /pipelined processing environments", IEEE transactions on computers, C-26, 11 (Nov. 1977), 1101-1112.
• 6: E. L. Lloyd, SCHEDULING TASK SYSTEMS WITH RESOURCES, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 7: 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]
• 8: James E. Smith, Decoupled access/execute computer architectures, Proceedings of the 9th annual symposium on Computer Architecture, p.112-119, April 26-29, 1982, Austin, Texas, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Languages, Performance, Theory, Verification