效能導向多層繞線系統

Performance-Driven Routing Tree Construction with Obstacles in Multilayer Systems

黃惠瑜(Hui-Yu Huang)

指導教授 ： 謝財明

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

https://doi.org/10.6840/cycu200700287

摘要

近年來深次微米技術的進步使得多層繞線成為主要改善時間的主要方式之一。近年研究驅向SoC 的設計，一些已經繞好的線及macro cell都可視為障礙物，因此在繞線階段我們必須將障礙物納入考量。
本論文擬提出一個分群的方式且同時考慮障礙物以及應用於多層繞線層的演算法，主要針對最小化從訊號起點到訊號終點的繞線總長度、最小化最大延遲(delay)、最小化時序差異。
本方法第一步先不考慮障礙物下對整個佈局做分群，對每一群找出中心點當做層與層之間打穿孔的初始位置，再根據打穿孔(via)的位置是否合法稍做移動以避免穿過障礙物。針對修正後的打穿孔分為4個區域對各區做繞線。分群技術不僅可以降低時序差異，也可以最小化最大延遲(delay)。對一區域先使用三角化方法(Delaunay Triangulation)找出所有點之間的連線關係，再利用擴張圖(Spanning graph)找出避開障礙物的路徑。實驗結果顯示我們所提出的演算法能夠有效改善時序差異和最小化最大延遲，且不增加過多的線長。當訊號起點在中心位置時我們的演算法平均改善最大延遲19.995%，可見本方法能夠有效改善最大延遲。

關鍵字

繞線樹 ； 最大延遲 ； 時序差異 ； 多層繞線 ； 障礙物

並列摘要

The multilayer routing problem becomes more important than ever for performance-driven physical design in the dep-submicron era. With the trend toward IP-block-based Soc design, the macro cells present in the design as obstacles.
In this paper, we present a clustering-based 3D rectilinear Steiner routing tree algorithm which minimizes the maximum source to sink path length, data skew, maximum delay, and total wire length simultaneously among the obstacles. First, the terminals are divided into g groups according to the net terminal distribution without the obstacles. Second, the local centroids in each layer are calculated for each layer. To minimize the via counts, the free-space is computed by projecting all obstacles to the same layer. For each local centroid in each layer, we fourth adjust the poison of local centroid outside the obstacles. We divide the each group into four sub-regions according to the adjusted local centroid location, and then we construct the wirelength-driven routing tree in each region. We use the delaunay triangulation approach to cluster all terminals and corners of obstacles into groups of three points nets then construct a spanning graph to avoid through out obstacles.As a result, we can minimize the data skew, and minimize the maximum delay. Experimental results show that the proposed algorithm minimizes the maximum source to sink path length, data skew, and the maximum delay effectively with a very little penalty of total wire length. In average, we can reduce the maximum delay than obtained by the traditional method without terminal-grouping about 19.995%.

並列關鍵字

multilayer ； obstacle ； skew ； routing tree

參考文獻

[1] C.J. Alpert, A. B. Kahng, C. Sze and Q. Wang, “Timing-Driven Steiner Trees are (Practically) Free,” in Proc. of ACM/IEEE Design Automation Conference, pp. 389-392, 2006

[3] K.D. Boese, A.B. Kahng, and G. Robins, “High-Performance Routing Tees with Identified Critical Sinks,” in Proc. of ACM/IEEE Design Automation Conference, pp. 182-187, 1993.

[7] C. Chu and Y.C. Wong, “Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” in Proc. of ACM International Symposium on Physical Design, pp. 28-35, 2005.

[11] .W. C. Elmore, “The Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers,” Journal of Applied Physics, Vol. 19, pp.55-63, 1948.

[12] J. L. Ganley and J. P. Cohoon, “Routing a Multi-Terminal Critical Net: Steiner Tree Construction in the presence of Obstacles,” in Proc. of IEEE International Symposium Circuits and Systems, pp.113-116, 1994.