芯片布局問題的求解算法研究

管瑤

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

關鍵詞：布圖規劃；中心生長法；模擬拼圖法

中圖分類號：TN401 文獻標識碼：A 文章編號：1007-9416（2018）09-0098-01

1 初始布局

對于布局問題而言，如果參與布局的所有模塊的尺寸都相同，憑直覺就可以容易地得到最優的布局。例如，對于49個尺寸相同的模塊來說，很容易就知道，如果按照7×7的方式來碼放就可以得到最佳布局。從這一想法出發，初始布局應為近似2*2，3*3，4*4等中心對稱圖形為佳。所以我們想到第一種初始布局安置策略，中心生長法。

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

我們在實驗該算法時，發現采用中心生長法構造初始布局時，我們并未考慮芯片與其它芯片間的要求，只是盲目的進行安置。例如一個案例：有4個正方形單元，邊長為2。若采用中心生長法，我們能得到的最好布局連線長度為2，實際上最優布局連線長度為0。

因此，中心生長法在安置過程中，并沒有考慮待安置單元與已安置單元的關系，每次安置都是機械與盲目的。而且很多的最優解并不是像直覺那樣為近似2*2，3*3，4*4等中心對稱圖[2]。介此，我們又提出了如下想法：模擬拼圖法。

2 模擬拼圖法

我們都玩過拼圖游戲，在整個研究過程中，集成電路布局問題感覺就象硅片上的拼圖游戲一樣，拼出最完美的那副圖。回憶一下在玩拼圖游戲時，我們人是怎么做的。我們首先隨機選擇一塊圖形碎片為基礎，然后在剩下眾多碎片中選取與該碎片圖形相吻合的拼接在一起成為新的基礎群，接著繼續在剩下碎片中選取與基礎圖形相吻合的拼接在一起成為新的基礎群，如此反復，直到難以找到相吻合的碎片為止。這時，我們會重新在剩下碎片中選取一個作為基礎，按如上方法拼成基礎群。當我們把所有碎片拼成基礎群后，我們再把基礎群拼在一起，成為完美的圖片。在安置時，模擬拼圖法充分考慮到了待安置單位與已安置單元的關系，并且采用結群的方式[3]。

3 改善布局

改善布局是整個布局過程中十分重要的一個環節，其迭代思想是，選中一種特定的布局方式，按照一定的辦法來改變其位置和單元，通過對比改變前后的布局效率來決定是否要采用新的布局方式。如果改變后的布局方式更為優秀，則更新布局算法。采用這個辦法一直迭代，知道無法找到更優的算法為止[4-5]。

3.1 成對交換法

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

公式（5）即可作為力矢量力矢量成對交換松弛法的目標函數。其算法步驟如下：

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

參考文獻

[1]董社勤，洪先龍.基于矩形宏模塊的片上系統布圖規劃算法[J].清華大學學報（自然科學版），2003，（4）：484-486.

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

[3]洪先龍，嚴曉浪，喬長閣.超大規模集成電路布圖理論與算法[M].科學出版社，1998.

[4]薄建國，俞明永，尹錦柏，等.具有多目標形狀選擇的布局方法[J].電子學報，1992，（2）：1-9.

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