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

摘 要： 雙層印制電路板（PCB）通常空間結(jié)構(gòu)及布線線形復(fù)雜、約束規(guī)則眾多，而常用PCB空間結(jié)構(gòu)簡單、布線線形單一，不能有效利用PCB的空間關(guān)系及拓?fù)湫畔⒁龑?dǎo)布線規(guī)劃。為彌補(bǔ)以前工作的不足，提出一種基于GIS（geographic information system）技術(shù)的空間剖分算法，首先利用空間距離與幾何要素拓?fù)潢P(guān)系進(jìn)行分組預(yù)處理，然后引入矢柵一體化模型構(gòu)建復(fù)雜空間及屬性約束下的網(wǎng)絡(luò)模型，基于該網(wǎng)絡(luò)模型提取區(qū)域基準(zhǔn)線并利用空間緩沖區(qū)技術(shù)得到空間剖分結(jié)果，從而引導(dǎo)布線規(guī)劃。實(shí)驗(yàn)結(jié)果表明，該算法能夠在滿足所有設(shè)計(jì)規(guī)則的情況下實(shí)現(xiàn)100%的布線連通率，同時(shí)有效利用布線空間資源；提出的算法布線線形接近人工布線，對于實(shí)現(xiàn)復(fù)雜場景與多約束下的雙層PCB自動(dòng)化布線具有實(shí)際意義。

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

中圖分類號： TP391.72"" 文獻(xiàn)標(biāo)志碼： 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開發(fā)主要包括電路原理圖設(shè)計(jì)、器件布局規(guī)劃、布線等步驟，其中布線是極為重要的步驟［1，2］。隨著電路板集成度提高、電路密度增大，完全人工的布線方式存在的重復(fù)性工作多、布線效率低下、耗時(shí)長等問題愈發(fā)突出［3］。盡管國內(nèi)外現(xiàn)有的電子設(shè)計(jì)自動(dòng)化（electronic design automation，EDA）軟件在電路設(shè)計(jì)與仿真、PCB設(shè)計(jì)、集成電路設(shè)計(jì)和可編程邏輯器件設(shè)計(jì)等應(yīng)用領(lǐng)域已取得諸多進(jìn)展［4～6］，一定程度上能夠提高PCB布線的自動(dòng)化程度［7～9］，但是針對復(fù)雜約束下的布線場景，仍需人工根據(jù)不同網(wǎng)絡(luò)的特性進(jìn)行詳盡的走線規(guī)則設(shè)計(jì)并對布線過程進(jìn)行追蹤，動(dòng)態(tài)修改甚至重新規(guī)劃不合理的布線結(jié)果，這對人工布線經(jīng)驗(yàn)與編程設(shè)計(jì)提出了較高要求。因此，在符合布線約束及設(shè)計(jì)要求的前提下提升布線連通率、減少人工干預(yù)，是實(shí)現(xiàn)PCB自動(dòng)化布線的關(guān)鍵所在。

1 相關(guān)工作

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

布線容量與布線代價(jià)是影響布線設(shè)計(jì)的重要方面。Hu等人［19］提出了布線資源分配模型，根據(jù)線的寬度、布線面積和層數(shù)為總體布線圖中的每條邊分配可用的布線路徑條數(shù)從而量化計(jì)算布線容量；Cao等人［20］提出了基于動(dòng)態(tài)資源分配的總體布線方法，考慮了總體布線圖中一條邊的布線對其相鄰邊的影響，進(jìn)而優(yōu)化了布線容量計(jì)算模型；孟暢等人［21］提出了一種基于數(shù)據(jù)場中勢能和場強(qiáng)的擁擠度建模方法，使布線路徑遠(yuǎn)離擁擠區(qū)域；陳秀華［22］引入了擁擠度代價(jià)函數(shù)以獲得更為精確的布線資源估計(jì)，并提出了基于擁擠度模型的多級布線策略。但上述基于計(jì)算布線容量的布線模型不能較好地利用電路板邊界等幾何拓?fù)湫畔ⅲ矡o法引導(dǎo)網(wǎng)絡(luò)在電路板上的正確走向，導(dǎo)致布通率的提升空間有限，難以應(yīng)用于復(fù)雜約束下的布線設(shè)計(jì)。

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

