RESCHEDULING IN HIGH-LEVEL SYNTHESIS

Abstract

In High Level Synthesis (HLS) of digital circuit systems, scheduling and allocation are considered two independent processes to be done one after another and by doing so, certain optimisation opportunities are lost. Scheduling is unable to take into account allocation impacts while making decisions. The schedule produced by the scheduling phase determines two cost measures of the eventual synthesized circuits. They are the number of control steps needed to execute the schedule and the number of functional units of each type to perform the operations specified by the schedule. The scheduling problem has been extensively studied. It is a very well-understood problem and existing scheduling algorithms are very successful in terms of optimising the two cost measures. Further improvements to the scheduling algorithms should result in very small, if any, reductions in the two cost measures. The allocation phase allocates hardware resources to carry out the operations specified in the schedule. It determines the number of registers used, interconnect cost, multiplex or cost and other allocation costs. All these costs are dependent on the schedule produced during the scheduling phase. Therefore, we believe that the next major improvement from scheduling will be to take into account other allocation costs. Our thesis focuses on rescheduling. Rescheduling differs from scheduling in that it lakes in a scheduled graph instead of an unscheduled graph. We apply rescheduling as an intermediate way to integrate both scheduling and allocation phases together instead of combining them. Our rescheduling approach allows us to modify the schedule produced without deteriorating the quality of the schedule to take into account other aspects of the schedule related to allocation. This approach also allows us to build on top of current existing HLS system rather than revamping the whole system to implement our work. Towards this end, we identify a new class of nodes called flexible nodes with respect to a schedule. Flexible nodes can be assigned to different control steps without increasing the number of different functional units used as compared to the original schedule. And a novel algorithm called flexible node detection algorithm that identify them in a schedule is also devised. A schedule with flexible nodes gives rise to a set of equivalent schedules that greatly increases the choices that allocation has. Thus our flexible node detection algorithm is designed with the aim of finding the largest possible set of equivalent schedules. This roughly corresponds to the problem of finding as many flexible nodes as possible. Suitable heuristics are designed to guide our algorithm in achieving this. Our flexible nodes can be put into a number of uses. New rescheduling algorithms can be devised to take advantage of these flexible nodes to produce schedules that exhibit certain desirable properties required by the allocation phase. For instance, it can be used to optimise allocation costs such as register cost, interconnect cost and datapath cost. In our case, we have chosen a well-defined problem, the register allocation problem. We try to exploit our flexible nodes to modify an existing schedule to produce a new one that consumes less registers. Furthermore, this rescheduling phase will help to verify the utility of flexible nodes. With the aim of reducing register cost, new rescheduling algorithms that take advantage of these flexible nodes to produce schedules with lower register costs are designed. A random graph generator is also written to generate large quantity of data to test the performance and robustness of our algorithms. In addition to that, different cost measures for our rescheduling algorithms are tested and verified for goodness before the best one is chosen and used to run against our benchmark data. Our flexible nodes detection and rescheduling algorithms taken together constitute our Scheduler Optimizer. Prom a high level point of view, its job is to preprocess a schedule taken from a HLS synthesis to take other factors into account to produce a more optimal schedule for further processing by HLS synthesis.