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

潘 旻，喻明艷

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

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

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

潘 旻，喻明艷

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

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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 四叉樹(shù)多層次分布模型圖

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

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

其中

因?yàn)榈趇層每個(gè)網(wǎng)格區(qū)域的邊長(zhǎng)為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所示的是將整個(gè)晶片細(xì)化成3層后的四叉樹(shù)網(wǎng)格投影圖，通過(guò)這樣不斷對(duì)生成的網(wǎng)格進(jìn)行進(jìn)一步細(xì)化，反復(fù)求解分布關(guān)系擬合權(quán)重系數(shù)方程組，第i層的空間關(guān)系影響擬合權(quán)重系數(shù)矩陣Vi就能依次被求出。

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

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

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

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

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

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

5 改進(jìn)的四叉樹(shù)模型方法仿真分析

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

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

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

6 結(jié)束語(yǔ)

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

圖5 仿真電路延時(shí)的概率密度函數(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è)計(jì)。

2014-02-12