Concurrent scheduling of multiple loops using the force-directed scheduling algorithm

Today electronic design automation software plays an important role in modern VLSI design technology. High-Level Synthesis (HLS) translates the behavioral specification of a digital system to a register transfer level structure. In this dissertation we focus on the scheduling problem in high-level synthesis. In particular, scheduling loop constructs under fixed hardware constraints. For software, 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. We proposed a new two-phase algorithm for loop scheduling based on the Force-Directed Scheduling (FDS) algorithm and loop fusion transformation. The algorithm interleaves the operations of the different control regions into the minimum number of control steps under a fixed hardware constraint. The algorithm also 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, 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 algorithm will result in effective reduction in the execution time under relaxed hardware resources and at least similar results to the traditional schedulers under tight hardware constraints. The performance of the proposed algorithm was evaluated and compared to the traditional sequential scheduling algorithms on a set of standard BLS benchmarks. The test results form the selected benchmarks show that the concurrent loop scheduling algorithm improves the execution time by 6 to 32% compared to the sequential scheduling algorithm.