基于多源迪杰斯特拉搜索和拥塞协商的详细布线

作者：张亚东; 李起宏; 陆涛涛; 冯小辉

来源：中国集成电路, 2022, 31(04): 53-63.

• 迪杰斯特拉
• 拥塞协商
• 详细布线

“详细布线”是大规模集成电路（VLSI）物理设计过程中非常重要的一步，它将分布在芯片核内的模块、标准单元和输入输出单元按照逻辑关系进行互连，其布线结果的好坏将直接影响整个芯片的性能。本文提出了一种基于多源迪杰斯特拉搜索和协商拥塞的详细布线算法用于解决多端线网的连接问题和多线网之间的冲突。多源迪杰斯特拉同步搜索的方法有效解决了最小生成树（MST）权值估算的误差，逼近了多端线网线长最小的优化目标。基于协商拥塞的策略是一种启发式的算法，相比线性建模配合ILP（整数线性规划）求解器进行求解拥有更大的性能优势。实验结果表明，本文所述布线方法可以在合理的运行时间内得到高质量的布线结果。