叶似锦1,
陈家瑞1,,,
陈传东2
1.福州大学数学与计算机科学学院 福州 350108
2.福州大学物理与信息工程学院 福州 350108
基金项目:国家自然科学基金 (61977017)，国家科技部重点研发计划课题(2018YFB2202704)，中国福建光电信息科学与技术创新实验室(闽都创新实验室)基金(2021ZR142)
详细信息
作者简介:邓新国：男，1975年生，博士，副教授，硕士生导师，研究方向为VLSI电子设计自动化
叶似锦：男，1997年生，硕士生，研究方向为VLSI布线算法设计
陈家瑞：男，1981年生，博士，讲师，硕士生导师，研究方向为VLSI电子设计自动化
陈传东：男，1984年生，博士，讲师，硕士生导师，研究方向为VLSI电子设计自动化
通讯作者:陈家瑞 chenjiarui@fzu.edu.cn
中图分类号:TN43; TP302.1计量
文章访问数:344
HTML全文浏览量:142
PDF下载量:43
被引次数:0
出版历程
收稿日期:2020-12-09
修回日期:2021-04-16
网络出版日期:2021-04-27
刊出日期:2021-06-18
Ordered Escape Routing Combining Improved A* Algorithm with Rip-up and Reroute
Xinguo DENG1,Sijin YE1,
Jiarui CHEN1,,,
Chuandong CHEN2
1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
2. College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108, China
Funds:The National Natural Science Foundation of China (61977017), The Key Research and Development Project of the Ministry of Science and Technology (2018YFB2202704), The Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China (Mindu Innovation Laboratory) (2021ZR142)
摘要
摘要:逃逸布线是印刷电路板设计的一个重要组成部分。针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题，该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法。首先，通过代价预估函数确定引脚的布线顺序，使用改进A*算法初始化有序逃逸布线。接着，优化同长度布线路径，调整拥挤区域布线路径。最后，使用A*算法和广度优先搜索进行拆线重布。实验结果表明，该方法对给出的所有测试用例都实现了100%的逃逸，得到有序逃逸路径的可行解非常接近最优解，CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6%, 97.8%，总体线长也接近最优。提出的方法能够明显减少寻找可行解的时间，提高布线质量。
关键词:A*算法/
拆线重布/
有序逃逸布线/
最短路径
Abstract: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.
Key words:A* algorithm/
Rip-up and reroute/
Ordered escape routing/
Shortest path
PDF全文下载地址:
https://jeit.ac.cn/article/exportPdf?id=2285de7f-8e85-495e-bf07-32a3b31aec36
