潘 旻，喻明艷

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

·大規(guī)模集成電路設(shè)計、制造與應(yīng)用·

基于改進四叉樹模型的統(tǒng)計靜態(tài)時序分析

潘 旻，喻明艷

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

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

工藝參數(shù)變化；空間關(guān)系；統(tǒng)計；四叉樹；靜態(tài)時序分析

1 引 言

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

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

2 片內(nèi)和片間工藝參數(shù)變化分析

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

圖1 片內(nèi)工藝參數(shù)變化平面模型圖

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

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

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

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

3 考慮空間關(guān)系的改進四叉樹分層模型

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

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

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

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

現(xiàn)在以第二層，即圖2中的第1層和區(qū)域（1，1）相關(guān)的區(qū)域為研究對象，那么區(qū)域（1，1），（1，2），（1，3），（1，4）的片內(nèi)門工藝參數(shù)變化量就可以表示如下：

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

其中

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

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

4 遍歷求取空間關(guān)系協(xié)方差矩陣

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

圖3 3層四叉樹網(wǎng)格投影圖

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

通過遍歷矩陣X中每個元素就可以求得每個網(wǎng)格的方差以及和其處于相鄰關(guān)系以及斜對角關(guān)系網(wǎng)格的協(xié)方差：

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

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

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

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

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

6 結(jié)束語

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

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

［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-），男，江蘇南通人，碩士研究生，主研方向：電子電路系統(tǒng)建模與數(shù)值仿真，數(shù)字集成電路設(shè)計。

2014-02-12