Scheduling problem definition

The scheduling problem is the problem of determining the order in which the operations in the behavioral description will be executed. Within a control step, a separated functional unit is required to execute each operation assigned to that step. Thus, the total number of functional units required in a control step directly corresponds to the number of operations scheduled into it. If more operations are scheduled into each control step, more functional units are necessary, which results in fewer control steps for the design implementation. On the other hand, if fewer operations are scheduled into each control step, fewer functional units are sufficient, but more control steps are needed. Thus, scheduling determines the tradeoff between design cost and performance. A scheduling function $\theta : V_0 \rightarrow \Pi(N^n)$ assigns to each DFG node $v \in V_0$ a sequence of cycle steps in which the node is executed. If these cycle steps are continuous, this will be called the execution interval of the operation v. A schedule will be called a simple schedule if all operations have an execution interval of length one. In this work, only execution in continuous cycle steps will be considered.

Mutual exclusion

Mutual exclusion: two operations will be called mutually exclusive if they are executed under mutually exclusive conditions. A mutual exclusive function $m : V_0 \rightarrow \Pi(N)$ is defined such that: $m(v_i) \wedge m(v_j) = 0$ when operations $v_i$ and operation $v_j$ are executed under mutually exclusive conditions.

Scheduling common approaches

There are two classes of scheduling problems: time-constrained scheduling and resource-constrained scheduling. Time-constrained scheduling minimizes the hardware cost when all operations are to be scheduled into a fixed number of control steps. Resource-constrained scheduling, instead, minimizes the number of control steps needed for executing all operations given a fixed amount of hardware.

The simplest constructive approach is the as soon as possible (ASAP) scheduling. First, operations are sorted into a list according to their topological order. Then, operations are taken from the list one at a time and placed into the earliest possible control step. The other simple approach is the as late as possible (ALAP) scheduling. The ALAP value for an operation defines the latest control step into which an operation can possibly be scheduled. In this approach, given a time constraint in terms of the number of control steps, the algorithm determines the latest possible control step in which an operation must begin its execution. The critical paths within the flow graph can be found by taking the intersection of the ASAP and ALAP schedules such that the operations that appear in the same control steps in both schedules are on the critical paths.

Implemented algorithms for scheduling

There are different algorithms implemented to solve the scheduling problem:

src_HLS_scheduling_list_based_page solve scheduling using list based algorithm.
src_HLS_scheduling_ilp_scheduling_page solve scheduling exploting an ILP formulation of the scheduling problem.
src_HLS_scheduling_ilp_scheduling_new_page solve scheduling exploting a new ILP formulation of the scheduling problem.
src_HLS_scheduling_silp_scheduling_page solve scheduling exploting a SILP formulation of the scheduling problem.
src_HLS_scheduling_force_directed_page solve scheduling using a new formulation of force directed algorithm
src_HLS_path_based_page solve scheduling using a path based approach.

An operation can be potentially executed if all its inputs have been already computed. Then the operation is selected to be executed if there is a free resource that is able to execute the type of the operation. If the operation has a partial binding (see Binding constraints) to a specific functional unit instance, the algorithm will have simply to check if the specific instance which the operation is bounded is free (not a generic one). If it is free, the operation can be assigned to its functional unit instance and scheduled in the current control step; if the resource is busy, the operation will be kept in the list and the next one is tested. When a partial binding has not been specified before for some operations, the algorithm performs the usual methodology to associate them to free resources.