有效率的全域繞線方法考慮優先方向及時間繞線成本

現今的積體電路設計中，繞線問題面臨了更多更新的挑戰，全域繞線問題首當其衝，因此在積體電路實體設計中，全域繞線扮演了一個相當重要的角色。在此篇論文當中，我們設計了一個全域繞線器，我們的繞線器命名為” WinGr”，我們期許我們的繞線器能優過於其他的繞線器。我們主要整合了一些演算法在其中，相對於其它的來說，我們兼顧了減少總線長，overflow數，及時間效能的考量。首先我們使用了FLUTE方法建立了表格儲存繞線資訊，以讓我們簡化及容易進行以後的設計；再來我們引用較少通道生成樹的方法，企圖減少繞線路徑中的通道；隨後我們使用IFR方法進行主要的繞線還有成本考量工作；最後，透過Robust的階層分配方式，完成最後的繞線工作。此外，我們使用了線段平移來優化我們的繞線器，它能透過在相同平面的通道平移取代，來減少考慮優先方向史坦納樹的繞線長度；另外我們也使用多執行緒的程式設計方法，來處理多網絡繞線的問題。總言之，我們整合出來的繞線流程有效率地考量了繞線長度及時間成本，是個有效率且節省成本的繞線器。

關鍵字

全域繞線；最小生成樹；優先方向；平行計算

並列摘要

The very-large-scale circuit (VLSI) design has faced to more and new challenges for routing algorithms. Global routing is the first stage to tackle the stringent routing challenges. Therefore, it is an important stage for physical design. In this paper, we develop a new global router. Some routing method will be integrated into our router. WinGr keeps a balance among total wirelength, overflow, and cost of running time based on preferred direction. It is the most difference from other routers. The congestion estimation use FLUTE technique to create a table for wirelength estimation. It is easy to realize and implement. The via minimization tree generation generate a via aware Steiner tree, and it reduce via wirelength effectively. The IFR replaces INR by enhanced iterative (a) forbidden-region rip-up/rerouting (IFR) which features three new (b) techniques of (1) multiple forbidden regions expansion, (2) critical (c) subnet rerouting selection, and (3) look-ahead historical cost increment. The Layer assignment uses “Robust Layer Assignment” to assign layers effectively. Besides, we use CLS (Consecutive Line Segment) to optimize our routing edges. It can reduce the wirelength cost of preferred direction rectilinear tree by shifting the edge with the same x-coordinate or y-coordinate. We also used pthread programming to speed up multi-net routing. To sum up, our router is an efficient and integrated routing flow, which performs with less wirelength and time cost.

並列關鍵字

Global Routing ； MST ； Preferred Direction ； Parallel Computing

參考文獻

[3] C.Y. Lee, “An Algorithm for Path Connection and its Application”, IRE Transactions on Electronic Computers, 1961.

[4] M. Pan, and C. Chu, “FastRoute: A step to integrate global routing into placement,” Proc. of Intl. Conf. on Computer-Aided Design, pp. 464-471, Nov 2006.

[5] Minsik Cho and Progressive ILP, “BoxRouter: A New Global Router Based on Box Expansion,” In Proc. DAC2006

[8]L.McMurchie and C. Ebeling, “PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs,” proc. the Int. ACM Symp. on Field-Programmable Gate Arrays, pp. 111–118, 1995.

[10] Kahng and Robins, “A new class of Steiner tree heuristics with good performance: the iterated 1-Steiner approach,” ICCAD-90.

國際替代計量

有效率的全域繞線方法考慮優先方向及時間繞線成本

全文下載

主題瀏覽