結(jié)合改進(jìn)A*算法與拆線重布的有序逃逸布線

鄧新國 葉似錦 陳家瑞* 陳傳東

①(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 福州 350108)

②(福州大學(xué)物理與信息工程學(xué)院 福州 350108)

1 引言

有序逃逸布線問題，作為印刷電路板(Printed Circuit Board， PCB)設(shè)計(jì)中的關(guān)鍵問題。目前，電路板的布線在很大程度上還是由專業(yè)人員手工完成。隨著電路板器件集成度不斷提高，器件引腳數(shù)量大規(guī)模增加，現(xiàn)有自動逃逸布線算法已經(jīng)無法為專業(yè)人員提供有效的幫助。因此，如何能夠快速得到一個可行的布線方案已成為急需解決的問題。

逃逸布線是將引腳網(wǎng)格內(nèi)的某些引腳連接到網(wǎng)格的邊界上，最主要的考慮因素是可布線性，在可布線性得到滿足的情況下優(yōu)化線長，逃逸布線問題主要分為無序逃逸布線和有序逃逸布線兩類[1，2]。目前，對于無序逃逸布線的研究已經(jīng)取得了很好的成果，由于無序逃逸布線沒有終點(diǎn)順序要求，所以對于該問題的研究[3—5]都使用網(wǎng)絡(luò)流方法進(jìn)行求解并可以在短時間內(nèi)得到最優(yōu)解，且文獻(xiàn)[6，7]研究并解決多層逃逸問題。

而有序逃逸布線由于逃逸目標(biāo)線路順序的限制，使用網(wǎng)絡(luò)流方法無法解決，現(xiàn)有的研究提出的方法又可以分為并行布線方法和串行布線方法[8]。并行布線就是一次性對所有引腳進(jìn)行線路規(guī)劃，文獻(xiàn)[9，10]用整數(shù)線性規(guī)劃(Integer Linear Programming， ILP)解決了一個相關(guān)但不同的逃逸問題，該問題中引腳具有固定的逃逸終點(diǎn)，文獻(xiàn)[11]使用分組等策略改進(jìn)ILP，降低約束項(xiàng)數(shù)量。Tomioka等人[12]只采用無繞行單調(diào)模式，這意味著即使存在解決方案，也不一定能保證找到解決方案。盡管他們使用的方法在圖有環(huán)時考慮非單調(diào)布線，但是在資源沖突需要繞行時，非單調(diào)布線就會失敗。文獻(xiàn)[13，14]將有序的逃逸布線轉(zhuǎn)換為一個布爾可滿足性問題(Boolean Satisfiability Problem， SAT)，并通過SAT求解器解決。該方法無需對路線始末進(jìn)行任何假設(shè)，即可準(zhǔn)確完成布線。但是，該方法很難解決逃逸布線容量不為1的情況。在最新的研究中，Jiao等人[15]使用最小費(fèi)用多商品流(Min-cost Multi-Commodity Flow， MMCF)方法來解決這個問題，主要是通過使用虛擬節(jié)點(diǎn)，構(gòu)建具有始末節(jié)點(diǎn)且符合求解約束的圖，進(jìn)而使用MMCF求解器來求解，在大規(guī)模引腳陣列中構(gòu)建圖，虛擬點(diǎn)的數(shù)量過多會使得運(yùn)算量大幅度增加。

串行布線則是按照每條線的順序依次進(jìn)行布線，每條線布線完成后更新占用的資源，下一條線在空余資源上進(jìn)行規(guī)劃。串行布線對布線的先后順序有很強(qiáng)的依賴性，因?yàn)橄刃械木€占用了資源后，之后的引腳可能無法逃逸，因此，使用拆線重布[16]的方法來對已有的線進(jìn)行調(diào)整。

