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

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

1 引言

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

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

2 相關(guān)工作

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

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

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

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

3 布局算法設(shè)計(jì)

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

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

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

3.1 模型構(gòu)建

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

Table 1 Edge node matrix

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

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

Table 2 Adjacency matrix

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

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

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

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

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

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

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

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

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

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

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

n/2·(1-p)

(1)

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

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

3.4 二元相對(duì)移動(dòng)算法

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

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

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

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

(2)

其中，α是根據(jù)具體算法對(duì)布線長(zhǎng)度和布線擁擠度的相對(duì)側(cè)重程度確定的參數(shù)；cd為空間擁擠程度，是區(qū)域section(A,B)內(nèi)被占用方格占全部方格的比重，區(qū)域section(A,B)是由A、B的8個(gè)頂點(diǎn)中位于最左上的頂點(diǎn)與最右下的頂點(diǎn)分別沿橫向和縱向做延伸線所圍成的區(qū)域，如圖3所示；maxl表示元件間布線長(zhǎng)度的最大值；pl為元件之間布線長(zhǎng)度的估計(jì)值，此處用元件中心坐標(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 二元移動(dòng)算法的移動(dòng)過(guò)程

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

Figure 4 Partition tree圖4 劃分樹(shù)

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

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

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

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

4 布線算法設(shè)計(jì)

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

4.1 A*尋路算法

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

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

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

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

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

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

(4)

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

Figure 6 Calculation of c value圖6 c值的計(jì)算

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

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

5 實(shí)驗(yàn)和結(jié)果分析

實(shí)驗(yàn)環(huán)境為如下配置的虛擬機(jī)：?jiǎn)魏薈PU，主頻2.8 GHz，內(nèi)存1 GB，操作系統(tǒng)為CentOS 6.4-64 bit。

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

Table 3 Circuit information

5.1 布局算法測(cè)試

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

Table 4 Layout results

5.2 布線算法測(cè)試

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

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

6 結(jié)束語(yǔ)

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

Table 5 Wiring results