Scheduling in High-Level Synthesis

High-Level Synthesis (HLS) translates the behavioral specification of a digital system to a register transfer level structure. In this book we focus on the scheduling problem in HLS. In particular, scheduling loop constructs under fixed hardware constraints. Loop execution time usually dominates the total execution time of the program. Therefore, efficient execution of loops is one of the most important obstacles facing high-performance scheduling. A new two-phase algorithm for loop scheduling based on the Force-Directed Scheduling (FDS) algorithm is proposed. The algorithm employs a local priority function called the 'mobility' of an operation to select the best operation to be rescheduled when resource violation is detected. In the first phase of the algorithm, the FDS algorithm is used to generate an initial schedule of the system that balances the distribution of the operations and optimizes the system hardware utilization. The second phase of the algorithm iteratively modifies the initial FDS schedule in order to resolve any hardware constraint violations. The performance of the proposed algorithm was evaluated using a set of standard HLS benchmarks.