并行布線的方法隨著電路板引腳數(shù)量變多，時間復(fù)雜度會迅速增加，耗費(fèi)的CPU時間會成倍增長，甚至?xí)o法求解。因此，當(dāng)遇到的引腳陣列規(guī)模較大時，并行布線的方法會允許程序?qū)ふ铱尚薪舛皇亲顑?yōu)解。

在逃逸布線中兼顧可布線性與線長，提出了一種3階段串行布線的逃逸布線方法。主要步驟為：首先構(gòu)造預(yù)估函數(shù)估算引腳逃逸所需的資源，確定可行的布線順序，以此構(gòu)造初始解，接著對擁擠區(qū)域與同長度布線路徑進(jìn)行優(yōu)化，最后使用拆線重布的方法對無法逃逸的引腳進(jìn)行重新布線。

2 問題描述

逃逸布線是將引腳陣列內(nèi)的某些引腳連接到組件邊界上。

目前市面上器件的封裝形式主要分為交錯引腳陣列(Staggered Pin Arrays， SPA)[17]和網(wǎng)格引腳陣列(Grid Pin Array， GPA)，本文主要研究GPA下的逃逸布線，如圖1。定義一個多行多列的規(guī)則排布引腳陣列，假設(shè)在每4個引腳中間有一個中心節(jié)點(diǎn)，使得需要逃逸的引腳通過中心節(jié)點(diǎn)連接到邊界上。

算法輸入為給定引腳陣列構(gòu)建的有向圖G(V，E)，其中V ={v0，v1，v2，···，vm}是引腳與中心點(diǎn)標(biāo)號集合， E是邊集合，S ， T分別表示起點(diǎn)集合(引腳集合)和終點(diǎn)集合，xuw=1表示由節(jié)點(diǎn)u前往節(jié)點(diǎn)w的有向邊被選中，xuw=0則表示沒被選中，cuw表示由節(jié)點(diǎn)u前往節(jié)點(diǎn)w的有向邊的代價，將問題描述為一個整數(shù)線性規(guī)劃問題，即

圖1 GPA單邊逃逸布線示意圖

其中，第1個約束確保每個節(jié)點(diǎn)只會被一條引腳布線選中，避免沖突。第2個約束確保每個除了源和目標(biāo)節(jié)點(diǎn)外的中間節(jié)點(diǎn)入度與出度是平衡的，即構(gòu)造的線路是連續(xù)的。其余約束確保每條線由逃逸引腳出發(fā)，到達(dá)邊界終點(diǎn)，最終目標(biāo)是最小化總體線長。每條邊的基礎(chǔ)代價都為1。

有序逃逸布線問題的輸入與逃逸布線相同，但要給出逃逸引腳的順序。本文中出線的順序都以順時針排列，如圖2。

圖2 單邊有序逃逸布線示意圖

當(dāng)引腳間的布線容量增加時，問題規(guī)模會成倍地增加，從而導(dǎo)致算法復(fù)雜的大幅提高。但是在實(shí)際情況下，引腳間的布線容量不一定為1，算法亦考慮了逃逸布線問題中可變?nèi)萘康那闆r，不同容量的引腳陣列如圖3所示。

3 有序逃逸布線

圖4為算法流程圖，算法框架分為構(gòu)建逃逸布線初始解、對擁擠區(qū)域的部分線路進(jìn)行優(yōu)化調(diào)整以及拆線重布共 3 個部分。

圖3 布線容量可變示意圖

圖4 算法流程圖

3.1 構(gòu)建布線初始解

在串行布線中，布線的順序?qū)τ谧罱K解的質(zhì)量會產(chǎn)生重大影響，在構(gòu)建初始解時，采用構(gòu)造預(yù)估函數(shù)對每一個引腳在當(dāng)前可用資源下逃逸可能耗費(fèi)的資源進(jìn)行計(jì)算，根據(jù)計(jì)算結(jié)果確定引腳的逃逸順序，能夠使初始解的結(jié)果更優(yōu)。設(shè)邊界點(diǎn)集合為K，邊界點(diǎn)標(biāo)記值為k，初始值為—1，當(dāng)前要逃逸的引腳編號為n，對應(yīng)目標(biāo)邊界點(diǎn)編號為m，則km=n，計(jì)算引腳與邊界點(diǎn)的曼哈頓距離作為該引腳的逃逸預(yù)估代價，引腳代價預(yù)估函數(shù)定義同式(2)。

