RLC零时脉偏移演算法.doc

RLC零時脈偏移演算法1RLC零時脈偏移演算法RLC Exact Zero-Skew Algorithm蔡加春 吳占鰲 郭仲傑 李文達Chia-Chun Tsai, Jan-Ou Wu, Chung-Chieh Kuo, Wen-Ta Lee國立台北科技大學電子工程系摘要由於積體電路的製程技術進入深次微米，且晶片內部電路的複雜度愈來愈高，各種影響系統效能的問題接踵而來，其中以時脈的影響最為嚴重。如果晶片內各功能電路方塊的時間延遲相差很大，則會產生時脈偏移的現象，使得系統效能下降，更有可能造成系統的當機，因此時脈繞線在電路的佈局中佔了很重要的一環。以往對於連線延遲的計算方法是採用模型，但隨著晶片工作時脈的提升，使得電感效應愈來愈明顯。本文提出了零時脈偏移演算法應用於實體佈局的時脈繞線，進而達到零時脈偏移量。我們將此演算法應用在MMM與GMA時脈繞線方法之一些例子，先經調整為零時脈偏移量的時脈樹，再實際驗證與H-SPICE比較結果而得到最大時脈延遲平均誤差為6.289383以內，相較於Ismail 5 所提出的方法之平均誤差減少了13.71061%，此實驗結果顯示我們的方法是有效的。關鍵詞：積體電路、時脈偏移、時脈繞線投稿受理時間: 92 年 10 月 15 日 審查通過時間: 92 年 12 月 24 日ABSTRACTDue to IC fabrication gets into deep submicron technology, the circuit interconnection is more complicated that will affect the chip performance. Clock delay is most important one for the chip performance and clock skew caused by the difference between clock delays could shut down the system work. So the clock routing plays an important role in VLSI physical design. In general, the model for wires was adopted in clock routing before. As the working frequency of a chip has promoted to GHz, the inductance for wires must be considered. In this paper, we present an algorithm based on model to solve an exact zero-skew clock routing. The algorithm is applied to the approaches of MMM（Method of Means and Medians） and GMA（Geometric Matching Algorithm） clock routings. After adjusting exact zero-skew clock trees for the examples, we get the maximum tolerance of 6.289383 in term of clock delay comparing with H-SPICE. The tolerance is reduced up to 13.71061 than that of Ismail approach 5. Experimental results show that our algorithm is effective.2臺北科技大學學報第三十七之一期Keyword:IC, clock skew, clock routing233壹、簡介過去幾年，邏輯閘的延遲一直是影響線路設計的最重要因素之一。由圖(一)可以知道在IC製程0.35m以前，電路的連線延遲（Interconnect delay）遠小於閘級延遲（Gate delay）1，所以電路設計者在規劃電路時，往往忽略了連線延遲，而只考慮到閘級延遲，正因連線延遲的限制，使得線路效能無法有效提升。在晶片系統中，影響其工作速度有兩個因素，其中一個是邏輯電路中所經過之最長路徑所產生的時脈延遲，也就是最大時脈延遲（Phase delay）；而另一個則是時脈偏移（Clock skew）2。較大的時脈延遲會降低系統晶片的執行效能，使工作時脈的提升受到限制；而較大的時脈偏移則會影響時脈端點的建立與保持時間（Setup and hold times）之邊際效應，造成系統的效能下降。因此一顆晶片要達到高效能的正常動作，最重要的就是讓系統的時脈延遲降到最低以及時脈偏移減至最小，且必須在系統要求的範圍之內。本文研究重點著重在整個時脈樹的時脈偏移達到零偏移。以往晶片工作時脈較低時，計算連線延遲的方法是採用Elmore3所提出的模型。但隨著製程技術的進步以及晶片的工作時脈愈來愈高，使得原先在低時脈下被忽略的電感效應變的愈來愈明顯。Kahng4提出用第一和第二瞬時項來描述時脈樹，並針對實數、複數以及重根三種情形下的極點（pole）分別提出公式，不過沒有對可直接用在延遲模型的瞬時項提出公式解。因此本文在計算連線延遲時改採用二階模型5，以求得更精確的電路延遲時間及時脈偏移，並提出零時脈偏移演算法。RLC零時脈偏移演算法3圖(一)閘級延遲與連線延遲的關係圖有關本論文其他章節安排如下，第二節分別說明模型及模型。第三節提出時脈樹的零時脈偏移演算法。我們將此演算法應用在MMM6和GMA7的時脈樹上，其實驗結果在第四節。最後作出結論以及說明未來更進一步的研究方向。貳、延遲模型1948年，Elmore3提出延遲模型用於計算一線性系統的連線延遲時間，不過Elmore僅考慮單位長度電阻和單位長度電容對連線延遲時間所產生的影響。若此系統的轉換函數為並將其做正規化後可得，表示成(1)其中和皆為實數且mn。式(1)可被展開成一個包含冪次方的級數，而50%訊號延遲時間可直接由的係數決定。根據式(1)，Elmore定義為連線延遲時間，和如式(2)所示。： and (2)其中和分別代表轉換函數的極點(poles)和零點(zeros)。1987年，Wyatt8將視為系統支配極點的倒數，計算出50訊號延遲時間為，這和Elmore的結果有所差異，通常由Wyatt算出的時間延遲會比用Elmore算出的時間更為接近實際的延遲時間。圖(二)為一個單位線段的等效電路，其轉換函數表示為：(3)圖(二)一個單位線段的等效電路而圖(三)是在模型下建出的一個時脈樹，Elmore根據式(3)導出計算節點的時間延遲公式為：(4)其中是時脈樹中每一個電容的索引值， 是從輸入端到節點與節點的共同電阻。4臺北科技大學學報第三十七之一期圖(三)時脈樹圖(四)表示單位線段的等效電路，其中、分別代表線電阻、線電感和線電容，但由於樹中有可能產生非單調響應(non-monotone)，使得Elmore延遲模型無法適當描述樹，因此並不適合用來計算連圖(四)簡單的電路線延遲。圖（四）的電路可表示成二階轉換函數：(5)其中的係數為，並未包含，因此說明了Elmore所推導出的延遲時間模型並沒有考慮到線電感對於連線延遲的影響。然而電感對於二階電路響應的影響是必須要被考慮的。為了方便觀察電感對二階電路的影響，我們將式(5)的二階轉換函數重組如下：(6)其中：(7)(8)接著解出式（6）的兩個極點為：(9)其中，稱為諧振弳頻率(resonant radian frequency)，稱為等效模型的阻尼係數(damping factor)。若，則稱為臨界阻尼響應(critically damped response)；若，則兩極點為實數且稱為過阻尼響應(over- damped response)；若，則兩極點為複數且會產生震盪，這種響應稱為欠阻尼響應(underdamped response)。圖(五)時脈樹圖(五)是由模型所建出的一個時脈樹，輸入電壓與任一節點的電壓相比較可得：(10)假設輸入的電壓是一單位脈衝，則且在此時脈樹中任一節點之電壓是這些節點的單位脈衝響應。由5可以得到轉換函數中任一節點之阻尼係數和諧振弳頻率的二階近似表示式：RLC零時脈偏移演算法5(11)(12)其中式(11)、(12)和式(7)、(8)的表示方法極為相似，這代表式(7)、(8)為單一線段的及，假若此二階系統為時脈樹，則只需將原先的計算式改成如(11)、(12)的總加方法即可。此二階近似值的求法和Elmore（Wyatt）所提出的時脈樹近似解有相同的精確度。在時脈樹中任一節點的延遲時間與上升時間由5可得到式(13)、(14)： (13)(14)由式(13)及Elmore(Wyatt)之連線延遲模型證明，此處所提出50%連線延遲模型的一般解亦包含時脈樹以Elmore(Wyatt)方式計算出的特別解。參、零時脈偏移演算法由於晶片工作時脈的提升，電感效應變的愈來愈明顯，使得先前用來計算連線延遲的模型不再適用，因此必須將模型加以改良，把電感考慮進去進而產生模型。為了達到時脈偏移的最小化，Tsay9提出了零時脈偏移演算法(Exact zero-skew Algorithm)，這個演算法採用由下而上以不斷遞迴的方法來合併兩子樹(subtree)，且在兩子樹的連線線段上找到一時脈輸入點(clock entry point；CEP)，使得時脈輸入點到兩子樹的延遲時間相等，此時脈輸入點又稱為為栓點(tapping point)，我們擴充此方法至模型，提出零時脈偏移演算法。圖(六)是一個時脈樹的零時脈偏移等效電路，根據此等效電路得到從tapping point到兩個子樹的延遲時間關係式：(15)其中和分別是taping point到子樹一與子樹二的連線延遲時間，與是子樹一和子樹二的本身延遲時間。圖(六)時脈樹的零時脈偏移等效電路假設兩子樹的連線長度為，單位長度電感、電阻和電容分別為、，則tapping 6臺北科技大學學報第三十七之一期point到子樹一的距離、線電感、線電阻、線電容分別為、。同理，tapping point到子樹二的距離、線電感、線電阻、線電容分別為、。將以上的假設代入式(15)中的以及並加以展開，我們得到下列式子： (16)(17)我們令、分別為：(18)(19)則與可以改寫為： (20) (21)假設、均為零或相等，並將式(20)、(21)代入式(15)中來解，得到的公式解為：(22)式(22)的其範圍在。然而在晶片系統中，兩子樹的及均為零或是相等的機會並不大，將使得tapping point不一定會在兩子樹的連線線段上，我們歸納出下列兩種情況：情況1：Tapping point在兩子樹的連線線段上，即：(23)此情形表示從tapping point到子樹一的連線延遲時間加上子樹一自身的延遲時間，會等於子樹二的連線延遲時間加上子樹二自身的延遲時間，且可以在兩子樹的連線線段上找到tapping point的位置。情況2：Tapping point不在兩子樹的連線線段上，即：(24)此情形代表無法直接在兩子樹的連線線段上找到tapping point的位置，所以必須將子樹的連線線段加以延長，且延長部分的長度為，延遲時間為。在兩子樹的及不相等的情形下，我們使用逼近法求得tapping point的位置。圖(七)是一個零時脈偏移演算法的實際例子。假設點在座標(10, 10)，其負載電容為0.001pF，本身的延遲時間為0.3ps；點在座標(13, 14)，其負載電容為0.004pF，本身的延遲時間為0.6ps；點在座標(17, 3)，其負載電容為0.001pF，本身的延遲時間為0.4ps；點在座標(20, 12)，其負載電容為0.002pF，本身的延遲時間為0.4ps。單位長度電感為10pH，單位長度電阻為0.075，單位長度電容為0.118fF。利用MMM6的配對方法得到與配對，和為另一配對。利用零時脈偏移演算法計算出點在座標(18.786, 8.359)，使得到和的連線延遲相等；同理計算出與的tapping point，因為與的tapping point不在其連線線段上，為了達到零時脈偏移，必須將與的連線線段中加一線段，以延長時間滿足tpd（i）+ ti= t + tpd（i+1）+ ti+1，因此計算出延長部分的長度為4.408個單位與點的座標(12.7, 13.6)；接著與配對並利用同樣的方法得到點在座標(15.788, 10.941)，最後將連接到時脈源(clock source)。RLC零時脈偏移演算法7圖(七)利用零時脈偏移演算法的例子零時脈偏移演算法如圖(八)所示。假設在晶片系統中的一個集合內有n個時脈輸入點(clock entry point；CEP)，則可計算出由n個CEP所建立之時脈樹的層數s。先將最底層的CEP透過配對函式pair_up將其配對完成，由函式find_tapping_point計算配對點pi與pi+1的tapping point P，以及cal_path_delay函式的tapping point到pi以及pi+1之時脈延遲tpd（i）和tpd（i+1）。假若tpd（i）+ ti不等於tpd（i+1）+ ti+1，表示無法在配對點的連線線段上找到tapping point的位置，所以必須經由函式find_added_ segment找到兩點連線線段的延長部分，且滿足tpd（i）+ ti= t + tpd（i+1）+ ti+1，而此時tapping point是距離為y倍之兩點直線長度的地方，但是y的值必須符合0y1，否則在計算上升時間時會發生錯誤。如圖(九)所示，y值愈小，那麼由P、以及組成的子樹其連線線段就會縮短，使得連線延遲也跟著減少。待最底層配對點的tapping point都計算出之後，再往上計算上面一層的tapping point。Algorithm RLC_Zero-skew（n）s = number of levels in n;while（s!=0）num = number of CEP in s;if（num1） pair_up（s）; for（i = 1 ; i num ; i = i + 2） P = find_tapping_point（pi，pi+1）; tpd（i）= cal_path_delay（P，pi）; tpd（i+1）= cal_path_delay（P，pi+1）; if（tpd（i）+ ti != tpd（i+1）+ ti+1 ）; =find_added_segment（pi，pi+1）; P = y pi +（1-y） pi+1； / y is a constant, 0y1. s = s-1;圖(八)零時脈偏移演算法8臺北科技大學學報第三十七之一期圖(九)P在距離為y倍之處肆、實驗結果我們使用0.18m10製程的連線參數，如表(一)所示。依據5所提到的公式(13)，其計算與模擬結果在平衡樹（即分支線段與負載電容均為相等）與不平衡樹（即分支線段與負載電容均為不等）情形下的平均誤差範圍分別是4以及20。由圖(十)與圖(十一)分別是用MMM6方法所建立的平衡樹與不平衡樹，端點一至四（即t1至t4）的本身延遲為0.3ps。我們用此二樹實驗零時脈偏移演算法，並將計算的延遲時間與SPICE模擬結果相比較，表(二)是實驗所得結果。圖(十)平衡樹RLC零時脈偏移演算法9圖(十一)不平衡樹表（一）0.18m製程的連線參數0.18m製程()()()製程參數0.075100.118表（二）平衡與不平衡樹的實驗結果平衡樹不平衡樹SPICE（ps）our（ps）誤差(%)SPICE（ps）our（ps）誤差(%)端點11.11.1193881.7625451.4771.460740.67434端點21.11.1193881.7625451.4781.460740.741543端點31.11.1193881.7625451.3581.3712230.97371端點41.11.1193881.7625451.3571.3743591.279218平均誤差1.762545%0.917202%由表(二)的實驗結果可知零時脈偏移演算法其誤差值在平衡樹與不平衡樹的情形下，其誤差分別為1.762545和0.917202，此結果符合5的模擬誤差範圍，這表示經由零時脈偏移演算法所得的延遲時間為正確的計算方法。如果我們再增加晶片上的時脈端點數，其位置、端點電容以及端點本身的延遲均以亂數產生，並將零時脈偏移演算法應用在MMM6與GMA7建立完成的不平衡時脈樹上，同樣計算出從時脈源到各端點的延遲時間，並與SPICE模擬結果相比較，可得表(三)實驗結果，由實驗得知，其模擬誤差最多為6.289383。所以由表(二)及表(三)實驗結果可知不平衡樹的誤差都在20之內甚至誤差更小。這表示零時脈偏移演算法不會因時脈的繞線方法、時脈端點的端點電容及端點本身的延遲不同而有所不正確，所以此方法可以取代模型的零時脈10臺北科技大學學報第三十七之一期偏移方法，進而在電路的延遲計算上更接近實際的延遲時間。表（三）多數點的實驗結果端點數8163264MMM的平均誤差4.5652096.2893835.1651933.071945GMA的平均誤差5.7038824.9900155.4493614.388705伍、結論與未來方向針對系統晶片的工作時脈所產生的電感效應，我們提出了零時脈偏移演算法，將時脈偏移降至最小且誤差均在5的容許範圍之內，不過在5當中的平衡樹與不平衡樹之延遲時間計算公式，以不平衡樹之20誤差最為嚴重，但在實際應用中，時脈樹為平衡樹的機會並不高，因此我們未來的目標是如何改善不平衡樹的時脈延遲計算公式，以達到能更接近實際模擬的結果。參考文獻1T. Mitsuhashi, T. Aoki, M. Murakata, and K. Yoshida, “Physical design CAD in deep sub-micron era,” Proc. of European on Design Automation Conference and Exhibition, pp. 350-355, 1996.2W. Li, D. Zhou, H. Kim, and X. Zeng, “Automatic clock tree design with IPs in the system,” in Proc. of ISCAS, pp. 387-390, 2001.3W. C. Elmore, “The transient response of damped linear networks,” J. Appl. Phys., vol. 19, pp. 55-63, Jan. 1948.4A. B. Kahng and S. Muddu, “An analytical delay model for RLC interconnections,” IEEE Trans. Computer-Aided Design, vol. 16, pp.1507-1514, Dec. 1997.5 Y