基于GIS技術的雙層PCB布線的空間剖分算法

摘 要： 雙層印制電路板（PCB）通常空間結構及布線線形復雜、約束規則眾多，而常用PCB空間結構簡單、布線線形單一，不能有效利用PCB的空間關系及拓撲信息引導布線規劃。為彌補以前工作的不足，提出一種基于GIS（geographic information system）技術的空間剖分算法，首先利用空間距離與幾何要素拓撲關系進行分組預處理，然后引入矢柵一體化模型構建復雜空間及屬性約束下的網絡模型，基于該網絡模型提取區域基準線并利用空間緩沖區技術得到空間剖分結果，從而引導布線規劃。實驗結果表明，該算法能夠在滿足所有設計規則的情況下實現100%的布線連通率，同時有效利用布線空間資源；提出的算法布線線形接近人工布線，對于實現復雜場景與多約束下的雙層PCB自動化布線具有實際意義。

關鍵詞： 空間剖分； 中心線提取； 貼邊線提取； 雙層PCB布線

中圖分類號： TP391.72"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-033-1483-08

doi：10.19734/j.issn.1001-3695.2021.11.0475

Spatial subdivision algorithm based on GIS

technology for double-layer PCB routing

Du Jing1， Zhang Jian2， Liu Mingyu3， Chen Datao3， Guo Wei1， Gao Fei1， Zhao Yuhui1， Yang Kun1

（1.State Key Laboratory of Information Engineering in Surveying， Mapping amp; Remote Sensing， Wuhan University， Wuhan 430079， China； 2.Fire Rescue Detachment of Jing’an District， Shanghai 200070， China； 3.Huawei Terminal Co.， Ltd， Wuhan 430206， China）

Abstract： Double-layer printed circuit board（PCB） usually has the complex spatial structure and the routing pattern，and many constraint rules.However，in the past researches，the spatial structure of PCB is simple and the routing pattern is single，and the spatial relationship and topological information of PCB can not be effectively used to guide the routing.In order to make up for the shortcomings of the previous work，this paper proposed a spatial subdivision algorithm based on geographic information system（GIS） technology.Firstly，it used the spatial distance and the topological relationship of the geometric elements for group preprocessing.Then it introduced the vector and grid model to construct the network model under the complex space and attribute constraints.Based on the network model，it extracted the regional reference line，and used the spatial buffer technology to obtain the spatial subdivision result for guiding the routing.Experimental results show that the proposed algorithm can achieve 100% routing connectivity under the condition that all design rules are met，and effectively utilize routing space resources.The routing shape of the proposed algorithm is close to manual routing，which is of practical significance to realize the automatic routing of double-layer PCB under complex scenes and multi-constraints.

Key words： spatial subdivision； center line extraction； side line extraction； double-layer PCB routing

0 引言

PCB開發主要包括電路原理圖設計、器件布局規劃、布線等步驟，其中布線是極為重要的步驟［1，2］。隨著電路板集成度提高、電路密度增大，完全人工的布線方式存在的重復性工作多、布線效率低下、耗時長等問題愈發突出［3］。盡管國內外現有的電子設計自動化（electronic design automation，EDA）軟件在電路設計與仿真、PCB設計、集成電路設計和可編程邏輯器件設計等應用領域已取得諸多進展［4～6］，一定程度上能夠提高PCB布線的自動化程度［7～9］，但是針對復雜約束下的布線場景，仍需人工根據不同網絡的特性進行詳盡的走線規則設計并對布線過程進行追蹤，動態修改甚至重新規劃不合理的布線結果，這對人工布線經驗與編程設計提出了較高要求。因此，在符合布線約束及設計要求的前提下提升布線連通率、減少人工干預，是實現PCB自動化布線的關鍵所在。

1 相關工作

PCB布線過程主要分為總體布線和詳細布線［10，11］兩個階段。總體布線是將網絡劃分到各個布線子區域中，將擁擠區域的走線均衡分布至布線資源充足的子區域；詳細布線則是根據電路互連關系確定各網絡在對應分配的布線子區域中的具體布線位置。基于上述思想，Cho等人［12］提出了一種框式布線方法，預處理階段在無溢出條件下滿足盡量多的網絡連接，然后選擇最擁擠區域作為初始布線框，對框內的線通過漸進式整數線性規劃［13］與自適應迷宮算法［14，15］布線，然后將框逐漸擴展直至覆蓋整個電路板進而完成布線；由于該研究沒有考慮電路板存在多層的復雜場景，在此基礎上Cho等人［16］提出了二維總體布線及層分配方法實現二維到三維的映射，解決多層布線問題；劉耿耿等人［17］同樣先采取預處理，然后兩階段布線的方法，與上述研究不同的是在預處理階段沒有采用L模式或Z模式布線［18］，而是采取斜率為0、-1、+1、∞的直線連接網絡。但上述研究方法僅適用于電路板邊界形狀規則、PIN在電路板上分布均勻并且可以通過簡單的直線或者折線完成連通的電路板，對于邊界復雜、PIN的分布存在聚集、連通走線較為復雜的情形，該算法無法較好適應。

布線容量與布線代價是影響布線設計的重要方面。Hu等人［19］提出了布線資源分配模型，根據線的寬度、布線面積和層數為總體布線圖中的每條邊分配可用的布線路徑條數從而量化計算布線容量；Cao等人［20］提出了基于動態資源分配的總體布線方法，考慮了總體布線圖中一條邊的布線對其相鄰邊的影響，進而優化了布線容量計算模型；孟暢等人［21］提出了一種基于數據場中勢能和場強的擁擠度建模方法，使布線路徑遠離擁擠區域；陳秀華［22］引入了擁擠度代價函數以獲得更為精確的布線資源估計，并提出了基于擁擠度模型的多級布線策略。但上述基于計算布線容量的布線模型不能較好地利用電路板邊界等幾何拓撲信息，也無法引導網絡在電路板上的正確走向，導致布通率的提升空間有限，難以應用于復雜約束下的布線設計。

