- 學位論文
超大型積體電路實體設計中考慮障礙物之直角史坦納樹建構
Obstacle-Avoiding Rectilinear Steiner Tree Construction in VLSI Physical Design
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
直角史坦納(Steiner)樹問題長久以來，都是一個非常重要的研究課題，並且已經在積體電路設計領域提供了大量的應用。在積體電路設計中，繞線工具通常用直角史坦納樹去繞訊號線，而且很多連接最佳化問題先建構直角史坦納樹，然後再藉由改變線路大小或是插入緩衝器去滿足實際要求。此外，在早期實體設計階段，直角史坦納樹建構也常被使用去估計連接的線長。 然而，隨著科技的進步，現在的積體電路設計包含了越來越多的障礙物。這些障礙物主要是硬式矽智財、巨型區塊、和已繞的繞線。因此，在積體電路設計中，「考慮障礙物的直角史坦納樹問題」已經變成相當重要的實際問題，並且也受快速增加的注視。此外，因為現在的繞線環境包含了許多繞線層，積體電路設計必須分層處理。對於多重繞線層，至少有兩個重要限制必須被考慮。它們是特定繞線方向和不同繞線資源。首先，特定繞線方向指的是在不同繞線層的繞線方向。考量到訊號完整度和積體電路製程，同一繞線層的繞線方向傾向不是水平就是鉛直。其次，因為在較低繞線層通常需要較短的繞線，繞線工具能藉由給於較低繞線層較重的成本，去避免繞出較長的線長。這就是不同繞線資源。所以，「考慮障礙物的特定方向史坦納樹」問題需要有系統地規劃去考慮上述的限制。 在此篇博士論文中，我們企圖在「考慮障礙物的直角史坦納樹問題」和「考慮障礙物的特定方向史坦納樹問題」的研究上取得進展。此外，「考慮障礙物的特定方向史坦納樹問題」也在這篇博士論文中第一次被有系統地規劃。 我們對於「考慮障礙物的直角史坦納樹問題」的研究，企圖在早期實體電路階段，譬如置放(Placement)和平面規劃(Floorplanning)，提供快速且精確的連接線長估計。我們循序漸進地發展出許多新穎的策略，並且藉由這些策略完成三個高效能的演算法。這些演算法成功地同時在時間和線長上，達到了實際最好的效能。 首先，我們提出考慮障礙物繞線圖。與現存的繞線圖相比，這個考慮障礙物繞線圖不是包含較好的解答就是有較高的效能。接著，不同於先前的研究，我們提出一個根據路徑的架構。這個架構直接產生關鍵路徑當作解答元件，而沒有建構一個繞線圖或是產生一個錯誤解答。我們的根據路徑演算法保證能對一些特定測資，在線性對數時間內產生最佳解，這樣的保證在過去的研究要花立方的時間。 最後，我們提出「根據史坦納點的架構」和「史坦納點位置」的概念。這些架構和概念深刻地反映了考慮障礙物的直角史坦納樹問題的本質。這個方法能在實際的線性對數時間內產生目前最好的解答，這樣的解答過去要使用迷宮(maze)繞線在平方空間的繞線圖上才能得到。更重要的是，這兩個新想法可以很自然地給予未來的「考慮障礙物的直角史坦納樹研究」貢獻，以及相關的重要問題，譬如多層考慮障礙物的直角史坦納樹問題以及考慮障礙物的特定方向史坦納樹問題。 我們對於「考慮障礙物的特定方向史坦納樹問題」的研究，企圖在繞線階段，為接下來的連接繞線最佳化提供較好的訊號線拓撲（topology）。作為第一個研究，我們循序漸進地建立基本的理論基礎，以幫助未來相關演算法的發展。 首先，我們根本地分析最佳解的結構，並且提供分析解答品質的方法。在演算法的設計方面，解答品質的分析通常提供非常大的幫助，尤其是近似演算法的設計。第二，我們證明「考慮障礙物的特定方向最小延伸樹」是「考慮障礙物的特定方向史坦納樹問題」的二倍近似解，因此提供相當重要的特色，去支持強力的探索式方法（heuristic）。第三，我們證明「考慮障礙物的特定方向最小延伸樹」至少需要平方的空間，因此提供了較強的動機，去發展其他演算法。最後，我們分析了「局部最小的保證」以及「最小節點延伸樹（Minimal Terminal Spanning Tree）演算法的本質」，去設計了一個花費線性對數平方時間的演算法。
並列摘要
The rectilinear Steiner minimal tree (RSMT) problem has been a very important research issue for a long time, and already provided a lot of applications in very large scale integration (VLSI) design. In VLSI design, routing tools usually use rectilinear Steiner trees (RSTs) to route signal nets, and many interconnect optimization approaches begin with RST constructions, and then apply wire sizing, driver sizing, and buffer insertion to meet the performance requirements. Furthermore, at early physical design stages, the RST construction is also employed to make interconnect estimation. However, as the technology advances, the modern integrated circuit (IC) design includes more and more routing obstacles incurred from hard intellectual property (IP) cores, macro blocks, and pre-routed nets. Therefore, the obstacle-avoiding RSMT (OARSMT) problem has arisen as an important practical problem in the VLSI physical design, and received dramatically increasing attention recently. Besides, since the modern routing environment includes a number of layers, IC designs are processed layer and layer. To deal with multiple layers, at least two important constraints should be considered: preferred directions and different routing resources. First, preferred directions are the routing orientations on those multiple layers. Considering signal integrity and IC manufacturing, the orientation of routing in a single layer tends to be either horizontal or vertical but not both. Second, since the lengths of wires tend to be shorter in lower layers, the router can weight the routing cost in lower layers higher to avoid routing long wires in lower layers, i.e., different routing resources. As a result, the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem needs to be formulated to catch all the mentioned constraints. This dissertation attempts to make progress in the study of the OARSMT problem and the OAPD-ST problem. This is also the first attempt to formulate the OAPD-ST problem. The study for the OARSMT problem attempts to provide quick and accurate interconnect estimation at early physical design stages such as floorplanning and placement. We progressively develop novel strategies to bring about three excellent algorithms, and successfully achieve the best practical performance in both wirelength and run time. Firstly, we propose an obstacle-avoiding routing graph (OARG). Compared with existing routing graphs, the OARG either contains better solutions or has higher efficiency. Secondly, unlike previous works, we propose a path-based framework to directly generate critical paths as solution components instead of constructing a routing graph or generating an invalid solution. Our path-based algorithm guarantees to provide optimal solutions for a number of specific cases, which requires O(n^3) time in previous works. Thirdly, we propose the Steiner-point based framework and the concept of Steiner point locations to give critical insights into the OARSMT problem. This approach achieves the best solution quality in empirical Theta(n log n) time, which was originally obtained by applying maze routing on an Omega(n^2) space graph. More importantly, the two ideas naturally contribute to the future researches on the OARSMT problem and its important generations such the multi-layer OARSMT problem and the OAPD-ST problem. The study for the OAPD-ST problem attempts to provide better signal net topologies at the routing stage for succeeding interconnect optimization. As the first study, we progressively build theoretical foundations for the development of future algorithms. Firstly, we analyze the structure of the optimal solution, and provide a way to analyze the solution quality, which significantly helps the development of algorithms, especially for approximation ones. Secondly, we prove that an obstacle-avoiding preferred direction minimum spanning tree (OAPD-MST) is a factor 2 approximation solution for the OAPDST problem, and thus provides important features to support strong heuristics. Thirdly, we prove the space complexity of an OAPD-MST is Omega(n^2), and give a strong motivation to develop more efficient algorithms instead of OAPD-MST construction. Fourthly, we analyze local minimal guarantees and the essentials of an minimal terminal spanning tree (MTST) based algorithm to develop an O(n log^2 n)-time strong heuristic.
並列關鍵字
Algorithm ； Physical Design ； Routing ； Steiner tree ； Spanning Tree ； Obstacles ； Multi-Layer參考文獻
[3] B. Chazelle, “An algorithm for segment dragging and its implementation,” Algorithmica, vol. 3,pp. 205–221, 1988.
[4] C. Chu and Y.-C.Wong, “FLUTE: Fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design,” journal = ”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems”, vol. 27, no. 1, pp. 70–83, 2008.
[5] K. Clarkson, S. Kapoor, and P. M. Vaidya, “Rectilinear shortest paths through polygonal obstacles in O(n log2 n) time,” in Proceedings of the ACM Symposium on Computational Geometry, pp. 251–257, 1987.
[7] M. Dorigo, V. Maniezzo, and A. Colorni, “The Ant System: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 26, no. 1, pp. 29–41, 1996.
[8] 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 Proceedings of the ACM International Symposium on Physical Design (ISPD), pp. 48–55, 2006.