基于多阶段优化的高质量总体布线算法  

High Quality Global Routing Algorithm Based on Multi-Stage Optimization

作　　者：刘耿耿[1,2] 裴镇宇 徐宁 Liu Genggeng;Pei Zhenyu;and Xu Ning(College of Computer and Data Science,Fuzhou University,Fuzhou 350116;State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190;School of Information Engineering,Wuhan University of Technology,Wuhan 430070)

机构地区：[1]福州大学计算机与大数据学院,福州350116 [2]中国科学院计算机体系结构国家重点实验室,北京100190 [3]武汉理工大学信息工程学院,武汉430070

出　　处：《计算机辅助设计与图形学学报》2024年第4期607-614,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(62372109);福建省杰出青年科学基金(2023J06017)。

摘　　要：总体布线是VLSI物理设计中关键的一个环节.针对现有总体布线算法的布线容量利用率低和布线结果容易陷入局部最优的问题,提出一种基于多阶段优化的高质量总体布线算法.首先在预连接阶段和全局考量下的布线重组阶段中引入虚拟容量动态调整策略,提高布线容量利用率;然后在布线重组阶段引入布线子区域自适应扩展策略,缩小算法全局搜索的空间,提高算法的布线效率;最后采用A*算法启发式搜索并结合粒子群算法全局搜索的能力,避免算法在布线过程中单一地选择最短路径,陷入局部最优.与现有总体布线算法在ISPD基准电路上的实验结果表明,所提算法的布线结果取得了6.0%~22.8%的线长优化.Global routing is a crucial step in VLSI physical design.To address the problems that the low utilization rate of capacity and easy to fall into local optimum in the existing global routing algorithms,a high-quality global routing algorithm based on multi-stage optimization is proposed.First,the virtual capacity dynamic adjustment strategy is introduced in the pre-connection stage and the routing reorganization stage to improve the utilization rate of capacity.Then,in the routing reorganization stage,the routing subarea adaptive expansion strategy is proposed to narrow the search space and improve the routing efficiency.Finally,the A*algorithm heuristic search is combined with the global search capability of the particle swarm algorithm to avoid the algorithm to choose the shortest path in the routing process,and thus avoid the algorithm to fall into the local optimum.Experimental results comparing with existing global routing algorithms on ISPD benchmark circuits show that the routing results of proposed algorithm reduce the wirelength by 6.0% to 22.8%.

关 键 词：超大规模集成电路 总体布线 多阶段优化 动态调整策略 A*算法 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]