jolpe19-publ.pdf (1.1 MB)
Download file

A Power-Driven Stochastic-Deterministic Hierarchical High-Level Synthesis Framework for Module Selection, Scheduling and Binding

Download (1.1 MB)
journal contribution
posted on 04.06.2021, 22:01 by Xiuyan Zhang, Ouwen Shi, Jian Xu, Shantanu DuttShantanu Dutt
We present a power-driven hierarchical framework for module/functional-unit selection, scheduling, and binding in high level synthesis. A significant aspect of algorithm design for large and complex problems is arriving at tradeoffs between quality of solution and timing complexity. Towards this end, we integrate an improved version of the very runtime-efficient list scheduling algorithm called modified list scheduling (MLS) with a power-driven simulated annealing (SA) algorithm for module selection. Our hierarchical framework efficiently explores the problem solution space by an extensive exploration of the power-driven module-selection solution space via SA, and for each module selection solution, uses MLS to obtain a scheduling and (integrated) binding (S&B) solution in which the binding is either a regular one (minimizing number of FUs and thus FU leakage power) or power-driven with mux/demux power considerations. This framework avoids the very runtime intensive exploration of both module selection and S&B within a conventional SA algorithm, but retains the basic prowess of SA by exploring only the important aspect of power-driven module-selection in a stochastic manner. The proposed hierarchical framework provides an average of 9.5% FU leakage power improvement over state of the art (approximate) algorithms that optimize only FU leakage power, and has a smaller runtime by factors of 2.5–3x. Further, compared to a sophisticated flat simulated annealing framework and an optimal 0/1-ILP formulation for total (dynamic and leakage) FU and architecture power optimization under latency constraints, PSA-MLS provides an improvement of 5.3–5.8% with a runtime advantage of 2x, and has an average optimality gap of only 4.7–4.8% with a significant runtime advantage of a factor of more than 1900, respectively.

Funding

An Effective and Time-efficient Approach to Solving Linear Discrete Optimization Problems using Discretized Network Flow

Directorate for Computer & Information Science & Engineering

Find out more...

History

Citation

Zhang, X., Shi, O., Xu, J.Dutt, S. (2019). A Power-Driven Stochastic-Deterministic Hierarchical High-Level Synthesis Framework for Module Selection, Scheduling and Binding. Journal of Low Power Electronics, 15(4), 388-409. https://doi.org/10.1166/jolpe.2019.1584

Publisher

American Scientific Publishers

Language

en

issn

1546-1998

Usage metrics

Categories

Exports