袁 也，王 剛，劉曉光，李雨森

(1.南開大學(xué)計算機學(xué)院，天津 300350；2.天津市網(wǎng)絡(luò)與數(shù)據(jù)安全重點實驗室(南開大學(xué))，天津 300350)

1 引言

發(fā)達(dá)國家在集成電路領(lǐng)域的高新技術(shù)成果方面始終對我國形成封鎖。近年來，集成電路自動化設(shè)計技術(shù)高速發(fā)展，為了推動我國邁入該領(lǐng)域發(fā)展的快車道，越來越多的學(xué)者開始研究電路自動化設(shè)計的相關(guān)技術(shù)。

當(dāng)前我國雖然在大規(guī)模電路的布局布線方面已有許多成果，但是對于中小規(guī)模電路的布局布線研究卻很少，更多的是追求快速求得整體結(jié)果和解決大規(guī)模問題的卓越能力，而暫時忽略了軟件商用時用戶自主設(shè)計的便捷性和舒適性以及用戶使用軟件時一些更具體的需求。對此本文改進(jìn)了劃分算法，提升了劃分結(jié)果質(zhì)量，提出了全新的布局算法，滿足對美觀度的要求，提升了A*算法的布線速度，提高了布線質(zhì)量，形成一套適用于中小規(guī)模模塊的布局布線方案，方便用戶在實際布線前檢查電路各模塊的邏輯錯誤，填補了相關(guān)研究領(lǐng)域的空白。

2 相關(guān)工作

目前電路布局算法主要有2類，一類是直接布局算法，另一類是面向劃分的布局算法。直接布局算法大多采用傳統(tǒng)啟發(fā)式算法如模擬退火算法[3,4]、遺傳算法[5,6]和粒子群優(yōu)化算法[7]等，是在一個初始布局的基礎(chǔ)上通過嘗試性改變的效果決定下一步迭代改進(jìn)的方向，循環(huán)往復(fù)直至結(jié)果滿足一定條件為止。這類算法的特點是布局效果較好，不易陷入局部最優(yōu)，但算法運行速度慢、時間長。

隨著電路元件規(guī)模達(dá)到數(shù)百甚至上千，這些元件組合成極其復(fù)雜的超圖，直接布局難度較大。面向劃分的布局算法將大規(guī)模的電路劃分為很多小規(guī)模的部分再布局，有效降低了布局難度，還可使各個功能模塊更加聚集，使得布局布線效果更好，缺點是部分算法的劃分結(jié)果常常不均衡。

電路布線技術(shù)多是在A*尋路算法[8]的基礎(chǔ)上進(jìn)行設(shè)計，該算法能夠在網(wǎng)格化空間內(nèi)有效尋找最短路徑，缺點是運行速度慢。

在布局階段本文改進(jìn)了Stoer-Wagner算法[9]，彌補了其劃分結(jié)果不均衡的缺點，同時使用Fiduccia-Mattheyses算法[10]優(yōu)化該算法的結(jié)果并形成一棵劃分樹，在劃分樹的基礎(chǔ)上設(shè)計了二元相對移動算法，能夠在兼顧布局擁擠度和布局空間大小的同時以較低的時間復(fù)雜度完成布局。在布線階段本文改進(jìn)了A*尋路算法，提高了其運行速度，并重新設(shè)計了其搜索函數(shù)，滿足了中小規(guī)模電路對較少的線路交叉、線路轉(zhuǎn)折以及較低的布線擁擠度的需求。

3 布局算法設(shè)計

本文設(shè)計的布局布線算法面向中小規(guī)模電路，試圖實現(xiàn)對元件的布局布線，區(qū)別于傳統(tǒng)的物理設(shè)計，本文設(shè)計的算法強調(diào)運行速度和布局布線結(jié)果的美觀性和邏輯性，而相對忽略布線空間的耗費。

在本文中布局算法的目標(biāo)有3點：(1)各元件按照功能模塊劃分和聚集；(2)各部分之間的割值盡量??；(3)劃分的各部分節(jié)點個數(shù)相差較??；(4)布局區(qū)域盡量小。

由于面向劃分的布局算法布局均勻，且相關(guān)技術(shù)較為成熟，因而本文基于面向劃分的布局算法進(jìn)行設(shè)計，選擇Stoer-Wagner算法生成初始劃分，并對算法做了改進(jìn)，避免出現(xiàn)不平衡的劃分結(jié)果，然后選擇Fiduccia-Mattheyses算法對初始劃分做進(jìn)一步改進(jìn)。

3.1 模型構(gòu)建