空間剖分是當前研究中解決集成電路布線優化的重要手段，通過規劃布線區間及布線線形對布線路徑提供指導。Zhang等人［23］引入了虛擬邊界進行空間剖分，利用虛擬節點轉換布線連接的空間拓撲關系，以降低芯片布線問題的規模；Tsai等人［24］針對PCB芯片布線問題將布線區域基于斜率法進行空間剖分，然后構建網絡交叉圖并進行分層，對每個子區域的PIN根據縱坐標進行網絡聚類后通過平面制圖法解決各區域網絡的交叉問題；Tian等人［25］以行為單位基于平均法為每條網絡分配可布線的行數，然后采用線搜索法迭代生成長度匹配的網絡路徑，最后基于擴散方法生成最長路徑并對路徑進行調整以滿足時延約束；Yan等人［26］將覆蓋兩個給定終端的最小矩形作為布線空間剖分的標準，從幾何拓撲角度將兩區域的相交情形分為對角線相交、相鄰相交、交叉相交、覆蓋相交，從而確定網絡在各區域內的準確路由方向。這些模型均采取了先對布線空間進行剖分，再在各子區域內分別布線的解決思路，一定程度上降低了復雜布線問題的規模，但由于PCB布線場景設計較為簡單，對于達到工業界實際需求仍存在差距。在實際布線場景下通常存在網絡約束復雜、電路板邊界形狀不規則、網絡類型種類多、PIN存在聚集分布等情形，如何在復雜約束下進行空間剖分與布線設計的相關研究較少。

針對上述不足，本文對雙層PCB自動化布線提出了一種基于GIS技術的空間剖分算法，其主要思路是以PIN組對為基本單位規劃每條網絡對應的可布線區域，在不違反各項設計規則的條件下實現對各布線區域網絡的全部連通。該算法通過對空間的剖分減小了直接布線的規模，基于GIS中柵格模型和矢量模型［27］組織存儲數據，通過提取PIN的空間特征與邊界幾何拓撲特征為后續模型構建提供支持，引入矢柵一體化模型［28］構建復雜空間及屬性約束下的網絡模型，基于該網絡模型提取基準線并利用空間緩沖區技術獲取空間剖分結果，最終實現布線連通。

2 問題建模

本文研究的雙層PCB均為柔性電路板，具有配線密度高、厚度薄、彎折性好的特點。為方便描述與表示，本章首先對雙層PCB相關重要術語、概念以及約束進行界定與解釋。

定義1 PIN，電路板引腳，通過網絡互連關系連通。對于n對引腳，源引腳si與目標引腳ti（i∈［1，n］）的坐標分別設為（Xsi，Ysi）與（Xti，Yti），n對引腳通過互連關系得到的雙端網絡集合為N={N1，N2，…，Nn}。

定義2 PIN組，將空間中位置鄰近的PIN劃分為組。設PIN共被劃分為k組，即k個PIN組，那么對于第i（i∈［1，k］）個PIN組，如果存在ni個PIN，則PIN的集合可表示為Si={pi1，pi2，…，pini}，PIN組的集合可表示為S={S1，S2，…，Sk}。PIN組排列方向一般為水平或豎直排列。

定義3 PIN組對，對于PIN組Si={pi1，pi2，…，pini}與Sj={pj1，pj2，…，pjnj}，只要存在任意pie與pjf有連接關系（e∈［1，ni］，f∈［1，nj］，e、f均為整數），就將PIN組Si與Sj稱為一個PIN組對。

定義4 封裝，屬于PCB元器件，任意一個封裝內都包含若干個PIN。封裝對PIN的空間包含關系為固有屬性，與PIN本身的空間位置無關。

定義5 電路板邊界，是由多條線段與弧段按一定順序連接形成的首尾閉合的多邊形，連接順序按照它們對應的序號決定。其中弧段是由起點、終點、圓心、圓的半徑、連接方向進行表示。

任意一個電路板的布線均需嚴格滿足其對應的空間約束、網絡約束、結構工藝約束。

定義6 空間約束。主要針對網絡與網絡、網絡與電路板邊界之間的最小距離約束；此外空間約束還包括網絡必須布設于可布線區域內，網絡之間不允許交叉。

定義7 網絡約束。描述了網絡與其所屬網絡組以及動態布線過程的約束。a）網絡組，一個網絡組中有若干條網絡，同組網絡通常平行布線；b）網絡名；c）網絡類型，包括信號線、電源線、地線（GND）；d）線寬；e）組外間距；f）組內間距；g）包地線，網絡兩側需與其平行布設地線，地線寬度由包地線線寬決定；h）參考層屏蔽，網絡所在層的對應層的投影位置需要布設指定參考層屏蔽網絡。

定義8 結構工藝約束。針對走向方向以及特殊區域能否布線的約束。特殊區域通常包括彎折區、補強區和禁止布線區，彎折區和補強區投影形狀常見為矩形，布線通過該區域必須與矩形長邊垂直；禁止布線區簡稱禁布區，是指電路板上禁止布設任何網絡的區域。可布線區域則是排除禁布區、PIN所在區、已布線區以外的區域。

