结合启发式算法与改进整数线性规划的有序逃逸布线  

Ordered escape routing combining heuristic algorithm and improved integer linear programming

作　　者：邓新国[1] 叶似锦 陈家瑞[1] DENG Xinguo;YE Sijin;CHEN Jiarui(College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China;Ruijie Network Co.,Ltd,Fuzhou 350007,China)

机构地区：[1]福州大学计算机与大数据学院,福建福州350108 [2]锐捷网络股份有限公司,福建福州350007

出　　处：《计算机集成制造系统》2024年第12期4302-4313,共12页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(61977017);中国福建光电信息科学与技术创新实验室(闽都创新实验室)基金(2021ZR142)。

摘　　要：在印刷电路板布线中,逃逸布线是重要的组成部分。随着器件引脚数量不断增加,引脚阵列规模不断扩大,有序逃逸布线问题变得愈发复杂。针对目前有序逃逸布线研究中布线时间与质量无法兼顾的问题,提出一种结合启发式算法与改进整数线性规划的布线方案。该方案分为构建初始解与拆线重布二个阶段。在第一个阶段,先利用最长公共子序列给出逃逸引脚初步布线顺序,接着利用分段代价预估函数的启发式算法,在短时间内对大部分引脚进行预布线。在第二个阶段,首先确定子图范围,然后给出改进的整数线性规划表达式,在初始布线的基础上进行拆线重布,提高布通率的同时达到局部最优。最后再使用最短路径算法进行拆线重布,进一步提高总体布通率。实验结果表明,提出的布线方案能够在较短的时间内得到最优或近似最优的布线结果,相较于使用整数线性规划方案来进行布线,CPU时间平均减少35.57%。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 approximate optimal results in a short time,and the CPU time was reduced by 35.57%on average compared with the previous integer linear programming.

关 键 词：启发式算法 整数线性规划 有序逃逸布线 拆线重布 最短路径 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TN41[自动化与计算机技术—控制科学与工程]