(3.236.122.9) 您好!臺灣時間:2021/05/12 20:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林佑儒
研究生(外文):Lin ,Yow-Ru
論文名稱:一些通道繞線問題的研究
論文名稱(外文):The Studies of Channel Routing Problems
指導教授:謝財明謝財明引用關係
指導教授(外文):Hsieh, Tshi Ming
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1995
畢業學年度:83
語文別:中文
論文頁數:74
中文關鍵詞:繞線通道問題混合斜率模式多層繞線模式晶元外繞線雙分圖
外文關鍵詞:channelmixedmulti-layerbipartiedover-the-cell
相關次數:
  • 被引用被引用:0
  • 點閱點閱:87
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文討論了兩個通道繞線問題 (1) 混合斜率通道繞線問題 (2) 通道外
繞線問題此兩問題基本上都應用了類似的通道壓縮處理方法。 (1) 混合
斜率通道繞線問題將一通道問題的兩層解轉換成該問題的多層繞線解。首
先,我們將兩通道繞線問題解的繞線線段作一檢查,將線段轉換成鏈結串
列。由此鏈結串列結構,我們可以求出每一線段間的交越關係,然後我們
將鏈結串列間的交錯關係轉換成交越圖,也就是將線段映射成頂點,而線
段間的交錯關係映射成連接頂點的邊。第二步,我們知道兩層繞線解的交
越圖可以雙分圖(bipartied graph)來表示,雙分圖皆可三色著色和四色
著色。本論文即是根據此著色理論,對兩層繞線解的交越圖著色,也就是
層分配(layer assignment)。因此可保證兩層繞線解皆可轉換成多層繞線
解,不論原繞線解為曼哈頓繞線解或混合斜率繞線解,根據本論文的演算
法,皆可轉換成多層繞線解。第三步,轉換成多層繞線解後,我們再進一
步對其作最佳化。 (2) 通道外繞線問題首先輸入通道內繞線,然後選擇
一些繞在通道內的線段,將其繞在通道外,使得通道內的通道密度降低,
進而減少通道內的軌道數目。最後對整個繞線重整,以進一步減少層間連
接點數目。因為混合斜率模式的最佳化的問題和晶元外繞線後所要最佳化
的過程有相當的相似性,因此我們將它們合併討論,期望能得到較一般演
算法為佳的解。本論文所提的方法,可直接應用在曼哈頓模式或混合斜率
模式中。

In this thesis, two routing problems are discussed . (1) Mixed
slope channel routing problem. (2) Over the cell channel
routing problem. These two routing problems use the similar
channel compression method. (1) Mixed slope channel routing
problem To transform the two layer channel routing solutions to
multi-layer channel routing solutions, our algorithm examines
all segments of two layer channel routing solutions and
converts them into linked-lists. From linked-lists structure,
we construct the so-called bipartied crossing graph
corresponding to two layer routing solution. And then the layer-
assignment problem can be treated as a graph coloring problem.
So ,we showed that no matter how the original channel model is
in the manhattan model or a mixed-slope model, we are sure that
these channel routing solutions can be translated into multi-
layer channel routing by our proposed algorithm. (2) Over the
cell channel routing problem First we use the output of an
existence channel router proposed by [HsKa,1994]as the input of
our algorithm. Then we choose some proper segments inside the
channel, and reroute them to minimize as channel width. The
minimization of number of vias is also discussed. Extensive
experiments show that our algorithm performs very well.

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