電路圖是非常典型的超圖模型，其中每條線路可能聯(lián)結(jié)2個以上的電路元件。本文首先建立了超圖模型，將數(shù)據(jù)讀入一張表中，例如表1，其中a、b、c代表超邊，數(shù)字表示節(jié)點，表項表示超邊與該節(jié)點聯(lián)結(jié)的權(quán)重。

Table 1 Edge node matrix

隨后將度為2以上的超邊，即聯(lián)結(jié)了2個以上節(jié)點的超邊轉(zhuǎn)化為節(jié)點，每個超邊轉(zhuǎn)化成的節(jié)點與原超邊關(guān)聯(lián)的每一個節(jié)點都有一條度為2的超邊，這樣超圖中則不存在度為2以上的超邊，則超圖轉(zhuǎn)化為圖，如圖1所示。數(shù)據(jù)存儲在鄰接矩陣中，如表2所示，數(shù)字表示節(jié)點，表項表示節(jié)點間邊的權(quán)重。之后的布局算法在此鄰接矩陣形式的基礎(chǔ)上進(jìn)行設(shè)計。

Figure 1 Transformation of hypergraph圖1 超圖的轉(zhuǎn)化

Table 2 Adjacency matrix

3.2 使用Stoer-Wagner算法獲得初始劃分

Stoer-Wagner算法是用于搜索無向圖的全局最小割的高效算法，普通的查找最小割的算法是Ford-Fulkerson算法，能在O(n2m)的時間復(fù)雜度內(nèi)查找到將確定的s、t2節(jié)點劃分到2部分的最小割，其中n為節(jié)點數(shù)，m為邊數(shù)，在復(fù)雜網(wǎng)絡(luò)下m甚至能達(dá)到O(n2)的復(fù)雜度，因此若使用Ford-Fulkerson算法查找全局最小割，復(fù)雜度可能會達(dá)到O(n5)，對于成百上千節(jié)點的情況，這樣的時間消耗顯然是無法接受的。Stoer-Wagner算法能在O(n3)的時間復(fù)雜度內(nèi)得出全局最小割，時間復(fù)雜度遠(yuǎn)遠(yuǎn)優(yōu)于Ford-Fulkerson算法。

Stoer-Wagner算法基于這樣一種思想：對于圖中任意2個節(jié)點，它們或者屬于全局最小割的2個不同劃分，或者屬于同一個劃分。如果是后者，那么合并這2個節(jié)點后并不影響全局最小割。

基于這種思路，若每次能求出將圖中某2個節(jié)點s、t劃分到2部分的最小割，記錄下割值和劃分后將這2個節(jié)點合并為1個節(jié)點，再求某2個節(jié)點的最小割，重復(fù)上述操作直至全部節(jié)點收縮為1個，此時記錄中割值最小的劃分就是所求的劃分。

其中在每次求將s、t劃分到2部分的最小割時基于一種貪心的策略：首先任選某一節(jié)點作為原點，從剩余節(jié)點中找出和原點相連的邊權(quán)重最大的一個，暫時將其與原點合并，重復(fù)此操作直至除原點外僅剩余一個節(jié)點為止，這個節(jié)點和最后一個與原點合并的節(jié)點即為上述的s、t，該節(jié)點和原點當(dāng)前的相連邊權(quán)重即為求得的割值。

如圖2所示節(jié)點3號和節(jié)點4號即為s、t，最小割值為2。詳細(xì)證明見參考文獻(xiàn)[11]。

Figure 2 Stoer-Wagner algorithm圖2 Stoer-Wagner算法

Stoer-Wagner算法能在O(n3)的時間復(fù)雜度內(nèi)得出有效解，效果遠(yuǎn)遠(yuǎn)好于傳統(tǒng)的最小割算法，但卻很少應(yīng)用于布圖算法，原因在于：(1)時間復(fù)雜度較高，難以用于大規(guī)模電路設(shè)計；(2)Stoer- Wagner算法求出的最小割是理論最小割，這樣的結(jié)果往往忽視了劃分的平衡要求，也就是說Stoer-Wagner算法常常會得出1∶99的元件比例的劃分結(jié)果，這樣的結(jié)果顯然不適合用于電路劃分。

