基于改進四叉樹模型的統計靜態時序分析

潘 旻，喻明艷

（哈爾濱工業大學國際微電子中心，威海264209）

·大規模集成電路設計、制造與應用·

基于改進四叉樹模型的統計靜態時序分析

潘 旻，喻明艷

（哈爾濱工業大學國際微電子中心，威海264209）

提出一種改進的靜態時序分析方法，該方法通過對片內工藝變化參數隨機變量進行改進四叉樹模型分解，然后建立多層分布空間關系指數函數方程組求得片內相鄰、次鄰塊間影響的擬合權重系數，使得非獨立的隨機變量轉化為一系列相互獨立的隨機變量線性相加的形式，最后遍歷獲取表征片內工藝參數變化空間關系的協方差矩陣。通過和Monte-Carlo方法以及Minnssta方法仿真結果對比，驗證了改進方法的精確性，同時也表明了該方法在降低片內非獨立空間關系復雜性方面的有效性。

工藝參數變化；空間關系；統計；四叉樹；靜態時序分析

1 引 言

隨著超大規模集成電路制造工藝逐步邁入深亞微米時代，芯片上互連線以及器件的尺寸和間隔迅速縮小，片上系統的信號頻率也急劇增加［1］。這些趨勢給互連線的寄生電阻和寄生電容帶來了不可忽視的影響，并隨之引發決定系統性能和可靠性的相關問題，比如電路串擾和電路延時。電路延時信息是靜態時序分析中時序驗證的基礎，由電磁波傳輸延時和上升沿延時組成，它決定了電路時鐘頻率的上限。實際上，由于芯片制造工藝的局限性，片內工藝參數并不是常數，然而即使存在很微小的變化都會帶來電路延時的巨大變化，所以在靜態時序分析中考慮工藝參數變化是必不可少的。近些年來很多學者和研究人員致力于這一領域，并有了一定的研究成果［2-4］。

現如今，有很多不同的并且行之有效的仿真方法來對帶隨機變量的集成電路問題進行時序分析。傳統上，人們會采用計算機仿真軟件例如PSpice，MentorGraphics，Cadence，Viewlogic，MicroSim等來進行Monte-Carlo統計分析［5］。雖然Monte-Carlo方法能夠逼真的描述隨機對象的特性和實驗過程，但它的收斂速度和一些數值方法相比比較慢，并且它的誤差大小是不確定的。為了克服這些缺點，采用基于改進四叉樹多層分布空間關系模型的新方法，該方法能夠很好的處理片內工藝參數非獨立隨機變量，充分考慮了片內相鄰、次鄰塊間工藝參數的空間關系，求得統計靜態時序分析中所需的協方差矩陣。和Monte-Carlo方法相比，它只需耗費很少的時間就能達到與其差不多的精確度。

2 片內和片間工藝參數變化分析

工藝參數變化通常分為片間變化和片內變化這兩種成分，其中片內變化可以進一步分解為隨機變量和空間相關變量。因為這里考慮了片內變化的空間關系，所以這些隨機變量并不是相互獨立的，它們之間的關系可以用協方差矩陣的形式來表示，在這樣的空間關系架構下，布局越近，門與門之間的空間關系越強，反之亦然。這種片內工藝參數間的空間關系可用簡單的由如圖1所示的平面模型來建模。從圖1可以看出，在隨機變量服從正態分布的情況下，參照點O和距離其最遠點（W，H）處的工藝參數變化差值達到了最大的3σ，呈現的空間相關關系也就最小。同樣，當把晶片劃分為塊狀模型來建模時，靠的越近的塊空間關系越強，相反，靠的越遠的塊之間空間關系就越小。很多空間關系模型，例如文獻［6］在建模塊與塊之間的空間關系時，只考慮了相鄰塊間的空間關系，而忽略了次鄰塊間，即對角塊間的空間關系，這就會帶來很大的誤差。

圖1 片內工藝參數變化平面模型圖

為了求得片內工藝參數變化的空間關系，首先需要對片內和片間的工藝參數變量進行建模。傳統上，一個特定晶片上任意門k的工藝參數變化量Ptotal，k是名義上的工藝參數值Pnom，片間的門工藝參數變化量△Pinter和片內的門工藝參數變化量△Pintra，k三者的代數和［3］：

其中，Pnom代表所有晶片的工藝參數變化均值，△Pinter和△Pintra，k都是隨機變量，在建模時，可以假設△Pinter和△Pintra，k都服從截尾的正態分布，當然其他任何合適的分布都可以采用。那么根據這個工藝參數變化量的模型，任意門k的延時dk可以表示為：

