A unified algorithm for estimation and scheduling in data path synthesis

A unified algorithm is presented to solve the problem of estimation and scheduling for performance constrained data path synthesis. The algorithm achieves superior results by first computing a lower bound on the number of functional units required to satisfy the performance constraint T, and then scheduling the operations into the best control steps using the lower bound algorithm. The lower bound not only greatly reduces the size of the solution space, but also provides a means to measure the proximity of the final solution to an optimal one. Our unified algorithm can also be incorporated in a branch-and-bound algorithm to solve the scheduling problem optimally. Experiments indicate that our scheduling algorithm can produce results very close to the lower bound. For all of the test cases the difference between our upper and lower bounds is not greater than one