但是，本文主要研究中小規(guī)模電路布局，因而雖然Stoer-Wagner算法時間復(fù)雜度較高，但仍能在較短時間內(nèi)獲得結(jié)果。因此，本文對Stoer-Wagner算法進(jìn)行修改使其能用于獲得高質(zhì)量的初始劃分。為了兼顧平衡約束和割值最小，對算法進(jìn)行如下修改：在每次選取與原點關(guān)聯(lián)最多的節(jié)點并入原點時，若并入后滿足平衡條件，則記錄下此時原點中包含的節(jié)點以及原點不包含的節(jié)點作為劃分結(jié)果。在算法運行結(jié)束時并不直接選擇割值最小的劃分，而是在記錄的割值與劃分結(jié)果中選擇割值最小的劃分作為初始劃分。

3.3 使用Fiduccia-Mattheyses算法優(yōu)化初始劃分

Fiduccia-Mattheyses算法的主要思想是：首先將圖隨機二等分，每次從2部分中選擇1個節(jié)點劃分到另一部分來最大程度地減小二劃分的割值，重復(fù)此過程直至劃分結(jié)果優(yōu)于某一限度并且滿足平衡條件。這里的平衡條件按式(1)計算：

n/2·(1-p)

(1)

其中,p為根據(jù)需求自定義的平衡參數(shù)，根據(jù)對運行效果和運行速度的需求進(jìn)行調(diào)整。評價當(dāng)前劃分的優(yōu)度時既考慮使割值較小，又要保證劃分出的2部分元件數(shù)量之差小于某一范圍。

Fiduccia-Mattheyses算法能在O(n2)的時間復(fù)雜度和O(n)的空間復(fù)雜度內(nèi)對初始劃分進(jìn)行有效優(yōu)化，優(yōu)化結(jié)果見第5節(jié)。

3.4 二元相對移動算法

本文使用Fiduccia-Mattheyses算法和Stoer-Wagner算法將全部元件劃分為一棵二叉劃分樹，提出了一種二元相對移動算法對劃分樹進(jìn)行布局。

二元相對移動算法是在網(wǎng)格上布局元件并搜尋最優(yōu)布局的算法，因此首先需對元件進(jìn)行網(wǎng)格化建模，暫時忽略元件的電路表示形式，用數(shù)個網(wǎng)格構(gòu)成的長方形代表元件。

在介紹算法的詳細(xì)步驟之前先給出優(yōu)度值的計算公式如式(2)所示：

gdegree=α·cd+(1-α)·pl/maxl

(2)

其中，α是根據(jù)具體算法對布線長度和布線擁擠度的相對側(cè)重程度確定的參數(shù)；cd為空間擁擠程度，是區(qū)域section(A,B)內(nèi)被占用方格占全部方格的比重，區(qū)域section(A,B)是由A、B的8個頂點中位于最左上的頂點與最右下的頂點分別沿橫向和縱向做延伸線所圍成的區(qū)域，如圖3所示；maxl表示元件間布線長度的最大值；pl為元件之間布線長度的估計值，此處用元件中心坐標(biāo)間的曼哈頓距離表示，如式(3)所示：

pl=|(Asx+Aex)/2-(Bsx+Bex)/2|+

|(Asy+Aey)/2-(Bsy+Bey)/2|

(3)

Figure 3 Moving process of binary moving algorithm圖3 二元移動算法的移動過程

布局時先使用Stoer-Wagner算法和Fiduccia-Mattheyses算法組合成的劃分算法對全部元件進(jìn)行遞歸劃分：先將元件劃分為2個割值較小且相對平衡的部分，再對割出的2個部分運行此劃分算法，重復(fù)此操作直至所有的元件均處于相互孤立的葉節(jié)點中，同時構(gòu)建出一棵二叉劃分樹，如圖4所示。

Figure 4 Partition tree圖4 劃分樹

從二叉劃分樹的葉節(jié)點開始對任意2個兄弟葉節(jié)點的元件測試在不同相對位置下排布的優(yōu)度，找出優(yōu)度值最大的排布方式，按照此排布確定2個元件的相對位置，組合成一個新的元件返回給父節(jié)點作為父節(jié)點的元件，再對父節(jié)點及其兄弟節(jié)點重復(fù)上述操作直至返回根節(jié)點，則獲得全部元件的整體布局情況。

二元相對移動算法存在一些不足，在運行二元相對移動算法時會導(dǎo)致布局空間的浪費，因為環(huán)繞排布的方式會導(dǎo)致元件間有空隙，因此本文在此基礎(chǔ)上對布局空間進(jìn)行自頂向下的規(guī)劃，從根節(jié)點開始對左右子樹根據(jù)其中的元件數(shù)和連線數(shù)設(shè)置矩形布局空間的長和寬的上限。在運行二元相對移動算法時不得越過上述界限。

