一個能避免擁擠及結合指定穿越點之多層全域繞線器

A congestion-Driven Multilayer Global Router with Cross Point Assignment

黃喬逸(Chiao-Yi Huang)

指導教授 ： 林榮彬

元智大學/資訊學院/資訊工程學系/碩士(2002年)

摘要

隨著超大型積體電路的製程進步到深次微米的層次，在相同大小的晶片中所能容納的邏輯元件數、接腳、和接線的個數都比以往多了許多。傳統的全域繞線器會完全忽略所要連接的接腳的細部位置、接腳們之間的相對應位置和擁擠程度。另一個問題是完全沒有討論到連結邏輯元件中具有相同電性的接腳，如選擇一個最適當的接腳。在本論文中，我們提出一個接腳相關示意圖來代表在一個指定繞線區域中接腳的分布位置，提出一個能避免擁擠區域並決定走最佳路徑的全域繞線演算法，再加上指定穿越點能夠決定細部的繞線分布。以MCNC測試電路所評估之數據顯示，由我們的全域繞線器所預估的繞線長度大約是比Cadence Silicon Ensemble作完全部細部繞線的繞線長度少35%。但是在只有兩層繞線層可用的條件下，卻有約45%的接線繞線失敗。未來所要延續的工作中，除了在尋找接線的直角走訪要改善時間複雜度，我們要再設計一個繞遠路卻能達成完繞率的機制。

關鍵字

全域繞線器 ； 指定穿越點 ； 避免擁擠 ； 多層繞線

並列摘要

As VLSI process technologies evolve into the deep sub-micron era, the number of cells, pins, and nets in a fixed chip area becomes larger. VLSI routing is much more difficult than ever before. Traditionally, global routing is performed with a total disregard of the positions of pins and their relative topological relation, as well as the existence of electrically equivalent pins. In this thesis, we implement a congestion-driven global router with cross point assignment (CPA) to address the above issues. The research work has to developed a pin relation graph to represent the relative topology of pins in each global routing grid (GRC), an approach to dividing multi-terminal nets into a set of two-pin nets, an algorithm to find a least congestion and shortest route for each two-pin net, and a method to perform CPA for each GRC. For each net, we generate a tentative route which is improved further to reduce local congestion by exploring equivalent pins based on pin relation graphs. Some MCNC benchmark circuits are used to evaluate the effectiveness of the proposed method. The estimated wire length of a design routed by our router is about 35% shorter than that obtained by Cadence Silicon Ensemble. However, our router results in about 45% failed connections when there are only two routing layers. Future work is proposed to make our global router more robustable.

並列關鍵字

global router ； cross point assignment ； congestion driven ； multilayer

參考文獻

[Chia90] C. Chiang, M. Sarrafzadeh, and C. K. Wong "Global routing based on Steiner min-max trees," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 9, no. 12, pp. 1318-1325, Dec. 1990.

[Coh88] J. P. Cohoon and P. L. Heck, “BEAVER: a computational-geometry-based tool for switchbox routing,” IEEE Transactions on Computer-Aided Design, Vol. 7, No. 6, June 1988

[Dua84] A. E. Dualop, et al., "Chip layout optimization using critical path weighting," Proc. of IEEE Design Automation conf., pp. 133-138, 1984.

[Gar77] M. R. Garry, and D. S. Johnson, “The rectilinear Steiner tree problem is NP-complete,” SIAM J. Appl. Math., Vol. 32, No. 4, pp826-834, 1977.

[Haya95] M. Hayashi and S. Tsukiyama, "A hybrid hierarchical approach for multi-layer global routing," Proc. of European Design and Test Conf., 1995.