Unification of scheduling, binding, and retiming to reduce power consumption under timings and resources constraints

摘要

Scheduling and binding are two tasks found in high-level synthesis of hardware as well as in compiling software. These tasks are realized on graphs that are models of the hardware or of the software to be compiled to run on a specific processor. Scheduling focuses on determining the start execution time of each node in the graph. Binding is the task of assigning each node in the graph to a specific computational element. Realize binding before or after scheduling can exclude generating high-quality designs (hardware or binary code). The latter statement is true in particular in the era of design for low power. Do not combine scheduling and binding can lead to designs with high switching activities and hence to high power consumption. To the best of our knowledge, there is no approach at this moment that addresses the problem of unifying scheduling and binding with an exact algorithm to produce designs with reduced power consumption. Known approaches to that problem are heuristics. That problem is NP-hard in general, since it is the composition of two NP-hard problems. Also, it has not yet been formulated in the literature. The problem becomes more complex when one has to deal with cyclic graphs and/or there are constraints to be met such as timings. For cyclic graphs, one has to integrate retiming in the unification of scheduling and binding. We propose a mathematical formulation to that problem. We extend this formulation to solve the problem of combining modulo scheduling, binding, and retiming under timings and resources constraints while reducing power consumption due to switching activities. The proposed approach is tested using known benchmarks. Based on obtained numerical results, this approach is able to reduce power consumption by 33.24% on average, with an average of 33.83 s as a run time.