A formal approach to the scheduling problem in high level synthesis

An integer linear programming (ILP) model for the scheduling problem in high-level synthesis is presented. In addition to time-constrained scheduling and resource-constrained scheduling, a scheduling problem called feasible scheduling, which provides a paradigm for exploring the solution space, is constructed. Extensive consideration is given to the following applications: scheduling with chaining, multicycle operations by nonpipelined function units, and multicycle operations by pipelined function units; functional pipelining; loop folding; mutually exclusive operations; scheduling under bus constraint; and minimizing lifetimes of variables. The complexity of the number of variables in the formulation is O(s*n) where s and n are the number of control steps and operations, respectively. Since the as soon as possible (ASAP), as late as possible (ALAP), and list scheduling techniques are used to reduce the solution space, the formulation becomes very efficient. A solution to a practical problem, such as the fifth-order filter, can be found optimally in a few seconds.>