此外在運行二元相對移動算法時，為了給布線留出足夠的空間，在元件外層套上一層空白層后再移動位置，如圖5所示，圖中sectionAC表示元件A及其外圍包裹的空白網(wǎng)格構(gòu)成的空間，sectionBC表示元件B及其外圍包裹的空白網(wǎng)格構(gòu)成的空間。

Figure 5 Extended A* algorithm圖5 擴(kuò)張后的A*算法

4 布線算法設(shè)計

本節(jié)設(shè)計并改進(jìn)了布線算法，在第1節(jié)布局結(jié)果的基礎(chǔ)上根據(jù)各個元件之間的聯(lián)結(jié)關(guān)系使用A*尋路算法布置線路，隨后針對A*算法的一些不足進(jìn)行了改進(jìn)。

4.1 A*尋路算法

A*算法的基本思想是在當(dāng)前搜索空間的基礎(chǔ)上選取較優(yōu)方向的網(wǎng)格加入搜索空間，而不是將所有方向的網(wǎng)格都加入搜索空間從而限制了搜索空間的膨脹，加快了搜索速度。

A*算法的基本流程是：建立一個開表和閉表，先將起點網(wǎng)格放入開表，每次從開表中選取與終點曼哈頓距離值f最小的網(wǎng)格放入閉表，并將其周圍的空白網(wǎng)格放入開表，重復(fù)此操作直至選取出的網(wǎng)格為終點網(wǎng)格為止，此時則搜索到了一條起點到終點的路徑。其中若即將加入開表的空白網(wǎng)格已在開表中，則比較其原本前驅(qū)網(wǎng)格與當(dāng)前選出網(wǎng)格與起點的距離，選取距離較小者作為其前驅(qū)網(wǎng)格。

4.2 A*尋路算法改進(jìn)

在面對成百上千的元件時，A*算法的時間開銷在數(shù)分鐘到數(shù)十分鐘之間，時間開銷是影響A*算法實用性的重要因素。分析4.1節(jié)A*算法的流程可知，A*算法的時間主要消耗在從開表中選出f值最小的網(wǎng)格，若使用排序算法查找最優(yōu)網(wǎng)格則每次查找的時間復(fù)雜度為O(mNum·logmNum)，其中mNum為開表中網(wǎng)格數(shù)量。這里用L表示網(wǎng)格區(qū)域的邊長，平均情況下的復(fù)雜度為O(L)，開表搜索的運行次數(shù)也為O(L)量級，則布線一次的時間復(fù)雜度平均情況下為O(L2·logL)。因此，本文改進(jìn)A*算法在選擇最優(yōu)f時不使用排序算法，而是維護(hù)一個最小堆，每次從堆頂直接取出f值最小的網(wǎng)格后再整堆，則布線一次的時間復(fù)雜度由O(L2·logL)降為O(logL)。

傳統(tǒng)A*算法的目標(biāo)在于找到最短距離，但本文的布線需求除了距離較短外還追求美觀度，而使用本網(wǎng)格到終點網(wǎng)格的曼哈頓距離來估計值，忽略了布線對布局擁擠程度的影響，因此在進(jìn)行較大規(guī)模的布線運算時，較晚布置的線路會因為較早布置的線路對可布線網(wǎng)格的占用而無法布通。因此，為了兼顧距離最短、擁擠度和美觀程度本文選擇構(gòu)造式(4)來滿足本算法的需求：

f=(μ·c+(1-μ)d)dis

(4)

其中,μ為一個小于1的參數(shù);c為本網(wǎng)格的擁擠程度，擁擠程度越大值越大，這樣就使得走線時盡量選擇擁擠度較低的方向，從而減小擁擠度，提高布通率。此處用此網(wǎng)格周圍5層網(wǎng)格中障礙網(wǎng)格的占比表示：在圖6中，淺色灰度網(wǎng)格的c值為黑色障礙網(wǎng)格數(shù)除以黑色方框區(qū)域內(nèi)的網(wǎng)格數(shù)。d為網(wǎng)格類型懲罰值，為了保證布線結(jié)果的美觀，應(yīng)盡量避免出現(xiàn)線路交叉或轉(zhuǎn)折，因此本文根據(jù)走線類型將網(wǎng)格分為3類，對3類不同的網(wǎng)格賦予不同的懲罰值，使得走線時盡量選擇懲罰值較小的網(wǎng)格，從而保證美觀程度。如圖7所示，類型1的懲罰值為0.5，類型2的懲罰值為1，類型3的懲罰值為0.3。另外走線類型是根據(jù)網(wǎng)格與父網(wǎng)格、祖先網(wǎng)格的相對關(guān)系以及布線次數(shù)確定的：對于類型1的網(wǎng)格，本網(wǎng)格與父網(wǎng)格的父網(wǎng)格的橫縱坐標(biāo)都不相同；對于類型2的網(wǎng)格，是根據(jù)布線數(shù)為2這一特征確定網(wǎng)格類型的；對于類型3的網(wǎng)格，本網(wǎng)格與父網(wǎng)格的橫縱坐標(biāo)中有且僅有一對不相同。dis為本網(wǎng)格與終點網(wǎng)格的曼哈頓距離。

