结合改进A^(*)算法与拆线重布的有序逃逸布线  

Ordered Escape Routing Combining Improved A^(*)Algorithm with Rip-up and Reroute

作　　者：邓新国[1] 叶似锦 陈家瑞[1] 陈传东[2] DENG Xinguo;YE Sijin;CHEN Jiarui;CHEN Chuandong(College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China;College of Physics and Information Engineering,Fuzhou University,Fuzhou 350108,China)

机构地区：[1]福州大学数学与计算机科学学院,福州350108 [2]福州大学物理与信息工程学院,福州350108

出　　处：《电子与信息学报》2021年第6期1609-1616,共8页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61977017);国家科技部重点研发计划课题(2018YFB2202704);中国福建光电信息科学与技术创新实验室(闽都创新实验室)基金(2021ZR142)。

摘　　要：逃逸布线是印刷电路板设计的一个重要组成部分。针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A^(*)算法与拆线重布的有序逃逸布线方法。首先,通过代价预估函数确定引脚的布线顺序,使用改进A^(*)算法初始化有序逃逸布线。接着,优化同长度布线路径,调整拥挤区域布线路径。最后,使用A^(*)算法和广度优先搜索进行拆线重布。实验结果表明,该方法对给出的所有测试用例都实现了100%的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6%,97.8%,总体线长也接近最优。提出的方法能够明显减少寻找可行解的时间,提高布线质量。Escape routing is an important part of the integrated circuit physical design.In order to solve the problem of slow parallel escape routing with unsatisfactory outcomes,an algorithm of ordered escape routing,combining the improved A^(*)algorithm with the rip-up and reroute method is proposed.Firstly,the routing sequence of pins is determined by the cost estimation function and the improved A^(*)algorithm is used to initialize the ordered escape routing.Secondly,the routing paths of the same length are optimized and the routing paths of the crowded areas are adjusted.Finally,A^(*)algorithm and breadth-first search are employed to rip-up and reroute.The experimental results shows that this method achieved 100%escape routing for all given test cases,and that the feasible solution of the ordered escape paths is,to a great extent,close to the optimal solution.Compared to the Boolean Satisfiability Problem(SAT)algorithm and MMCF algorithm,this algorithm reduces CPU time by 95.6%and 97.8%,respectively,and makes the overall line length shorter.It is evident that the proposed method reduces the time required to find the feasible solution and optimize wire routing.

关 键 词：A^(*)算法 拆线重布 有序逃逸布线 最短路径 

分 类 号：TN43[电子电信—微电子学与固体电子学] TP302.1[自动化与计算机技术—计算机系统结构]