圖1為雙層PCB示意圖，頂（top）層和底（bottom）層的投影完全重合。灰色矩形為PIN，綠色區域表示可布線區域（參見電子版）。設網絡N1、N2為一個網絡組，網絡N3為一個網絡組，且均為信號線，則a1表示線寬，a2表示組外間距，a3表示組內間距，a4表示可布線區域與邊界的距離。其中a2、a3需滿足網絡最小間距的空間約束，a4需滿足網絡與電路板邊界最小間距的空間約束。假設top層的網絡N1、N2均存在參考層屏蔽約束且屏蔽網絡指定為GND，則在對應bottom層的投影位置需要布設GND，N1與GND的投影關系如橙色虛線所示，N2與GND的投影關系如藍色虛線所示；若網絡N4存在包地線約束，則在N4兩側需要平行布設GND，同時GND與N4需要滿足網絡最小間距的空間約束。

為簡化問題，本文針對雙層PCB布線場景提出以下基本假設：

a）雙層PCB邊界及元器件布局位置確定，電路板邊界多邊形連接順序默認為順時針方向。

b）PIN在電路板上的連接關系確定，PIN在二維平面的投影形狀一般為矩形。PIN間的連接關系與其投影形狀無關，因此通常取PIN的投影矩形的幾何中心點表示PIN位置。本文研究針對雙端PIN，即兩兩存在連接關系的PIN，設定多端PIN已分解處理為雙端PIN。

c）地線與電源線布線較復雜，本文布線只針對信號線，只需在信號線布線規劃過程中預留出地線和電源線的布線區域［30］，但需要考慮其對于布信號線的影響。具體為，當電源線網絡存在時，需要為其劃分盡量多的空間；當參考層屏蔽網絡指定為地線時，需在相應位置為其劃分空間并將這類預留區視為布線障礙。

d）同一個PIN組內的PIN排列緊密，PIN之間的距離不超過封裝的長度，且組間間距遠大于組內間距。

e）空間剖分只針對于可布線區域。

3 基于GIS技術的空間剖分算法

基于GIS技術的空間剖分算法利用幾何要素的空間拓撲關系，結合基于距離的空間聚類技術、矢柵一體化模型、最短路徑規劃、線要素簡化以及空間緩沖區技術得到最終空間剖分結果。首先利用PIN在電路板上聚集分布的空間特征，基于空間距離聚類實現PIN分組，并利用組成電路板邊界幾何要素間的拓撲關系有序性對電路板邊界進行分組；然后根據PIN組間連接關系數確定剖分子區域的個數，并在柵格模型下進行區域預劃分，同時設置空間權重用于引導尋找區域中心線；根據場景進行判斷，只有一組連接關系且邊界附近無禁止布線區時提取貼近電路板邊界的線（簡稱貼邊線），其他情況下，基于矢柵一體化模型在滿足結構工藝約束下通過A*算法提取矢量中心線，并通過Douglas-Peucker（DP）算法簡化；最后根據網絡約束計算PIN組對至少所需的區域寬度，以化簡后的矢量線為基準基于試探法創建空間緩沖區，最終得到空間剖分區域。

空間剖分算法總體流程如圖2所示，主要分為三個步驟：a）基于空間距離和幾何要素拓撲關系的分組預處理，詳細闡述了基于空間距離對PIN進行聚類分組，以及根據電路板邊界組成要素的幾何拓撲關系對邊界分組；b）區域中心線或貼邊線提取首先需要確定剖分區域個數，并根據電路板具體場景確定選擇提取中心線還是貼邊線的方案；c）基于試探法，創建空間緩沖區，最終得到空間剖分結果。

3.1 基于空間距離與幾何要素拓撲關系的分組預處理

分組預處理是進行區域預劃分的前提。由于區域預劃分步驟需要找到PIN組對對應的電路板邊界，再基于對應邊界向電路板內部擴展得到預劃分結果，所以首要任務是識別PIN組，并根據電路板邊界的幾何拓撲信息對邊界進行分組。

3.1.1 基于空間距離聚類方法的PIN分組

PIN在電路板上通常存在空間聚集，因此PIN分組問題是對空間中的PIN進行聚類的問題。PIN分組分為粗略分組和基于空間距離聚類分組兩個步驟。首先，粗略分組根據PIN所在的封裝屬性對PIN進行分組，即封裝屬性相同的PIN合并為一組；基于此結果可以計算得到各組的組間距離，并基于組間距離以上一步分得的PIN組為基本單位進行聚類，從而確定PIN的最終分組數。基于空間距離聚類的PIN分組偽代碼見算法 1，輸入為粗略分組得到的PIN組的集合，輸出為最終PIN分組結果。算法通過雙層循環從集合中任選出兩個PIN組計算組間距離，若小于閾值thresh_D，則將包含PIN數量少的組合并到數量多的組，依此遍歷整個集合。由于PIN組間距離遠大于組內PIN間距，thresh_D可根據具體電路板場景設置為一個合理數值用于區分不同PIN組。

算法1 Get_pingroup，基于空間距離聚類的PIN分組

輸入：粗略分組后PIN組的集合S。

輸出：基于空間距離聚類的PIN分組結果S。

for Si in S

for Sj in S

dist←Cal_pingroup_dist（Si，Sj）；// 計算組間最短距離

if distlt;thresh_D // thresh_D為區分PIN組的閾值

if Si.size（）gt;Sj.size（） then

Si←Si+Sj；

else Sj←Si+Sj；

end for

end for

PIN分組過程中計算PIN組間最短距離算法的偽代碼見算法2，輸入為兩個不同PIN組，輸出為兩PIN組間的最短距離。算法分別在兩個不同PIN組中各選出一個PIN，并計算兩PIN間的歐氏距離，依此循環遍歷計算兩個PIN組的所有PIN，從而得到距離的最小值。

算法2 Cal_pingroup_dist，計算兩PIN組間的最短距離

