Optimizing the instruction scheduler of high-level synthesis tool

Abstract: With the increasing complexity of the chip architecture design for meeting different application requirements, the corresponding instruction scheduler of high-level synthesis tool needs to solve complex scheduling problems. Dynamically Reconfigurable Resource Array (DRRA) is a novel architecture based on Coarse-Grained Reconfigurable Architecture (CGRA) on SiLago platform, the instruction scheduler of Vesyla-II, the dedicated High-Level Synthesis (HLS) tool targets for DRRA needs to schedule the specific instruction sets designed for Distributed Two-level Control System (D2LC). This kind of instruction has different lifetimes and is fully cooperative and persistent. Based on these features, the instruction scheduler needs to be applied to the scheduling algorithm under complex constraints. The previously existing naive algorithm shows poor scalability and low efficiency. This thesis attempts to design and implement a new scheduling algorithm to improve the performance of a constraint programming engine-based scheduler. The new scheduling algorithm is based on the heuristic method, the scheduler with this algorithm does the order prediction during the resource scheduling process. Besides, a test bench for meeting different instruction scheduling behavior is also designed, and the test bench could generate the maximum boundary of the schedule to do the performance profiling of the developed algorithm. Several experiments are performed to compare the proposed method against the previous naive algorithm. The execution time and quality of the result are crucial to determine which algorithm has better performance. The experiment result shows that the scheduler with a heuristic algorithm could reduce the execution time and have comparable schedule quality, and it could solve all the test cases, whilst the naive algorithm only can solve part of them.