請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43250
標題: | 考慮障礙物之最短直徑直角史坦納樹建立 Obstacle-Avoiding Rectilinear Steiner Tree with Minimal Diameter |
作者: | Wen-Di Cheng 鄭文迪 |
指導教授: | 郭斯彥 |
關鍵字: | 繞線,系統晶片設計,繞線半徑, Steiner tree,obstacle-avoiding,diameter, |
出版年 : | 2009 |
學位: | 碩士 |
摘要: | 在現今的超大型積體電路設計中,繞線問題一直扮演著重要的角色,許多有效的演算法不斷的提出。 而主流的SoC (System on Chip) 設計中,既有的IP block、macro cells 和預先繞好的線路等,都可視為繞線問題的障礙物。二維平面包含障礙物的繞線問題在許多前人的研究下,也提出多種有效的演算法。 本論文提出一種不同於以往只考慮總線長的演算法來處理二維平面包含障礙物的繞線問題,在同步電路中,最長的路徑被視為是影響整個系統的關鍵,我們提出的演算法在於能降低繞線結果的半徑,即最長的節點到節點的路徑。 實驗結果顯示我們的演算法相對於只考慮總線長的繞線方式能夠確實的降低繞線結果的半徑。 In today’s VLSI designs, there can be many blockages in a routing region. The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has become an important problem in the physical design stage of VLSI circuits. Although this problem has attracted a lot of attentions in research and several approaches have been proposed to solve this problem effectively. But all the pervious works didn’t consider the diameter of the RSMT. Consider the critical path make the OARSMT more reasonable for time-driven circuits. In this paper, we develop an algorithm that combining Prim’s and Dijkstra’s algorithm to construct OARSMT balancing the wire length and radius for a better diameter. In our work, the experimental result shows that we do better in minimized the diameter of an OARSMT in most cases, but the wire length is close to double in worst case. For best case we can improve the diameter about 57% and average in 20.4% for those cases we truly have smaller diameter, for all cases we have improve in 14%. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43250 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 941.94 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。