考慮時間效能以及緩衝器植入之繞線生成樹

傳統的全域繞線器(Global Routing)通常是以線長(Wire-Length)或擁擠度(Congestion)為主要的考量，但是隨著製程的微縮，時間效能問題已經慢慢地變成超大型積體電路實體設計流程(VLSI Routing flow)中決定晶片效能的一個重要的因素。在本論文中，提出了一個可以改善線路最大延遲的方法。首先將平面根據電流源(Source)分成k個不等大平面用來降低迂迴所造成之最大source-to-source延遲，接著再針對上述步驟的每一個區域用循序的方式(Sequential-based Method)分別建立一棵避開直角障礙物的史坦那繞線樹(Obstacle Avoiding Minimal Steiner Tree)，接下來再利用Elmore Delay Model計算從電流源到每一點的到達時間，為了更有效地降地延遲那些違反時間限制的節點，還會再利用重新繞線的方式去降低此條線路的最大延遲，最後我們也提出兩個加入緩衝器(Buffer)的方法來改善其到達時間以符合時間上的限制。在實驗結果當中，我們將會比較傳統的、有分區以及有分區加重繞的三個主要結果：最大延遲(Maximal Delay)、總線長(Total Wire Length)以及所需要的緩衝器個數(Number of Buffers)。而對於以上三個結果，我們分區再加上重新繞線的方法比幾傳統以線長為導向(One-Region)的方式改善了最大延遲平均70.31% 但需要13.07% 的額外線長，而緩衝器個數方面也可以看出兩個演算法的分別優點以及其缺點，但使用我們的演算法均可以估出只需要更少的緩衝器就可以使所有的節點符合時間上的限制。

關鍵字

緩衝器植入；效能導向；繞線樹；訊號延遲

並列摘要

Traditional Global Router usually considers wire-length or congestion. But the timing problem are become an important factor which dominate chip’s performance in Very Large Scale Integrartion(VLSI) flow as fabrication technology of semiconductors keeps shrinking. In this paper, we present a timing-driven routing tree construction algorithm to minimize the maximum source-to-sink delay. First, timing-driven partition-based method is divide the chip into k irregular sub-regions to improve the detour routing, ie. The maximum source-to-sink delay. Second, a sequential-based routing algorithm is applied to generate a rectilinear Steiner tree with rectilinear obstacles for each region. Third, for some critical terminals, the rewire technique is then utilized to reduce maximum source-to-sink delay calculated by Elmore Delay Model. Finally, two methods of buffer insertion is proposed to fix the timing violated terminals. We compared three different methods in our experiments: tradidional method, partitioning method and partitioning method with wiring techenique and consider three objective, maximum source-to-sink delay, total wire-length and number of inserted buffers. Compared to the traditional method, our timing-driven partitioning method can reduce maximum source-to-sink delay about 70.31% and 13.07% additional wire-length. We can observe that our two methods of buffer insertion has its own strength and weakness. But the number of buffers is also significant reduced by the proposed algorithm to fix all timing-violated terminals.

並列關鍵字

Buffer insertion ； Performance-driven ； Routing tree ； Delay

參考文獻

[1] C.J. Alpert, J. Hu, S.S. Sapatnekar and P.G. Villarrubia, “A Practical Methodology for early Buffer and Wire Resource Allocation,” in Proc. of ACM/IEEE Design Automation Conference, pp. 573-583, 2001.

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

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

[5] J. Cong, T. Kong and D.Z. Pan, “Buffer Block Planning for Interconnect-Driven Floorplanning,” in Proc. IEEE/ACM International Conference on Computer Aided Design, pp. 358-363, 1999.

[6] 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.

國際替代計量

考慮時間效能以及緩衝器植入之繞線生成樹

全文下載

主題瀏覽