新型電路版圖布局布線算法設計

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

(1.南開大學計算機學院，天津 300350；2.天津市網絡與數據安全重點實驗室(南開大學)，天津 300350)

1 引言

發達國家在集成電路領域的高新技術成果方面始終對我國形成封鎖。近年來，集成電路自動化設計技術高速發展，為了推動我國邁入該領域發展的快車道，越來越多的學者開始研究電路自動化設計的相關技術。

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

2 相關工作

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

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

電路布線技術多是在A*尋路算法[8]的基礎上進行設計，該算法能夠在網格化空間內有效尋找最短路徑，缺點是運行速度慢。

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

3 布局算法設計

本文設計的布局布線算法面向中小規模電路，試圖實現對元件的布局布線，區別于傳統的物理設計，本文設計的算法強調運行速度和布局布線結果的美觀性和邏輯性，而相對忽略布線空間的耗費。

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

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

3.1 模型構建

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

Table 1 Edge node matrix

隨后將度為2以上的超邊，即聯結了2個以上節點的超邊轉化為節點，每個超邊轉化成的節點與原超邊關聯的每一個節點都有一條度為2的超邊，這樣超圖中則不存在度為2以上的超邊，則超圖轉化為圖，如圖1所示。數據存儲在鄰接矩陣中，如表2所示，數字表示節點，表項表示節點間邊的權重。之后的布局算法在此鄰接矩陣形式的基礎上進行設計。

Figure 1 Transformation of hypergraph圖1 超圖的轉化

Table 2 Adjacency matrix

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

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

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

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

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

如圖2所示節點3號和節點4號即為s、t，最小割值為2。詳細證明見參考文獻[11]。

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

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

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

3.3 使用Fiduccia-Mattheyses算法優化初始劃分

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

n/2·(1-p)

(1)

其中,p為根據需求自定義的平衡參數，根據對運行效果和運行速度的需求進行調整。評價當前劃分的優度時既考慮使割值較小，又要保證劃分出的2部分元件數量之差小于某一范圍。

Fiduccia-Mattheyses算法能在O(n2)的時間復雜度和O(n)的空間復雜度內對初始劃分進行有效優化，優化結果見第5節。

3.4 二元相對移動算法

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

二元相對移動算法是在網格上布局元件并搜尋最優布局的算法，因此首先需對元件進行網格化建模，暫時忽略元件的電路表示形式，用數個網格構成的長方形代表元件。

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

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

(2)

其中，α是根據具體算法對布線長度和布線擁擠度的相對側重程度確定的參數；cd為空間擁擠程度，是區域section(A,B)內被占用方格占全部方格的比重，區域section(A,B)是由A、B的8個頂點中位于最左上的頂點與最右下的頂點分別沿橫向和縱向做延伸線所圍成的區域，如圖3所示；maxl表示元件間布線長度的最大值；pl為元件之間布線長度的估計值，此處用元件中心坐標間的曼哈頓距離表示，如式(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算法組合成的劃分算法對全部元件進行遞歸劃分：先將元件劃分為2個割值較小且相對平衡的部分，再對割出的2個部分運行此劃分算法，重復此操作直至所有的元件均處于相互孤立的葉節點中，同時構建出一棵二叉劃分樹，如圖4所示。

Figure 4 Partition tree圖4 劃分樹

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

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

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

Figure 5 Extended A* algorithm圖5 擴張后的A*算法

4 布線算法設計

本節設計并改進了布線算法，在第1節布局結果的基礎上根據各個元件之間的聯結關系使用A*尋路算法布置線路，隨后針對A*算法的一些不足進行了改進。

4.1 A*尋路算法

A*算法的基本思想是在當前搜索空間的基礎上選取較優方向的網格加入搜索空間，而不是將所有方向的網格都加入搜索空間從而限制了搜索空間的膨脹，加快了搜索速度。

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

4.2 A*尋路算法改進

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

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

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

(4)

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

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

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

Figure 7 Grid types圖7 網格類型

5 實驗和結果分析

實驗環境為如下配置的虛擬機：單核CPU，主頻2.8 GHz，內存1 GB，操作系統為CentOS 6.4-64 bit。

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

Table 3 Circuit information

5.1 布局算法測試

在表4中，括號中的數據是3.4節的改進方法實現前的劃分算法和布局算法的效果，括號外的數據為改進后的算法效果。可以看出，改進后的算法運行速度提升了數倍到數十倍，擁擠度降低了數倍到數十倍，節點數越多提升越大。此外布局面積大幅減小，為布線算法降低了搜索難度。由表4可以看出，布局區域形狀均勻，在保證擁擠度小于0.5的前提下布局區域較小。劃分時間與節點數呈正相關，布局時間和線路數呈正相關，對于數百節點，上千條線路的電路圖，本文使用的算法均能在0.5 s內得出劃分和布局結果。

Table 4 Layout results

5.2 布線算法測試

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

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

6 結束語

本文在當前電路布局布線相關研究的基礎上設計并實現了一個布局布線方案，用于滿足大規模電路設計軟件中用戶對于中小規模模塊的快速排查錯誤的需求。在設計布局算法時本文使用Stoer-Wagner算法生成初始劃分，用Fiduccia-Mattheyses算法優化劃分結果，提出并改進了二元相對移動算法生成布局結果。在設計布線算法時本文在A*尋路算法的基礎上實現并優化了布線算法。整個設計的布局布線結果較為美觀，在控制布局面積和布線總長度的前提下擁擠情況較為良好，元件和線路分布較為均勻，對于規模小于數百元件、數千線路數的電路能在0.1 s～1 min內得出結果，滿足了用戶對中等規模電路功能模塊的快速定位和排查錯誤的需求。

Table 5 Wiring results