基于多策略优化的Slew约束下的X结构Steiner树构造方法

摘要

本发明提出一种基于多策略优化的Slew约束下的X结构Steiner树构造方法，包括以下步骤：步骤S1：结合三角剖分方法和最小生成树方法获得点集为引脚集的最小生成树；步骤S2：生成用于记录引脚以及障碍之间的信息的预查表，并将最小生成树转换成Steiner树；步骤S3：进行重布线，通过消除布线中经过障碍的较长片段并重新布线以降低Slew大小，使Steiner树部分满足Slew约束；并采用精炼策略，以进一步减少Steiner树的布线代价；步骤S4：逐个计算并修正不满足Slew约束的布线，使得内部树完全满足Slew约束。经过实验表明，本发明方案在线长及算法运行时间上均取得最优的结果。