繞線在積體晶片的實體設計中開始占一要角，尤其是當製程進步到深次微米世代，許多在之前忽略的電磁效應開始浮現。除了物理上的效應，積體晶片中線的數量亦以驚人的速度在增加，使得繞線中必須去注意壅塞度的議題。壅塞度議題相關於一顆積體晶片的繞線是否可以成功，因此，這是一個必須解決的問題。
　　為了解決壅塞度的問題，本論文從繞線中一個基本的問題，避開障礙物之直角史坦納樹的建構開始。這是因為大部分的壅塞度繞線器都將此議題視為一個有硬限制之最佳化問題，而避開障礙物之概念可以替換成避開壅塞區域，並進而達到符合壅塞度繞線中的硬限制。
　　在建構開障礙物直角史坦納樹中，本論文呈獻基於路徑之避開障礙物直角史坦納樹演算法[2]之部分實作細節，並在實作中延伸成考量複雜直角障礙物。最小生成樹演算法中，更加入了連線直角化之前瞻概念，以及一個全面考量路徑重疊的演算法去改善總線長。根據實驗結果，前瞻概念平均可得到0.11%之線長改善。除此之外，本論文也提出一個更有效之區域淬煉方法。實驗結果展現出，此淬鍊方法相對於無任何淬鍊之版本，可以達到平均2.33%的總線長改善。所有提出之改善線長的方法，皆可套用在目前科技水平最佳之演算法[2][9][22]。
　　在第三章，本論文發展了幾個關於將壅塞度模型化成複雜直角障礙物的相關理論，而這些理論是基於沒有任何一個接線點落在障礙物的假設下才成立。致於將避開障礙物直角史坦納樹中的一個障礙物，定義成複雜直角障礙物之必要性，則在應用於壅塞度驅動繞線中顯現。所發展的壅塞度障礙物模型法可以保留所有無溢位之路徑，並且可以在有新的繞線情形下，動態的去維持和形成新的障礙物。對同時繞線之問題，本論文介紹了有限容量障礙物的概念。並在結合了有限障礙物和壅塞度障礙物的概念下，對於多條二接線點之線，提出了一個連線候選產生法，此產生法可保證在候選中擁有最佳解。對於現有的同時繞線問題之整數線性規畫的公式，可將以上的概念結合，並全部套用。我們相信所提出之壅塞度障礙物模型應可在壅塞度驅動繞線啟發出全新、而且有效的作法。

Routing is becoming a critical role in physical level design of an IC, especially many previous ignored electromagnetic effects emerge as process technology advanced to deep submicron era. Except physical effect, net number of an IC grows with amazing speed which causes congestion issues. This issue is related to whether an IC can be successfully routed, and then congestion is a must solved issue in routing.
To resolve the congestion issue, this thesis starts with a fundamental topic in routing, obstacle-avoiding rectilinear Steiner tree construction. This is since congestion-driven routers typically treat the issue as an optimization problem with hard constraints, and the concept of obstacle-avoiding can be replaced by congestion-avoiding to fit the hard constraints.
In obstacle-avoiding rectilinear Steiner tree construction, this thesis presents part of the implementation details of the path-based obstacle-avoiding rectilinear Steiner tree algorithm [2] and extends with complex rectilinear obstacle in implementation. The minimum spanning tree algorithm adds a rectilinear edge look-ahead concept, which results in 0.11% improvement in average, and a comprehensive path-overlapping algorithm to increase the effectiveness. Furthermore, a more effective local refinement method is also proposed with 2.33% improvements in wirelength compared to the version without local refinement stage. All proposed techniques are applicable to state of the art [2][9][22].
In Chapter 3, several theories are developed on modeling congestion information as obstacles under an assumption that no pin locates inside an obstacle, and the necessity to define an obstacle as a complex rectilinear obstacle in obstacle-avoiding Steiner tree is then disclosed in application of congestion-driven routing. Proposed obstacle modeling on congestion reserves all overflow-free paths, and modeled obstacle can be dynamically maintained and formulated with new nets routed. Concept of finite-capacity obstacle is also introduced for concurrent routing, and this thesis demonstrates a method to generate a set of candidate of multi 2-pin nets routing with optimum solution. Formulations of congestion-driven routing considers with obstacle concept is also provided for all published global routes with integer linear programming formulation for direct applications. We believe proposed modeling shall enlighten a brand new and effective way in congestion-driven routing.

