时序松弛约束下绕障X结构布线算法

摘要

超大规模集成电路布线结果的优劣将直接影响芯片设计的质量.随着互连延迟逐渐成为芯片延迟的主要来源，在布线过程中进行时序分析变得愈发重要，同时，考虑到障碍在芯片布线中无法避免，以及X结构的引入可以更充分利用布线空间资源，因此，首次综合考虑时序松弛、障碍物以及更具互连优势的X结构，提出了一种时序松弛约束下绕障X结构布线算法.首先，为了避免重复地判断引脚间的连线是否经过障碍，提出一种高效的预处理策略，通过构建边障表来记录任意两引脚间的4种布线方式与所有障碍的关系.其次，为了解决构造Steiner最小树这一离散问题，将遗传算法与粒子群优化算法相结合，引入变异算子和交叉算子作为粒子群的离散更新方式.然后，提出了一种局部时序优化策略，通过优化布线半径达到优化最坏负松弛值的目的.接着，提出了一种有效的绕障策略，使布线在不经过障碍的前提下尽可能优化线长.最后，提出了一种路径精炼策略，选择布线资源共享程度最高的布线结构对原有的布线结构进行替换，进而达到优化线长的目标.实验结果表明，所提算法优化了布线的线长以及半径并在时序的关键性指标—最坏负松弛值上比相关算法分别优化了59%、51%和40%,极大提高了电路的稳定性.

关键词

超大规模集成电路 / Steiner最小树 / 绕障 / X结构布线 / 时序松弛约束