VLSI Digital Signal Processing Systems: Design and Implementation

B.4    INTEGER LINEAR PROGRAMMING MODELS

Integer linear programming (ILP) models provide a formal method to describe and solve the scheduling problems in an optimal manner. The models primarily differ in the manner they are described and their objective functions. Although ILP models provide a formal method to address the scheduling problem, they have been used sparingly until recently, because they require longer execution times and when constraints are relaxed, the run times increase exponentially. New models have been developed to reduce the execution time [13]–[15]. ILP models are attractive because they can produce optimal solutions and can be easily modified to accommodate additional constraints.

A general description of ILP modeling for high-level synthesis consists of an objective function to be minimized (or maximized) and a set of constraints to be satisfied. Most approaches also utilize scheduling ranges to reduce the design space and run times. When constructing an ILP model, integer variables are used to describe the objective function and the constraints. The primary variables are binary decision variables, x_i,j, which represent whether node i can be scheduled into time step j. Other important variables are , which represent the number of t_k type functional units that will be allocated. Costs associated with each t_k type functional unit are represented by constants: ...