其中，M為可用邊界點(diǎn)集合，任取m ∈M，可使以下布爾表達(dá)式成立

按照預(yù)估函數(shù)計(jì)算出各個引腳逃逸所需的預(yù)估代價后，選擇所需代價最小的引腳優(yōu)先逃逸，因?yàn)橐_逃逸所需資源越少，則代表引腳需要在之后的引腳先布線后再進(jìn)行繞路逃逸的可能性越低。

獲得需要逃逸的引腳編號與邊界點(diǎn)編號后，需要選用一種最短路徑的尋路算法，閱讀多路徑[18]文獻(xiàn)及多次實(shí)驗(yàn)對比后，最終選用A*算法來規(guī)劃逃逸路徑，總體代價函數(shù)如式(4)所示

其中，F(xiàn)(i)是當(dāng)前點(diǎn)i的綜合代價，G(i)是從起點(diǎn)沿著當(dāng)前生成的路徑移動到當(dāng)前點(diǎn)的真實(shí)移動代價，H(i)是A*算法的啟發(fā)式函數(shù)，計(jì)算從當(dāng)前點(diǎn)移動到終點(diǎn)的估算成本，H *(i)是從當(dāng)前點(diǎn)移動到終點(diǎn)的真實(shí)成本。本算法選用當(dāng)前點(diǎn)與終點(diǎn)的曼哈頓距離作為估算成本H(i)，由于H(i)=H *(i)，因此A*算法能夠在最短時間取得最優(yōu)解。A*算法主要通過維護(hù)OPEN表和CLOSE表來規(guī)劃路線。其中，OPEN表用于存放已經(jīng)生成，且已用啟發(fā)式函數(shù)做過估算，但尚未產(chǎn)生后繼節(jié)點(diǎn)的那些節(jié)點(diǎn)，也稱未考查節(jié)點(diǎn)；CLOSE表則用于存放已經(jīng)生成，且已經(jīng)考查過的節(jié)點(diǎn)。

A*算法步驟如下：

輸入：圖G，起始點(diǎn)s，終點(diǎn)t。

輸出：路徑點(diǎn)集合P。

步驟 1 讀入圖G，起始點(diǎn)s，終點(diǎn)t。

步驟 2 初始化OPEN={s}，CLOSE={}。

步驟 3 如果OPEN={}，規(guī)劃路徑失敗。

步驟 4 從OPEN表中取出F值最小的節(jié)點(diǎn)n，n放入CLOSE表中。

步驟 5 如果n=t，規(guī)劃路徑成功，返回路徑。

步驟 6 計(jì)算所有n的后繼節(jié)點(diǎn)F值。

步驟 7 將不在OPEN表中的點(diǎn)加入OPEN表，否則比較F值，如果當(dāng)前計(jì)算的F值更小，則更新該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。

步驟 8 返回步驟3。

為了進(jìn)一步提高算法的尋路效率，使用改進(jìn)的A*算法[19]，將代價函數(shù)修改為

其中，w定義為

當(dāng)搜索區(qū)域靠近邊界時，權(quán)值w會減小以弱化線長的影響，能夠使算法規(guī)劃路徑速度更快，為w設(shè)置上下界w ∈(0.6，0.9)確保算法可接納性不受影響。此外，還使用小根堆來使A*算法最壞時間復(fù)雜度由O(n2)降為O(nlog2n)。

