|
超大型積體電路佈圖大致可分成Placement,Global繞線,Detail繞線三大
階段,而佈圖的三大階段中的Detail繞線主要又可分成通道(Channel)繞
線,Switchbox繞線等兩大類.其中通道繞線問題研究至今已有二十餘年的
歷史了.在超大型積體電路佈圖中,所佔的面積愈小,可使得成本降低並提
高產品良率.因此,盡量縮小通道的寬度,可使佈圖面積跟著縮小.繞線使用
的線段過長,將可能造成訊號的延遲,而層間連接點過多將可能造成訊號的
衰減,故用較短的線及較少的層間連接點,除了降低成本外,亦可提高線路
的性能.可見繞線問題在超大型積體電路佈圖設計過程中是個非常重要的
問題.而在通道繞線問題的領域中,混合斜率模式(Mixed Slope Model,
MSM)是個新興的繞線模式,除了水平及垂直方向外它比傳統的曼哈頓模式
(Manhattan Model,MM)多了+45度及-45度兩個繞線方向.而本論文將提出
一貪婪繞線方法(Greedy Routing Method),來求解通道繞線問題中的雙接
腳問題(Two Terminal Problem)在混合斜率模式下的通道繞線解.我們所
提出的貪婪繞線方法是以Track by Track的方式分成縱向配線 ,及橫向配
線兩部份交互進行,來完成整個通道的繞線.首先,我們輸入一組通道的接
腳配置串列(Netlist),並設定相關繞線控制參數的初始值,接著便進行各
個Track的繞線動作,直到所有的連線組皆到達其目的接腳為止,而每個繞
線軌道(Track)的繞線配置動作如下:一. 縱向配線處理 :按照各連線組目
前在通道中的對應位置計算其向位差,然後依照此向位差值建立繞線的優
先權串列,並配合通道當時各連線組之繞線狀況進行-45度,90度及+45度三
個繞線方向的配線選擇,並於繞線的過程當中動態地調整繞線優先權串列,
以使各個連線組皆有繞線方向可進行.二. 橫向配線處理 :計算於縱向配
線完成的當時各個連線組在通道中的向位差,建立繞線優先權串列,接著配
合通道當時各個連線組之繞線狀況建立水平位移配置表,並配合繞線層變
換法,來配置水平空間.實驗証明以此方式進行繞線在大部份的例子上均可
得到不錯的繞線品質,在一些典型的例子像Shift by N Channel及
Reverse by N Channel都可得到和前人最好的繞線結果相同的繞線品質.
特別在Perfect Shuffle Permutation Channel上,我們可用這類通道之最
佳解的track數來完成繞線 ,其結果優於1991年由Ravikumar[13]提出的繞
線結果.
|