(3.215.183.251) 您好!臺灣時間:2021/04/23 12:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:江炳輝
研究生(外文):Jiang, Bing-Hui
論文名稱:通過高效且有效的布林運算將多層之避障直角史坦那樹方法用來解決繞線開路問題
論文名稱(外文):Extending ML-OARSMT to Net Open Locator with Efficient and Effective Boolean Operations
指導教授:陳宏明陳宏明引用關係
指導教授(外文):Chen, Hung-Ming
口試委員:林柏宏方劭云
口試委員(外文):Lin, Po-HungFang, Shao-Yun
口試日期:2018-08-21
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電子研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2018
畢業學年度:107
語文別:英文
論文頁數:40
中文關鍵詞:繞線實體設計直角史坦納樹避障布林操作
外文關鍵詞:routingphysical designrectilinear Steiner treeobstacle-avoidanceBoolean operations
相關次數:
  • 被引用被引用:0
  • 點閱點閱:70
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:2
  • 收藏至我的研究室書目清單書目收藏:0
近年來,多層之障礙物避障直角史坦那樹 (ML-OARSMT) 問題得到了廣泛的研究。在這項工作中,我們考慮多層之障礙物避障直角史坦那樹問題的變體,並將適用性擴展到開放網路定位器。由於工程變更命令 (ECO) 或路由器的限制可能導致開放網路,我們提出了一個框架來檢測和重新連接現有網路來解決開放網路問題。與先前基於連接圖的方法不同,我們提出一個藉由應用高效的布林運算技術來修復開放網路。我們的方法具有良好的品質與可擴展性,並且是可高度平行化。與 ICCAD2017 競賽的結果相比,我們表明我們提出的演算法與前三名優勝者相比,可以達到最低的成本,並且平均有 4.81 倍的加速。
Multi-layer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem has been extensively studied in recent years. In this work, we consider a variant of ML- OARSMT problem and extend the applicability to the net open location finder. Since ECO or router limitations may cause the open nets, we come up with a framework to detect and reconnect existing nets to resolve the net opens. Different from prior connection graph based approach, we propose a technique by applying efficient Boolean operations to repair net opens. Our method has good quality and scalability and is highly parallelizable. Compared with the results of ICCAD-2017 contest, we show that our proposed algorithm can achieve the smallest cost with 4.81 speedup in average than the top-3 winners.
Contents
Abstract (Traditional Chinese) ii
Abstract iii
Acknowledgement iv
Contents vi
List of Tables viii
List of Figures ix
List of Symbols xi

Chapter 1 Introduction 1
1.1 Previous Works in OARSMT and ML-OARSMT Problem 3
1.1.1 Maze Routing Based Approach 3
1.1.2 Non-deterministic Approach 4
1.1.3 Construction-by-Correction Approach 4
1.1.4 Connection Graph Based Approach 5
1.2 Contribution 7
1.3 Organization 7

Chapter 2 Problem Formulation 8
2.1 Terminologies 8
2.2 Problem Formulation and Objective 9
2.2.1 Evaluation Methodology 10

Chapter 3 Algorithms 11
3.1 Framework Overview 11
3.2 Initial polygons and spatial index construction 13
3.3 Routing Based on Boolean Operations: Overview 15
3.4 First Boolean Stage 16
3.4.1 Op. 1 - The intersection of shapes on adjacent layers 16
3.4.2 Op. 2 - The self-grow intersection of shapes on the same layer 18
3.4.3 Real path selection in first stage 20
3.5 Second Boolean Stage 21
3.5.1 Op. 3 - The intersection of components extension across layers 21
3.5.2 Op. 4 - The intersection of shapes on enumerative non-adjacent multiple layers 24
3.5.3 Real path selection in second stage 24
3.6 Path Finding Based on Spatial Index 25

