在數位積體電路的設計流程結束後，工程變更命令(Engineering Change Order)可能造成某些線路開路，如電源線或接地線。由於存在著大量的障礙物，因此解決這些開路線路是一個極具挑戰性的問題。在現有的學術研究，多層並且能迴避障礙物的直線史坦納樹(Steiner Tree)，將輸入接腳(Pin)視為固定位置的點；而此問題將這些分散的開路線路的輸入接腳視為非固定位置的直線接腳(Rectilinear Pin)，因此無法直接應用在此問題。此篇論文提出能有效率地處理非固定位置的直線接腳之線路開路連接器。我們提出的演算法流程由於能在複雜的障礙物分佈中準確地估計任兩對線路的直線最短距離，因此可以得到最小化的總線長。實驗結果顯示，在總連接線長和運行時間中，此篇論文提出的方法能夠獲得比2017 年電腦輔助設計競賽(2017 CAD Contest at ICCAD)之前三名更佳的結果。

At the end of digital integrated circuit (IC) design flow, some nets may still be left open due to engineering change order (ECO). Resolving these opens could be quite challenging for some huge nets such as power ground nets because of a large number of obstacles and greatly distributed net components. Existing studies on multilayer obstacle-avoiding rectilinear Steiner trees may not be applicable to solve this problem because they assume the pins of an input net is a set of points, while the discrete net components in this problem can be regarded as a set of rectilinear pins.
In this thesis, we develop an efficient open-net connector that can deal with rectilinear pins. The proposed algorithm flow minimizes the total connection cost based on precise estimation of the shortest distance between each pair of rectilinear net components with the presence of complex obstacles. Experimental results show that the proposed flow can outperform the top three teams of 2017 CAD Contest at ICCAD in terms of total connection cost or runtime efficiency.

[1] H.-Y. Chen, M.-F. Chiang, and Y.-W. Chang, "Novel full-chip gridless routing considering double-via insertion," In ACM/IEEE Design Automation Conference (DAC), pp. 755-760, 2006.
[2] J. Cong, J. Fang, and K.-Y. KhooAn, "Implicit connection graph maze routing algorithm for ECO routing," In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 163-167, 1999.
[3] T. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd edition, Cambridge, MIT Press, 2009.
[4] 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 Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 7-12, 2005.
[5] Y.-L. Li, J.-Y. Li, and W.-B. Chen, "An efficient tile-based ECO router using routing graph reduction and enhanced global routing flow," In IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 26, no. 2, pp. 345-358, 2007.
[6] C.-W. Lin, S.-Y. Chen, C.-F. Li, Y.-W. Chang, and C.-L. Yang, "Efficient obstacle-avoiding rectilinear Steiner tree construction," In International Symposium on Physical Design (ISPD), pp. 127-134, 2007.
[7] C.-W. Lin, S.-L. Huang, K.-C. Hsu, M.-X. Lee, and Y.-W. Chang, "Multi-layer obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs," In IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 27, no. 11, pp. 2007-2016, 2008.
[8] C.-H. Liu, C.-X. Lin, I.-C. Chen, D.-T. Lee, and T.-C, Wan, "Efficient multi-layer obstacle-avoiding rectilinear Steiner tree construction based on geometric reduction," In IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 33, no. 12, pp. 1928-1941, 2014.
[9] J. Long, H. Zhou, and S. O. Memik, "An O(n log n) edge-based algorithm for obstacle-avoiding rectilinear Steiner tree construction," In International Symposium on Physical Design (ISPD), pp. 126-133, 2008.
[10] C. Shen and K.-S. Hu, "CAD contest in net open location finder with obstacles and benchmark suite," In IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2017.
[11] P.-C. Wu, J.-R. Gao, and T.-C. Wang, "A fast and stable algorithm for obstacle-avoiding rectilinear Steiner minimal tree construction," In Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 262-267, 2007.
[12] P.-H. Wu, S.-Y. Bai, and T.-Y, Ho, "A Topology-based ECO Routing Methodology for Mask Cost Minimization," In Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 507-512, 2014.
[13] S. Q. Zheng, J. S. Lim, and S. S. Iyengar, "Finding obstacle-avoiding shortest paths using implicit connection graphs," In IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 15, no. 1, pp. 103-110, 1996.