應用於系統晶片設計之有效避免障礙物的直角化最小史坦那樹建構演算法

An Effective Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction Algorithm in SOC Designs

張永泰(Yung-Tai Chang)

指導教授 ： 陳美麗

中原大學/工學院/資訊工程研究所/碩士(2007年)

https://doi.org/10.6840/cycu200700734

摘要

在實體電路設計之中，繞線問題一直是很重要的一個課題。在現在的SOC(System on Chip)晶片設計之中常常存在著一些障礙物，例如：已經繞過的線、IP block、hard macro等，因此如何找到一顆有效地避免障礙物的直角化最小史坦那樹變成為一個很重要的問題。本篇論文提出一個在平面上建構有效避免障礙物之直角化史坦那樹的方法。
本論文中的演算法可以分為下列步驟：1. 讀進輸入檔案後建立非均勻間距之繞線格。2.建立escape graph。3.建立障礙物加權之完全圖。4建立障礙物加權之最小生成樹。5.對每一條兩接腳線段繞線。6. 檢查是否產生U型多餘線段(U-shaped redundant segment)並修正。
本篇論文針對14個測試檔案[4][6]來建立避免障礙物之直角化史坦那樹，而測試的平台為Sun Blade 2000工作站，1.2GHz CPU，記憶體大小為4GB，作業系統為Solaris 2.9版，在實驗結果中顯示，以本篇論文的演算法所建立出來的避免障礙物之直角化史坦那樹，與其他參考文獻中的實驗結果相比較，平均改善了0.96%~21.25%的總線長，而繞線於escape graph可以比繞線於非均勻間距之繞線格平均改善0.33%的總線長。使用障礙物加權之最小生成樹之繞線順序則比使用傳統最小生成樹的繞線順序平均改善0.35%的總線長。而本論文提出之修正U型多餘線段的方法則可以改善1.45%的總線長。因此本論文所提出之演算法可以很有效地建立出避免障礙物之直角化史坦那樹。

關鍵字

繞線 ； 演算法 ； 避免障礙物之直角化最小史坦那樹

並列摘要

Routing is always an important problem in physical designs. Today’s design often contains rectilinear obstacles, like pre-routed net, IP blocks and hard macros. Therefore, how to construct an obstacle-avoiding rectilinear Steiner minimal tree becomes a very practical problem. In this paper we present an effective algorithm for obstacle-avoiding rectilinear Steiner tree construction.
First, we construct a non-uniform routing grid, then we convert it to an escape graph. Second, we build an obstacle-weighted minimum spanning tree as a guidance to construct OARSMT on an escape graph. Finally, applying Dijkstra's algorithm for routing and a refinement technique is applied during the routing process to further reduce the wire length.
We implement our program in 14 testcases, the experimental results show that comparing to several state-of-the-art works the average total wire length is reduced 0.96%~21.25% and it achieves the shortest average total wire length. Using escape graph instead of non-uniform routing grid achieves 0.33% improvement of average total wire length and using OWMST instead of MST achieves 0.35% improvement of average total wire length. The U-shaped redundant segment removal refines 1.45% of total wire length. The algorithm proposed in this thesis is effective for obstacle-avoiding rectilinear Steiner minimal tree problems.

並列關鍵字

routing ； obstacle-avoiding rectilinear Steiner minimal tree ； algorithm

參考文獻

[1] M. Garey and D. Johnson, “The rectilinear Steiner tree problem in NP-Complete,” SIAM Journal of Applied Mathematics, pp. 826– 834, 1977.

[3] Yu Hu, Tong Jing, Xianlong Hong, Zhe Feng, Xiaodong Hu, Guiying Yan, “An-OARSMan: Obstacle-Avoiding Routing Tree Construction with Good Length Performance,” in Proc. of IEEE/ACM ASP-DAC, Shanghai, China, pp.7-12, 2005.

[4] Z. Feng, Y. Hu, T. Jing, X. Hong, X. Hu, and G. Yan, “An O(nlogn) algorithm for obstacle-avoiding routing tree construction in the lambda-geometry plane,” in Proc. of ISPD, pp. 48–55, 2006.

[5] Y. Shi, T. Jing, L. He, and Z. Feng, “CDCTree: novel obstacle avoiding routing tree construction based on current driven circuit model,” in Proc. of ASP-DAC, pp. 630–635, 2006.

[6] Pei-Ci Wu, Jhih-Rong Gao and Ting-Chi Wang , “A Fast and Stable Algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction, ” in Proc. of ASP-DAC, pp. 262–267, 2007.