一种基于分段并行思想的PCB布线加速策略.pdf

引用格式：李元康，郭权葆，高诗宇，等一种基于分段并行思想的 PCB 布线加速策略 J.微电子学与计算机，2023，40（9）：1-11LI Y K，GUO Q B，GAO S Y，et al.Segmented parallelism-based PCB routing acceleration strategyJ.Microelectronics&Computer，2023，40（9）：1-11.DOI：10.19304/J.ISSN1000-7180.2022.0529一种基于分段并行思想的 PCB 布线加速策略李元康，郭权葆，高诗宇，邱柯妮（首都师范大学 信息工程学院,北京 100048）摘要：基于网格的搜索布线方式是印制电路板 PCB 自动布线的主要手段.随着电路系统的规模不断增大、功能日益复杂,PCB 布线设计的挑战也不断增大.针对 PCB 布线地图规模较大且元器件障碍物较多的布线场景,常用的Lees 和 A*等布线算法突显出着搜索空间迅速增大且无法有效解决多网络布线顺序的问题.由此,提出一种基于分段并行思想的布线加速策略以提升布线效率.其基本思路为：将一个较大区域内的搜索问题分解成多个小区域内的并行搜索问题,并且针对不同区域内障碍物的特征采用自适应的启发引导函数,从而实现有效减少搜索空间、加快搜索速度、优化布线效果.模拟实验表明,在 150150 的网格布线场景中,所提方法与 Lees 算法和 A*算法相比较,搜索速度分别可提升 160 倍和 17 倍.关键词：PCB；自动布线；分段并行；启发函数；A*算法中图分类号：TN41 文献标识码：A 文章编号：1000-7180（2023）09-0001-11Segmented parallelism-based PCB routing acceleration strategyLI Yuankang，GUO Quanbao，GAO Shiyu，QIU Keni（College of Software,Capital Normal University,Beijing 100048,China）Abstract：The grid-based routing method is the main means of printed circuit boards(PCB)routing.As the componentdensity and functional complexity of circuit systems continue to increase,the challenges of PCB routing rapidly grow.While routing map size and component obstacles increase,the commonly used PCB routing algorithms such as Lees and A*have a dramatically increasing search space and cannot effectively solve the problem of multiple network routingsequences.To address these problems,a routing acceleration strategy based on the idea of segmented parallelism isproposed to improve the routing efficiency.The basic idea is to decompose the search problem in an original large area intoparallel search problems within multiple smaller areas,and adopt an adaptive heuristic guidance function to adapt to thefeature of multiple areas.In this way,the huge search space can be effectively reduced,thus accelerating the routingprocess.The simulation experiments show that in a 150150 grid map,the proposed method can improve the search speedby 160 times and 17 times compared with the Lees and A*algorithms,respectively.Key words：PCB；Auto-routing；Segmented parallelism；Heuristic functions；A*algorithms 1引言电子设备广泛应用于汽车、国防、航空航天、消费娱乐、医疗器械等与国计、民生密切相关的领域.电子设备中的印制电路板（Printed Circuit Board,PCB）通过导线将各电子元器件按照设计意图进行电气互连,由此实现预定的电气功能.PCB 布线是电子产品设计中至关重要的一环,其目标可以归纳为两个 收稿日期：2022-09-03；修回日期：2022-11-03基金项目：国家自然科学基金（61872251）40 卷 第 9 期微 电 子 学 与 计 算 机http:/Vol.40No.92023 年 9 月MICROELECTRONICS&COMPUTERSeptember 2023层次：（1）根据电路的连接关系描述,在满足设计、工艺规则的要求和满足电气性能的条件下,在限定区域内 100%地 完 成 既 定 的 电 气 互 连1；（2）在完成布线的前提下,PCB 布线的目标还在于进一步优化布线结果,使所需的 PCB 面积最小化、PCB 实现的功能完备、PCB 布线的效率更佳.随着集成电路工艺的迅速发展及复杂应用不断增多,电子设备的体积越来越小、功能日益复杂,PCB布线难度也持续增大2.此时,纯粹人工布线的效率已经远远不能满足设计场景的需求,而基于 EDA 工具实现的自动布线功能能够大大提升设计效率.但随着电子元器件管脚排布密度越来越高、PCB 尺寸越来越小,现有的 PCB 自动布线工具正面临着日益严峻的挑战,主要表现为 PCB 自动布线的难度越来越大,布线效率越来越不能满足设计周期的需求.实现高效的 PCB 自动布线需要依赖成熟可靠的布线算法.最早使用的 Lees 算法3的基本思想是在整个布线路径搜索过程中总是向四周同时扩散多个搜索方向,其缺点是搜索过程缓慢、对内存空间的需求很大.后来,人们对 Lees 算法进行了不断的改进和完善,其中,A*搜索算法4是之后最经典也是目前应用最为广泛的算法之一.该算法通过启发式搜索,基于评估函数找到一条最优路径.A*算法并没有遍历所有可行解,比 Lees 算法速度更快捷高效,但是计算量依然很大.A*算法中,不同的启发式函数会产生不同的布线结果,糟糕的情况下会造成布线拥堵5.针对现有布线算法搜索空间大、搜索时间慢的问题,本文在 A*算法的基础上提出一种基于分段并行思想的布线加速策略.其基本思路为将一个较大区域内的搜索问题分解成多个小区域内的并行搜索问题,并且针对多个区域内元器件障碍物的特征采用适应性的启发引导函数,由此可有效减少搜索空间、加快搜索速度、优化布线效果.本文提出了分段拐点和布线地图复杂度的概念,指导布线区域分块,进而在此基础上设计了高效的分段节点搜索方法.进一步地,本文还探讨了针对不同区域分块采用适宜的启发式函数来指导布线.基于上述举措,我们提出的分段并行布线算法能够大大减少搜索空间、有效缩短自动布线时间和线长.总结来说,本论文研究的主要贡献表现在如下四个方面：(1)将 A*算法中复杂的启发式搜索问题分解成多段更为简单的搜索布线问题并且并行执行,有效删减了无意义的搜索范围、缩短了布线时间.(2)提出了一个搜索分段节点的算法,引入了拐点和地图复杂度的概念来指导搜索区域的分解.(3)探究了启发函数中欧几里得距离、曼哈顿距离和切比雪夫距离在不同布线场景中的布线效果,并提出采用适应性的启发函数进一步提升布线效率.(4)搭建了模拟布线平台,该平台具备自定义布线网络、障碍物和网格地图大小的功能.并且支持Lees 算法、多种启发函数下的 A*搜索算法和分段并行搜索算法.2相关工作随着 PCB 上承载的功能的复杂度日益增强,EDA 工具软件成为电子工程师依赖的主要设计手段.在 PCB 设计中,布线是非常关键并且耗时的过程.电子元器件布局结束后,需要将电势相同的信号网络在满足设计、工艺规则的要求和满足电学规则的条件下,在限定区域进行连接6.而自动布线算法将这个过程模拟成在一定区域内具有相同电势引脚相连接的优化问题7.自动布线算法驱动布线过程的执行,优秀的布线算法可以实现极高的布通率,并且大大节省布线时间.布线策略通常可以分为直接区域内布线8和在复杂和大规模的信号网络中分布实现的全局布线和详细布线9-11.其中,全局布线中经常遇到的子问题也是在有障碍物的网格地图上寻找两个管脚的最短距离.表 1 总结了目前应用最广泛的经典路径搜索算法 Lees 算法和 A*搜索算法,以及在这两种算法基础上的优化算法.表 1 路径搜索算法Tab.1 Path Searching Algorithm算法名称特征描述Lees算法3大范围搜索,速度慢且对内存需求高最小迂回算法12加入了评价函数L(p)指导布线非对称搜索13加快搜索速度但无法保证最短距离A*算法4利用启发式信息寻找最优路径LPA*算法14处理动态环境下最短路径问题A*变体算法15减少扩展的优先级队列操作的次数GAA*算法16在随时间变化的状态空间中工作ARA*算法17应用在机械臂和小车路径规划中DRAPS18可以处理复杂的设计规则父节点约束19引入当前节点的父节点改进型A*20改进距离计算公式和评估函数3D A*21用于多层PCB布线2微电子学与计算机2023 年Hadlock 基于 Lees 算法提出了一种加速优化版本：最小迂回算法12.J.Soukup 提出了一个带有固定含义的非对称搜索算法13,可以加快搜索速度但是不能保证最短距离.LPA*算法14,是一种参考人工智能的增量搜索进行改进的 A*搜索算法,它可以解决动态环境下从给定起始点到给定目标点的最短路径问题.文献 15 中提出的 A*变体算法可以减少 A*及其扩展的优先级队列操作的次数.GAA*算法16是另一项加速优化 A*搜索算法的改进工作,它能够在开始状态随时间变化的状态空间中找到最短路径.ARA*算法是基于 A*算法改进的随时启发式搜索算法17,它能够在极短时间内找到一个次优解,然后随着时间推移,找到一个最优解,该算法主要用于机械臂的路径规划问题中.DRAPS18提出了一种基于 A*搜索的算法来处理复杂的设计规则.文献 19 在 A*算法的基础上,引入了当前节点的父节点对 A*算法中启发函数的影响,并且寻求启发函数的最优权重.文献 20 通过改进 A*算法中距离计算公式和评估函数,提高了 A*算法的搜索效率,与标准的 A*算法相比搜索时间减少了约 14%,该算法主要用于机器人的路径规划问题.文献 21 提出了一种考虑实际约束的优化 3D A*算法,用于多层 PCB 自动布线,实现了较高的布通率.此外,机器学习也用于 PCB 布线中的子问题,例如将全局布线建模为深度强化学习问题22.A*搜索算法实际上也是 Lees 算法的一种优化形式,是基于启发式算法的思维,利用启发函数 h(n)获得对于从任意结点 n 走到目标结点的最小代价的估计.因此,选取合适的启发函数对于提高布线的效率和精度至关重要.h(n)是节点 n 距离目标点的预计代价,如果 h(n)恰好等于从结点 n 走到目标结点的步数,A*算法扩展的所有结点都在最优路径上,而不会扩展任何其他无关结点,此时 A*算法的速度相较于Lees 算法更快.如果 h(n)所给出的信息大于从结点n 走到目标结点的步数,那么 A*算法将无法确保能够找到最优路径,但它会运行得更快.基于网格的路径规划问题中通常用曼哈顿距离（公式 1）、欧几里得距离（公式 2）或切比雪夫距离（公式 3）作为启发函数.不同的启发函数对最终寻径的结果会产生不同的结果.（1）基于曼哈顿距离的启发函数：h(n)=|x1x2|+|y1y2|（1）（2）基于欧几里得距离的启发函数：h(n)=(x1x2)2+(y1y2)2（2）（3）基于切比雪夫距离的启发函数：h(n)=max(|x1x2|,|y1y2|)（3）通常利用公式（4）中的评价函数来评估各个节点的代价,以获取代价最低的节点为拓展方向,直至达到目标点位置23.f(n)=g(n)+h(n)（4）上述函数中,g(n)是节点 n 距离起点的代价,h(n)是节点 n 距离目标点的预计代价,也就是 A*搜索算法中的启发函数.评价函数 f(n)中 g(n)和 h(n)的权重比例也影响 A*搜索算法的计算结果23.尽管在寻径搜索算法演进的过程中各种优化技术层出不穷,但是它们的应用场景通常定位在机械臂和小车的路径规划中,于 PCB 自动布线场景还存在诸多不相适宜之处.本文针对 PCB 布线场景提出了一种基于 A*搜索算法的并行优化方法,不仅可以减少搜索成本,还可以通过分段并行布线来加速和优化布线过程.3研究动机A*搜索算法是一种直接的搜索算法,因此被广泛应用于路径规划问题.其缺点是实时性差,每一节点计算量大、运算时间长,而且随着节点数的增多,算法搜索效率降低.以图 1(a)为例,黑色方格代表元器件障碍物,红色方格代表 A*搜索算法计算出的路径,黄色区域为A*搜索算法遍历的区域.随着布线地图的增大、元器件障碍物增多,A*搜索范围会大大增加,布线速度也由此大大拖慢.针对这一问题,考虑将布线区域进行分块,通过选取合适的“分段节点”,将 A*搜索算法分段并行执行.如图 1(b)所示,可以将搜索区域分成多个更小的区域来做并行的路径规划.这样能够有效缩小搜索区域、缩短搜索时间,从而提升搜索效率.A*搜索算法的本质是迷宫算法24,一次只计算一个网络7,因此常常会产生布线堵塞的情况,可能导致一个可解的问题无法解决25.在图 2(a)所示的例子中,网络 1 的布线结果造成了网络 2 的布线区域被堵塞,修改 A*搜索的启发函数后可以给网络 2 预留出走线空间,从而提高布通率,如图 2(b)所示.可见,选择合适的启发式函数可以提高布线的效率和精度.在分段搜索的基础上,本文还将从启发函数的角度切入,研究不同启发式函数在特定的 PCB 布线场景下对布线效果的影响,为不同的布线区域匹配合适的布第 9 期李元康，等：一种基于分段并行思想的 PCB 布线加速策略3 线启发引导方案.4分段并行搜索算法为了缩小 A*搜索算法遍历的空间,本文提出了一种分段式并行搜索的 A*改进算法.图 3 为提出改进布线算法的流程框图.输入地图信息搜索拐点搜索分段节点并行搜索Find Path 1Find Path 2Find Path n输出路径图 3分段并行搜索算法流程图Fig.3 Flowchart of segmented parallel search algorithm 分段并行搜索算法步骤如下：输入.地图 mazeMap,初始点坐标 StartPoint,目标节点坐标 EndPoint输出.搜索路径 pathStep1.利用算法 1 搜索拐点Step2.输入拐点,利用算法 2 搜索分段节点 Q1,Q2,Step3.第一段搜索 FindPath1(StartPoint,Q1);第二段搜索 FindPath2(Q1,Q2);第 n 段搜索 FindPath2(Qn-1,EndPoint);StartPoint(x1,y1)EndPoint(x2,y2)Q(x,y)FindPath1StartPoint(x1,y1)Q(x,y)T1首先输入初始点坐标和目标节点坐标,以及网格地图信息.通过网格中不同区域的地图复杂度将地图分块,然后通过算法1（5.11 节详述）和算法 2（5.12 节详述）找到合适的分段节点,将原本搜索过程分成多段并行执行.第一段搜索过程为,以起始点为初始节点,分段节点为目标节点,然后用 A*搜索算法进行搜索,计算时间为.以此类推,第 N 段 阻碍物(元器件)阻碍物(元器件)搜索区域布线结果分界线目标点(x2,y2)目标点(x2,y2)初始点(x1,y1)(a)原始 A*算法搜索(b)将搜索区域分块初始点(x1,y1)图1基于 A*算法的分区域搜索思想Fig.1 The idea of subregional search based on A*algorithm 障碍物2SSSSTTTSST211网络 1 布线结果(a)通道堵塞(b)通道没有堵塞网络 1网络 2障碍物SS网络 2 布线结果网络 1 布线结果网络 1网络 2图2A*算法会造成通道堵塞,造成布线问题无法解决Fig.2 The A*algorithm may suffer channel congestion,resulting in routing failure4微电子学与计算机2023 年FindPathNQ(x(n1),y(n1)EndPoint(x2,y2)T2T=maxT1,T2,.TN搜索过程为,以分段节点为初始节点,为目标节点,依旧利用 A*搜索算法进行搜索,计算时间为.由于提前找到分段节点,各段搜索过程互不影响,可以并行执行,最终整体搜索时间.FindPathFindPath1FindPath2以二分段并行为例,图 4(a)所示为 A*搜索算法的搜索结果,红色线段为搜索路径,它直接通过 A*搜索得到布线结果.图 4(b)为分段并行搜索算法的搜索结果,红色线段为搜索结果,蓝色线段为搜索结果,并且这两个搜索过程并行执行.显而易见,A*搜索算法和分段并行搜索算法的布线结果也不同,分段并行搜索算法的路径更贴合PCB 布线的要求.这是因为 A*搜索算法的计算过程中只是单一的启发函数指导布线方向,而分段并行搜索算法可以将多种启发函数相结合,最终获得更合适的布线结果.总之,提出的分段并行搜索算法,不仅可以通过将布线区域分块并行执行来减少搜索区域、加快搜索速度,还可以灵活选择不同的启发函数来驱动布线,以达到布线加速和布线优化的效果.Find Path搜索结果Find Path 1搜索结果Find Path 2搜索结果初始点(x1,y1)初始点(x1,y1)目标点(x2,y2)目标点(x2,y2)分段节点(x0,y0)图 4基于分段并行优化的 A*搜索算法寻径Fig.4 Pathfinding of A*Search Algorithm Based on Segmented Parallel Routing Optimization 5关键技术分析本文提出的分段并行 A*搜索算法需要解决两个关键问题：（1）如何确定最佳的分段节点,使得各段的搜索时间接近,由此实现最佳的加速比；（2）如何根据不同区域内元器件障碍物的特征来选择合适的启发函数驱动布线,由此提升寻径效率.5.1分段节点的搜索如前所述,提出的基于分段并行思想的 A*搜索算法的基本思路是将一个较大区域内的搜索问题分解成多个小区域内的并行搜索问题.其中的一个关键点在于确定合适的分段节点,使得各段的搜索时间尽可能短并且均衡.由于不同区域的元器件障碍物布局和复杂度不同,分段节点的选择很难通过平均分段的方式来实现均衡,本文在这一关键点上提出一种基于拐点的分段节点搜索算法,可快速定位布线起点至终点之间的 N 分段点.其主要步骤由 N 段拐点搜索算法和 N 分段节点搜索算法两部分组成.5.1.1拐点搜索为便于进一步解释,首先给出拐点的定义：拐点是指布线路径的搜索区域内满足其上下相邻的节点有且仅有一个为障碍物,并且它左右相邻的节点有且仅有一个为障碍物的布线网格点.S(x1,y1)T(x2,y2)xxx拐点的意义在于为起始点和目标点之间提供有效绕过障碍物的线段连接.图 5 示例了一种针对起始点和目标点之间存在一个障碍物的拐点搜索过程.通过遍历初始点和目标点线段之间的元素可以得到第一个遇到障碍物的节点（图 5(a)中黄色的点）.从节点 开始搜索.首先搜索节点垂直方向相邻两个节点,如图 5(b)所示.如果两个节点均为障碍物,那么将节点 x 向垂直方向平移,如图 5(c),继续搜索该节点上下相邻节点是否都为障碍物.重复此搜索过程,直至将黄色节点 垂直移动到障碍物边缘,如图 5(d),满足该节点的上下相邻两个节点有且仅有一个障碍物.接下来搜索该节点左右相邻节点,与垂直方向的搜索过程一样,直至该节点左右相邻节点有且仅有一个障碍物,如图 5(e),最后根据搜索方向推算出满足需求的点的位置,如图 5(f)中蓝色的点.通过图 5 演示的方法可以从障碍物着眼找到初始点和目标点线段上的拐点.如果既定目标为 N 段并行,则由此在该线段上选取 N-1 个障碍物,并找到绕过这些障碍物的 N-1 个拐点.其搜索过程可由算法 1 描述如下：算法 1 拐点搜索算法输入：地图 mazeMap,初始点 S,目标节点 T第 9 期李元康，等：一种基于分段并行思想的 PCB 布线加速策略5 输出：搜索拐点 yStep1.从初始点开始,遍历 mazeMap 中初始点和目标点线段上元素,直到遇到障碍物节点 xStep2.搜索节点 x 垂直相邻节点,判断是否为障碍物Step3.如果垂直相邻节点都为障碍物,则将节点垂直平移,然后重复 Step2.否则进行 Step4Step4.搜索节点 x 水平相邻节点,判断是否为障碍物Step5.如果垂直相邻节点都为障碍物,则将节点水平平移,然后重复 Step4.否则输出节点 x 继续水平、垂直平移一个单位的节点,即拐点 y.5.1.2分段节点搜索拐点提供了布线寻径过程中可有效绕过障碍物的关键点.根据给定的 N 段并行规划,可以形成 N-1个拐点集.结合起点、终点和拐点集中的关键点,可以依据其中相邻点构成的矩形构建 N 个布线地图子区域.接下来如何在此基础上进一步确定合适的分段节点使得最大的分段搜索时间尽可能小呢？不难发现,元器件障碍物的复杂程度是影响搜索时间的重要因素之一,越是障碍物复杂的区域,搜索空间就越大,导致搜索时间长.因此为了更加合理评 0,1)SiNSi总格数SiNSi障碍物数量SiSiNSi总格数NSi障碍物数量i判分段节点的位置,提出了布线地图复杂度的概念,表示布线区域内元器件障碍物与区域面积的比值.如公式(5)所示,表示分段节点和初始节点横纵坐标所包含的矩形的区域.表示在区域中所有方格的数量,表示在区域中障碍物方格的数量.如图 6 所示,绿色的点为分段节点,分段节点与初始点围成的矩形区域.=36,=2,=1/18.i=NSi障碍物数量NSi总格数（5）障碍物分段节点初始点(x1,y1)目标点(x2,y2)分段节点(x0,y0)SiSj图 6地图复杂度示例Fig.6 An example of map complexity in(x,y)Si(xs,ys)Si(xs,ys)T(xt,yt)显而易见,布线距离也是影响路径搜索时间的一个重要指标.为此,引入布线距离比的概念,表示某布线区域内节点和初始节点的曼哈顿距离与初始节点和目标节点的曼哈顿距离的比值.i=|xxs|+|yys|xtxs|+|ytys|（6）P(n)综合上述两个关键的考量因素：布线地图复杂度和布线距离比,建立代价函数来指导分段节点的决策：P(n)=i+i（7）可见,代价函数值越大表示针对该区域的路径搜索时间越长,反之亦然.为实现在指定分段数 N 下的均衡分段,本文基于上述代价函数提出如下搜索算法.算法 2 分段节点搜索算法输入：布线地图 mazeMap,拐点集y1,y2,y3,初始点 S,目标点 T输出：搜索分段节点 QStep1.由S,y1,y2,y3,T构建布线地图子区域；Step2.分别以拐点集y1,y2,y3,中的节点为父 障碍物当前搜索点拐点初始点目标点(a)遍历 S 和 T 之间元素找到障碍物(b)搜索竖直相邻节点(c)竖直平移后继续搜索相邻节点(d)竖直相邻节点符合定义(e)搜索水平相邻节点(f)推算得到拐点图5搜索拐点示例Fig.5 An example of inflection point searching6微电子学与计算机2023 年节点搜索其周围相邻节点,逐一计算每个子区域对应的代价函数值；Step3.直至找到 max子区域代价函数合计,最小的各子区域节点集合n1,n2,n3,n(N-1),即为分段节点.maxPS(n),PT(n)以二分段并行寻径为例,算法 2 的过程可以简述如下：从拐点开始,沿着初始点 S 和目标点 T 直线的方向搜索.如图 7 所示,首先遍历蓝色节点周围的黄色节点,并逐一计算这些节点对应的代价函数值,直至找到为最小的节点 n,即为其二分段点.mm在搜索的过程中如果遇到障碍物,如图 8(a)所示,搜索拐点周围的节点 恰好经过障碍物,那么会根据节点 和算法 1 找到该障碍物上的拐点（图 8(b)中蓝色的节点）.然后根据这个新的拐点,利用算法 2找合适的分段节点（图 8(b)中绿色的节点）.搜索点搜索点拐点 1(a)搜索到障碍物(b)再次搜索拐点拐点 2分段节点初始点(x1,y1)目标点(x2,y2)图 8搜索分段节点过程中遇到障碍物Fig.8 Obstacle encountered while searching for segment nodes 5.2启发函数的应用找到合适的分段节点后,将一个大区域内的寻径过程分解成多段小区域内的寻径过程.由于不同的启发函数会导向不同的布线结果,提出针对不同的障碍物场景,灵活地选择合适的启发函数来指导算法的寻径方向,实现最优的寻径效果.从垂直布线和水平布线两种情况分别讨论.仍然以二分段并行为例,如图 9 所示,其中(a)(d)为垂直方向走线,(e)(h)为水平方向走线,S 为初始节点,T为目标节点,Q 为分段节点,红色路径代和蓝色路径分别代表一个搜索过程.图 9 的(a)和(e)是以欧几里得距离为启发函数指导布线的结果,布线结果后半段趋近于目标节点的布线部分,它会同时且随机地靠向目标节点水平方向和垂直方向,最终的布线效果就是以欧几里得距离为启发函数的布线路径不是直线且没有规律.图 9 的(b)和(g)是以曼哈顿距离为启发函数指导布线的结果,发现初始节点布线部分以斜线、而最后以直线的形式进入目标节点.图 9 的(c)和(f)是以切比雪夫距离为启发函数指导布线的结果,其效果与曼哈顿距离启发函数正好相反,初始节点布线部分是以直线的形式、而最后以斜线的形式进入目标节点.在实际的 PCB 布线场景中,尤其是在多管脚的芯片互连的场景下,为了提高布通率,要求走线“直出直进”.障碍物当前搜索点拐点初始点(x1,y1)目标点(x2,y2)图7分段节点的搜索过程(搜索过程未遇到障碍物)Fig.7 The search process of segmented nodes(the searchprocess did not encounter obstacles)第 9 期李元康，等：一种基于分段并行思想的 PCB 布线加速策略7 基于以上分析不同启发函数布线的特点,在二分段并行例子中,可以将切比雪夫距离作为分段并行搜索中的第一段搜索的启发函数,将曼哈顿距离作为第二段搜索的启发函数距离,搜索结果如图 9 的(d)和(h)所示,最终搜索的结果可以达到“直出直进”的效果.将在实验部分探讨在复杂的障碍物场景中,这种混合的启发函数对布线效果的影响.6实验 6.1实验设置本实验平台设置如表 2 所示.表 2 硬件平台设置Tab.2 Experimental Platform Settings处理器Intel(R)Core(TM)i7-9750H CPU2.60 GHz 2.59 GHz内存16GB编程工具QT5.12.0（MSVC 2015,32 bit）平台功能（1）支持分段并行搜索、Lees算法和A*算法等不同算法下的布线算法（2）支持自定义布线网络、障碍物和地图尺寸（3）支持以曼哈顿距离、欧几里得距离、切比雪夫距离构建启发函数 为了检验本文提出的算法的有效性,在模拟PCB 布线场景障碍物地图中进行实验.首先通过深度优先搜索算法生成搜索路径,确保初始点和目标点之间存在一条路径.然后在不同大小的地图中与Lees 算法和 A*搜索算法的搜索结果进行比较.为了实验对比有效,使用 A*算法中的启发函数和 A*分段并行搜索算法中的启发函数都是切比雪夫距离,每组对照实验中障碍物的数量和位置都是相同的.选择五种尺寸的二维网格地图：（1）6060；（2）8080；（3）100100；（4）120120；（5）150150；评价指标有三个：（1）搜索时间；（2）搜索空间；（3）布线长度.由于 LPA*14和 ARA*17等优化算法并不适用于 PCB 布线场景,并且提出该算法的目标是综合考虑优化布线效果和布线速度,所以本实验未与这些优化算法作比较.6.2实验 1 结果与分析实验 1 主要进行了搜索时间、搜索空间、布线长度三个维度的评估.通过实验结果和比较分析,可以得出以下结论：(1)搜索时间图 10(a)展示了三种搜索算法的搜索时间,很明显,提出的算法搜索时间是要远远小于 Lees 算法和A*搜索算法,在尺寸为 150150 的网格地图中,分段并行搜索算法比 Lees 算法和 A*搜索算法分别快160 倍和 17 倍.并且随着地图尺寸的增大,尽管搜索时间也在增加,但是分段并行搜索算法的时间增长要比其他两种算法增长得慢得多.提出的算法能有效将一个复杂的搜索问题拆分成多个简单易解的搜索问题并行解决,缩短搜索时间.障碍物Find Path 1 搜索结果Find Path 2 搜索结果(a)A*搜索(欧几里得距离)(b)A*搜索(曼哈顿距离）(c)A*搜索(切比雪夫距离)(e)A*搜索(欧几里得距离)(f)A*搜索(曼哈顿距离)(g)A*搜索(切比雪夫距离)(h)分段并行搜索(切比雪夫距离+曼哈顿距离)(d)分段并行(切比雪夫+曼哈顿)图9分析两种障碍物中不同启发函数布线效果Fig.9 Routing results with different heuristic functions in twoobstacle scenarios8微电子学与计算机2023 年Lees45 00010 000搜索时间/ms060608080100100(a)三种寻路算法在五种尺寸地图中的搜索时间1201201501501 1023 4538 40521 27645 4721413609062 0774 561151653163261A*分段并行Lees25 00015 000搜索空间/格5 00060608080100100(b)三种寻路算法在五种尺寸地图中的搜索空间1201201501503 2175 6908 91313 45819 6931 1271 8202 8174 1355 9403197581 2641 6802 454A*分段并行12050搜索线长/格060608080100100(c)两种寻路算法在五种尺寸地图中的布线长度1201201501505164799211151628292112A*分段并行图 10不同搜索算法分别在五个尺寸大小不同的网格地图中实验数据Fig.10 Results with different searching algorithms under fivesized maps(2)搜索空间图 10(b)展示了三种搜索算法的计算整个路径所需要扩展节点的总工作量,Lees 算法搜索与地图大小有很大关系,它是向周围均匀扩散地搜索,因此在较大的区域中 Lees 算法需要很大的存储空间.分段并行搜索算法正如理论分析预期那样,能够将一个很大区域内的搜索问题分解成多个小区域内的搜索问题,大大减少了搜索空间.在五个网格地图中 Lees 算法和 A*搜索的搜索空间大约是分段并行搜索算法的 8 倍和 2 倍.(3)搜索线长图 10(c)展示了 A*算法和分段并行搜索算法的搜索线长,本文提出的分段并行搜索算法是在 A*算法的基础上改进.五组实验中的结果显示分段并行搜索算法和 A*算法的搜索线长相差无几,分段并行搜索算法可以确保线长尽可能短的同时,并获得比A*算法更高的搜索效率.6.3实验 2 结果与分析为了验证分段并行搜索算法可以获得更好的布线效果,模拟实际布线场景中的优化效果.图 11(a)(b)分别为障碍物类型 1 中 A*搜索算法和分段并行搜索算法搜索结果,图 11(c)(d)分别为障碍物类型 2 中 障碍物分段节点Find Path 1 搜索结果Find Path 2 搜索结果(a)A*搜索结果(b)分段并行搜索结果(c)A*搜索结果(d)分段并行搜索结果图11A*搜索算法和 A*分段并行算法在两种障碍物中的布线效果Fig.11 Routing results with A*search algorithm and theproposed segmented A*parallel algorithm第 9 期李元康，等：一种基于分段并行思想的 PCB 布线加速策略9 A*搜索算法和分段并行搜索算法搜索结果.分段并行搜索算法所使用的启发函数与之前讨论的一样,初步采用第一段搜索的启发函数是切比雪夫距离,第二段搜索的启发函数是曼哈顿距离,根据实验结果可以看到使用这两个启发函数使布线通道腾出更多空间用与其他网络布线.虽然切比雪夫距离搜索速度较慢,但是牺牲搜索速度可以得到更优的布线效果.图 12是这两种算法的搜索时间,可以看出即使少许拖慢搜索速度,分段并行搜索算法依然是比 A*搜索算法更快.604020障碍物 1障碍物 25316139地图尺寸A*搜索分段并行搜索A*搜索分段并行搜索时间/ms图 12A*算法和 A*分段并行搜索算法在两种障碍物中的搜索时间Fig.12 Searching time comparison of A*algorithm and theproposed segmented A*parallel algorithm ii考虑启发函数是曼哈顿距离的搜索速度有时会比切比雪夫距离作为启发函数的搜索速度快很多,尤其是在复杂的布线场景中,因此利用前文提出的“布线地图复杂度”来“自动化”选取启发函数.若第一段搜索区域 S1 的布线地图复杂度 0.5,则用曼哈顿距离,而第二段搜索的启发函数固定为曼哈顿距离.这样可以在布线效果和布线速度中达成平衡.6.4未来工作本文以实际的 PCB 布局案例为参照,在模拟PCB 布线平台上对算法进行验证.在未来的工作中,将继续探究以下问题：（1）讨论更复杂的 PCB 布局场景和布线需求,进一步评估本方法的有效性；（2）覆盖更多的实际 PCB 布局案例,来评估和优化拐点选择方案；（3）探讨“分段”和“并行”这两个因素对性能提升的贡献比；（4）展示更多线程的布线效果.7结束语本文展示了一种基于分段并行思想的 PCB 布线加速策略,这种分段并行思想的布线加速策略旨在将庞大且复杂的地图分解成多个小区域内的求解问题.本文重点讨论了分段节点的选取和不同分段下启发函数的选择问题.通过在自行搭建的平台上模拟验证,得到如下结论：本文提出的方法可以在保证线长与 Lees 算法和 A*搜索算法基本相同的情况下,减少搜索空间、提升搜索速度和优化布线效果.在150150 的网格地图中,本文方法与 Lees 算法和 A*算法相比较,搜索速度分别可提升约 160 倍和 17 倍.本文提出的方法有望为 PCB 自动布线的加速设计提供有价值的技术参考.参考文献：费艳.PCB自动布线算法主要策略综述J.科技风，2011（14）：16.DOI:10.3969/j.