跳到主要內容

臺灣博碩士論文加值系統

(44.210.149.205) 您好!臺灣時間:2024/04/12 22:32
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:余彥廷
研究生(外文):Yu, Yen-Ting
論文名稱:系統晶片及奈米技術下直角史坦那樹之建構
論文名稱(外文):Unification of rectilinear steiner tree construction for SoC and nanometer technologies
指導教授:江蕙如江蕙如引用關係
指導教授(外文):Jiang, Hui-Ru
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電子工程系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:39
中文關鍵詞:直角史坦那樹特定繞線方向
外文關鍵詞:rectilineear stenier treepreferred direction
相關次數:
  • 被引用被引用:0
  • 點閱點閱:191
  • 評分評分:
  • 下載下載:15
  • 收藏至我的研究室書目清單書目收藏:0
直角史坦那最小樹是實體設計上的一個必要問題,此外,在製程上有不同的限制,包括障礙物的避開、多層繞線、特定層的繞線方向,在系統晶片及奈米技術下的直角史坦那最小樹的建構上是不能被忽略的。這篇論文首先統合單層及多層避開障礙物的直角史坦那最小樹的建立,之後將其延伸到考慮特定繞線方向以及時間驅動的直角史坦那最小樹。這些延伸說明了我們的演算法可以很容易的適用到這些結構上,實驗結果也顯示我們的演算法超越文獻中的最佳結果。
The rectilinear Steiner minimal tree (RSMT) problem is essential in physical design. Moreover, the variant constraints for fabrication issues, including obstacle avoidance, multiple routing layers, layer-specific routing directions, cannot be ignored during RSMT construction for modern SoC and nanometer technologies. This thesis unifies single- and multi-layer obstacle-avoiding RSMT construction first and then extends it to consider preferred routing directions and to target timing-driven RSMT. These extensions demonstrate that our algorithm can easily be adapted to configurations. Experimental results show that our algorithm is promising and outperforms the state-of-the-art works.
Abstract(Chinese) i
Abstract ii
Acknowledgements iii
List of Tables v
List of Figures vi
Chapter 1 INTRODUCTION 1
Chapter 2 PROBLEM FORMULATION AND ALGORITHM 8
A. Delaunay Triangulation of Pins 10
B. Obstacle-Weighted MST on DT 12
C. Rectilinearization and 3D U-Shaped Pattern Refinement 15
D. Time Complexity Analysis 19
Chapter 3 EXTENSIONS 22
A. Preferred Directions 22
B. Global Routing 25
Chapter 4 EXPERIMENTAL RESULTS 26
A. SL-OARSMT 27
B. ML-OARSMT 27
C. OAPDST 29
Chapter 5 CONCLUSION 35
REFERENCES 36
APPENDIX 38
Timing-Driven Steiner Trees 38
[1] The International Technology Roadmap for Semiconductors (ITRS), 2007. Available: http://www.itrs.net/
[2] M. R. Garey and D. S. Johnson, “The rectilinear Steiner tree problem is NP-complete,” SIAM J. Appl. Math., vol. 32, no. 4, pp. 826-834, 1977.
[3] J. L. Ganley and J. P. Cohoon, “Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles,” in Proc. IEEE Int. Symp. on Circuits and Systems (ISCAS’94), vol. 1, May 1994, pp.113-116.
[4] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications, 3rd ed., Springer-Verlag, 2008.
[5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001.
[6] Z. Feng, Y. Hu, T. Jing, X. Hong, X. Hu, and G. Yan, “An O(nlogn) algorithm for obstacle-avoiding routing tree construction in the lambda geometry plane,” in Proc. ACM Int. Symp. on Physical Design (ISPD’06), Apr. 2006, pp. 48-55.
[7] Z. Shen, C. C. N. Chu, and Y.-M. Li, “Efficient rectilinear Steiner tree construction with rectilinear blockages,” in Proc. IEEE Int. Conf. on Computer Design (ICCD’05), Oct. 2005, pp. 38-44.
[8] P.-C. Wu, J.-R. Gao, and T.-C. Wang, “A fast and stable algorithm for obstacle-avoiding rectilinear Steiner minimal tree construction,” in Proc. ACM/IEEE Asia and South Pacific Design Automation Conf. (ASP-DAC’07), Jan. 2007, pp. 262-267.
[9] C.-W. Lin, S.-Y. Chen, C.-F. Li, Y.-W. Chang, and C.-L. Yang, “Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs,” IEEE Trans. Computer-Aided Design, vol. 27, no. 4, pp.643-653, Apr. 2008. Also see Proc. ACM Int. Symp. on Physical Design (ISPD’07), pp.127-134.
[10] J. Long, H. Zhou, and S. O. Memik, “An O(nlogn) edge-based algorithm for obstacle-avoiding rectilinear Steiner tree construction,” in Proc. ACM Int. Symp. on Physical Design (ISPD’08), Apr. 2008, pp. 126-133
[11] C.-W. Lin, S.-L. Huang, K.-C. Hsu, M.-X. Lee, and Y.-W. Chang, “Multilayer obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs,” IEEE Trans. Computer-Aided Design, vol. 27, no.11, pp. 2007-2016, Nov. 2008. Also see Proc. IEEE/ACM Int. Conf. on Computer-aided Design (ICCAD’07), pp.380-385.
[12] M. C. Yildiz and P. H. Madden, “Preferred direction Steiner trees,” IEEE Trans. Computer-Aided Design, vol. 21, no. 11, pp. 1368-1372, Nov.2002.
[13] C.-H. Liu, Y.-H. Chou, S.-Y. Yuan, and S.-Y. Kuo, “Efficient multilayer routing based on obstacle-avoiding preferred direction Steiner tree,” in Proc. ACM Int. Symp. on Physical Design (ISPD’08), Apr. 2008, pp.118-125.
[14] I. H.-R. Jiang, S.-W. Lin, and Y.-T. Yu, “Unification of obstacle-avoiding rectilinear Steiner tree construction,” in Proc. IEEE Int. SOC Conf. (SOCC’08), Sep. 2008.
[15] I. H.-R. Jiang and Y.-T. Yu, “Configurable rectilinear Steiner tree construction for SoC and nano technologies,” in Proc. IEEE Int. Conf. on Computer Design (ICCD’08), Oct. 2008, pp. 34-39.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top