閘矩陣佈局的改良演算法

Abstract

閘矩陣佈局架構是一種具有順序性及規則性的佈局方式，用於CMOS客戶型電路。閘矩 陣佈局問題的目標是排列閘的順序，使佈局所需的面積為最少，這問題已被證明是 NP-complete 問題。所以我們須採用啟發式的演算法，以得到近似解。 在本論文中，我們提出一套自動化閘矩陣佈局的系統，能在可被接受的計算時間內， 得到近似最佳化的佈局結果。 我們的系統接受電晶體層次的電路描述，經電路轉換產生n．v．g． 矩陣。接著採用 反覆改善演算法去重排閘的順序，使佈局所需的軌道數為最少。 我們的演算法分為兩個階段，階段一的主要目標是快速地降低軌道數，我們定義成本 函數等於軌道數，使用尋找鄰近區演算法，找出使軌道數降低的可能性較高的鄰近解 ，這樣可以節省大量的時間，並獲致很好的結果。 在階段二，我們定義一個新的成本函數，除了嘗試繼續降低軌道數外，並考慮水平繞 線長度最小化，及電源繞線最佳化，並獲得可行的佈局。 我們除了採用反覆改善演算法外，並使用模擬加熱後退火的方法，以便比較二者所得 的結果。 我們在SUN 工作站上，以C 語言製作了此系統。所產生的符號檔，載入SYMBAD系統， 再使用S 語用執行OED 指令，並經壓縮後，產生光罩佈局。實驗結果顯示我們的系統 具有很好的效率，與模擬加熱後退火的方法相比，我們的方法，在軌道數方面減少 １．７％，在計算時間方面減少８２．６％。