Y. Hu et Bs. Carlson, A UNIFIED ALGORITHM FOR THE ESTIMATION AND SCHEDULING OF DATA-FLOW GRAPHS, Journal of circuits, systems, and computers, 6(3), 1996, pp. 287-318
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.