Estimating lower-bound performance of schedules using a relaxation technique

A technique for computing a lower bound for nonpipelined resource-constrained scheduling performance is presented. Given a data-flow graph, a set of resources, resource delays, and clock cycle, a lower bound on the performance of a schedule is derived. The technique is fast (typical runtime of 50 ms), and the experimental lower-bounds are within two time steps of the actual schedules produced by a scheduling heuristic. The technique is also constructive and can be incorporated in a branch-and-bound method for solving the scheduling problem. The lower bound can be used to reduce a design search space. The method is applicable to lower-bound estimation in high-level synthesis