A recursive technique for computing lower-bound performance of schedules

Presents a fast recursive technique for estimating a lower-bound performance of data path schedules. The method relies on the determination of an ASAPUC (as soon as possible under constraint) time-step value for the root of the DFG (data flow graph) that is based on the ASAPUC values of its predecessor nodes, etc., until the leaf nodes are reached where this value becomes the regular ASAP value. The method computes a tighter lower-bound than the greedy technique and is only two times slower on the same benchmarks. Synthesis methods that depend on the exploration of the solution space directed by a lower-bound estimation, such a local microcode generation and behavioral synthesis, can benefit from our method. This is because bad solutions can be pruned earlier. We illustrate this dramatic effect on the reduction of the search space during the synthesis of an optimal microcode sequence for the elliptic wave filter benchmark and a fixed data path (containing a multiport RAM and a ROM)