基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法

摘要：

Steiner最小树是超大规模集成电路中布线阶段的最佳模型,进一步考虑能够有效防止信号失真的电压转换速率(Slew)约束这一个更为贴近实际芯片设计模型和更具线长优化能力的X结构,首次提出基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法.首先,为了避免频繁的Slew约束计算,提出了高效的预处理策略,并且提出一种能够有效考虑Slew约束的针对性的惩罚机制.其次,为了能够有效求解该离散问题,基于遗传算子重新设计了粒子群优化算法的离散更新机制,并提出一种更适合遗传算子的引脚对编码方式.然后,为了进一步优化布线树的长度,提出一种有效的精炼策略.最终,提出一种混合修正策略以完全满足Slew约束.实验表明,所提算法可完全满足电压转换速率约束并取得同类工作中最佳的布线结果.

关键词：粒子群优化;Steiner树;电压转换速率约束;X结构;超大规模集成电路

所属期刊栏目：44

分类号：TP18(自动化基础理论)

资助基金：本课题得到国家自然科学基金;国家重点基础研究发展计划;计算机体系结构国家重点实验室开放课题;福建省自然科学基金

在线出版日期：2021-12-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共18页

页码：2542-2559