針對上述不足，本文對雙層PCB自動(dòng)化布線提出了一種基于GIS技術(shù)的空間剖分算法，其主要思路是以PIN組對為基本單位規(guī)劃每條網(wǎng)絡(luò)對應(yīng)的可布線區(qū)域，在不違反各項(xiàng)設(shè)計(jì)規(guī)則的條件下實(shí)現(xiàn)對各布線區(qū)域網(wǎng)絡(luò)的全部連通。該算法通過對空間的剖分減小了直接布線的規(guī)模，基于GIS中柵格模型和矢量模型［27］組織存儲數(shù)據(jù)，通過提取PIN的空間特征與邊界幾何拓?fù)涮卣鳛楹罄m(xù)模型構(gòu)建提供支持，引入矢柵一體化模型［28］構(gòu)建復(fù)雜空間及屬性約束下的網(wǎng)絡(luò)模型，基于該網(wǎng)絡(luò)模型提取基準(zhǔn)線并利用空間緩沖區(qū)技術(shù)獲取空間剖分結(jié)果，最終實(shí)現(xiàn)布線連通。

2 問題建模

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

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

定義2 PIN組，將空間中位置鄰近的PIN劃分為組。設(shè)PIN共被劃分為k組，即k個(gè)PIN組，那么對于第i（i∈［1，k］）個(gè)PIN組，如果存在ni個(gè)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有連接關(guān)系（e∈［1，ni］，f∈［1，nj］，e、f均為整數(shù)），就將PIN組Si與Sj稱為一個(gè)PIN組對。

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

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

任意一個(gè)電路板的布線均需嚴(yán)格滿足其對應(yīng)的空間約束、網(wǎng)絡(luò)約束、結(jié)構(gòu)工藝約束。

定義6 空間約束。主要針對網(wǎng)絡(luò)與網(wǎng)絡(luò)、網(wǎng)絡(luò)與電路板邊界之間的最小距離約束；此外空間約束還包括網(wǎng)絡(luò)必須布設(shè)于可布線區(qū)域內(nèi)，網(wǎng)絡(luò)之間不允許交叉。

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

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

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

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

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

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

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

d）同一個(gè)PIN組內(nèi)的PIN排列緊密，PIN之間的距離不超過封裝的長度，且組間間距遠(yuǎn)大于組內(nèi)間距。

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

3 基于GIS技術(shù)的空間剖分算法

基于GIS技術(shù)的空間剖分算法利用幾何要素的空間拓?fù)潢P(guān)系，結(jié)合基于距離的空間聚類技術(shù)、矢柵一體化模型、最短路徑規(guī)劃、線要素簡化以及空間緩沖區(qū)技術(shù)得到最終空間剖分結(jié)果。首先利用PIN在電路板上聚集分布的空間特征，基于空間距離聚類實(shí)現(xiàn)PIN分組，并利用組成電路板邊界幾何要素間的拓?fù)潢P(guān)系有序性對電路板邊界進(jìn)行分組；然后根據(jù)PIN組間連接關(guān)系數(shù)確定剖分子區(qū)域的個(gè)數(shù)，并在柵格模型下進(jìn)行區(qū)域預(yù)劃分，同時(shí)設(shè)置空間權(quán)重用于引導(dǎo)尋找區(qū)域中心線；根據(jù)場景進(jìn)行判斷，只有一組連接關(guān)系且邊界附近無禁止布線區(qū)時(shí)提取貼近電路板邊界的線（簡稱貼邊線），其他情況下，基于矢柵一體化模型在滿足結(jié)構(gòu)工藝約束下通過A*算法提取矢量中心線，并通過Douglas-Peucker（DP）算法簡化；最后根據(jù)網(wǎng)絡(luò)約束計(jì)算PIN組對至少所需的區(qū)域?qū)挾龋曰喓蟮氖噶烤€為基準(zhǔn)基于試探法創(chuàng)建空間緩沖區(qū)，最終得到空間剖分區(qū)域。