式中的函數Dk一般情況下是非線性方程，這就比較難處理，但是片內工藝參數隨機變化量△Pinter和△Pintra，k通常都很小，3σ值小于Pnom的15%。因此，門延時的變化和工藝參數的變化可視為線性關系，從而式（2）就可以處理成如下形式：

式（4）采用了一個簡單的線性近似，這樣的近似對目前的工藝參數變化來說有很好的精確度［7］。由于這里并沒有考慮片內工藝參數變化隨機變量間的空間關系，所以dk是一系列相互獨立的隨機變量和的形式，這就非常方便后續處理。而一旦引入空間關系，為了降低分析的難度，就要將非獨立的變量△Pintra，k進行分解，進而轉化為獨立的隨機變量，這就需要求取表征塊間空間關系的協方差矩陣。

3 考慮空間關系的改進四叉樹分層模型

為了將空間關系有效的考慮進來，首先將晶片的面積分割為四叉樹多層次分布［8］，對于每個層次i（i＝0，1，2，...，n），晶片面積被劃分成2i×2i個方格。圖2顯示的就是一個晶片通過3層分割的例子，其中最頂層（第0層）只有一個區域，并且這個區域范圍覆蓋了整個晶片，被以下所有的層次共享，最底層（第n層）擁有4n個區域。分配給每個特定層次下所有的隨機變量相同的概率分布以及將整個片內變量分給這些不同的層次，這樣每層的每個區域（i，j）和一個獨立的正態隨機變量聯系起來，以此來表示總共片內工藝參數變化量的一部分成分，那么片內門k的工藝參數變化就可以定義為所有與之相關的隨機變量△Pi，j代數和的形式：

其中△Pi，j是和四叉樹相關的服從正態分布的隨機變量，△Prandom，k是每個門k和空間關系無關的獨立隨機變量，層次i的變化范圍是從0到n，任何特定層次下的區域j指的是其投影能夠覆蓋到門k位置的那個區域。

這里定義在四叉樹中每個節點的任意一個子樹根據相對位置關系，和其余三個子樹存在且僅有兩種空間關系，即相鄰關系和對角關系，那么就可以將每個層次任意網格中的變量對所投影的子層次網格變量的空間影響進行建模。

圖2 四叉樹多層次分布模型圖

現在以第二層，即圖2中的第1層和區域（1，1）相關的區域為研究對象，那么區域（1，1），（1，2），（1，3），（1，4）的片內門工藝參數變化量就可以表示如下：

將上四式改寫為用矩陣表示的緊湊形式：

其中

因為第i層每個網格區域的邊長為W／2i，所以就有dsel＝0，dadjW＝W／2i，dadjH＝H／2i，ddig＝（W2＋H2）1／2／2i。然后這里假定模型的空間關系影響函數為指數函數形式［9］，則第i＝1層的關于0層變量的分布關系擬合權重系數方程組為：

求解式（12）方程組，就能得到頂層的擬合權重系數矩陣V0的值。圖3所示的是將整個晶片細化成3層后的四叉樹網格投影圖，通過這樣不斷對生成的網格進行進一步細化，反復求解分布關系擬合權重系數方程組，第i層的空間關系影響擬合權重系數矩陣Vi就能依次被求出。

4 遍歷求取空間關系協方差矩陣

當空間關系模型確立后，只要選取合適的層數，底層每個區域的隨機變量組成成分就可以確定，片內工藝參數變化就可以表示為如下形式：

圖3 3層四叉樹網格投影圖

其中任何特定層次下的區域j指的是和具體門的位置相交的那個區域，i的變化范圍從0到n-1。這樣底層每個網格的工藝參數變化都可以用一系列獨立的隨機變量成分線性相加的形式表示，所有網格的片內變化可以由2n×2n的矩陣X表征：

通過遍歷矩陣X中每個元素就可以求得每個網格的方差以及和其處于相鄰關系以及斜對角關系網格的協方差：

在改進模型中，某些布置在同個網格中的門要比雖然布置在很靠近的位置，但是落在不同網格中的門的相關關系來的強，例如圖3所示，門B和門A之間的空間關系要強于門B和門C之間的空間關系，雖然門B與門C布置的非常近。因此，對四叉樹空間關系模型層次分的越細，最底層相同區域、相鄰區域以及對角區域內的門與門之間越能保持工藝參數變化的一致性，雖然這樣能更準確地模擬真實情況，但不可避免的是建模復雜度也就越高，仿真越耗時，因此為了適當地對片內工藝參數進行建模，就需要在準確度和復雜度之間做一個折衷。