[1]. Jieyi Long; Hai Zhou; Memik, S.O.; , "EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction Algorithm," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.27, no.12, pp.2169-2182, Dec. 2008.
[2]. Chih-Hung Liuf; Shih-Yi Yuan; Sy-Yen Kuo; Yao-Hsin Chou; , "An O(n log n) path-based obstacle-avoiding algorithm for rectilinear Steiner tree construction," Design Automation Conference, 2009. DAC '09. 46th ACM/IEEE , vol., no., pp.314-319, 26-31 July 2009.
[3]. Chung-Wei Lin; Szu-Yu Chen; Chi-Feng Li; Yao-Wen Chang; Chia-Lin Yang; , "Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.27, no.4, pp.643-653, April 2008.
[4]. J. S. B. Mitchell, “L1 shortest paths among polygonal obstacles in the plane,”Algorithmica, Vol. 8, pp. 55–88, 1992.
[5]. J. S. B. Mitchell, “An optimal algorithm for shortest rectilinear paths among obstacles,” in Proceedings of Canadian Conference on Computational Geometry, 1989.
[6]. B. Chazelle, “An algorithm for segment dragging and its implementation,”Algorithmica, Vol. 3, pp 205–221, 1988.
[7]. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd edition, Springer, 2000.
[8]. Yoav Giora, and Haim Kaplan, “Optimal Dynamic Vertical Ray Shooting in Rectilinear Planar Subdivision,” ACM Trans. on Algorithms, Vol. 5, Issue 3, July 2009.
[9]. Chih-Hung Liu; Shih-Yi Yuan; Sy-Yen Kuo; Jung-Hung Weng; , "Obstacle-avoiding rectilinear Steiner tree construction based on Steiner point selection," Computer-Aided Design - Digest of Technical Papers, 2009. ICCAD 2009. IEEE/ACM International Conference on , vol., no., pp.26-32, 2-5 Nov. 2009.
[10]. Chu, C.; Yiu-Chung Wong; , "FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.27, no.1, pp.70-83, Jan. 2008
[11]. Yue Xu; Yanheng Zhang; Chu, C.; , "FastRoute 4.0: Global router with efficient via minimization," Design Automation Conference, 2009. ASP-DAC 2009. Asia and South Pacific , vol., no., pp.576-581, 19-22 Jan. 2009.
[12]. Minsik Cho; Pan, D.Z.; , "BoxRouter: a new global router based on box expansion and progressive ILP," Design Automation Conference, 2006 43rd ACM/IEEE , vol., no., pp.373-378.
[13]. Tai-Hsuan Wu; Davoodi, A.; Linderoth, J.T.; , "GRIP: Scalable 3D global routing using Integer Programming," Design Automation Conference, 2009. DAC '09. 46th ACM/IEEE , vol., no., pp.320-325, 26-31 July 2009.
[14]. Jinan Lou; Thakur, S.; Krishnamoorthy, S.; Sheng, H.S.; , "Estimating routing congestion using probabilistic analysis," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.21, no.1, pp.32-41, Jan 2002.
[15]. Moffitt, M.D.; , "MaizeRouter: Engineering an effective global router," Design Automation Conference, 2008. ASPDAC 2008. Asia and South Pacific , vol., no., pp.226-231, 21-24 March 2008.
[16]. Johannes Fischer, Daniel H. Huson, “New common ancestor problems in trees and directed acyclic graphs, Information Processing Letters,” Volume 110, Issues 8-9, 1 April 2010, Pages 331-335, ISSN 0020-0190.
[17]. http://homepages.cae.wisc.edu/~adavoodi/gr/cgrip.htm
[18]. Y.-J. Chang, Y.-T. Lee, J.-R. Gao, P.-C. Wu, and T.-C. Wang, “NTHU-Route 2.0: A Robust Global Router for Modern Designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, Vol. 29, No. 12, December 2010, pp. 1931-1944.
[19]. Y. Yang, Q. Zhu, T. Jing, X.Hong, and Y.Wang, “Rectilinear steiner minimaltrees among obstacles,” in Proc. ASIC, pp. 630–635, 2003.
[20]. Z. Shen, C. Chu, Y. Li, “Efficient rectilinear steiner tree construction with rectilinear blockages,” in Proc. ICCD, pp. 38–44, 2005.
[21]. Tao Huang; Young, E.F.Y.; , "Obstacle-avoiding rectilinear Steiner minimum tree construction: An optimal approach," Computer-Aided Design (ICCAD), 2010 IEEE/ACM International Conference on , vol., no., pp.610-613, 7-11 Nov. 2010
[22]. Tao Huang and Evangeline F. Y. Young, “An Exact Algorithm for the Construction of Rectilinear Steiner Minimum Trees among Complex Obstacles,” Proceedings ACM/IEEE Design Automation Conference, 2011.
[23]. Tung-Chieh Chen, Tien-Chang Hsu, Zhe-Wei Jiang, and Yao-Wen Chang. 2005. NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs. In Proceedings of the 2005 international symposium on Physical design (ISPD '05). ACM, New York, NY, USA, 236-238.
[24]. Tony F. Chan, Jason Cong, Joseph R Shinnerl, Kenton Sze, and Min Xie. 2006. mPL6: enhanced multilevel mixed-size placement. In Proceedings of the 2006 international symposium on Physical design (ISPD '06). ACM, New York, NY, USA, 212-214.
[25]. Yanheng Zhang and Chris Chu. 2009. CROP: fast and effective congestion refinement of placement. In Proceedings of the 2009 International Conference on Computer-Aided Design(ICCAD '09). ACM, New York, NY, USA, 344-350.
[26]. http://www.ispd.cc/contests/11/ispd2011_contest.html
[27]. 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 lambda-geometry plane,” in Proc. ISPD, 2006, pp. 48–55.
[28]. Roy, J.A.; Markov, I.I.; , "High-performance routing at the nanometer scale," Computer-Aided Design, 2007. ICCAD 2007. IEEE/ACM International Conference on , vol., no., pp.496-502, 4-8 Nov. 2007.