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

作者：

陈虹1，陈传东1，2，魏榕山1

作者单位：

1.福州大学 物理与信息工程学院，福建 福州 350108；

2.福建省光电信息科学与技术实验室，福建 福州 350108。

摘要：

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

引言：

印制电路板（Printed Circuit Board，PCB）是集成电路（Integrated Circuit，IC）的载体^[1]。随着大规模集成电路和超大规模集成电路的发展，PCB的集成度要求越来越高，现有的电子设计自动化（Electronic Design Automation，EDA）工具已无法满足高密度引脚布线要求，一般与人工布线相结合，布线工作变得耗时且复杂^[2]。因此，为了得到更高效的布线结果，EDA自动布线算法成为近几年的研究热点。

传统意义上，PCB布线分为逃逸布线（Escape Routing）和区域布线（Area Routing）^[3]。逃逸布线是指将引脚按要求逃逸到组件边界，其作为PCB布线的关键一环，对电路性能好坏和后期的区域布线起着决定性作用。区域布线是指将不同组件中对应功能的引脚实现互连，合法化的逃逸布线结果为区域布线阶段节省布线空间，并大大提升PCB整体布通率。为实现更高的空间利用率，逃逸布线又可精细化分为有序逃逸布线（Ordered Escape Routing，OER）和无序逃逸布线^[4]。

文章来源：《电子技术应用》杂志1月刊