一种基于线性规划的全局逃逸布线算法
2023年电子技术应用第1期
陈虹1，陈传东1，2，魏榕山1
1.福州大学 物理与信息工程学院，福建 福州 350108；2.福建省光电信息科学与技术实验室，福建 福州 350108
摘要： 有序逃逸布线问题作为PCB设计中的关键一环，属于一类特殊的NP-困难问题，近年来得到广泛研究。传统方法中，基于整数线性规划或者是拆线重布类的启发式算法只适用于引脚数目较少的PCB引脚阵列，否则容易出现时间违规而导致布线失败。针对传统方法中大规模全局自动布线难的问题，基于线性规划的全局自动布线算法提出采用线性规划解决逃逸布线问题，并提出降低线网容量化解拥塞的新方法。与最新的逃逸布线算法相比，在处理大规模问题时，该算法不仅可以实现全部引脚的有序逃逸，并且布线时间提升50%，节省31%线长。
中图分类号：TN47；TP391
文献标志码：A
DOI: 10.16157/j.issn.0258-7998.222554
中文引用格式： 陈虹，陈传东，魏榕山. 一种基于线性规划的全局逃逸布线算法[J]. 电子技术应用，2023，49(1)：97-101.
英文引用格式： Chen Hong，Chen Chuandong，Wei Rongshan. Algorithm of global escape routing problem based on linear programming[J]. Application of Electronic Technique，2023，49(1)：97-101.
文献标志码：A
DOI: 10.16157/j.issn.0258-7998.222554
中文引用格式： 陈虹，陈传东，魏榕山. 一种基于线性规划的全局逃逸布线算法[J]. 电子技术应用，2023，49(1)：97-101.
英文引用格式： Chen Hong，Chen Chuandong，Wei Rongshan. Algorithm of global escape routing problem based on linear programming[J]. Application of Electronic Technique，2023，49(1)：97-101.
Algorithm of global escape routing problem based on linear programming
Chen Hong1，Chen Chuandong1，2，Wei Rongshan1
1.School of College and Information Engineering， Fuzhou University， Fuzhou 350108， China； 2.Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China， Fuzhou 350108， China
Abstract： As a key part of PCB design, the ordered escape routing problem is a special NP-hard problem, which has been studied extensively in recent years. In the traditional method, both ILP method and the heuristic algorithms based on ripping-up and rerouting are only applicable to small-scaled pin arrays with fewer pins, which easily lead to time violation. Aiming at the difficulty of large-scale global routing in traditional methods, the iteration-driven method is proposed to solve the global escaping routing problem by linear programming (LP), and to optimize area congestion by reducing capacity. Compared with the latest work, this algorithm can not only escape all pins but also achieve up to 50% times speed up and save 31% wire length.
Key words : PCB design；ordered escape routing；LP；congestion-driven
0 引言
印制电路板（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]。
本文详细内容请下载：https://www.chinaaet.com/resource/share/2000005084。
作者信息：
陈虹1，陈传东1，2，魏榕山1
（1.福州大学 物理与信息工程学院，福建 福州 350108；2.福建省光电信息科学与技术实验室，福建 福州 350108）
此内容为AET网站原创，未经授权禁止转载。