Abstract
本文提出二種方法來解決gate array和custom cell 設計上的總體繞線問題（glob-al routing problem）。首先，我們提出一個層次式總體繞線演算法（hierarchic-al flobal routing algorithm ）來解決custom cell 設計中不可切割結構俙局（non-slicingstructure floorplan）的總體繞線問題。利用切割方塊與重新分配端點（terminals ），我們將一個不可切割結構佈局轉換成一個可切割結構佈局（sl-icing structrue floorplan ）。如此，我們可以將一個Luk 所提解決可切割結構佈局之總體繞線問題的層次式演算法直接應用而不必修改。基於此方法，我們已經成功地完成一個總體繞線系統（global router ）叫ＳＬＩＣＥＲ。此方法兼具有二者的優點：不可切割結構佈局的面積小和可切割結構佈局的計算時問少之優點。其次，我們提出另一個方法來解決custom cell 和gate array設計的總體繞線問題。此方法立基於（１）一個表示方式將繞線區域描述成一個矩陣（matrix）和（２）一個隨機技術的拔掉重繞的方法叫模擬演化（simulated evolution ）。一個總體繞線系統ＴＲＡＣＥＲ己經成功地被設計出來。ＴＲＡＣＥＲ利用一個修改過的Lee 演算法（modified Lee's algorithm），在不考慮繞線容量限制下，產生一起始的結果，此結果有可能不是可行解。依據一個類似自然演化規則，一個拔掉重繞的程序執行拔掉和重繞一些nets直到其結果是可行解為止。根據實驗，ＴＲＡＣＥＲ所產生的結果，其品質均較我們所比較的其他方法之結果要好。