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

逃逸布线是印刷电路板设计的一个重要组成部分。针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题，该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法。首先，通过代价预估函数确定引脚的布线顺序，使用改进A*算法初始化有序逃逸布线。接着，优化同长度布线路径，调整拥挤区域布线路径。最后，使用A*算法和广度优先搜索进行拆线重布。实验结果表明，该方法对给出的所有测试用例都实现了100%的逃逸，得到有序逃逸路径的可行解非常接近最优解，CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6%, 97.8%，总体线长也接近最优。提出的方法能够明显减少寻找可行解的时间，提高布线质量。

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

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.