基于傳導(dǎo)閉包圖結(jié)構(gòu)的布圖算法研究.pdf

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

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

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

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