空間剖分算法總體流程如圖2所示，主要分為三個(gè)步驟：a）基于空間距離和幾何要素拓?fù)潢P(guān)系的分組預(yù)處理，詳細(xì)闡述了基于空間距離對PIN進(jìn)行聚類分組，以及根據(jù)電路板邊界組成要素的幾何拓?fù)潢P(guān)系對邊界分組；b）區(qū)域中心線或貼邊線提取首先需要確定剖分區(qū)域個(gè)數(shù)，并根據(jù)電路板具體場景確定選擇提取中心線還是貼邊線的方案；c）基于試探法，創(chuàng)建空間緩沖區(qū)，最終得到空間剖分結(jié)果。

3.1 基于空間距離與幾何要素拓?fù)潢P(guān)系的分組預(yù)處理

分組預(yù)處理是進(jìn)行區(qū)域預(yù)劃分的前提。由于區(qū)域預(yù)劃分步驟需要找到PIN組對對應(yīng)的電路板邊界，再基于對應(yīng)邊界向電路板內(nèi)部擴(kuò)展得到預(yù)劃分結(jié)果，所以首要任務(wù)是識別PIN組，并根據(jù)電路板邊界的幾何拓?fù)湫畔吔邕M(jìn)行分組。

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

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

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

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

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

for Si in S

for Sj in S

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

if distlt;thresh_D // thresh_D為區(qū)分PIN組的閾值

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

Si←Si+Sj；

else Sj←Si+Sj；

end for

end for

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

算法2 Cal_pingroup_dist，計(jì)算兩PIN組間的最短距離

輸入：PIN組A，PIN組B。

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

dist←INT_MAX；

for ai in A

for bi in B

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

if dlt;dist then

dist←d；

end for

end for

3.1.2 基于要素拓?fù)潢P(guān)系的電路板幾何邊界分組

對電路板幾何邊界進(jìn)行分組的目的是找到PIN組對對應(yīng)的電路板邊界。在PIN分組結(jié)果的基礎(chǔ)上，首先通過構(gòu)造PIN組的最小外接矩形（minimum bounding rectangle，MBR）判斷PIN組的排列方向，并計(jì)算各PIN組MBR及兩端點(diǎn)的位置，然后利用組成電路板邊界的幾何要素的拓?fù)潢P(guān)聯(lián)有序性對電路板邊界進(jìn)行分組。

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

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

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

輸入：某一PIN組的左或下端點(diǎn)pmin，某一PIN組的右或上端點(diǎn)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組個(gè)數(shù)pg、第i（i∈［0，pg-1］）個(gè)PIN組MBR兩對邊上的中點(diǎn)，輸出為電路板邊界分組結(jié)果以及邊界對應(yīng)的各個(gè)PIN組。首先根據(jù)算法 3遍歷所有PIN組后可以獲取各PIN組對應(yīng)的線或弧編號Nij（j=0，1），Ni0和Ni1表示第i個(gè)PIN組對應(yīng)的兩個(gè)線或弧的編號；其次遍歷電路板邊界線段和弧段，index表示當(dāng)前編號，cur表示當(dāng)前PIN組編號，startIndex表示起始線或弧編號；然后根據(jù)index的值進(jìn)行判斷，如果index等于當(dāng)前PIN組對應(yīng)編號之一，則說明temp中存放的線或弧組成的邊界對應(yīng)當(dāng)前PIN組；如果index等于其他PIN組對應(yīng)編號之一，則說明temp中存放的編號組成的邊界對應(yīng)當(dāng)前PIN組和另一個(gè)PIN組形成的PIN組對；當(dāng)index再次與起始值相等時(shí)終止循環(huán)，輸出電路板邊界分組結(jié)果。

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

輸入：PIN組個(gè)數(shù)pg，第i個(gè)PIN組的左或下端點(diǎn)pmini，第i個(gè)PIN組的右或上端點(diǎn)pmaxi。

輸出：電路板邊界分組結(jié)果以及邊界對應(yīng)的各個(gè)PIN組C。

for i in pg

Nij=Get_borderinter_segment（pmini，pmaxi）