為證明所采用的構(gòu)造預(yù)估函數(shù)逃逸所需耗費(fèi)的資源來引導(dǎo)初始解布線順序是有效的，使用另外兩種方法來代替預(yù)估函數(shù)計(jì)算的布線順序，選取給出的測試用例中引腳陣列規(guī)模較大的4個例子來對比3種方法構(gòu)建的初始解的總線長與布通率。對比結(jié)果如表1所示，其中，第1種是依照逃逸引腳的順序進(jìn)行布線，第2種是距離可用邊界近的引腳優(yōu)先逃逸，第3種則是使用預(yù)估函數(shù)進(jìn)行成本估計(jì)后確定逃逸順序。

表1、表2和表3中總線長以單元網(wǎng)格為基準(zhǔn)。從結(jié)果中可以看出，第3種方法在大規(guī)模陣列的布通率上有較大提高，在小規(guī)模陣列上也可以避免部分引腳進(jìn)行不必要的繞行。

表1 3種順序選擇方法結(jié)果對比

表2 3種算法布線結(jié)果對比

3.2 擁擠區(qū)域線路調(diào)整

調(diào)整階段主要是對擁擠區(qū)域與可同長度布線的路徑進(jìn)行優(yōu)化，策略是在不減少當(dāng)前已經(jīng)布好的線的情況下，對現(xiàn)有線的位置進(jìn)行調(diào)整，釋放因布線順序所產(chǎn)生的無意義的資源占用。

3.2.1 同長度布線路徑優(yōu)化

同長度布線路徑優(yōu)化是指引腳選擇另一條相同程度的路線可以防止去其他引腳繞路前往終點(diǎn)，從而避免資源的浪費(fèi)。如圖5所示，調(diào)整引腳2的布線方式，能夠使得引腳1在布線時使用更少的資源。

表3 3個階段布線結(jié)果對比

圖5為右側(cè)單邊逃逸，實(shí)線為已布好的線，虛線表示該引腳調(diào)整后的走線。

3.2.2 擁擠區(qū)域布線路徑調(diào)整

擁擠區(qū)域是指在一定區(qū)域內(nèi)線的排布使得某些引腳無法找到可行的邊界點(diǎn)作為自己的終點(diǎn)。如果邊界點(diǎn)集中有點(diǎn)i使式(7)成立

ki+1

則代表該區(qū)域?qū)τ谝_是擁擠的，如圖6所示。算法將對部分引腳進(jìn)行重新布線，在不減少成功逃逸的引腳數(shù)量的前提下，為目標(biāo)引腳預(yù)留出可行的目標(biāo)終點(diǎn)。

本階段算法步驟如下：

輸入：已布線圖G，未逃逸引腳集合R。

輸出：布線路徑集合P。

步驟 1 讀入布線圖G與引腳R。

步驟 2 從引腳集合R中選取引腳r。

步驟 3 使用式(7)尋找引腳r的擁擠區(qū)域。

步驟 4 檢索擁擠區(qū)域兩側(cè)的空余邊界點(diǎn)。

圖5 同長度優(yōu)化調(diào)整示意圖

圖6 造成阻擋的擁擠區(qū)域布線調(diào)整示意圖

步驟 5 將已布好的線向兩側(cè)移動。步驟 6 對引腳r進(jìn)行重新布線。

步驟 7 返回步驟2，直至集合為空。

3.3 拆線重布

如果經(jīng)過第2階段優(yōu)化后依然存在無法逃逸的引腳，則代表僅靠對現(xiàn)有線路的簡單調(diào)整無法給予該引腳足夠的資源，因此，將對圖中線路進(jìn)行拆線重布來尋找所有引腳的逃逸方法。

3.3.1 基于A*算法的拆線重布

使用前兩個階段確定的邊界終點(diǎn)，A*算法能夠快速規(guī)劃路徑。