輸入：PIN組A，PIN組B。

輸出：PIN組間最短距離dist。

dist←INT_MAX；

for ai in A

for bi in B

d←EuclideanDist（ai，bi）；// 計算歐氏距離

if dlt;dist then

dist←d；

end for

end for

3.1.2 基于要素拓撲關系的電路板幾何邊界分組

對電路板幾何邊界進行分組的目的是找到PIN組對對應的電路板邊界。在PIN分組結果的基礎上，首先通過構造PIN組的最小外接矩形（minimum bounding rectangle，MBR）判斷PIN組的排列方向，并計算各PIN組MBR及兩端點的位置，然后利用組成電路板邊界的幾何要素的拓撲關聯有序性對電路板邊界進行分組。

如圖3（a）所示，首先PIN分組算法將PIN分為PIN_0、PIN_1、PIN_2三組，然后通過PIN組MBR提取PIN組中心線，三個PIN組對應的中心線分別設為L_0、L_1、L_2，并設直線L_0與電路板交點分別為A、B，直線L_1與電路板交點分別為C、D，直線L_2與電路板交點分別為E、F。記錄交點所在線段或弧段的編號，設交點A、B所在線段或弧段編號為objA、objB，則PIN組與線或弧段的對應關系為PIN_0對應objA、objB，其他組同理。根據電路板邊界由線段與弧段組成的有序性，A～F對應的六個編號序列從某個編號開始必然可組成嚴格遞增數列。由此可以得知，同一個PIN組的兩交點之間存在哪些線段或弧段編號，即獲取了各PIN組對應的線段或弧段編號集合。

獲取各PIN組中心線與電路板邊界相交的線段或弧段編號的算法偽代碼見算法 3。輸入為某PIN組MBR兩個邊界上的中點以及組成電路板邊界的線段與弧段集合OBJ，輸出結果R是一個二維向量，用于存儲距離pmin 最近和距離pmax最近的線段或弧段編號。算法根據PIN組MBR判斷排列方向，并以該方向延長中心線與電路板邊界相交，然后遍歷集合OBJ并判斷中心線是否與該線段或弧段相交，記錄相交的線段或弧段。

算法3 Get_borderinter_segment，獲取各PIN組延長線與電路板邊界相交線段或弧段的編號

輸入：某一PIN組的左或下端點pmin，某一PIN組的右或上端點pmax，組成電路板邊界的線段與弧段集合OBJ。

輸出：PIN組與電路板邊界相交線段或弧段的編號集合R。

if PinGroupType==horizontal then//若PIN組為水平方向排列

pmin.x←pmin.x-999

pmax.x←pmax.x+999

else pmin.y←pmin.y-999 //若PIN組為豎直方向排列

pmax.y←pmax.y+999

for obji in OBJ

if is_Intersect（obji，LINESEG（pmin，pmax）） then

//相交判斷

R.push_back（obji）

end for

電路板邊界分組的算法偽代碼見算法4，輸入為PIN組個數pg、第i（i∈［0，pg-1］）個PIN組MBR兩對邊上的中點，輸出為電路板邊界分組結果以及邊界對應的各個PIN組。首先根據算法 3遍歷所有PIN組后可以獲取各PIN組對應的線或弧編號Nij（j=0，1），Ni0和Ni1表示第i個PIN組對應的兩個線或弧的編號；其次遍歷電路板邊界線段和弧段，index表示當前編號，cur表示當前PIN組編號，startIndex表示起始線或弧編號；然后根據index的值進行判斷，如果index等于當前PIN組對應編號之一，則說明temp中存放的線或弧組成的邊界對應當前PIN組；如果index等于其他PIN組對應編號之一，則說明temp中存放的編號組成的邊界對應當前PIN組和另一個PIN組形成的PIN組對；當index再次與起始值相等時終止循環，輸出電路板邊界分組結果。

算法4 Get_border_group獲取電路板邊界分組

輸入：PIN組個數pg，第i個PIN組的左或下端點pmini，第i個PIN組的右或上端點pmaxi。

輸出：電路板邊界分組結果以及邊界對應的各個PIN組C。

for i in pg

Nij=Get_borderinter_segment（pmini，pmaxi）

/*獲取各PIN組延長線與電路板邊界相交線段或弧段的編號，Nij為一個i×2的矩陣*/

end for

index←startIndex+1//startIndex初始為Ncur0，cur初始為0

while Tag！=0 do //Tag初始為1

temp.push_back（index）；

if index==Ncur0‖index==Ncur1 then

/* 若該線段（或弧段） 屬于編號為cur 的PIN組 */

C.put（cur，temp）；

temp.push_back（index） //該步驟執行后清空temp；

else // 若線段（或弧段）屬于其他PIN組

for j in pg

if j！=curamp;amp;（index==Nj0‖index==Nj1）

then C.put（［cur，j］，temp）；

cur=j；

temp.push_back（index）；//執行后清空temp

end for

++index；//當index達到最大編號后，規定index+1=0

if index==startIndex+1 then

Tag←0；

end

將算法 4的輸出結果進行可視化，可以得到圖3（b）所示的電路板分組結果。設電路板上存在三組PIN組對，分別是PIN_0組與PIN_1組、PIN_1組與PIN_2組、PIN_2組與PIN_0組，那么PIN_0組與PIN_1組組成的PIN組對對應的電路板邊界即為黃色邊界“0-1”，藍色邊界“1-2”、紅色邊界“2-0”，分別對應第二、三組PIN組對。

3.2 區域中心線或貼邊線提取

