A recursive technique for estimating lower-bound performance of data path schedules is presented. The technique gives an improved complete lower bound in many cases where the Rim and Jain estimator was employed. In the introduction, the authors focus on estimating lower-bound performance of schedules under resource constraints for acyclic finite dataflow graphs.

In the next section, they consider the relaxation of the scheduling problem, using the Rim and Jain framework to introduce concepts. At the end of this section, the authors formulate the key points to improve on. Section 3 contains the new algorithm for computing ASAPUC values (“as soon as possible under constraints” time for each operation). The last section before the conclusion gives a huge body of experimental results, mainly drawn from digital signal processing. This section is of interest to a broad range of professionals because, as the authors state in the conclusion, similar considerations may apply to software schedules. In the light of existing and forthcoming very high speed digital signal processors (including the TMS320C6xx), where scheduling of instructions among available processing units emerges as a major issue, this work should be enlightening to many people who do not have much knowledge of this area.