考慮電路延遲與障礙物迴避之直角史坦那樹建構法

Abstract

隨著製程的演進，線路所造成的延遲已經變為最主要影響電路延遲的一個因素。而且，在先進的積體電路設計中，對一些比較先進的設計進行繞線時，那些設計常常會包含許多障礙物，例如: 區塊所產生障礙物，或者一些已經繞好的線路。然而，避開障礙物的史坦那繞線研究卻很少考慮如何去減少電路延遲，大部分之前的研究都只針對如何來減少整體繞線的長度，因此，這些研究被稱為避開障礙物且最短繞線長度之直角史坦那樹 (OARSMT)。

這篇論文中，我們提出一個新穎且快速的演算法稱為關鍵樹幹為基礎之電路延遲最小化演算法(critical-trunk based delay minimization algorithm)，在考慮障礙物的情況下同時解決電路延遲問題。我們的演算法可以分為5個主要的部分; (1) 建立避開障礙物的擴張圖(spanning graph)，(2) 對遠離驅動源(driver)的接腳(pin)先進行繞線，(3) 再連接其他的接腳(pin)，(4) 將歪斜的線轉化為水平或垂的線段，(5) 優化違反時序限制最大的路徑延遲(Worst Negative Slack)。

實驗結果顯示，對於OARSMT，我們提出的演算法平均改進違反時序限制最大路徑延遲和最大路徑延遲，分別是81.52 %以及28.42 %，而且，僅僅增加了9.15%的線長，且外，我們更比[10]平均快了32.06%。對於C-Tree[21]，我們的演算法相對改進的違反時序限制最大的路徑延遲和總線長，分別是53.92%以及15.61%，我們提出的演算法更比[21]快了27.69倍。

With technology scaling, interconnect delay has dominated circuit delay. Mean-while, modern System on Chip (SOC) design contains many obstacles such as IP cores, macro blocks, and pre-routed nets within the routing region. Most previous works on obstacle-avoiding rectilinear Steiner tree construction only focus on mini-mizing total tree wire-length, and thus their works are called obstacle-avoiding recti-linear Steiner minimal tree (OARSMT).

In this thesis, we propose a novel and fast algorithm called critical-trunk based delay minimization algorithm to tackle timing issue regarding existing blockages. The proposed algorithm can be classified into 5 main steps: (1) construct an obsta-cle-avoiding spanning graph; (2) pre-route the sinks that are far away from the driver; (3) connect other sinks; (4) transform every slant edge into horizontal or vertical edges; (5) refine worst negative slack (WNS).

Experiments show that the proposed algorithm achieves the average reduction rates of WNS and maximum delay over OARSMT approach are 81.52 % and 28.42%. Besides, the proposed algorithm runs faster by 32.06% as compared to that in [10]. As compared to the C-Tree approach in [21], the reduction rates of WNS and wire length are 53.92% and 15.61%, respectively. The proposed algorithm achieves a 27.69X runtime speedup as compared to that in [21].