針對不同PCB布線場景，采取不同的基準線提取方案能夠更充分地利用電路板邊界等已知信息，同時可以提高算法效率。因此，本文針對PIN組連接關系數與電源線的約束規則分別提出區域中心線和貼邊線兩種基準線提取策略。只有一組連接關系且邊界附近無禁止布線區時提取電路板貼邊線，其他情況下基于矢柵一體化模型通過考慮空間權重的A*算法提取區域中心線。區域中心線是用于標志可布線空間中心的線，貼邊線是指在電路板邊界以內且最貼近邊界的線。空間剖分各區域均以對應的矢量線為基準線，通過創建空間緩沖區得到，因此中心線或貼邊線提取質量的高低對最終剖分結果有直接影響。

首先根據PIN組與PIN組之間的連接關系數確定剖分區域個數，基于柵格模型進行區域預劃分，并設置柵格的空間權重；然后判斷提取區域中心線還是貼邊線，如果采用中心線則基于矢柵一體化模型在考慮空間權重及電路板結構工藝約束的條件下使用改進A*算法進行提取，如果采用貼邊線則提取PIN組對對應邊界的平行線作為基準線；最后基于DP法簡化矢量線。區域中心線或貼邊線提取的總體流程如圖4所示。

3.2.1 基于柵格模型的區域預劃分

區域預劃分是得到空間剖分結果前的預處理步驟，是以PIN組對對應的電路板邊界為基礎向電路板內部擴展，將與該邊界接觸的柵格合并到屬于該PIN組對的剖分區域中的過程。通過區域預劃分可以初步區分不同PIN組對的對應區域。

由于提取貼邊線利用的是電路板邊界的幾何特征，所以只有提取區域中心線的情形需要進行區域預劃分。對于存在電源線且采取提取區域中心線方案的PCB，需要進行預劃分的區域為除去電源線區域后的剩余空間；對于無電源線網絡的PCB，進行預劃分的區域為整個電路板的可布線區域。基于柵格模型的區域預劃分流程如圖5所示。

在柵格模型下將PIN組對對應的電路板邊界所在柵格單元設為屬于該PIN組對的初始區域，PIN組對對應區域寬度根據空間約束和網絡約束進行計算。通過最大寬度比例是否超過τ來判斷各組寬度的差異大小：當各個PIN組對對應區域寬度相近時，各初始區域按照對應比值來確定向電路板內部每次擴展多少個單位；當PIN組區域寬度差異較大時，各初始區域依次向內部擴展，且僅擴展一個單位，這樣的策略是為防止寬度差異較大時仍按照寬度比進行擴展導致各個區域預劃分范圍不均衡。具體而言，以當前柵格為中心探索八個方向的鄰域柵格，若柵格不屬于其他PIN組對則將該柵格合并入當前PIN組對，否則跳過該柵格，按上述步驟遍歷屬于該區域的所有柵格，此為擴展一個單位。各區域依次循環進行擴展，每次擴展均基于上一次循環擴展得到的區域為基礎，然后各區域依次循環擴展，直至整個電路板被劃分。最后進行空間權重的設置，目的是設置越靠近區域中心的柵格空間權重越小，從而可以有效引導中心線的提取。

3.2.2 矢量貼邊線提取

根據圖4所示的流程圖，只有存在一組組間連接關系的場景才需要提取貼邊線。通過觀察人工布線方案，存在一組組間連接關系的電路板布線線形與邊界幾何形狀極為相似，因此可以利用電路板邊界的幾何特征提取貼邊線。通過以PIN組對對應的邊界為基準線創建緩沖區可以提取貼近邊界且與邊界平行的線，該邊即為貼邊線提取結果。

3.2.3 矢量中心線提取

根據圖4流程，提取區域的矢量中心線存在兩種情形：存在電源線且不再適用貼邊線的；不存在電源線。情形的主要區別在于是否存在電源線網絡，因此需要對電源線網絡進行特殊考慮。對于存在電源線的第一種情形，距離電路板邊界較近范圍內存在禁止布線區域，表明電路板邊界幾何形狀受禁布區影響較大，因此提取貼邊線方案不再適用。這種情況下需要先預留出布設電源線區域，且只需設置一個合理的值作為預留電源線區域寬度，因為后續步驟為提取電路板上除電源線區域外剩余空間的中心線，中心線線形與電源線區域預留寬度無關。所以第一種情形需要預留電源線區域后提取剩余可布線區域的中心線，第二種情形直接進行中心線提取。

首先將存在連接關系的PIN組MBR的幾何中心設為中心線的起點和終點，然后基于考慮空間權重的A*路徑搜索算法提取區域的中心線。考慮空間權重的改進A*算法代價函數為

F（i）=G（i）+H（i）×weight（i）（1）

其中：F（i）為節點i的總代價；G（i）為節點i距離起點的距離代價；H（i）為節點i距離終點的預計代價；weight（i）為節點i的空間權重。節點在模型中可理解為柵格。算法在搜索當前節點的八鄰域節點時，若節點i的鄰域節點mik（k∈［1，8］）在彎折區或補強區這類特殊區域中并且與父節點i的連線與該區域的長邊不呈垂直關系，或者節點mik在電路板邊界外部或禁止布線區域，則跳過該節點，以此保證提取的區域中心線符合結構工藝約束。

以一塊存在電源線網絡且有兩個PIN組對的電路板為例，如圖6所示，紅色區域為電源線預留區域（參見電子版），圖6（a）為區域預劃分結果，藍色區域為預劃分區域1，黃色區域為預劃分區域2；圖6（b）為區域1空間權重的示意圖，從區域的邊界向內空間權重值逐漸減小，即區域中心路徑代價更小，從而可以引導中心線的提取；圖6（c）中橙色表示的線為兩個區域的中心線提取結果（化簡前）。

