網格網路上RST演算法

Grid Networks RST Algorithms

詹勳旻(Hsun-Min Chan)

指導教授 ： 黃俊平

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2010年)

摘要

當積體電路板在追求輕薄、高效能的設計時，繞線問題一直是一個相當受到重視的一個議題，目前在IC晶片設計上有著一些障礙物，因此如何找到一個有效避免障礙物的直線式史坦納樹成為一個重要的問題，將提出一個有效避免障礙物的直線式史坦納樹方法，演算法可分為下列幾個步驟：1、選定一起始點為出發點，再連接下一個距離最近的節點，建構一四點模式。2、選擇與剩餘之點最近距離的端點為出發點，再連接下一個距離最近之節點，以建構出四點模式。3、對於尚未連線的剩餘之點，可以三點模式、單點連線方式連接。4、修改U型線段縮短總線長。而對於沒有障礙物限制的繞線總長度，與文獻作結果比較，在不同節點數的改善率有4.38%∼6.67%，而對於有障礙物限制下的繞線總長度，會與兩方法作比較，分別為escape graph與spanning tree，對於線段長度的改善率分別為1.39%與4.05%，由實驗結果得知使用本文方法將可建立一個高品質的繞線。

關鍵字

史坦納樹 ； 史坦納點 ； 障礙物 ； 繞線

並列摘要

With the request for lighter weight and smaller size in the commercial market routing for the design of the IC board. Routing is always an important problem in physical designs. IC design often contains rectilinear obstacles. Therefore, how to construct an obstacle-avoiding rectilinear Steiner minimal tree becomes a very practical problem. Present an effective algorithm for obstacle-avoiding rectilinear Steiner tree construction. Step1：Select a node as a starting point，then connect the next nearest node，construct a four-point routing mode. Step2：Select the point based on the recently distance of the remaining points as the starting point，and then connect the next nearest node to construct a four-point routing mode. Step3：For the remainder of the points have not yet connected，can be use three-point mode and a single point of connection. Step4：The total wire length is further reduced by U-shape refinement. The experimental results show that the total wire length is reduced 4.38%∼6.67% in non-obstacle constraint and the total wire length is reduced 1.39%∼4.05% in obstacle constraint. Experimental results show that our algorithm can construct a high-quality routing result.

並列關鍵字

Steiner tree ； Steiner point ； Obstacle ； Routing

參考文獻

6. Huang, H. H., Huang, H. Y., Huang, D. J., & Hsieh, T. M. (2006). “Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction Algorithms”, WSEAS Transactions on Circuits and Systems, Vol. 5, pp. 1775-1782.

3. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. & Clifford Stein (2001). “The algorithms of Kruskal and Prim”, INTRODUCTION TO ALGORITHMS Second Edition, pp. 567-573.

1. Chu, C. & Wong, Y. C. (2005). ” Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design”, Proc. International Symposium on Physical Design, pp. 28-35.

algorithm for obstacle-avoiding routing tree construction in the λ-geometry plane”, in Proc. of ACM International Symposium on Physical Design, pp. 48-55.

5. Garey, M. & Johnson, D. (1977). “The rectilinear Steiner tree problem is NP-complete”, SIAM J. Appl. Math., pp. 826–834.