5 改進的四叉樹模型方法仿真分析

實驗模擬在Linux下完成，Linux內核版本為Linux 2.6.9，操作系統為Red Hat Enterprise Linux AS release 4（Nahant Update 8）。實驗硬件配置為Intel（R）Xeon（R）型號的CPU，主頻為2.4GH，內存為12G。仿真分析的benchmark電路是s38417，這里考慮以下這些晶體管的工藝參數［10］：柵長Lg，柵寬Wg，線寬Wi，線厚Ti，ILD厚度HILD。

圖4和圖5分別是電路延時的累積分布密度曲線和概率密度函數曲線仿真結果。改進方法的延時均值誤差為-0.0753%，延時標準差誤差為-0.0592%，從圖中也可以看出較Minnssta方法而言，改進方法和Monte-Carlo方法仿真結果更為接近，這也說明改進方法是行之有效的。

圖4 仿真電路延時的累積分布函數曲線

6 結束語

針對片內工藝參數的非獨立隨機變化，提出了改進的基于四叉樹多層分布空間的關系模型方法，考慮了處于相鄰位置和次鄰位置網格間的空間影響關系，求解出了線性擬合權重系數，并進一步得到包含片內不同位置空間關系的協方差矩陣。通過實驗仿真，驗證了該方法的精確性和有效性，為解決統計靜態時序分析中其他種類的含非獨立隨機變量的獨立主成分分解問題提供了新的思路。

圖5 仿真電路延時的概率密度函數曲線

［1］JCong，Z Pan，L He，et al.Interconnect Design for Deep Submicron IC’s［J］.IEEE／ACM International Conference on Computer-Aided Design，1997：478-485.

［2］H Chang，S S Sapatnekar.Statistical Timing Analysis Under Spatial Correlations［J］.IEEE Trans.on Computer-Aided Design of Integrated Circuits and Systems，2005，24（9）：1467-1482.

［3］A Agarwal，D Blaauw，V Zolotov，et al.Statistical Delay Computation Considering Spatial Correlations［J］.IEEE／ACM Asia-Pacific Design Automation Conf，2003：271-276.

［4］B Stine，D Boning，JChung.Analysis and Decomposition of Spatial Variation in Integrated Circuit Processes and Devices［J］.IEEE Trans.on Semicond.Manuf，1997，10（1）：24-41.

［5］D Frenkel.Introduction to Monte Carlo Methods［J］.NIC Series，2004（23）：29-60.

［6］H Chang，SSSapatnekar.Statistical Timing Analysis Considering Spatial Correlations Using a Single PERT-like Traversal［J］.IEEE／ACM International Conference on Computer-Aided Design，2003：621-625.

［7］A Gattiker，SNassif，R Dinakar，et al.Timing Yield Estimation from Static Timing Analysis［J］.Quality Electronic Design，2001：437-442.

［8］A Agarwal，D Blaauw，V Zolotov.Statistical Timing Analysis for Intra-Die Process Variations with Spatial Correlations［J］.IEEE／ACM International Conference on Computer-Aided Design，2003：900-907.

［9］R Shen，SX.-D.Tan，JXiong.A Linear Algorithm for Full-Chip Statistical Leakage Power Analysis Considering Weak Spatial Correlation［J］.IEEE／ACM International Great Lakes Symposium on VLSI，2010：227-232.

［10］SNassif.Delay variability：Sources，impact and trends［J］.IEEE International Solid-State Circuits Conference，2000：368-369.

Statistical Static Tim ing Analysis Based on Modified Quad-Tree Model

PAN Min，YU Ming-yan
（International Microelectronics Center，Harbin Institute of Technology，Weihai264209，China）

In this paper，amodified approach for static timing analysis is presented.It decomposes intra-die random variables based on modified quad-tree distribution model and makes the dependent random variables as a linear sum of independent random variables，by solving themulti-level distributed spatial correlation equations，which are related to exponential functions，to obtain the fittingweight coefficients of adjacentand diagonal intra-die squares.Consequently，the covariancematrix，which represents for the spatial correlations of intra-die process variations，can be derived through traversal.The simulation results，from Monte-Carlomethod and Minnsstamethod，confirm the accuracy ofmodified approach and show that it is effective in reducing the complexity of analyzing the dependent spatial correlations.

Process Variation；Spatial Correlation；Statistical；Quad-Tree；STA

10.3969／j.issn.1002-2279.2014.05.001

TN402

：A

：1002-2279（2014）05-0001-04

潘旻（1989-），男，江蘇南通人，碩士研究生，主研方向：電子電路系統建模與數值仿真，數字集成電路設計。

2014-02-12