多約束增量式布局.pdf

1、布圖是超大規(guī)模集成電路(Very Large Scale Integrated circuit，VLSI)物理設(shè)計(jì)的一個(gè)重要的階段。本文主要是針對(duì)布圖規(guī)劃需要，建立相關(guān)的增量式布局規(guī)劃工具，對(duì)前期得到的布局結(jié)果進(jìn)行校正和優(yōu)化。
　　 模擬退火(Simulated Annealing，SA)是一種廣泛應(yīng)用VLSI標(biāo)準(zhǔn)單元布局優(yōu)化的算法，該算法的不足之處是運(yùn)算時(shí)間較長(zhǎng)。本文對(duì)模擬退火算法進(jìn)行改進(jìn)，提出了一種有序擾動(dòng)模擬退火過(guò)程O(píng)PS

2、A(Ordered Perturb SA)思想，以減少其運(yùn)行時(shí)間。
　　 TCG表示法是一個(gè)基于圖的表示法。保證其可行性是一件非常復(fù)雜的工作。本文針對(duì)保持可行性，給出具體分析，并對(duì)違反可行性的例子進(jìn)行了說(shuō)明。同時(shí)給出了改進(jìn)的TCG數(shù)學(xué)描述。
　　 針對(duì)基于固定邊界約束，本文提出了一種處理固定模塊位置約束的后處理優(yōu)化算法。該算法首先通過(guò)迭代的調(diào)整TCG圖中的關(guān)鍵路徑，使不滿足固定邊界約束的布圖將會(huì)滿足該約束。同時(shí)，為處理固

3、定模塊而在TCG中增加虛擬節(jié)點(diǎn)，使得固定邊界約束和固定模塊位置約束統(tǒng)一起來(lái)。從而在為滿足固定邊界約束而進(jìn)行的后處理優(yōu)化過(guò)程中，固定模塊位置約束也會(huì)滿足。
　　 本文提出了一種基于松弛量計(jì)算的增量式優(yōu)化算法。在布局完成后，將布局轉(zhuǎn)化為T(mén)CG，根據(jù)模塊間的松弛量分配，對(duì)模塊進(jìn)行區(qū)間擴(kuò)展(enlargeRegion)操作，得到重布置/重設(shè)置大小/重設(shè)置形狀操作的結(jié)果。該算法可用于減少空白區(qū)間，線長(zhǎng)，分散熱點(diǎn)溫度：可以處理固定邊界約束，