VLSI布圖規(guī)劃-布局若干算法研究.pdf

1、布圖規(guī)劃是超大規(guī)模集成電路(Very Large Scale Integrated circuit，VLSI)物理設(shè)計中一個重要的階段。它主要是規(guī)劃模塊在芯片上的形狀和位置。隨著集成電路設(shè)計的發(fā)展，越來越多的問題需要被考慮，特別是操作頻率的逐漸增加和芯片的更高的集成度，使得芯片上的面積、延遲、溫度等成為集成電路設(shè)計中嚴(yán)重的問題。
　　 本文對大規(guī)模集成電路物理設(shè)計中的布圖/布局算法進行了研究，包括模擬退火算法，禁忌搜索等方法，并

2、對布圖中的一些目標(biāo)，如：面積、線長、擁塞等進行了考慮，提出了一些解決方法。論文的主要貢獻(xiàn)如下：
　　 在模擬退火算法和禁忌搜索的基礎(chǔ)上提出了一種混合算法用于在有限的解空間中搜索最優(yōu)解，利用模擬退火來產(chǎn)生鄰域解，同時利用B*-tree表示法來表示布圖，以B*-tree的前序和中序序列作為禁忌對象。實驗結(jié)果表明我們的方法能夠在更短的時間內(nèi)獲得較高的面積的利用率。
　　 在處理多目標(biāo)最優(yōu)化問題時，用傳統(tǒng)的線性加權(quán)函數(shù)方法平衡不

3、同的目標(biāo)很困難。為了克服這個問題，模糊準(zhǔn)則和隸屬函數(shù)被引入用來結(jié)合不同的目標(biāo)。它是一個很方便的方法用于結(jié)合沖突的目標(biāo)并且能夠利用專家知識。實驗結(jié)果表明，這個方法穩(wěn)定有效，能在更短的時間內(nèi)得到令人滿意的解。通過實驗結(jié)果，我們能夠?qū)?shù)設(shè)置的變化有一個直觀的理解。這個方法也能夠被延伸去解決其它大規(guī)模多目標(biāo)最優(yōu)化問題。
　　 為了避免耗時的拆線重布，提出了一個新的二階段布圖規(guī)劃方法用于擁塞最優(yōu)化。我們采用了概率估計模型去評估線網(wǎng)的擁塞