(54.236.58.220) 您好!臺灣時間:2021/02/28 23:30
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李毅郎
研究生(外文):LI,YI-LANG
論文名稱:切割繞線法
論文名稱(外文):A greedy zone router
指導教授:許有進
指導教授(外文):XU,YOU-JIN
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1990
畢業學年度:78
語文別:中文
論文頁數:37
中文關鍵詞:繞線法切割線垂直限制圖有向圖繞線
外文關鍵詞:(CUT-LINE-VERTICAL-CONSTRAINT-(DIGRAPH)
相關次數:
  • 被引用被引用:0
  • 點閱點閱:111
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本篇論文探討了一個新的繞線演算法,可以用來解決非常大的Channel 繞線問題。它
包括了三個步驟:(1) 區域繞線;(2) 區域的重新切割;(3) 繞線後最佳化處理。
在區域繞線中,我們首先將一個大的channel 繞線區域由左至右的切割,直到每一個
子區域的大小都在SILK的繞線能力範圍之內。每一次的切割位置,均選擇局部密度 (
local density)較小的地方,如此可使得每一個子區域的可繞度較高。
在切割完成後,我們根據三個因素來估計每一個子區域的可繞度,然後選出可繞度最
低的子區域;在完成此子區域的繞線後,再以此子區域為基底,往左右兩邊擴展繞線
,直到整個 channel的繞線完成為止。
在完成每個子區域的繞線之前,必須固定每一個子區域左右兩邊上 net的位置。首先
必須決定這些net 在左右邊界的上下順序關係,我們建立一個切割線垂直限制圖(Cut
Line Vertical Constraint Graph) ,然後用演算法將此有向圖(digraph) 變成沒有
圓(cycle) 的有向圖,以得到他們上下順序的關係;接著我們用整數線性規劃來決定
這些net 的確實位置。
在區域的重新切割步驟裡,其目的是要改進在區域繞線中,一些沒有分配好位置的n-
et的繞線。作法是針對每個子區域,選擇其中間的一行當作新的切割線,然後再對每
個新形成的子區域,用SILK作繞線處理。
最後,我們在繞線後最佳化處理中,整體地改進一些繞線品質不好的 net。我們一次
拔掉一個 net,然後再重新繞線,在所有的 net都處理過後,若結果有整體地改進,
則一直重覆此步驟,直到結果無法再改進為止。
實驗結果證實,成功地用19個軌道(track) 繞出Deutsch difficult example ,而且
繞線品質也都優於大部份已發表過的論文。

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