3.3 基于試探法創建空間緩沖區的空間剖分

在提取各區域中心線/貼邊線結果的基礎上，根據電路板的網絡約束計算得到的各PIN組對應空間寬度，以該區域提取的中心線/貼邊線為基準，基于試探法及創建空間緩沖區方法得到各區域的空間剖分最終結果。中心線/貼邊線結果為有矢量方向的線，在提取矢量線步驟中設置PIN組對的起點、終點為順時針順序，且所有組的起點、終點順次相連的順序同樣為順時針順序；當只有一組組間關系且存在電源線時，遵循電源線區域在起點、終點連線形成的矢量線的左側設置規則。依此可以確定各區域的中心線/貼邊線的哪一側遠離電源線區域，哪一側靠近電源線區域，這是試探法中判斷創建緩沖區方向的重要前提。

基于試探法創建空間緩沖區的空間剖分方法流程如圖7所示。其中Wi=Bi/電路板總層數。當電源線網絡存在且只有一組PIN組對時，以區域中心線/貼邊線為基準，向遠離電源線方向（矢量線的右側） 基于試探法創建緩沖區，直至到達電路板邊界，記錄右側創建緩沖區寬度為Wi1，然后以區域中心線/貼邊線為基準，向靠近電源線方向（矢量線的左側） 創建緩沖區，左側緩沖區寬度為Wi2=Wi-Wi1（Wi2≥0） ；當電源線網絡存在且有多個PIN組對時，需要判斷電源線預留區域是否與布線區域在同側，如果是則同上，否則先向遠離電源線方向（矢量線的左側） 基于試探法創建緩沖區直至到達電路板邊界，記錄寬度為Wi1，然后以向矢量線的右側創建寬度為Wi2=Wi-Wi1（Wi2≥0） 的緩沖區；當電源線網絡不存在時，直接以中心線為基準，以線寬Wi為半徑向兩側創建緩沖區。

4 實驗結果與分析

4.1 實驗參數

本文的實驗參數有柵格分辨率α、DP算法化簡閾值θ、各組組寬最大比值τ、擴展迭代結束閾值σ。具體各參數取值如表1所示。本文的實驗環境為 Intel Core，CPU i5 - 3570 HQ，16.00 GB 內存 、主頻 3.40 GHz，64 位 Windows 10 操作系統，并以C++作為編程語言進行開發實現。

4.2 實驗數據

本文選取三個有代表性的雙層PCB數據進行實驗，來源為企業提供的符合PCB設計標準并實際應用于生產的真實數據。數據1～3的電路板二維平面示意圖分別如圖8所示，PIN用紫色矩形表示（見電子版），可布線區域用綠色多邊形表示，可布線區域與邊界距離滿足最小間距約束。經過分組預處理可以獲取以下信息：數據1存在兩個PIN組，且兩PIN組存在連接關系組成PIN組對，電路板上存在電源線網絡，電源線PIN所在區域用藍色斜線填充的矩形表示，因此在電路板右側需要預留電源線區域，該電路板符合貼邊線提取方案；數據2有三個PIN組，PIN組間均存在兩兩連接關系，即共三個PIN組對，電路板上不存在電源線網絡，符合中心線提取方案；數據3有四個PIN組，PIN組對為兩組，且存在電源線PIN，需要在電路板右側區域預留電源線區域，該電路板符合預留電源線區域后的中心線提取方案。

實驗采取如表2所示的空間約束。表中的數值表示top層與bottom層均需滿足線與線之間的距離不得小于3 mil，線與電路板邊界的最小距離不得小于3 mil。

表3～5分別為數據1～3的網絡約束，表中所有網絡均為信號線。由于篇幅原因，此處僅完整列出數據1的所有網絡，數據2、3僅選取部分網絡列出，其中數據1共15條網絡，數據2共44條網絡，數據3共56條網絡，均不包括地線與電源線。

4.3 實驗結果

實驗以布線連通率、空間占用率和時間效率作為評價指標，布線連通率為詳細布線的網絡連通率，空間占用率為布線結果占用可布線區域比例。本文將空間剖分算法分別與FreeRouting（FR）、Konekt Electra（KE）以及人工的布線結果進行對比。FreeRouting是用Java語言編寫的開源PCB布線軟件［30，31］，是目前最先進的布線器之一；Konekt Electra是一款商業布線器［32］，其研發的自適應布線算法為目前復雜PCB實現高布通率的唯一經過驗證的方法。在實驗過程中，兩個布線器都設置了各自的默認參數，并給出了與本文算法一致的輸入設計和布線規則。

針對三個PCB數據，本文算法對其劃分得到柵格行、列數分別為410×94、382×96、415×128。表6為FreeRouting、Konekt Electra、人工以及本文算法的布線實驗結果。

表6的實驗結果證明，本文算法在滿足第2章所有約束的條件下能夠實現PCB布線連通率達100%，而FreeRouting和Konekt Electra布線器在實驗中由于布線約束的違反，均存在部分網絡無法連通的情形。同時，本文算法布線結果的空間占用率在所有實驗中均小于FreeRouting、Konekt Electra以及人工布線，其中對于FreeRouting布線器更是減少了超過20%，這表明本文算法能夠有效利用布線空間資源，有利于為后續其他方面PCB設計預留更多可協調空間，為優化調整PCB電路板布局及形狀設計提供了一定參考。此外，本文算法與Konekt Electra布線器相比具有較高的耗時，但遠低于FreeRouting 布線器所用時間，這是因為本文算法將布線連通率作為最高優先級，其次才是效率問題，在能夠保證連通率的前提下，本文算法所用時間仍然是在可接受范圍內。因此整體上看，基于空間剖分算法的布線效果更為靈活、有效。通過實驗數據2和3的對比可以發現，電路板場景規模越大，柵格模型中用于描述電路板場景與空間屬性的柵格單元數量也越多，由于實驗耗時與實驗過程中需要存儲、處理的數據量呈正相關關系，實驗耗時通常會更長。特別地，與實驗數據2、3基于柵格進行提取中心線方案不同，實驗數據1采用提取貼邊線方案，直接利用了電路板邊界的幾何矢量信息，因此場景規模雖然較大但用時較少。