Figure 6 Calculation of c value圖6 c值的計算

經(jīng)過上述改進(jìn)，A*算法時間復(fù)雜度降為O(L2)，布線結(jié)果更加美觀，布通率大大提升。

Figure 7 Grid types圖7 網(wǎng)格類型

5 實驗和結(jié)果分析

實驗環(huán)境為如下配置的虛擬機：單核CPU，主頻2.8 GHz，內(nèi)存1 GB，操作系統(tǒng)為CentOS 6.4-64 bit。

本文使用C++語言實現(xiàn)并測試整個布局布線算法，包括布局階段的Fiduccia-Mattheyses算法、Stoer-Wagner算法、二元相對移動算法、模擬退火算法和布線階段A*算法的實現(xiàn)。電路信息如表3所示。

Table 3 Circuit information

5.1 布局算法測試

在表4中，括號中的數(shù)據(jù)是3.4節(jié)的改進(jìn)方法實現(xiàn)前的劃分算法和布局算法的效果，括號外的數(shù)據(jù)為改進(jìn)后的算法效果?？梢钥闯觯倪M(jìn)后的算法運行速度提升了數(shù)倍到數(shù)十倍，擁擠度降低了數(shù)倍到數(shù)十倍，節(jié)點數(shù)越多提升越大。此外布局面積大幅減小，為布線算法降低了搜索難度。由表4可以看出，布局區(qū)域形狀均勻，在保證擁擠度小于0.5的前提下布局區(qū)域較小。劃分時間與節(jié)點數(shù)呈正相關(guān)，布局時間和線路數(shù)呈正相關(guān)，對于數(shù)百節(jié)點，上千條線路的電路圖，本文使用的算法均能在0.5 s內(nèi)得出劃分和布局結(jié)果。

Table 4 Layout results

5.2 布線算法測試

由表5可以看出，4.2節(jié)的改進(jìn)方法實現(xiàn)后的布線算法相對于改進(jìn)前速度有了近百倍的提升，交叉數(shù)、轉(zhuǎn)折數(shù)、擁擠度和布線總長度大幅縮小。本文提出的改進(jìn)策略實現(xiàn)了較好的效果，在盡量保證較低擁擠度的前提下減少了布線總長度，使得布線總長度隨著線路數(shù)的增加近似保持線性增長，同時盡量減少了交叉數(shù)和轉(zhuǎn)折數(shù)，使得交叉數(shù)和轉(zhuǎn)折數(shù)大約保持在布線總長度的10%，保證了布局布線結(jié)果的美觀性。此外表5中電路的布通率均為100%。

在運行速度方面，本文算法在布線數(shù)小于500時，布線時間不超過0.5 s；布線數(shù)超過1 000時布線時間大約需要20 s～1 min，本文算法的運行速度能夠滿足數(shù)十到數(shù)百電路元件的布局布線需求。圖8展示了電路17的最終布局布線效果。

6 結(jié)束語

本文在當(dāng)前電路布局布線相關(guān)研究的基礎(chǔ)上設(shè)計并實現(xiàn)了一個布局布線方案，用于滿足大規(guī)模電路設(shè)計軟件中用戶對于中小規(guī)模模塊的快速排查錯誤的需求。在設(shè)計布局算法時本文使用Stoer-Wagner算法生成初始劃分，用Fiduccia-Mattheyses算法優(yōu)化劃分結(jié)果，提出并改進(jìn)了二元相對移動算法生成布局結(jié)果。在設(shè)計布線算法時本文在A*尋路算法的基礎(chǔ)上實現(xiàn)并優(yōu)化了布線算法。整個設(shè)計的布局布線結(jié)果較為美觀，在控制布局面積和布線總長度的前提下?lián)頂D情況較為良好，元件和線路分布較為均勻，對于規(guī)模小于數(shù)百元件、數(shù)千線路數(shù)的電路能在0.1 s～1 min內(nèi)得出結(jié)果，滿足了用戶對中等規(guī)模電路功能模塊的快速定位和排查錯誤的需求。

Table 5 Wiring results