基于傳導閉包圖結構的布圖算法研究.pdf

1、隨著科技的快速發(fā)展，超大規(guī)模集成電路的規(guī)模變得越來越大，其設計工作也愈加復雜。人們廣泛地使用分級設計和知識產(chǎn)權核復用技術來處理復雜的設計工作。作為物理設計的核心，布圖規(guī)劃需要確定模塊在芯片上的位置，并達到芯片面積最小和線網(wǎng)連接線長度最短等優(yōu)化目標。布圖規(guī)劃問題已被證明是 NP難題。
　　在深入研究了當前主流的布圖算法之后，本論文基于傳導閉包圖結構，在芯片面積最小和連接線長度最優(yōu)等布圖規(guī)劃的關鍵問題上展開了進一步的研究，并取得如下成

2、果：
　　1．大部分現(xiàn)有的布圖規(guī)劃算法基于模擬退火框架實現(xiàn)，在放置完所有模塊后才得到目標面積，判斷是否接受此次擾動。本文提出了一種不可二劃分且可預判面積的傳導閉包圖算法(AP-TCG)。該算法在循環(huán)框架下實現(xiàn)，能估計目標面積而無需放置所有的模塊，具有速度快，效果好，易于得到高品質(zhì)次優(yōu)解的特點。
　　2．在實際的物理設計中，有時需要將一些模塊放置在芯片邊界，以便更好地連接輸入/輸出接口。為了解決帶邊界約束條件的布圖規(guī)劃問題，本

3、文提出了一種將邊界約束的可行條件引入擾動操作的改進型AP-TCG算法。該算法能保證每次擾動后的中間結果均是可行解，而不像當前的其它算法需把非可行解轉換成可行解而付出大量額外的計算開銷。
　　3．大部分現(xiàn)有的布圖規(guī)劃算法得到左下壓縮的版圖結果。對結果中的空白區(qū)域重分配，且不改變原版圖的拓撲結構和面積，能得到連接線總長度不同的版圖。本文提出一種基于模塊移動的貪婪算法。它首先計算出各模塊唯一的移動范圍。然后，創(chuàng)建移動代價樹來表示移動和連

4、接線長度之間的關系。最終可以得到不改變拓撲結構和面積、具有更短連接線的版圖。
　　4．通過研究，我們提出一種新的模型化方法，可以將空白區(qū)域重分配優(yōu)化連接線總長度問題公式化成為一個混合型整數(shù)線性規(guī)劃問題，利用線性規(guī)劃問題解決器，得到每個模塊的最佳位置，且使連接線總長度最短。
　　5．通過反裝一些模塊，也可以在不改變原版圖的拓撲結構和面積的約束下優(yōu)化連接線長度。本文提出一種混合型的算法，同時考慮空白區(qū)域分配和模塊反裝來綜合優(yōu)化連