實驗還將本文算法與人工布線結果進行可視化對比，從空間剖分結果的空間占用情況、布線線形相似性等方面的異同進行對比分析，結果如圖9～11所示。

如圖9（a）所示，數據1提取的化簡后的貼邊線用紅色線段表示，空間剖分結果為藍色區域，表示該區域為這一組PIN組對對應的布線區間；圖9（b）展示了基于空間剖分進行詳細布線的結果；圖9（c）為人工布線結果（參見電子版）。從圖中可直觀地看出，基于空間剖分算法的布線結果與人工布線線形較為相似，僅在首尾處存在一定差異。這是由于算法采用了提取電路板貼邊線方案，所以剖分結果以及基于剖分的布線都會更貼近于邊界的幾何形狀。

如圖10（a）所示，數據2的三組PIN組對對應的布線區間分別為藍色、黃色、橙色區域，各區域中心線提取結果為紅色線（參見電子版）。基于剖分結果的布線與人工布線的對比如圖10（b）（c） 所示，藍色表示top層走線，綠色表示bottom層走線。兩種布線結果在電路板中部存在一定差異，這是由于人工布線過程中對此處走線進行了弧化處理。

如圖11（a）所示，數據3中兩個PIN組對對應的走線區間分別為黃色和綠色區域（參見電子版）。由于電源線網絡的存在，電路板右側預留了電源線區域，去除電源線區域后的中心線提取結果用紅色線條表示。基于空間剖分的布線與人工布線結果對比如圖11（b）（c）所示。從對比圖可以看出，兩者布線走向及線形均較為相似，而在電路板左側和中部的布線走向差異是由于算法采用提取區域中心線方案，所以各區域中心線均會向電路板中間靠近，從而導致以中心線為基準布設的線也靠近空間中部。

總體而言，針對雙層PCB復雜布線場景，本文算法在不違反任何設計規則的條件下能夠實現布線全部連通，并且空間占用率低，布線線形與人工較為相似。實驗結果證明，本文算法對于實現雙層PCB自動化布線具有實際意義。

5 結束語

為彌補現有PCB布線研究中鮮有涉及網絡類型種類多、網絡約束復雜、電路板邊界形狀不規則、PIN存在聚集分布等復雜布線場景的不足，本文提出了一種基于GIS技術的雙層PCB自動化布線的空間剖分算法。該算法通過空間距離聚類與拓撲分析較好地利用了PCB復雜邊界的幾何特征；提出了中心線與貼邊線的不同提取方案，可以適用于多種不同的布線場景；同時采用了矢柵一體化模型以及空間緩沖區技術，實現了空間剖分，并能夠有效引導實際布線。

實驗結果表明：a）所提算法能夠在實現布線連通率達100%的同時合理利用空間資源；b）適應性強，根據不同場景采取提取中心線和貼邊線方案，兩種方案可以有針對性地處理不同電路板場景，提高了算法的適應度；c）能夠有效引導、規劃布線線形，提高了網絡之間的線形相似性。

本文主要針對雙層布線場景，后續研究可以關注多層電路板的空間剖分問題；此外，柵格分辨率的取值關系到空間剖分的最終結果以及算法耗時，下一步工作可以考慮區域預劃分以及A*算法的優化等問題，從而提升效率。

參考文獻：

［1］林秀鳳.PCB設計流程與經驗分析［J］.河南科技，2020，39（35）：59-61. （Lin Xiufeng.PCB design process and experience analysis［J］.Journal of Henan Science and Technology，2020，39（35）：59-61.）

［2］胡宗海，趙彥，王立平，等.PCB設計流程的改進研究［J］.成都工業學院學報，2017，20（1）：16-19. （Hu Zonghai，Zhao Yan，Wang Liping，et al.Research on the designing process for PCB［J］.Journal of Chengdu Technological University，2017，20（1）：16-19.）

［3］宋謙，路林吉.面向目標的主動繞障PCB布線算法［J］.電子測試，2018（22）：44-45. （Song Qian，Lu Linji.Goal-oriented PCB routing algorithm for active wound barrier［J］.Electronic Test，2018（22）：44-45.）

［4］劉超，王珺，張天儀.集成電路EDA行業發展態勢分析［J］.中國集成電路，2021，30（6）：32-37. （Liu Chao，Wang Jun，Zhang Tianyi.Analysis of the EDA industry tendency for integrated circuit field［J］.China lntegrated Circuit，2021，30（6）：32-37.）

［5］劉昌華.EDA技術綜述［J］.計算機與數字工程，2007，35（12）：49-53. （Liu Changhua.Evolution of EDA technology［J］.Computer amp; Digital Engineering，2007，35（12）：49-53.）

［6］楊焯群.EDA技術發展綜述［J］.電子制作，2018（1）：90-91. （Yang Chaoqun.Summary on development of EDA technology［J］.Practical Electronics，2018（1）：90-91.）

［7］毛忠宇.PCB設計軟件未來5～10年發展趨勢預測［J］.印制電路信息，2016，24（9）：43-45. （Mao Zhongyu.PCB design software development tendency prediction in the next 5～10 years［J］.Printed Circuit Information，2016，24（9）：43-45.）

