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

Algorithm of global escape routing problem based on linear programming

作　　者：陈虹 陈传东[1,2] 魏榕山 Chen Hong;Chen Chuandong;Wei Rongshan(School of College and Information Engineering,Fuzhou University,Fuzhou 350108,China;Fujian Science&Technology Innovation Laboratory for Optoelectronic Information of China,Fuzhou 350108,China)

机构地区：[1]福州大学物理与信息工程学院,福建福州350108 [2]福建省光电信息科学与技术实验室,福建福州350108

出　　处：《电子技术应用》2023年第1期97-101,共5页Application of Electronic Technique

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

关 键 词：PCB自动布线 有序逃逸 线性规划 拥塞驱动 

分 类 号：TN47[电子电信—微电子学与固体电子学] TP391[自动化与计算机技术—计算机应用技术]