基于傳導閉包圖結構的布圖算法研究.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算法。該算法能保證每次擾動后的中間結果均是可行解，而不像當前的其它算法需把非可行解轉(zhuǎn)換成可行解而付出大量額外的計算開銷。
　　3．大部分現(xiàn)有的布圖規(guī)劃算法得到左下壓縮的版圖結果。對結果中的空白區(qū)域重分配，且不改變原版圖的拓撲結構和面積，能得到連接線總長度不同的版圖。本文提出一種基于模塊移動的貪婪算法。它首先計算出各模塊唯一的移動范圍。然后，創(chuàng)建移動代價樹來表示移動和連

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