考量序號延遲及可繞度之多層次繞線系統

A Multilevel Routing System Considering Delay and Routability

戴昌亮(Chang-Liang Tai)

指導教授 ： 謝財明

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

https://doi.org/10.6840/cycu200500292

摘要

繞線問題是積體電路實體設計中非常重要的ㄧ個部份，由於製程技術持續進步與電路複雜度急速增加，導致晶片單位面積繞線密度隨之大幅提升，為繞線階段帶來許多新的挑戰。晶片設計中，繞線所造成的問題佔整體晶片設計效能的比例逐漸提高，如何有效的決定繞線路徑來處理繞線的問題是一個很重要的研究課題。
本論文提出一新的考量訊號延遲的繞線樹建置方式，我們根據結點間的拓墣關係建立對應的繞線樹，使得從訊號起點至各訊號終點之距離不超過最小曼哈頓距離(Manhattan distance)，以改善訊號延遲。而在決定繞線路徑時引入繞線擁擠度的考量以提升可繞度，最後再利用多層次的架構加以整合。
多層次繞線演算法根據切割方格的大小可分成粗略化及細緻化兩個階段：1.本論文在粗略化階段的每一層皆會進行全域繞線與細部繞線，先計算資源分布的情形，並以此資訊決定每一條連線的全域繞線路徑解(gird-to-gird path)，之後再將資源分配給該連線(track assignment)以完成細部繞線的初始解；2.細緻化階段則是利用迷宮繞線器處理在粗略化階段無法找到繞線路徑的連線。
最後我們以MCNC提供的六個測試電路來進行實驗，並將結果與利用最小生成樹(minimum spanning tree)建立繞線樹的演算法做比較[23]，我們的演算法可以有效的降低訊號延遲且可繞度達98.7%。

關鍵字

訊號延遲 ； 繞線擁擠度 ； 繞線樹 ； 多層次架構

並列摘要

Routing problem has been a very important part in VLSI physical design flow for a long time. As fabrication technology entered very deep sub-micron (VDSM) era, rapidly increasing of circuit complexity and wire density made a great impact on routing problem. In order to obtain good quality results, it is very important to decide routing path effectively for each net.
In this paper, we propose a new routing tree construction algorithm and integrate it into a multi-level routing system. For each net of a circuit, the proposed algorithm constructs a delay-driven routing tree according to the topological relationship of locations between the source terminal and the sink terminals. The minimum Manhattan distance from input terminal to each output terminals on the generated routing tree is guaranteed. We integrate the routing system into multilevel framework.
In multilevel routing, there are two stages: coarsening and uncoarsening. 1. Coarsening: we perform global route, detailed route and resource estimation at each level. We first analysis the resource distribution on the chip and then decide the global routing solution (grid-to-grid path), and a fast track assignment is applied to obtain initial detailed routing solution. 2. Uncoarsening: use maze router to find paths for those nets failed in coarsening stage.
The proposed algorithm has been implemented and tested on MCNC benchmarks. Compared with algorithm with minimum spanning tree[23], experiments result show that our algorithm can effectively reduce delay and the average of routability is about 98.7%.

並列關鍵字

routing tree ； congestion ； delay ； multilevel framework

參考文獻

[11] J. Cong, J. Fang and Y. Zhang, "Multilevel Approach to Full-Chip Gridless Routing," Proc. IEEE International Conference on Computer Aided Design, pp. 396-403. 2001.

[1] C. Albrecht, "Global Routing by New Approximation Algorithms for Multicommodity Flow," IEEE Trans. on CAD, vol. 20, no. 5, pp. 622-632, May 2001.

[5] L. Behjat and A. Vannelli, "Steiner Tree Construction Based on Congestion for the Global Routing Problem," Proceedings of the 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications, pp. 28 - 31, 2003.

[6] L. Behjat, A. Vannelli, and A. Kennings. "Congestion Based Mathematical Programming Models for Global Routing." Proceedings of Mid-West Symposium on Circuits and Systems, 2002.

[7] T. Chan, J. Cong, T. Kong, and J. Shinnerl, "Multilevel Optimization for Large-Scale Circuit Placement," Proc. ICCAD, pp. 171-176, Nov. 2000.