本論文旨在提出一個超大型積體電路多層通道繞線 (multi-layer channel routing) 演算法。所謂繞線乃是以最少空間來作電路元件音的訊號連結,以提高整顆積體電路 的密度。 一個多層的繞線問題,我們先將整個問題分成數組次問題,再分別解決每組次問題。 而分組以“相鄰節點分開”的原則,分開訊號網 (net)間的水平限制、垂直限制,使 訊號網的繞線均勻分布於每一層的空間。解決每組次問題時再以統計訊號網的位置機 率分布、控制彼此影響的因素等方法,使訊號網繞線很容易被安排位置。 垂直限制關係的循環衝突(cyclic verticai-constraint)一直是繞線問題的一項困擾 ,在本論文中我們提出一個有效的方法來解決循環衝突。我們以去除非循環路徑可以 經過的節點的方式,來檢測是否有循環衝突存在。循環衝突檢出之後,再以縱向優先 搜尋法,找出循環衝突的路徑。為去除垂直限制關係的循環衝突,我們作訊號網分割 、加入 dongleg、讓垂直限制關係趨於更簡單,同時也降低垂直限制的長度,使通道 繞線寬度可以降低。 從程式的實驗結果,證實我們的演算法確實可以用來解決任意層的通道繞線問題。另 外我們也作減短繞線長度、接點 (via)數減少,使繞線結果更好、制造成本更少。減 短繞線長度減短繞線長的方法是將水平線段位置,作適當移動。接點數減少,則是改 變水平線段、垂直線段所在層,使得同一訊號網的水平線段、垂直線段,書可能在同 一層。附加迷宮繞線 (mazerouting),使系統功能更臻完備,許多特殊情況也能有好 的解決。 本論文所提的演算法,我們以C語言在SUNwrok station上發展成MLCR程式軟 體。針對各項功能,我們都作了詳書的實驗,證實本系統確實可行。
|