標題: 閘矩陣佈局的改良演算法
作者: 林鴻裕
LIN, HONG-YU
沈文仁
SHEN, WEN-REN
電子研究所
關鍵字: 閘矩陣佈局;演算法;佈局;矩陣;排列
公開日期: 1988
摘要: 閘矩陣佈局架構是一種具有順序性及規則性的佈局方式,用於CMOS客戶型電路。閘矩 陣佈局問題的目標是排列閘的順序,使佈局所需的面積為最少,這問題已被證明是 NP-complete 問題。所以我們須採用啟發式的演算法,以得到近似解。 在本論文中,我們提出一套自動化閘矩陣佈局的系統,能在可被接受的計算時間內, 得到近似最佳化的佈局結果。 我們的系統接受電晶體層次的電路描述,經電路轉換產生n.v.g. 矩陣。接著採用 反覆改善演算法去重排閘的順序,使佈局所需的軌道數為最少。 我們的演算法分為兩個階段,階段一的主要目標是快速地降低軌道數,我們定義成本 函數等於軌道數,使用尋找鄰近區演算法,找出使軌道數降低的可能性較高的鄰近解 ,這樣可以節省大量的時間,並獲致很好的結果。 在階段二,我們定義一個新的成本函數,除了嘗試繼續降低軌道數外,並考慮水平繞 線長度最小化,及電源繞線最佳化,並獲得可行的佈局。 我們除了採用反覆改善演算法外,並使用模擬加熱後退火的方法,以便比較二者所得 的結果。 我們在SUN 工作站上,以C 語言製作了此系統。所產生的符號檔,載入SYMBAD系統, 再使用S 語用執行OED 指令,並經壓縮後,產生光罩佈局。實驗結果顯示我們的系統 具有很好的效率,與模擬加熱後退火的方法相比,我們的方法,在軌道數方面減少 1.7%,在計算時間方面減少82.6%。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT772430071
http://hdl.handle.net/11536/53941
Appears in Collections:Thesis