代價函數(shù)對于拆線重布階段至關(guān)重要，通過修改邊的代價將指引程序在不同的方向檢索可行路徑。若一條邊同時被多條線路選中，則該邊為擁擠邊，當(dāng)線路需要通過擁擠邊時，增加擁擠邊的代價會鼓勵程序考慮從其他位置布線。

因此，本階段邊的代價由代價函數(shù)確定

p為人為設(shè)定的懲罰系數(shù)，目的是防止邊的代價的增長速度過快，定義為

如果某條邊的代價達(dá)到cmax，則代表布通率無法達(dá)到100%，程序?qū)⒆詈笠淮螌ξ刺右菀_隊(duì)列中的引腳進(jìn)行布線后進(jìn)入下一個步驟，cmax設(shè)為定值100。

對拆線重布效果有主要影響的另一個因素是布線順序，對每個引腳前一次布線的真實(shí)線長升序排列來確定布線順序可以有效地減少重布線的次數(shù)，并且提高布線的質(zhì)量。

3.3.2 基于廣度優(yōu)先算法的拆線重布

由于預(yù)先確定的始末節(jié)點(diǎn)可能會導(dǎo)致算法無法找到合適的逃逸路徑，因此，在不預(yù)設(shè)邊界終點(diǎn)的情況下，使用基于廣度優(yōu)先算法進(jìn)行第二輪拆線重布，當(dāng)算法檢索到邊界節(jié)點(diǎn)時，使用式(3)判斷該邊界節(jié)點(diǎn)是否符合要求。同時，代價函數(shù)重新定義如式(11)所示：

其中，p定義為常數(shù)1.1，廣度優(yōu)先搜索會消耗大量的時間，因此通過放大歷史代價來加快算法規(guī)劃路徑的速度，但是過多地增加邊的代價，會導(dǎo)致算法規(guī)劃的路徑繞行過多，為了平衡布線速度與總線長兩個方面，該常數(shù)設(shè)置為1.1時能在短時間內(nèi)得到較優(yōu)的布線結(jié)果。需要說明的是，如果經(jīng)過上一個步驟后全部引腳都能夠成功逃逸，則不進(jìn)行這個步驟。

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

由于知識產(chǎn)權(quán)限制，本文無法得到已發(fā)表論文中實(shí)現(xiàn)方法的源代碼。因此，本文對互聯(lián)網(wǎng)中開源的論文方法復(fù)現(xiàn)代碼進(jìn)行修改調(diào)試，重新實(shí)現(xiàn)的程序可能由于計(jì)算機(jī)硬件以及其他各方面的差異，導(dǎo)致實(shí)驗(yàn)結(jié)果與已發(fā)表的論文中結(jié)果有所不同。但在相同的測試案例中，我們復(fù)現(xiàn)的代碼的實(shí)驗(yàn)結(jié)果與已有論文中的結(jié)果相差較小，因此，將復(fù)現(xiàn)代碼的實(shí)驗(yàn)結(jié)果作為對比的實(shí)驗(yàn)結(jié)果。

圖7 Case8最終布線結(jié)果圖

由于沒有行業(yè)基準(zhǔn)的有序逃逸布線測試用例，文獻(xiàn)[13—15]構(gòu)造了一些可布線的測試用例，并使用了一些文獻(xiàn)[15]中的測試用例用作對比，這些案例的引腳陣列規(guī)模由小到大，包含了單側(cè)、兩側(cè)、三側(cè)以及全方向的逃逸用例，同時也構(gòu)建了引腳間容量為2的測試用例來測試算法性能。實(shí)驗(yàn)結(jié)果如表2所示，其中Row和Col代表引腳的行數(shù)和列數(shù)，Pin表示需要逃逸的引腳數(shù)量，Cap表示引腳間的布線容量，Side則表示該引腳陣列有幾個方向可用于逃逸，其中帶*號的表示該結(jié)果為文獻(xiàn)[13—15]中的實(shí)驗(yàn)結(jié)果。圖7則給出了Case8的布線結(jié)果圖。

