Abstract
The most compelling reason for High-Level Synthesis (HLS) to be accepted in the state-of-the-art CAD flow is its ability to perform design space exploration. Design space exploration requires efficient scheduling techniques that have a low complexity and yet produce good quality schedules. The Time-Constrained Scheduling (TCS) problem minimizes the number of functional units required to schedule a particular Data Flow Graph (DFG) within a specified number of time steps.Over the past few years a number of techniques have been proposed to solve the TCS problem. Heuristic list scheduling algorithms have been widely used for their low-complexity and good performance. The complexity of a dynamic-list scheduling algorithm, such as the Force Directed Scheduling (FDS), is O(T*N2), where T is the time constraint and N is the number of operations. Static-list scheduling algorithms are the least complex among the known class of scheduling techniques with a linear time complexity of O(T*N). Typically, static-list scheduling algorithms, in order to maintain low-complexity, do not perform any look-ahead like that of FDS. The drawback is that, static-list scheduling algorithms may not generate high-quality schedules.