［8］杜昶旭，蔡懿慈，洪先龍，等.基于線網分類的模擬電路自動布線器［J］.計算機輔助設計與圖形學學報，2008，20（4）：417-424. （Du Changxu，Cai Yici，Hong Xianlong，et al.A net-classification based analog IC router［J］.Journal of Computer-Aided Design amp; Computer Graphics，2008，20（4）：417-424.）

［9］Wu Peici，Ma Qiang，Wong M D F.An ILP-based automatic bus planner for dense PCBs［C］//Proc of the 18th Asia South Pacific Design Automation Conference.Piscataway，NJ：IEEE Press，2013：181-186.

［10］Udgirkar G，Indumathi G.VLSI global routing algorithms：a survey［C］//Proc of the 3rd International Conference on Computing for Sustainable Global Development.Piscataway，NJ：IEEE Press，2016：2528-2533.

［11］Hu Jiang，Sapatnekar S S.A survey on multi-net global routing for integrated circuits［J］.Integration，2001，31（1）：1-49.

［12］Cho M，Pan D Z.BoxRouter：a new global router based on box expansion and progressive ILP［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2007，26（12）：2130-2143.

［13］Luenberger D G，Ye Yinyu.Linear and nonlinear programming［M］.Berlin：Springer，2009.

［14］Lee C Y.An algorithm for path connections and its applications［J］.IRE Trans on Electronic Computers，1961，10（3）：346-365.

［15］Moore E F.The shortest path through a maze［C］//Proc of International Symposium on Switching Theory.Cambridge：Harvard University Press，1957：285-292.

［16］Cho M，Lu K，Yuan Kun，et al.BoxRouter 2.0：architecture and implementation of a hybrid and robust global router［C］//Proc of IEEE/ACM International Conference on Computer-Aided Design.Washington DC：IEEE Computer Society，2007：503-508

［17］劉耿耿，莊震，郭文忠，等.VLSI中高性能X結構多層總體布線器［J］.自動化學報，2020，46（1）：79-93. （Liu Genggeng，Zhuang Zhen，Guo Wenzhong，et al.High performance X-architecture multilayer global router for VLSI［J］.Acta Automatica Sinica，2020，46（1）：79-93.）

［18］Kastner R，Bozorgzadeh E，Sarrafzadeh M.Predictable routing［C］//Proc of IEEE/ACM International Conference on Computer Aided Design.New York：ACM Press，2000：110-114.

［19］Hu Yu，Jing Tong，Hong Xianlong，et al.A routing paradigm with novel resources estimation and routability models for X-architecture based physical design［C］//Proc of the 5th International Conference on Embedded Computer Systems：Architectures，Modeling，and Simulation.Berlin：Springer，2005：344-353.

［20］Cao Zhen，Jing Tong，Hu Yu，et al.DraXRouter：global routing in X-architecture with dynamic resource assignment［C］//Proc of Asia and South Pacific Design Automation Conference.Piscataway，NJ：IEEE Press，2006：618-623.

［21］孟暢，蔡懿慈.基于數據場的總體布線擁擠度計算模型［J］.微電子學，2013，43（2）：296-300. （Meng Chang，Cai Yici.Congestion estimation model for global routing based on data field［J］.Micro-electronics，2013，43（2）：296-300.）

［22］陳秀華.一種考慮擁擠度的布線模型及其算法［J］.福州大學學報：自然科學版，2015，43（1）：47-53. （Chen Xiuhua.A routing model and algorithm with routing congestion control［J］.Journal of Fuzhou University：Natural Science Edition，2015，43（1）：47-53.）

［23］Zhang Ran，Watanabe T.A parallel routing method for fixed pins using virtual boundary［C］//Proc of the 1st IEEE TENCON Spring Confe-rence.Piscataway，NJ：IEEE Press，2013.

［24］Tsai C C，Wang C M，Chen Saojie.NEWS：a net-even-routing system for the routing on a multilayer PGA package［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，1998，17（2）：182-189.

［25］Tian Yang，Zhang Ran，Watanabe T.Efficient delay-matching bus routing by using multi-layers［C］//Proc of International Conference on Electronics Packaging.Piscataway，NJ：IEEE Press，2014.

［26］Yan Jintai，Tseng Y J，Yen C H.Feasible region assignment of routing nets in single-layer routing［C］//Proc of IEEE International Symposium on Circuits and Systems.Piscataway，NJ：IEEE Press，2014：393-396.

［27］李德仁，龔健雅，邊馥苓.GIS的數據組織與處理方法［J］.測繪通報，1994（1）：28-37. （Li Deren，Gong Jianya，Bian Fuling.Methods to organizing and processing data in GIS［J］.Bulletin of Surveying and Mapping，1994（1）：28-37.）

［28］龔健雅.GIS中矢量柵格一體化數據結構的研究［J］.測繪學報，1992，21（4）：259-266. （Gong Jianya.Research on vector and raster integrated data structure in GIS［J］.Acta Geodaetica et Cartographica Sinica，1992，21（4）：259-266.）

［29］辜慧貞.初探PCB印刷電路板中地線設計［J］.數字通信世界，2019（11）：120，217. （Gu Huizhen.Design of the ground wire in PCB［J］.Digital Communication World，2019（11）：120，217.）

［30］FreeRouting［EB/OL］.https：//freerouting.org/.

［31］Lin T C，Merrill D，Wu Y Y，et al.A unified printed circuit board routing algorithm with complicated constraints and differential pairs［C］//Proc of the 26th Asia and South Pacific Design Automation Conference.New York：ACM Press，2021：170-175.

［32］KONEKT Electra［EB/OL］.https：//konekt.com/.