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

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

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

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

一种基于线性规划的全局逃逸布线算法

有序逃逸布线问题作为PCB设计中的关键一环,属于一类特殊的NP-困难问题,近年来得到广泛研究。传统方法中,基于整数线性规划或者是拆线重布类的启发式算法只适用于引脚数目较少的PCB引脚阵列,否则容易出现时间违规而导致布线失败。针对传统方法中大规模全局自动布线难的问题,基于线性规划的全局自动布线算法提出采用线性规划解决逃逸布线问题,并提出降低线网容量化解拥塞的新方法。与最新的逃逸布线算法相比,在处理大规模问题时,该算法不仅可以实现全部引脚的有序逃逸,并且布线时间提升50%,节省31%线长。