二維矩形Packing問題和大規(guī)模集成電路布圖規(guī)劃問題的算法研究.pdf

1、NP難問題是一大類問題，其解空間隨著數(shù)據(jù)規(guī)模的增加呈指數(shù)型增長，不存在多項式時間復(fù)雜度的精確求解算法，除非P=NP。設(shè)計可在有效時間內(nèi)給出NP難問題的高質(zhì)量解的啟發(fā)式算法或近似算法，是現(xiàn)代計算機科學(xué)界的一個核心問題。二維矩形Packing問題是一種典型的NP難問題，對它的啟發(fā)式算法的研究，可以為其它NP難問題的求解提供參考，有深刻的理論意義。作為二維矩形Packing問題在工業(yè)應(yīng)用中的一個擴展問題，布圖規(guī)劃是大規(guī)模集成電路設(shè)計中的一個核

2、心步驟，其算法研究將有力推動集成電路產(chǎn)業(yè)的發(fā)展。
　　本文有機地結(jié)合了二維矩形Packing問題的研究和布圖規(guī)劃問題的研究，對三類二維矩形Packing問題和兩類布圖規(guī)劃問題，設(shè)計了高效率的啟發(fā)式求解算法。主要工作包括：
　?。?）對于二維矩形Packing中的背包問題和面積最小化問題，分別設(shè)計了最小損害度算法（LIF）和動態(tài)規(guī)約算法（DRA）。對于背包問題，提出了衡量矩形塊放置動作對后續(xù)矩形塊放置影響程度的標(biāo)準(zhǔn)——損害度，

3、并基于此標(biāo)準(zhǔn)設(shè)計了貪心構(gòu)造算法LIF，迭代執(zhí)行損害度最小的矩形塊放置動作以構(gòu)造布圖。不同于背包問題，面積最小化問題要求在面積最小的矩形框內(nèi)放入所有矩形塊。通過動態(tài)地構(gòu)造一組矩形框，DRA將求解一個面積最小化問題轉(zhuǎn)化為求解一組背包問題，并用LIF計算對應(yīng)的背包問題。使用了15個面積最小化問題的代表性算例對DRA進行了測試，DRA改進了8個算例的當(dāng)前最優(yōu)解，另有3個算例與當(dāng)前最優(yōu)解持平。
　　（2）對于二維軟矩形Packing問題和固

4、定邊界的軟模塊布圖規(guī)劃問題，分別設(shè)計了迭代糅合Packing算法（IMP）和基于迭代糅合的層次劃分算法（IMP-HP）。IMP是用以處理矩形框上無閑置空間的問題的原創(chuàng)算法。首先，類似于哈弗曼樹的構(gòu)造過程，IMP迭代地將面積最小的兩個矩形塊糅合成組合矩形塊，直至所有矩形塊均被糅合在一起。之后，遞歸地根據(jù)每個組合矩形塊的位置和形狀，確定兩個子矩形塊的位置和形狀。證明了IMP可得可行布圖（所有矩形塊均被合法放置的布圖）的一組充分條件，相比于同

5、類算法Zero-Dead-Space（ZDS）可得可行布圖的充分條件，該組充分條件更加寬松?；谔岢龅拈e置空間動態(tài)分配策略，進一步擴展了IMP，使其可處理矩形框上有閑置空間的問題。IMP-HP采用了層次劃分的算法框架，首先利用超圖分割算法hMetis層次地將原問題劃分成一組子問題，然后用IMP計算子問題得到原問題的布圖。將電路板高寬比為1的18個IBM-HB算例中的硬模塊松弛為軟模塊，得到18個IBM-SHB算例，并與兩個代表性算法PA

6、TOMA和DeFer進行了比較。實驗結(jié)果表明，IMP-HP的平均連線長度優(yōu)于PATOMA和DeFer，分別減小了4.1％和4.0%，并在其中10個算例上找到了更好的解。
　?。?）對于固定邊界的混合模塊布圖規(guī)劃問題，設(shè)計了基于擬牛頓法的布圖規(guī)劃算法（QNF）。QNF包含三個子算法：粗略放置算法、局部優(yōu)化算法和精細(xì)放置算法。粗略放置算法利用hMetis遞歸地劃分問題，直至所有子問題都只包含一個模塊，然后將模塊放置到相應(yīng)的子電路板上，

7、其目標(biāo)是得到一個模塊均勻放置、連線長度較短的布圖，但模塊間允許有重疊。局部優(yōu)化算法設(shè)計了彈性勢能函數(shù)，以評估布圖中模塊間重疊的面積和模塊超出電路板的幅度，并用擬牛頓法L-BFGS-B優(yōu)化彈性勢能函數(shù)，其目標(biāo)是通過局部微調(diào)模塊的位置和形狀，設(shè)法將粗略放置算法所得布圖轉(zhuǎn)化為合法布圖。若以上合法化失敗，則調(diào)用提出的精細(xì)放置算法重新生成模塊放置更加均勻的布圖，并用局部優(yōu)化算法將其合法化。精細(xì)放置算法先將尺寸超大的模塊無重疊地固定在電路板上，然后