.png){kind=icon}
返回
Bounded Dynamic Level Maintenance for Efficient Logic Optimization
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2026.3688680.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
逻辑优化是电子设计自动化（EDA）流程中满足预期电路功耗、性能和面积（PPA）目标的关键阶段。这些逻辑电路通常表示为有向无环图（DAG），其中由节点层级量化的结构深度与定时性能密切相关。现代优化策略常采用迭代局部变换启发式方法（如重写、重构）直接作用于该DAG结构。由于优化会局部修改图，节点层级需要动态更新以指导后续决策。然而，存在显著差距：现有增量更新节点层级的算法对小变化无界。这导致给定局部子图$\{\Delta G_{i}\}_{i = 1}^{|V|}$在DAG$G(V,E)$上的更新总复杂度最坏为$O(|V|^{2})$。这种无界性质造成了严重的效率瓶颈，阻碍了优化流程的可扩展性，尤其是在应用于当今盛行的复杂电路设计时。本文分析了迭代逻辑优化中固有的动态层级维护问题，并从部分拓扑排序的角度进行阐述。基于分析，我们提出了首个有界算法以维护层级约束，对于更新序列$\{\Delta G_{i}\}$，其时间复杂度为$O(|V|\Delta\log\Delta)$，其中$\Delta=\max_{i}\|\Delta G_{i}\|$表示$\Delta G_{i}$的最大扩展规模。综合基准测试表明，我们的算法使重写和重构的平均整体速度提升6.4倍，得益于所提出的有界维护实现了亚二次时间更新，且不牺牲任何质量。
Keyword:
Logic optimization
dynamic level maintenance
incremental graph computation
查看更多机构