A scheduling method by stepwise expansion in high-level synthesis

A fast heuristic method for the scheduling problem that minimizes hardware costs of functional units, registers, and buses on the basis of an integer linear programming (ILP) model is proposed. In the method, the total computation time can be greatly reduced compared to the general ILP method, since the number of the integer variables which appear in the ILP formulation is reduced by introducing a stepwise expansion approach. Results obtained for a practical scheduling problem indicate that the computation time of the proposed method is linear to the number of the control steps, and optimal or near-optimal solutions can be found.<>