一种基于线性规划的全局逃逸布线算法_陈虹.pdf

电子技术应用 2023年 第49卷 第1期Computer Technology and Its Applications计算机技术与应用一种基于线性规划的全局逃逸布线算法陈虹1，陈传东1，2，魏榕山1（1.福州大学 物理与信息工程学院，福建 福州 350108；2.福建省光电信息科学与技术实验室，福建 福州 350108）摘 要：有序逃逸布线问题作为 PCB 设计中的关键一环，属于一类特殊的 NP-困难问题，近年来得到广泛研究。传统方法中，基于整数线性规划或者是拆线重布类的启发式算法只适用于引脚数目较少的 PCB 引脚阵列，否则容易出现时间违规而导致布线失败。针对传统方法中大规模全局自动布线难的问题，基于线性规划的全局自动布线算法提出采用线性规划解决逃逸布线问题，并提出降低线网容量化解拥塞的新方法。与最新的逃逸布线算法相比，在处理大规模问题时，该算法不仅可以实现全部引脚的有序逃逸，并且布线时间提升 50%，节省 31%线长。关键词：PCB 自动布线；有序逃逸；线性规划；拥塞驱动中图分类号：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 programmingJ.Application of Electronic Technique，2023，49(1)：97-101.Algorithm of global escape routing problem based on linear programmingChen 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-driven0 引言印制电路板（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。以往的工作中一般采用网络流方法解决无序逃逸布线问题57，然而网络流不能处理 OER 问题，因为其并不携带有序信息，一般采用启发式算法叠加拆线重布进行布线8。Luo 等人首次提出了将 OER 问题建模为平面布尔可满足性问题9，提出利用现有的布尔可满足性求解器进行求解，但其没有解决容量限制问题；2009 年，Yan 等人提出一种新的网络流模型建模10，在原本基础上解决了对角线容量建模的问题，但该模型有可能丧失97Computer Technology and Its Applications计算机技术与应用www.ChinaAET.com大量最优解；2016 年，Jiao 等人首次提出将最小成本多商品流方法（Min-Cost Multi-Commodity Flow，MMCF）用于解决有序逃逸布线问题11，主要通过在原始网络流模型中加入大量虚拟中转节点，以满足有序逃逸布线的约束，并采用 MMCF 求解器求解；最新的研究中，Jiao 等人将 MMCF 模型充分扩展以求解差分对问题12，并首次考虑优化线长问题，但该模型由于加入过多的虚拟点，在求解大规模问题时，解空间规模过大，容易引起时间冲突。本文主要讨论有序逃逸布线，即将 PCB 上的所有待逃逸引脚按照一定的顺序逃逸到组件的边界，如图 1所示。1 模型建立1.1 问题描述给定一个 OER 实例R，包含了逃逸区域R和待逃逸引脚集合。逃逸布线定义为：原始输入是一个m n的针栅引脚阵列（Grid Pin Array，GPA），其中有n个待逃逸引脚P=p1,p2,p3,pn，要求在满足指定布线约束下 逃 逸 到 指 定 边 界，并 输 出 所 有 逃 逸 路 径Nets=net1,net2,net3,netn。多商品流问题是指将网络中的多种商品从不同的源节点运输到不同的汇节点的问题13，根据目标函数的不同主要分为最小化成本和最大化利润两类，且商品在流通中不能超过每条有向边（弧）的承载能力14。在传统多商品流模型基础之上，有序逃逸布线还需满足 3 类布线约束，分别是线网非交叉约束、有序约束和容量约束15。1.2 网络流建模OER 问题是一类特殊的 MMCF 问题。给定一个拓扑网络G=(V,E)，其中V代表的是所有节点的集合，E代表的是有向图中所有弧的集合。对于所有的节点，按照运输的目的分为供应节点、需求节点和中转节点 3 类，其中：Vi代表逃逸引脚点的集合，对应 MMCF 模型中的供应节点；Vt代表加入的假想节点，对应中转节点；Vb代表组件边界节点，对应需求节点。其中(i,j)E代表从节点i到达节点j的有向弧。最终的网络流建模如图 2所示。为了便于描述问题，将其描述为整数线性规划约束式，引入以下符号：K表示所有待运输商品集合；ukij表示弧段(i,j)上的最大运输量；bki表示第k个商品在节点i的需求量，bki 0表示节点i是供应节点，bki j(11)xkij(0,1),(i,j)A,k K(12)其中，是一个很大的常量。目标函数（5）是最小化线长 和 违 反 逃 逸 引 脚 数 目yk的 惩 罚 成 本 之 和，只 有 当k Kyk=K时，所得到的才是主问题的最优解；约束（6）为引脚点作为起始点的网络约束；约束（7）为边界点作为逃逸终点的网络约束；约束（8）为中转节点的流量守恒约束；约束（9）限制所有经过某中转节点的流值不超过其容量；约束（10）限制中转节点出现走线交叉情况，其中W、E、N、S代表以i节点作为入点的 4 个方向的有向边；约束（11）为有序约束；约束（12）为变量取值约束。2.2 局部优化阶段基于上述操作，得到了 LP 初始解，但由于线性规划的解集为非整数，因此本次结果并不能作为最终的布线结果。根据 LP 初始解的结果构造新的子图，使用深度优先搜索找到每个引脚对应的所有路径，将每条路径映射为路径点集。遍历所有路径线网，若不同引脚对应的线网之间存在交叉，表示有多个引脚重复占用局部线网资源，判定为拥塞区域，将这两个路径点对应相连，完成子图构建。与传统增大拥塞区域权重来协商拥塞的方法不同，本文提出降低容量，迫使 LP 求解时发散出更多的路径边，增加可选路的概率。为了得到具体的拥塞区域，采用最大独立集方法求解子图中的非交叉路径点集合，一方面得到当前部分引脚的逃逸路线，另一方面得到当前存在交叉拥塞的剩余路径集合。降低剩余路径中的容量并返回 LP 模型，迭代求解，直至最大独立集求解出全部待逃逸引脚的逃逸路径，该路径集合则为主问题的最优解结构。2.3 加速策略对于大规模的 OER 问题中引脚个数庞大，导致约束式规模骤增、求解速度缓慢、效率低下等问题，设计了相应的加速策略来提高迭代算法的求解效率。加速策略如下：（1）利用启发式算法添加初始可行解线性规划迭代求解算法需要不断根据局部优化阶段返回的拥塞结果调整区域容量，在求解过程中，LP 可能需要根据优化结果求解多次，如果重复重新建模并求解，则时间成本过大。采用 Gurobi 支持利用启发式算法图 3算法流程图99Computer Technology and Its Applications计算机技术与应用www.ChinaAET.com输入初始可行解的功能，可以提早确认部分引脚的逃逸结果，将其作为初始解输入到后期迭代模型中，这样既可以消除重复建模求解的时间消耗，还可以保存之前模型的最优解结构，加速 Gurobi 的迭代求解。（2）利用 ILP 实现小规模分区求解由于线性规划是全局求解函数，求解时间与变量规模成正相关，当迭代时间超过允许范围时，将线性规划作为分区条件，保留当前可行解。在未逃逸的引脚集合中，以当前引脚点为中心选定初始范围，并利用 ILP 求解，若范围内未包含最优解，则向外扩散逃逸范围。经验证 ILP 算法在小规模 OER 问题求解已十分成熟，该策略大大缩减了不必要的迭代时间，加速主问题的求解。3 实验结果本节展示了所提出的基于线性规划的全局布线算法在有序逃逸布线方面的高效性。由于知识产权的限制，无法获得已发表的研究的执行代码，本文基本复现了 MMCF 算法12来比较最终布线结果。由于设备差异和算法的实施具有随机性，本文复现的算法所得到的结果可能与原数据存在差异，但是对比文献12所给定的结果相差较小，因此将复现代码的结果作为本文算法结果的对比数据。另外，由于该问题缺少基准数据，因此在算法性能分析上除了采用从各类学术工作中收集的数据集(包括 Case2、Case3、Case6、Case7、Case8）之外，为了更好对比算法在复杂绕障方面的性能，本文还随机生成了一些可布线的测试用例，共计 10 组不同的测试用例。本文算法采用 C+语言在 VS2019 平台上编程实现，线性模型采用 Gurobi9.1 求解器优化求解16。算法在处理器为英特尔酷睿 i7（主频为 2.30 GHz）、内存为 16 GB的 PC 上运行。表 1 所示为不同测试用例的布线结果。其中 Col 和 Row 表示引脚阵列的列数和行数，Pins 表示待逃逸引脚数量，Type 表示逃逸方向，本文默认引脚按顺时针方向逃逸。图 4 给出了 Case10 的布线结果。在小规模引脚阵列情况下，本文算法与 MMCF12运行性能相差不大，二者都可以在合理的 CPU 时间内保持高布通率。随着引脚阵列规模和 PCB 复杂程度增大，MMCF 方法12的时间复杂度增长很快，在 Case9 中，两种算法都能实现 100%的布通率，但是本文算法相较于MMCF 算法，CPU 时间平均优化 50%，线长优化平均提升 31%。当处理大规模引脚阵列如 Case10 时，MMCF 求解器在求解过程出现 CPU 运行时间违规，布线失败。而本文算法不仅能够逃逸出全部的引脚，而且能够实现线长和运行时间的双重优化。4 结论本文提出采用线性规划方法作为全局求解器求解有序逃逸布线问题，建立了相应的求解约束式，通过流分解成路之后采用最大独立集方式优化拥塞，为求解大规模的此类问题提供了一种新的方法。测试结果表明，所设计的基于线性规划的迭代算法在解决大规模或者是引脚阵列密集的有序逃逸布线问题时有很大的潜力。后续的研究可以在多商品流问题中考虑更多的加速策略，如优化求解方式等。参考文献 1 YAN T,WONG M D F.Recent research development in PCB layoutC/2010 IEEE/ACM International Confer表 1全局逃逸布线算法结果对比测试用例Case1Case2Case3Case4Case5Case6Case7Case8Case9Case10#Cols681010102020302550#Rows56615152115302630#Pins5625201842457060100#Type&1-side&2-side&3-side&3-side&2-side&4-side&2-side&4-side&4-side&3-sideMMCF-based12线长18227584106240360550452-时间/s0.0760.1200.7680.6282.35334.82050.78446.15083.404 1 000布通率/%100100100100100100100100100-本文算法线长1718607496166312510343860时间/s0.0650.0920.4200.6281.64421.13140.24437.65041.74089.438布通率/%100100100100100100100100100100图 4Case10 最终布线结果100Computer Technology and Its Applications计算机技术与应用电子技术应用 2023年 第49卷 第1期ence on Computer-Aided Design(ICCAD).IEEE,2010:398-403.2 HO Y K,LEE H C,CHANG Y W.Escape routing for staggered-pin-array PCBsJ.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2013,32(9):1347-1356.3 FANG J W,LIN I J,CHANG Y W,et al.A network-flow-based RDL routing algorithmz for flip-chip designJ.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2007,26(8):1417-1429.4 YAN T,WONG M D F.Correctly modeling the diagonal capacity in escape routingJ.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2012,31(2):285-293.5 MA Q,YOUNG E F Y,WONG M D F.An optimal algorithm for layer assignment of bus escape routing on PCBsC/2011 48th ACM/EDAC/IEEE Design Automation Conference(DAC).IEEE,2011:176-181.6 WANG K,WANG H,DONG S.Escape routing of mixed-pattern signals based on staggered-pin-array PCBsC/Proceedings of the 2013 ACM International symposium on Physical Design,2013:93-100.7 FANG J W,LIN I J,CHANG Y W,et al.A network-flow-based RDL routing algorithmz for flip-chip designJ.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2007,26(8):1417-1429.8 朱自然,陈建利,朱文兴.基于多阶段拆线重布的总体布线算法J.计算机辅助设计与图形学学报,2016,28(11):2000-2008.9 LUO L,WONG M D F.Ordered escape routing based on Boolean satisfiabilityC/2008 Asia and South Pacific Design Automation Conference.IEEE,2008:244-249.10 YAN T,WONG M D F.A correct network flow model for escape routingC/Proceedings of the 46th Annual Design Automation Conference,2009:332-335.11 JIAO F,DONG S.Ordered escape routing for grid pin array based on min-cost multi-commodity flowC/2016 21st Asia and South Pacific Design Automation Conference(ASP-DAC).IEEE,2016:384-389.12 JIAO F,DONG S.Ordered escape routing with consideration of differential pair and blockageJ.ACM Transactions on Design Automation of Electronic Systems(TODAES),2018,23(4):1-26.13 AHUJA R K,MAGNANTI T L,ORLIN J B.Network flowsJ.SIAM Review，1995,37(1):115-116.14 吴国涛,戚铭尧,张莹,等.考虑成本上涨的多商品流问题J.计算机集成制造系统,2015,21(12):3330-3335.15 SATTAR K,NAVEED A.Ordered escape routing using network flow and optimization modelC/2015 6th International Conference on Automation,Robotics and Applications(ICARA).IEEE,2015:563-568.16 BIXBY B.The gurobi optimizerJ.Transp.Research Part B,2007,41(2):159-178.（收稿日期：2022-01-11）作者简介：陈虹（1995-），女，硕士研究生，主要研究方向：集成电路设计。陈传东（1984-），男，博士，讲师，硕士生导师，主要研究方向：集成电路设计。魏榕山（1980-），男，博士，教授，硕士 生 导 师，主 要 研 究 方 向：集 成 电 路设计。扫码下载电子文档101