管瑤

摘要：本文基于布局問(wèn)題及其特點(diǎn)，提出了以先初始布局再改善布局的解決布局問(wèn)題的基本思想。對(duì)于初始布局，提出了中心生長(zhǎng)法和模擬拼圖法兩種算法。對(duì)于改善布局提出二類基于迭代改善的算法。

關(guān)鍵詞：布圖規(guī)劃；中心生長(zhǎng)法；模擬拼圖法

中圖分類號(hào)：TN401 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）09-0098-01

1 初始布局

對(duì)于布局問(wèn)題而言，如果參與布局的所有模塊的尺寸都相同，憑直覺(jué)就可以容易地得到最優(yōu)的布局。例如，對(duì)于49個(gè)尺寸相同的模塊來(lái)說(shuō)，很容易就知道，如果按照7×7的方式來(lái)碼放就可以得到最佳布局。從這一想法出發(fā)，初始布局應(yīng)為近似2*2，3*3，4*4等中心對(duì)稱圖形為佳。所以我們想到第一種初始布局安置策略，中心生長(zhǎng)法。

中心生長(zhǎng)法。首先將所有單元按COST排序。憑直覺(jué)，我們知道擁有連接點(diǎn)越多的單元，應(yīng)安置在越中心的位置，所以我們這里的COST可以為單元上有連接點(diǎn)的個(gè)數(shù)。然后將接點(diǎn)個(gè)數(shù)排序第一位的單元布置到在芯片的中心位置。以這些單元為中心，從未安置的單元中按照排序集中選擇單元，圍繞核心選擇合適的位置進(jìn)行布置。使用類似的原理，向芯片四周擴(kuò)展，直至把整個(gè)芯片都布局完成[1]。

我們?cè)趯?shí)驗(yàn)該算法時(shí)，發(fā)現(xiàn)采用中心生長(zhǎng)法構(gòu)造初始布局時(shí)，我們并未考慮芯片與其它芯片間的要求，只是盲目的進(jìn)行安置。例如一個(gè)案例：有4個(gè)正方形單元，邊長(zhǎng)為2。若采用中心生長(zhǎng)法，我們能得到的最好布局連線長(zhǎng)度為2，實(shí)際上最優(yōu)布局連線長(zhǎng)度為0。

因此，中心生長(zhǎng)法在安置過(guò)程中，并沒(méi)有考慮待安置單元與已安置單元的關(guān)系，每次安置都是機(jī)械與盲目的。而且很多的最優(yōu)解并不是像直覺(jué)那樣為近似2*2，3*3，4*4等中心對(duì)稱圖[2]。介此，我們又提出了如下想法：模擬拼圖法。

2 模擬拼圖法

我們都玩過(guò)拼圖游戲，在整個(gè)研究過(guò)程中，集成電路布局問(wèn)題感覺(jué)就象硅片上的拼圖游戲一樣，拼出最完美的那副圖。回憶一下在玩拼圖游戲時(shí)，我們?nèi)耸窃趺醋龅摹Ｎ覀兪紫入S機(jī)選擇一塊圖形碎片為基礎(chǔ)，然后在剩下眾多碎片中選取與該碎片圖形相吻合的拼接在一起成為新的基礎(chǔ)群，接著繼續(xù)在剩下碎片中選取與基礎(chǔ)圖形相吻合的拼接在一起成為新的基礎(chǔ)群，如此反復(fù)，直到難以找到相吻合的碎片為止。這時(shí)，我們會(huì)重新在剩下碎片中選取一個(gè)作為基礎(chǔ)，按如上方法拼成基礎(chǔ)群。當(dāng)我們把所有碎片拼成基礎(chǔ)群后，我們?cè)侔鸦A(chǔ)群拼在一起，成為完美的圖片。在安置時(shí)，模擬拼圖法充分考慮到了待安置單位與已安置單元的關(guān)系，并且采用結(jié)群的方式[3]。

3 改善布局

改善布局是整個(gè)布局過(guò)程中十分重要的一個(gè)環(huán)節(jié)，其迭代思想是，選中一種特定的布局方式，按照一定的辦法來(lái)改變其位置和單元，通過(guò)對(duì)比改變前后的布局效率來(lái)決定是否要采用新的布局方式。如果改變后的布局方式更為優(yōu)秀，則更新布局算法。采用這個(gè)辦法一直迭代，知道無(wú)法找到更優(yōu)的算法為止[4-5]。

3.1 成對(duì)交換法

成對(duì)交換法是一種最簡(jiǎn)單的交換策略。每次選定一個(gè)單元，依次與其他的單元進(jìn)行交換，看交換以后的布局是否更優(yōu)秀。若交換以后，這兩個(gè)單元相關(guān)的布線總長(zhǎng)有減少，則采用新的布局方式。整個(gè)交換枚舉次數(shù)為n（n-1）/2，與單元i相關(guān)的布局總線長(zhǎng)度可用下式表示：

公式（5）即可作為力矢量力矢量成對(duì)交換松弛法的目標(biāo)函數(shù)。其算法步驟如下：

（1）根據(jù)公式（5）計(jì)算每個(gè)模塊i的（xi，yi），即每個(gè)模塊0張力的位置；（2）選擇滿足如下條件的一對(duì)單元i，j：模塊i的0張力位置（xi，yi）剛好在模塊j處或在j附近，模塊j的0張力位置（xi，yi）剛好在模塊i處或在i附近，交換模塊i和模塊j的位置；（3）計(jì)算總張力和，如比原布局小，則接受新的布局，否則保持原布局；（4）反復(fù)執(zhí)行上述3個(gè)步驟，直到使總張力之和不能再減小為止。

參考文獻(xiàn)

[1]董社勤，洪先龍.基于矩形宏模塊的片上系統(tǒng)布圖規(guī)劃算法[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，（4）：484-486.

[2]董社勤，洪先龍，黃鋼，顧均.基于新約束圖模型的布圖規(guī)劃和布局算法[J].軟件學(xué)報(bào)，2001，（11）：1586-1594.

[3]洪先龍，嚴(yán)曉浪，喬長(zhǎng)閣.超大規(guī)模集成電路布圖理論與算法[M].科學(xué)出版社，1998.

[4]薄建國(guó)，俞明永，尹錦柏，等.具有多目標(biāo)形狀選擇的布局方法[J].電子學(xué)報(bào)，1992，（2）：1-9.

[5]俞明永，薄建國(guó)，洪先龍，等.一種有效地綜合兩種分級(jí)設(shè)計(jì)方法的BBL布局算法[J].Journal of Semiconductors，1990，（8）：609-614.