Scheduling Arithmetic and Load Operations in Parallel with No Spilling

Authors:
  • DBDavid Bernstein
    David Bernstein
  • JJJeffrey M. Jaffe
    Jeffrey M. Jaffe
  • MRMichael Rodeh
    Michael Rodeh

Abstract
A machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units is considered. For this model, the evaluation of a set of expression trees is discussed. A dynamic programming algorithm for producing an approximate solution is described and analyzed. For binary trees its worse-case cost is at most $\min (1.091,1 + {{(2\log n)} / n})$ times the optimal cost.

This publication has 11 references indexed in Scilit: