A UNIFIED ALGORITHM FOR THE ESTIMATION AND SCHEDULING OF DATA-FLOW GRAPHS

A unified algorithm is presented to solve the problem of estimation an d scheduling for performance constrained data flow graphs. The algorit hm achieves superior results by first computing a lower bound on the n umber of functional units required to satisfy the performance constrai nt T, and then scheduling the operations into the best control steps u sing the lower bound algorithm. The lower bound not only greatly reduc es the size of the solution space, but also provides a means to measur e the proximity of the final solution to an optimal one. Our algorithm is the first one to use a sharp lower bound estimation technique to d irect scheduling. In addition, our unified algorithm can easily be inc orporated into a branch-and-bound algorithm to solve the scheduling pr oblem optimally. Since our algorithm computes a sharp lower bound, the computation time of an optimal algorithm can be greatly reduced. Expe riments indicate that our scheduling algorithm can produce results ver y close to the lower bound. For all of the test cases the difference b etween our upper and lower bounds is not greater than one.