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

来源：计算机集成制造系统杂志2024年第12期北京时间：

作者：邓新国, 叶似锦, 陈家瑞

单位：1.福州大学计算机与大数据学院2.锐捷网络股份有限公司

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

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

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