/*獲取各PIN組延長線與電路板邊界相交線段或弧段的編號，Nij為一個(gè)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） //該步驟執(zhí)行后清空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）；//執(zhí)行后清空temp

end for

++index；//當(dāng)index達(dá)到最大編號后，規(guī)定index+1=0

if index==startIndex+1 then

Tag←0；

end

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

3.2 區(qū)域中心線或貼邊線提取

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

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

3.2.1 基于柵格模型的區(qū)域預(yù)劃分

區(qū)域預(yù)劃分是得到空間剖分結(jié)果前的預(yù)處理步驟，是以PIN組對對應(yīng)的電路板邊界為基礎(chǔ)向電路板內(nèi)部擴(kuò)展，將與該邊界接觸的柵格合并到屬于該P(yáng)IN組對的剖分區(qū)域中的過程。通過區(qū)域預(yù)劃分可以初步區(qū)分不同PIN組對的對應(yīng)區(qū)域。

由于提取貼邊線利用的是電路板邊界的幾何特征，所以只有提取區(qū)域中心線的情形需要進(jìn)行區(qū)域預(yù)劃分。對于存在電源線且采取提取區(qū)域中心線方案的PCB，需要進(jìn)行預(yù)劃分的區(qū)域?yàn)槌ル娫淳€區(qū)域后的剩余空間；對于無電源線網(wǎng)絡(luò)的PCB，進(jìn)行預(yù)劃分的區(qū)域?yàn)檎麄€(gè)電路板的可布線區(qū)域。基于柵格模型的區(qū)域預(yù)劃分流程如圖5所示。

在柵格模型下將PIN組對對應(yīng)的電路板邊界所在柵格單元設(shè)為屬于該P(yáng)IN組對的初始區(qū)域，PIN組對對應(yīng)區(qū)域?qū)挾雀鶕?jù)空間約束和網(wǎng)絡(luò)約束進(jìn)行計(jì)算。通過最大寬度比例是否超過τ來判斷各組寬度的差異大小：當(dāng)各個(gè)PIN組對對應(yīng)區(qū)域?qū)挾认嘟鼤r(shí)，各初始區(qū)域按照對應(yīng)比值來確定向電路板內(nèi)部每次擴(kuò)展多少個(gè)單位；當(dāng)PIN組區(qū)域?qū)挾炔町愝^大時(shí)，各初始區(qū)域依次向內(nèi)部擴(kuò)展，且僅擴(kuò)展一個(gè)單位，這樣的策略是為防止寬度差異較大時(shí)仍按照寬度比進(jìn)行擴(kuò)展導(dǎo)致各個(gè)區(qū)域預(yù)劃分范圍不均衡。具體而言，以當(dāng)前柵格為中心探索八個(gè)方向的鄰域柵格，若柵格不屬于其他PIN組對則將該柵格合并入當(dāng)前PIN組對，否則跳過該柵格，按上述步驟遍歷屬于該區(qū)域的所有柵格，此為擴(kuò)展一個(gè)單位。各區(qū)域依次循環(huán)進(jìn)行擴(kuò)展，每次擴(kuò)展均基于上一次循環(huán)擴(kuò)展得到的區(qū)域?yàn)榛A(chǔ)，然后各區(qū)域依次循環(huán)擴(kuò)展，直至整個(gè)電路板被劃分。最后進(jìn)行空間權(quán)重的設(shè)置，目的是設(shè)置越靠近區(qū)域中心的柵格空間權(quán)重越小，從而可以有效引導(dǎo)中心線的提取。

3.2.2 矢量貼邊線提取

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

3.2.3 矢量中心線提取

根據(jù)圖4流程，提取區(qū)域的矢量中心線存在兩種情形：存在電源線且不再適用貼邊線的；不存在電源線。情形的主要區(qū)別在于是否存在電源線網(wǎng)絡(luò)，因此需要對電源線網(wǎng)絡(luò)進(jìn)行特殊考慮。對于存在電源線的第一種情形，距離電路板邊界較近范圍內(nèi)存在禁止布線區(qū)域，表明電路板邊界幾何形狀受禁布區(qū)影響較大，因此提取貼邊線方案不再適用。這種情況下需要先預(yù)留出布設(shè)電源線區(qū)域，且只需設(shè)置一個(gè)合理的值作為預(yù)留電源線區(qū)域?qū)挾龋驗(yàn)楹罄m(xù)步驟為提取電路板上除電源線區(qū)域外剩余空間的中心線，中心線線形與電源線區(qū)域預(yù)留寬度無關(guān)。所以第一種情形需要預(yù)留電源線區(qū)域后提取剩余可布線區(qū)域的中心線，第二種情形直接進(jìn)行中心線提取。

首先將存在連接關(guān)系的PIN組MBR的幾何中心設(shè)為中心線的起點(diǎn)和終點(diǎn)，然后基于考慮空間權(quán)重的A*路徑搜索算法提取區(qū)域的中心線。考慮空間權(quán)重的改進(jìn)A*算法代價(jià)函數(shù)為

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

其中：F（i）為節(jié)點(diǎn)i的總代價(jià)；G（i）為節(jié)點(diǎn)i距離起點(diǎn)的距離代價(jià)；H（i）為節(jié)點(diǎn)i距離終點(diǎn)的預(yù)計(jì)代價(jià)；weight（i）為節(jié)點(diǎn)i的空間權(quán)重。節(jié)點(diǎn)在模型中可理解為柵格。算法在搜索當(dāng)前節(jié)點(diǎn)的八鄰域節(jié)點(diǎn)時(shí)，若節(jié)點(diǎn)i的鄰域節(jié)點(diǎn)mik（k∈［1，8］）在彎折區(qū)或補(bǔ)強(qiáng)區(qū)這類特殊區(qū)域中并且與父節(jié)點(diǎn)i的連線與該區(qū)域的長邊不呈垂直關(guān)系，或者節(jié)點(diǎn)mik在電路板邊界外部或禁止布線區(qū)域，則跳過該節(jié)點(diǎn)，以此保證提取的區(qū)域中心線符合結(jié)構(gòu)工藝約束。

以一塊存在電源線網(wǎng)絡(luò)且有兩個(gè)PIN組對的電路板為例，如圖6所示，紅色區(qū)域?yàn)殡娫淳€預(yù)留區(qū)域（參見電子版），圖6（a）為區(qū)域預(yù)劃分結(jié)果，藍(lán)色區(qū)域?yàn)轭A(yù)劃分區(qū)域1，黃色區(qū)域?yàn)轭A(yù)劃分區(qū)域2；圖6（b）為區(qū)域1空間權(quán)重的示意圖，從區(qū)域的邊界向內(nèi)空間權(quán)重值逐漸減小，即區(qū)域中心路徑代價(jià)更小，從而可以引導(dǎo)中心線的提取；圖6（c）中橙色表示的線為兩個(gè)區(qū)域的中心線提取結(jié)果（化簡前）。

3.3 基于試探法創(chuàng)建空間緩沖區(qū)的空間剖分

在提取各區(qū)域中心線/貼邊線結(jié)果的基礎(chǔ)上，根據(jù)電路板的網(wǎng)絡(luò)約束計(jì)算得到的各PIN組對應(yīng)空間寬度，以該區(qū)域提取的中心線/貼邊線為基準(zhǔn)，基于試探法及創(chuàng)建空間緩沖區(qū)方法得到各區(qū)域的空間剖分最終結(jié)果。中心線/貼邊線結(jié)果為有矢量方向的線，在提取矢量線步驟中設(shè)置PIN組對的起點(diǎn)、終點(diǎn)為順時(shí)針順序，且所有組的起點(diǎn)、終點(diǎn)順次相連的順序同樣為順時(shí)針順序；當(dāng)只有一組組間關(guān)系且存在電源線時(shí)，遵循電源線區(qū)域在起點(diǎn)、終點(diǎn)連線形成的矢量線的左側(cè)設(shè)置規(guī)則。依此可以確定各區(qū)域的中心線/貼邊線的哪一側(cè)遠(yuǎn)離電源線區(qū)域，哪一側(cè)靠近電源線區(qū)域，這是試探法中判斷創(chuàng)建緩沖區(qū)方向的重要前提。

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)參數(shù)

本文的實(shí)驗(yàn)參數(shù)有柵格分辨率α、DP算法化簡閾值θ、各組組寬最大比值τ、擴(kuò)展迭代結(jié)束閾值σ。具體各參數(shù)取值如表1所示。本文的實(shí)驗(yàn)環(huán)境為 Intel Core，CPU i5 - 3570 HQ，16.00 GB 內(nèi)存 、主頻 3.40 GHz，64 位 Windows 10 操作系統(tǒng)，并以C++作為編程語言進(jìn)行開發(fā)實(shí)現(xiàn)。

4.2 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

4.3 實(shí)驗(yàn)結(jié)果

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

針對三個(gè)PCB數(shù)據(jù)，本文算法對其劃分得到柵格行、列數(shù)分別為410×94、382×96、415×128。表6為FreeRouting、Konekt Electra、人工以及本文算法的布線實(shí)驗(yàn)結(jié)果。

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

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

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

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

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

總體而言，針對雙層PCB復(fù)雜布線場景，本文算法在不違反任何設(shè)計(jì)規(guī)則的條件下能夠?qū)崿F(xiàn)布線全部連通，并且空間占用率低，布線線形與人工較為相似。實(shí)驗(yàn)結(jié)果證明，本文算法對于實(shí)現(xiàn)雙層PCB自動(dòng)化布線具有實(shí)際意義。

5 結(jié)束語

為彌補(bǔ)現(xiàn)有PCB布線研究中鮮有涉及網(wǎng)絡(luò)類型種類多、網(wǎng)絡(luò)約束復(fù)雜、電路板邊界形狀不規(guī)則、PIN存在聚集分布等復(fù)雜布線場景的不足，本文提出了一種基于GIS技術(shù)的雙層PCB自動(dòng)化布線的空間剖分算法。該算法通過空間距離聚類與拓?fù)浞治鲚^好地利用了PCB復(fù)雜邊界的幾何特征；提出了中心線與貼邊線的不同提取方案，可以適用于多種不同的布線場景；同時(shí)采用了矢柵一體化模型以及空間緩沖區(qū)技術(shù)，實(shí)現(xiàn)了空間剖分，并能夠有效引導(dǎo)實(shí)際布線。

實(shí)驗(yàn)結(jié)果表明：a）所提算法能夠在實(shí)現(xiàn)布線連通率達(dá)100%的同時(shí)合理利用空間資源；b）適應(yīng)性強(qiáng)，根據(jù)不同場景采取提取中心線和貼邊線方案，兩種方案可以有針對性地處理不同電路板場景，提高了算法的適應(yīng)度；c）能夠有效引導(dǎo)、規(guī)劃布線線形，提高了網(wǎng)絡(luò)之間的線形相似性。

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

參考文獻(xiàn)：

［1］林秀鳳.PCB設(shè)計(jì)流程與經(jīng)驗(yàn)分析［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設(shè)計(jì)流程的改進(jìn)研究［J］.成都工業(yè)學(xué)院學(xué)報(bào)，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］宋謙，路林吉.面向目標(biāo)的主動(dòng)繞障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］劉超，王珺，張?zhí)靸x.集成電路EDA行業(yè)發(fā)展態(tài)勢分析［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技術(shù)綜述［J］.計(jì)算機(jī)與數(shù)字工程，2007，35（12）：49-53. （Liu Changhua.Evolution of EDA technology［J］.Computer amp; Digital Engineering，2007，35（12）：49-53.）

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

［7］毛忠宇.PCB設(shè)計(jì)軟件未來5～10年發(fā)展趨勢預(yù)測［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］杜昶旭，蔡懿慈，洪先龍，等.基于線網(wǎng)分類的模擬電路自動(dòng)布線器［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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結(jié)構(gòu)多層總體布線器［J］.自動(dòng)化學(xué)報(bào)，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］孟暢，蔡懿慈.基于數(shù)據(jù)場的總體布線擁擠度計(jì)算模型［J］.微電子學(xué)，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］.福州大學(xué)學(xué)報(bào)：自然科學(xué)版，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的數(shù)據(jù)組織與處理方法［J］.測繪通報(bào)，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中矢量柵格一體化數(shù)據(jù)結(jié)構(gòu)的研究［J］.測繪學(xué)報(bào)，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印刷電路板中地線設(shè)計(jì)［J］.數(shù)字通信世界，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/.