Escape routing is an important part in printed circuit board routing.As the number of pins increases and the scale of pin array expands,the ordered escape routing becomes more and more complex.To solve the problem that the time and quality of ordered escape routing cannot be balanced simultaneously,an ordered escape routing scheme combining heuristic algorithm and improved integer linear programming was proposed.The scheme consisted of two stages:initial solution construction,rip-up and reroute.In the first stage,the longest common subsequence was used to determine the initial wiring sequence of escape pins.Then,the heuristic algorithm of piece-wise cost prediction function is used to pre-route most pins in a short time,and finally to optimize and adjust the circuit.In the second stage,the subgraph range was determined first,then the improved integer linear programming expression was given,and the rip-up and rerouting was carried out based on the initial routing,to improve the routing rate and achieve local optimization.Finally,the shortest path algorithm was used to rip-up and reroute to further enhance the overall routing rate.Experimental results showed that the proposed routing scheme could obtain the optimal or ap-proximate optimal results in a short time,and the CPU time was reduced by 35.57％on average compared with the previous integer linear programming.
关键词
启发式算法/整数线性规划/有序逃逸布线/拆线重布/最短路径
Key words
heuristic algorithms/integer linear programming/ordered escape routing/rip-up and reroute/shortest path
维普
万方数据