實(shí)驗(yàn)使用個人電腦CPU為Intel Core i5-6500，主頻為3.20 GHz。從表2可以看出，隨著引腳陣列規(guī)模的不斷增大，無論是使用SAT求解器，或是使用ILP求解器，都會因?yàn)榧s束式的大量增加，導(dǎo)致求解速度不斷下降，甚至是無法求解；而我們的算法在數(shù)據(jù)規(guī)模變大時，求解時間仍處在可接受的范圍內(nèi)。

算法的CPU時間相較于SAT算法結(jié)果平均提升約95.6%，相較于MMCF算法結(jié)果平均提升約97.8%。在大規(guī)模引腳陣列案例Case8中，與MMCF方法相比，總體線長減少約7.7%，布線時間減少約99.8%。在容量為2的測試用例中，SAT方法由于本身的限制，無法解決此類問題，而使用MMCF方法在規(guī)模較大的例子中會因?yàn)闃?gòu)建的圖規(guī)模過大而需要消耗大量的CPU時間。而本文算法在可變?nèi)萘康那闆r下，依舊可以在短時間內(nèi)給出可行解，證明了算法的可行性。

為進(jìn)一步分析算法效果，收集對比了部分測試用例經(jīng)過每一個階段后的布線率、總線長以及每一個階段的用時情況，結(jié)果如表3所示?？梢钥闯?，經(jīng)過第1階段的布線，剩余無法逃逸的引腳數(shù)量比例已經(jīng)很低。在經(jīng)過第2階段優(yōu)化調(diào)整后，總線長都有一定程度的減少，可以看出擁擠資源得到釋放。在第3階段結(jié)束后，所有的引腳都能夠成功逃逸，證明了該方法每個階段的有效性。從表中可以看出串行布線最耗費(fèi)時間的階段是第3階段的拆線重布，并且從Case8與Case10 (圖8)的布線結(jié)果可以看出，拆線重布的次數(shù)過多會導(dǎo)致邊的代價過高使得算法無法找到最短路徑，因此，算法對于引腳的位置與順序較為敏感。

在通常情況下，專業(yè)設(shè)計(jì)的電路板器件，在于可布線性方面都進(jìn)行過精心調(diào)整，器件內(nèi)部要逃逸的引腳不會出現(xiàn)大量無序、混亂的情況。綜上所述，算法無論是在學(xué)術(shù)方面，還是在工業(yè)設(shè)計(jì)中，都具有一定的優(yōu)勢。

5 結(jié)束語

圖8 Case10最終布線結(jié)果圖

針對現(xiàn)有的逃逸布線算法大都采用整數(shù)線性規(guī)劃等并行布線方法，在大規(guī)模引腳陣列中由于約束式過多導(dǎo)致運(yùn)行速度慢，并且求得的解效果不佳甚至無法求解的情況。本文提出一種基于A*算法的串行有序逃逸布線算法。用預(yù)估函數(shù)判斷目標(biāo)終點(diǎn)，用改進(jìn)的A*算法快速構(gòu)建初始解，用拆線重布對所有引腳進(jìn)行布線。多個測試用例結(jié)果表明，總體質(zhì)量較高的逃逸布線能夠在較短時間內(nèi)完成，在規(guī)模最大的測試用例Case8中，效果提升最為明顯。本文提出的方法能夠有效提升布線速度與質(zhì)量。

隨著VLSI技術(shù)的發(fā)展，電路板器件集成度不斷提高，逃逸布線規(guī)模也不斷增大，求解時間急劇增加。因此，探索并改進(jìn)串行布線算法，使算法能夠更好地求解更大規(guī)模的逃逸布線問題是我們今后研究的一個重點(diǎn)。此外，逃逸布線中的差分對以及分層問題的求解也是亟待解決的重點(diǎn)問題，設(shè)計(jì)一個合理的算法來綜合解決PCB自動布線方面的問題將是我們未來的研究方向。