Chapter 4 Experimental Results 28
Chapter 5 Conclusion 37
References 38
[1] K. S. Hu, M. J. Yang, Y. H. Huang, B. Y. Wong, and C. Shen, “ICCAD-2017 CAD contest in net open location finder with obstacles: Invited paper,” in 2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Nov 2017, pp. 863–866.
[2] 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 Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 4, pp. 643–653, Apr. 2008.
[3] C. H. Liu, C. X. Lin, I. C. Chen, D. T. Lee, and T. C. Wang, “Efficient multilayer obstacle-avoiding rectilinear steiner tree construction based on geometric reduction,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 12, pp. 1928–1941, Dec. 2014.
[4] C. H. Liu, S. Y. Kuo, D. T. Lee, C. S. Lin, J. H. Weng, and S. Y. Yuan, “Obstacle- avoiding rectilinear steiner tree construction: A steiner-point-based algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 7, pp. 1050–1060, Jul. 2012.
[5] M. R. Garey and D. S. Johnson, “The rectilinear steiner tree problem is NP-complete,” SIAM Journal on Applied Mathematics, vol. 32, no. 4, pp. 826–834, 1977. [Online]. Available: https://doi.org/10.1137/0132071
[6] C. Y. Lee, “An algorithm for path connections and its applications,” IRE Transac- tions on Electronic Computers, vol. EC-10, no. 3, pp. 346–365, Sept. 1961.
[7] S.-Q. Zheng, J. S. Lim, and S. S. Iyengar, “Finding obstacle-avoiding shortest paths using implicit connection graphs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 1, pp. 103–110, 1996.
[8] L. Li and E. F. Y. Young, “Obstacle-avoiding rectilinear steiner tree construction,” in 2008 IEEE/ACM International Conference on Computer-Aided Design, Nov. 2008, pp. 523–528.
[9] W.-K. Chow, L. Li, E. F. Young, and C.-W. Sham, “Obstacle-avoiding rectilinear steiner tree construction in sequential and parallel approach,” Integration, the VLSI Journal, vol. 47, no. 1, pp. 105 – 114, 2014. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0167926013000424
[10] Y. Hu, T. Jing, X. Hong, Z. Feng, X. Hu, and G. Yan, “An-oarsman: Obstacle- avoiding routing tree construction with good length performance,” in Proceedings of the 2005 Asia and South Pacific Design Automation Conference. ACM, 2005, pp. 7–12.
[11] C.-W. Lin, S.-Y. Chen, C.-F. Li, Y.-W. Chang, and C.-L. Yang, “Efficient obstacle- avoiding rectilinear steiner tree construction,” in Proceedings of the 2007 international symposium on Physical design. ACM, 2007, pp. 127–134.
[12] Z. Feng, Y. Hu, T. Jing, X. Hong, X. Hu, and G. Yan, “An o (n log n) algorithm for obstacle-avoiding routing tree construction in the λ-geometry plane,” in Proceedings of the 2006 international symposium on Physical design. ACM, 2006, pp. 48–55.
[13] 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 Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 11, pp. 2007–2016, Nov. 2008.
[14] M. d. Berg, O. Cheong, M. v. Kreveld, and M. Overmars, Computational Geome- try: Algorithms and Applications, 3rd ed. Santa Clara, CA, USA: Springer-Verlag TELOS, 2008.
[15] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, 3rd ed. The MIT Press, 2009.
[16] L. J. Simonson, “Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD,” Computer-Aided Design, vol. 42, no. 12, pp. 1189 – 1196, 2010. [Online]. Available: http://www.sciencedirect.com/science/article/pii/ S0010448510001478
[17] E. Fogel, O. Setter, R. Wein, G. Zucker, B. Zukerman, and D. Halperin, “2D regularized boolean set-operations,” in CGAL User and Reference Manual, 4.11.1 ed. CGAL Editorial Board, 2018. [Online]. Available: http://doc.cgal.org/4. 11.1/Manual/packages.html#PkgBooleanSetOperations2Summary
[18] C. Shen and K.-S. Hu, “ICCAD 2017 Contest Net Open Location Finder with Ob- stacles,” http://cad-contest-2017.el.cycu.edu.tw/Problem_B/default.html.
[19] R. Brinkmann, The Art and Science of Digital Compositing: Techniques for Visual Effects, Animation and Motion Graphics, 2nd ed. Morgan Kaufmann Publishers Inc., 2008.
[20] A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in ACM International Conference On Management of Data, 1984, pp. 47–57.
[21] M. Hanan, “On steiner’s problem with rectilinear distance,” SIAM Journal on Applied Mathematics, vol. 14, no. 2, pp. 255–265, 1966. [Online]. Available: https://doi.org/10.1137/0114025
[22] R.-Y. Wang, C.-C. Pai, J.-J. Wang, H.-T. Wen, Y.-C. Pai, Y.-W. Chang, J. C. M. Li, and J.-H. R. Jiang, “Efficient multi-layer obstacle-avoiding region-to-region rectilinear steiner tree construction,” in Proceedings of the 55th Annual Design Automation Conference, 2018, pp. 45:1–45:6. [Online]. Available: http://doi.acm.org/10.1145/3195970.3196040
[23] G.-Q. Fang, Y. Zhong, Y.-H. Cheng, and S.-Y. Fang, “Obstacle-avoiding open-net connector with precise shortest distance estimation,” in Proceedings of the 55th Annual Design Automation Conference, 2018, pp. 46:1–46:6. [Online]. Available: http://doi.acm.org/10.1145/3195970.3196081
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