在平面規劃及繞線中，對於訊號線建立直角史坦納樹是一個非常重要的過程，因為我們可以使用直角史坦納樹去尋找線拓撲(topology)和測量設計的品質。然而，在現今積體電路設計中，點分布在多重繞線層中且每層繞線都遵守特定方向，而且有越來越多的障礙物。這些障礙物主要是智財區塊(IP block)、動力網路系統(power network)、已繞的繞線等，使得我們必須去考量多層平面及障礙物之特定方向直角史坦納樹的問題。但是這會大幅度地提高問題的複雜度，所以我們需要一個效率高及有效的演算法去處理這個問題。在這個論文中，我們提出一個非常簡明及有效的方法去處理考量多層平面及障礙物之特定方向直角史坦納樹的問題。在先前的研究中，通常建立一個延伸圖並且去尋找延伸樹來處理此問題，這會花費許多時間。但是，不同於先前的研究，我們首先決定所有點的連接順序，然後利用一個貪婪的演算法反覆地去連接相鄰的兩個點。在我們的方法中，在不使用複雜的程序對每個兩個點的線去尋找最短路徑的情況下，我們會小心謹慎地衡量設計的品質及時間，而且我們的方法對於所有例子都可得到可行的繞線。實驗結果顯示我們的方法與Liu [7]做比較，仍可得到較低的成本及較快的執行速度。

Constructing rectilinear Steiner trees for signal nets is a very important procedure for placement and routing because we can use it to find topologies of nets and measure the design quality. However, in modern VLSI designs, pins are located in multiple routing layers, each routing layer has its own preferred direction, and there exist numerous routing obstacles incurred from IP blocks, power networks, pre-routed nets, etc, which make us need to consider multilayer obstacle-avoiding preferred direction rectilinear Steiner minimal tree (ML-OAPDRSMT) problem. This significantly increases the complexity of the problem, and an efficient and effective algorithm to deal with the problem is desired. In this paper, we propose a very simple and effective approach to deal with ML-OAPDRSMT problem. Unlike previous works usually build a spanning graph and find a spanning tree to deal with problem, which takes a lot of time, we first determine a connection ordering for all pins, and then iteratively connect every two neighboring pins by a greedy algorithm. In our approach, we carefully trade off the design quality and running time in order to find a shortest path for every two pin nets without a complex procedure, and our procedure guarantees a feasible routing in all cases. The experimental results show that our method has average 5.78% improvement over [7] and at least five times speed up comparing with their approach.

[1] 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, pp. 48-55, 2006.
[2] M. Garey and D. Johnson, “The Rectilinear Steiner Tree Problem in NPComplete,” in Proc. SIAM Journal of Applied Mathematics, pp. 826-834, 1977.
[3] F.K. Hwang, “On Steiner Minimal Trees with Rectilinear Distance,” in Proc. SIAM Journal on Applied Mathematics, Vol.30, pp. 104-114, 1976.
[4] I. H.-R. Jiang, S.-W. Lin and Y.-T. Yu, ”Unification of Obstacle-Avoiding Rectilinear Steiner Tree Construction,” in Proc. SOCC, pp. 127-130, 2008.
[5] C. W. Lin, S. Y. Chen, C. F. Li, Y. W. Chang and C. L. Yang, “Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction,” in Proc. ISPD, pp. 127-134, 2007.
[6] C. W. Lin, S. L. Huang, K. C. Hsu, M. X. Lee, and Y. W. Chang, “Efficient multilayer obstacle-avoiding rectilinear Steiner tree construction,” in Proc. ICCAD, pp. 380-385, 2007.
[7] C. H. Liu, Y. H. Chou, S. Y. Yuan, and S. Y. Kuo, “Efficient Multi-layer Routing Based on Obstacle-Avoiding Preferred Direction Steiner Tree,” in Proc. ISPD, pp. 118-125, 2008.
[8] Y. Shi, T. Jing, L. He, and Z. Feng, “CDCTree: Novel Obstacle-Avoiding Routing Tree Construction Based on Current Driven Circuit Model,” in Proc. ASP-DAC, pp. 630-635, 2006.
[9] Y. Shi, P. Mesa, H. Yu and L. He, “Circuit Simulation Based Obstacle-Aware Steiner Routing,” in Proc. DAC, pp. 385-388, 2006.
[10] P. C. Wu, J. R. Gao, and T. W. Wang, “A Fast and Stable Algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree,” in Proc. ASP-DAC, pp. 262-267, 2007.
[11] M. C. Yildiz and P. H. Madden, “Preferred Direction Steiner Trees,” in IEEE TCAD, Vol. 21, No. 11, pp. 1368-1372, 2002.