A Power-Driven Stochastic-Deterministic Hierarchical High-Level Synthesis Framework for Module Selection, Scheduling and Binding
A Power-Driven Stochastic-Deterministic Hierarchical High-Level Synthesis Framework for Module Selection, Scheduling and Binding
复制标题
用于模块选择、调度和绑定的动力驱动随机确定性分层高级综合框架
DOI：
--
复制
发表时间：
2019
影响因子：
--
通讯作者：
S. Dutt
中科院分区：
文献类型：
--
作者：
Xiuyan Zhang;Ouwen Shi;Jian Xu;S. Dutt
我们提出了一个能量驱动的层次结构框架，用于高级综合中模块/功能单元的选择、调度和绑定。对于大型和复杂问题的算法设计的一个重要方面是在解的质量和时间复杂性之间达成折衷。
为此，我们集成了运行时间效率非常高的列表调度算法的改进版本，称为修改列表调度(MLS)和用于模块选择的功率驱动模拟退火法(SA)。我们的分层框架有效地探索了问题的解决方案
通过SA对功率驱动的模块选择解空间的广泛探索，并且对于每个模块选择解，使用最小二乘法来获得调度和(集成)绑定(S&B)解，其中绑定是规则的(最小化FU的数量，从而
FU漏电)或具有多路复用器/多路分解器功率考虑的功率驱动。该框架避免了传统SA算法中非常密集的模块选择和S&B的探索，但通过仅探索功率驱动的重要方面，保留了SA的基本能力
以随机方式选择模块。与仅优化FU泄漏功率的现有(近似)算法相比，所提出的分层框架提供了平均9.5%的FU泄漏功率改进，并且具有2.5-3倍的较小运行时间。更进一步，比较
对于复杂的扁平模拟退火法框架和用于延迟约束下的总(动态和泄漏)FU和体系结构功耗优化的最优0/1-ILP公式，PSA-MLS提供了5.3-5.8%的改进和2倍的运行时间优势，并且具有平均最优性
差距只有4.7-4.8%，显著的运行时优势分别是1900倍以上。
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.