一種考慮空間關聯工藝偏差的統計靜態時序分析方法

喻 偉楊海鋼劉 洋黃 娟蔡博睿陳 銳

①(中國科學院電子學研究所 北京 100190)

②(中國科學院大學 北京 100086)

一種考慮空間關聯工藝偏差的統計靜態時序分析方法

喻 偉①②楊海鋼*①劉 洋①黃 娟①蔡博睿①陳 銳①②

①(中國科學院電子學研究所 北京 100190)

②(中國科學院大學 北京 100086)

為了準確評估工藝參數偏差對電路延時的影響，該文提出一種考慮空間關聯工藝偏差的統計靜態時序分析方法。該方法采用一種考慮非高斯分布工藝參數的二階延時模型，通過引入臨時變量，將2維非線性模型降階為1維線性模型；再通過計算到達時間的緊密度概率、均值、二階矩、方差及敏感度系數，完成了非線性非高斯延時表達式的求和、求極大值操作。經ISCAS89電路集測試表明，與蒙特卡洛仿真(MC)相比，該方法對應延時分布的均值、標準差、5%延時點及95%延時點的平均相對誤差分別為0.81%, -0.72%, 2.23%及-0.05%，而運行時間僅為蒙特卡洛仿真的0.21%，證明該方法具有較高的準確度和較快的運行速度。

集成電路；統計靜態時序分析；空間關聯；非高斯非線性；工藝偏差；延時模型

1 引言

隨著集成電路工藝的特征尺寸縮小到納米尺度，工藝參數偏差的影響變得越來越顯著。這些工藝偏差導致了芯片電氣參數隨機變化，并給電路的時序評估帶來極大挑戰。為了解決工藝偏差帶來的影響，傳統的靜態時序分析(Static Timing Analysis, STA)，通過在不同的工藝角下執行時序裕量檢查，來實現電路的時序評估。然而，隨著工藝參數偏差源的增多，需要考慮的工藝角數量隨之增多，基于多工藝角的STA變得越來越費時；而且由于片內邏輯門不同位置的工藝參數存在空間關聯，多工藝角STA也沒有考慮到這些關聯統計信息，從而使得評估結果過于悲觀。在利用這些悲觀結果指導時序優化時，將會造成嚴重的資源浪費，并影響到電路功耗、面積等其他性能參數的評估。

因此，與傳統多工藝角STA相比，統計靜態時序分析(Statistical Static Timing Analysis, SSTA)顯得更為可靠。SSTA的處理對象為延時的概率分布函數(Probability Distribution Function, PDF)和累計分布函數(Cumulative Distribution Function, CDF)，換句話說，SSTA利用工藝參數偏差的統計信息來評估最終延時的統計分布。盡管影響SSTA延時變化的因素很多[1-9]，但隨著工藝尺寸的不斷縮小，在深亞微米尺度下工藝參數偏差仍然是影響延時變化的最大因素。考慮工藝參數偏差的SSTA方法雖不是最新的研究熱點，但在算法分析方面還是為國內的研究開展提供了方向；而且從目前SSTA EDA工具的開發經驗來看，考慮工藝參數偏差的SSTA方法顯得更切實際。

考慮工藝偏差的SSTA方法大致可以分為兩類：一類是基于路徑的方法[6]，這類方法通常先利用傳統的STA方法找到一定數量的關鍵路徑，然后再采用基于路徑的分析流程來運行參數化SSTA，由于需要遍歷一定數量的路徑，其時間代價往往較高；另一類是基于塊的方法[7-9]，這類方法通常先采用基于項目評估技術[10](Program Evaluation and Review Technique, PERT)的拓撲技術遍歷時序圖，然后再完成從輸入到輸出的延時分布傳遞，由于不需逐個遍歷路徑，其時間代價相對較小。從區分工藝參數分布和延時依賴關系的角度看，這些基于塊的SSTA方法大致又可以分為4類：(1)線性高斯SSTA，在這類方法中，研究人員將工藝參數假設為高斯分布，在利用主元分析(Principle Component Analysis, PCA)技術[11]把那些空間關聯高斯變量轉換為彼此獨立高斯變量后，將延時表示為獨立高斯變量的一階線性表達式，如文獻[7]，這類方法忽略了工藝參數的非高斯分布形式和延時變量的非線性表示方式，因而是一種不完備的SSTA分析方法；(2)非線性高斯SSTA：在這類方法中，研究人員仍將工藝參數假設為高斯分布，在利用PCA技術進行變量轉換后，將延時表示為獨立高斯變量的非線性表達式，特別是二階表達式，如文獻[8]，由于這類方法同樣忽略了工藝參數的非高斯分布形式，所以也是一種不完備的SSTA分析方法；(3)線性非高斯SSTA：在這類方法中，研究人員不再將工藝參數局限于高斯分布，可以是任意非高斯分布，在利用獨立元分析(Independent Component Analysis, ICA)技術[12]把那些空間關聯非高斯變量轉換為彼此獨立非高斯變量后，將延時表示為工藝參數的一階線性表達式，如文獻[9]。由于這類方法也忽略了延時變量的非線性表示方式，同樣是一種不完備的SSTA分析方法；(4)非線性非高斯SSTA：這類方法是其他3類方法的綜合，工藝參數既能滿足任意分布，延時又可以是工藝參數的非線性表達式，因此是一種更通用更完備的方法。

基于以上分析，本文提出了一種基于塊的考慮空間關聯非高斯分布工藝偏差的非線性統計靜態時序分析方法。這種方法首先假設了芯片內不同位置的工藝參數存在空間關聯性，使其更加符合實際情況；然后將工藝參數假設為高斯分布和非高斯分布并存的情形，并將延時表示為工藝參數的二階表達式；最后利用降階方法將非線性延時模型降階為線性延時模型，通過計算延時的緊密度概率、均值、二階矩、方差及敏感度系數，完成非線性非高斯延時表達式的求和及求極大值操作。本文方法避免了前文方法中工藝參數的不完備表達，改進了延時變量的建模方法，并提高了SSTA分析的完整性和準確性。

2 工藝參數的空間關聯與電路延時的非高斯非線性屬性

2.1 SSTA中的工藝參數空間關聯

為了探究芯片內邏輯門不同位置工藝參數之間的空間關聯性，本文借鑒了文獻[7]提出的方格樹模型，如圖1所示。在此模型中，芯片被抽象為一個多層次的方格樹，在樹的第i層，芯片被劃分為2i×2i個方格。這種樹形結構在不同層次的方格間形成一種等級關系，若較高層的一個方格和較低層的某些方格共享面積，那么較高層的這個方格就被稱為父方格，較低層的方格則被稱為子方格。對于同一個方格內的不同邏輯門，它們具有相同的工藝參數敏感度，如頂層內的所有邏輯門就具有相同的工藝參數敏感度；對于不同方格內的不同邏輯門，其工藝參數的空間關聯性由它們的父方格所決定。

圖1 工藝參數空間關聯的方格模型示意圖

在每一個方格內，本文用一個單獨的隨機變量表示一個工藝參數，最底層方格內的邏輯門工藝參數是由其自身方格內的工藝參數和所有父方格內的工藝參數共同決定的。例如在圖1(a)中，方格[0,1]為[1,1]的父方格，方格[1,1]為[2,1]的父方格，那么方格[2,1]內的邏輯門溝道長度L(2,1)就可以表示為如式(1)與物理位置相關的參數化表達式：

其中，L0為溝道長度本征值，ΔL2,1, ΔL1,1, ΔL1,0分別表示方格[2,1], [1,1], [1,0]內的溝道長度偏差。

不同方格內工藝參數的空間關聯程度是由其共同的父方格所決定的，例如方格[2,1], [2,2]及[2,16]內的邏輯門溝道長度分別可以表示為

在式(2)中，方格[2,1]和[2,2]共享兩個父方格(ΔL1,1,ΔL0,1)，而方格[2,1]和[2,16]只共享一個父方格(ΔL0,1)。因此，與方格[2,1]和[2,16]對應空間關聯程度相比，方格[2,1]和[2,2]之間的工藝參數空間關聯程度更高，這也表明兩個邏輯門離得越近，其工藝參數空間關聯程度越高，邏輯門的工藝參數變化越具有相似性。

另外需要指出的是：(1)空間關聯僅局限于同一種工藝參數，不同的工藝參數之間彼此獨立，例如方格[2,1]內的溝道長度僅與其它方格內的溝道長度存在關聯，而和其它諸如柵氧化層厚度、半導體摻雜濃度等工藝參數沒有關系；(2)對于一個3層的方格樹，在表示最底層兩個方格內任一工藝參數的關聯關系時，需要一個16×16的協方差矩陣；(3)對于頂層方格，由于它是所有其它方格的父方格，所以它可以用來表示片外工藝參數偏差，而片內工藝參數偏差則可由其它層次的方格來表示，這樣本文方格模型就可以表示所有的片內偏差和片外偏差。

2.2 SSTA中的非高斯非線性

隨著工藝尺寸的減小，電路延時呈現出越來越多的非高斯屬性。實際分析時，一些工藝參數往往會極大地偏離高斯分布，如互連線的金屬寬度會呈現出非對稱的概率分布，半導體摻雜濃度會呈現出泊松分布等；同時由于片內空間鄰近效應的存在，這些非高斯分布工藝參數彼此空間關聯，若依據傳統的SSTA方法將這些工藝參數表示為高斯分布，則很可能會導致電路延時的PDF嚴重偏離實際情形。

隨著工藝尺寸的減小，電路延時也呈現出越來越多的非線性屬性。因為邏輯門延時和互連線延時往往是工藝參數的參數化表達式，當工藝參數偏差較小時，一階泰勒展開式足夠精確；然而隨著工藝參數偏差的增大，一階線性表達式已不再適用，延時表達更多地呈現非線性特征。另外，對于基于塊的SSTA方法，在時序圖上傳遞延時分布時，執行了兩個基本操作：求和、求極大值。求和一般適用于單輸入邏輯單元，如反相器、緩沖器和互連線等，若輸入信號到達時間和單輸入邏輯單元延時都服從高斯分布，那么輸出信號到達時間也是一個高斯分布，所以求和操作是一個線性操作；求極大值一般適用于多輸入邏輯單元，如與門、或門等，即使兩個隨機變量A, B相互獨立且滿足高斯分布，其極大值仍為非高斯分布，所以求極大值操作是一個非線性操作。同時還需要指出的是，在求解延時偏斜時，需要計算其三階矩，如果延時為一階線性表達，那么其三階矩則為零，這與實際非高斯分布隨機變量對應延時偏斜非零的事實相矛盾，所以在計算延時偏斜時，也有必要將延時表示為非線性表達式，如二階表達式等。

針對SSTA中工藝參數的空間關聯性及延時表達的非高斯非線性，本文提出一種改進的空間關聯統計靜態時序分析(Correlated Statistical Static Timing Analysis, CSSTA)方法，從而將這兩個問題考慮進來。

3 CSSTA算法流程

本文CSSTA算法流程如圖2所示。首先根據前文的非高斯非線性分析，將影響延時分布的工藝參數劃分為高斯參數和非高斯參數兩部分，將空間關聯的高斯分布(非高斯分布)工藝參數轉化為一組彼此獨立的高斯分布(非高斯分布)隨機變量，并將延時表示為這組獨立隨機變量的二階非線性模型；然后基于二階非高斯非線性模型，采用基于PERT的延時分布拓撲傳遞方法，針對時序圖上的每一個節點執行求和操作(sum)和求極大值操作(max)，以期獲得節點到達時間的參數化表達式，并通過計算節點到達時間的緊密度概率、均值、二階矩、方差及敏感度系數，得到參數化延時表達式的近似擬合；最后根據參數化延時表達式的具體形式，通過匹配工藝參數的k階矩，得到經由PCA (ICA)轉化后的獨立隨機變量的矩，并根據這些獨立隨機變量的矩和延時變量非線性模型，得到延時變量的矩，從而利用延時變量的矩和概率提取流程算法，生成延時變量的PDF。

3.1 基于工藝參數偏差的延時建模

圖2 CSSTA算法流程圖

為了描述工藝參數偏差對電路延時的非線性影響，本文采用基于截斷的泰勒展開多項式，將一階線性表達式擴展為二階延時模型：

其中，D為對應邏輯門延時或輸入端到達時間的隨機變量，d0為D的本征值，xi為空間關聯工藝參數高斯變量，yj為空間關聯工藝參數非高斯變量，z為空間獨立工藝參數隨機變量；,分別為第i個高斯分布工藝參數的一階、二階敏感度系數，,分別為第j個非高斯分布工藝參數的一階、二階敏感度系數，e為隨機變量z的敏感度系數；n和m分別為空間關聯高斯分布和非高斯分布工藝參數的個數。

考慮到正交變換的處理流程，將D表示為工藝參數的向量表達式：

其中x=(x1,x2,…,xn)T為空間關聯高斯分布工藝參數向量，y=(y1,y2,…,ym)T為空間關聯非高斯分布工藝參數向量；p′=(,,…,)為一階項x的敏感度系數向量，q′=(,…,)為一階項y的敏感度系數向量，p′為n×n對角矩陣，其對角線系數為二階項x的敏感度系數，q′為m×m對角矩陣，其對角線系數為二階項y的敏感度系數。

接著，運用PCA (ICA)技術，將空間關聯的高斯分布工藝參數向量x(空間關聯的非高斯分布工藝參數向量y)轉換為彼此獨立的高斯分布工藝參數向量X(彼此獨立的非高斯分布工藝參數向量Y)，將D進一步表示為

其中，X為轉換后的高斯分布工藝參數向量，Y為轉換后的非高斯分布工藝參數向量；P′=(,…,)為一階項X的敏感度系數向量，Q′=(,…,)為一階項Y的敏感度系數向量，P′為n×n對角矩陣，其對角線系數為二階項X的敏感度系數，Q′為m×m對角矩陣，其對角線系數為二階項Y的敏感度系數。需要注意的是，對于空間獨立隨機變量z，根據中心極限定理(不同獨立隨機變量的疊加滿足高斯分布)，可以將z轉換為一個均值為0，方差為1的標準正態分布變量Z,Z～N(0,1)，同時所有的Xi,Yj也滿足均值為0,-1≤Xi≤1, -1≤Yj≤1。

3.2 非線性非高斯延時的統計操作

參數化基于塊的SSTA方法通常將電路抽象為一個統計時序圖G=(N,E,ns,nf)。其中，N為節點集合，E為邊集合，ns為源節點，nf為終節點。從源節點到終節點傳遞延時分布時，通過執行求和或求極大值操作，就可以依次求出節點到達時間的概率分布(參數化表達式)，如圖3所示。

圖3 統計時序圖中求和、求極大值操作及延時分布傳遞

3.2.1 求和 因為求和操作是一個線性操作，所以求和結果應該與輸入到達時間及門延時具有相同的表達式。參考式(5)，考慮兩個非線性非高斯延時表達式A和B：

求和結果C=A+B可以表示為

其中

3.2.2 求極大值 因為求極大值是一個非線性操作，所以為了獲取max(A,B)的近似估計，本文借鑒了線性高斯SSTA[7]中的處理方法。本文算法通過引入臨時變量，將2維非線性模型降階為1維線性模型；然后在此1維線性模型的基礎上，通過計算max(A, B)的緊密度概率、均值、二階矩及方差，獲得了max(A,B)的近似表達。

觀察式(6)，將其中的隨機變量表達式分解為4部分：線性高斯部分、非線性高斯部分、線性非高斯部分及非線性非高斯部分；令X為線性高斯隨機變iL量，XiN為非線性高斯隨機變量，YjL為線性非高斯隨機變量，YjN為非線性非高斯隨機變量，則式(5)可表示為

其中，h(XiN,YjL,YjN)為一個臨時變量，它代表了線性高斯部分以外的隨機變量表達式。

假設非線性高斯部分、線性非高斯部分及非線性非高斯部分是固定的，那么臨時變量h(XiN,YjL, YjN)也將固定，將h(XiN,YjL,YjN)和d0當作一個整體，重寫式(9)為

式(11)可以看作為一個本征值為d0+h(XiN,YjL,YjN)的一階線性表達式，再次考慮兩個用式(11)表示的A和B：

于是，當XiN,YjL及YjN固定時，max(A,B)的臨時緊密度概率TA,cond、臨時均值μC,cond及臨時二階矩m2C,cond就可以表示為XiN,YjL及YjN的函數。

同時，由于XiL的概率分布可以簡單地等效為XiN,YjL及YjN的聯合概率分布：

在用d0A+hA(XiN,YjL,YjN)和d0B+hB(XiN,YjL, YjN)替換掉線性高斯延時表達式中的d0A和d0B后，將臨時緊密度概率、臨時均值及臨時二階矩在聯合概率分布的隨機變量參數空間內積分，就可以計算出max(A,B)的正式緊密度概率TA、正式均值μC、正式二階矩m2C及正式方差。

在獲得max(A,B)的緊密度概率、均值及二階矩之后，就可以利用Cappr來近似估計max(A,B)。因為系數是和Pi′B的線性組合，系數hC是hA和hB的線性組合，所以可以將Cappr視為一階線性情形

令Cappr的方差為var(Cappr)，則Cappr的相關參數為

為了突出本文非線性非高斯延時表達式與傳統線性高斯延時表達式求極大值操作的對比結果，圖4給出了包含兩個隨機變量的max(A,B)近似示意圖，其中圖4(a)為線性高斯情形，圖4(b)為本文非線性非高斯情形。在圖4(b)中，虛曲線分別為非線性表達式A, B，彎折實曲線為準確的max(A,B)，光滑實曲線為近似的Cappr。可以看出，光滑實曲線Cappr和彎折實曲線max(A,B)具有較高的擬合度，證明本文參數化表達式的近似擬合結果具有一定的合理性。若把各個隨機變量從1維擴展到多維，這種圖示方法仍然適用，只不過圖中曲線變成了曲面。

3.3 基于矩匹配的延時評估

在計算延時或到達時間的PDF(CDF)時，本文采用了文獻[13]提出的概率提取流程算法(Asymptotic Probability Extraction, APEX)。算法首先將一個隨機變量的二階矩作為輸入，采用漸進波形評估技術來匹配這個隨機變量的2M階矩，從而生成一個M階的線性無關系統；接著利用這個M階線性無關系統的沖激響應(階躍響應)來近似擬合隨機變量的PDF (CDF)。

圖4 max(A,B)的準確表達與近似表達示意圖

本文以一個簡單的例子解釋基于矩匹配的PDF評估方法。假設w, l為空間關聯高斯分布(非高斯分布)隨機變量，且w和l相互獨立。令= p·w+q·l ，其中=D-μ，經PCA, ICA轉換后，=P·W+Q·L ，其中W, L為高斯分布(非高斯分布)彼此獨立隨機變量，那么的k階矩就可以用式(18)的二項展開式表示。

因為W和L的所有i階矩可按文獻[9]所提方法求得，所以根據式(18)計算得到的2M矩后，利用M階線性無關系統的沖激響應即可近似擬合的實際PDF。

式(19)中，ri, ρi為M階線性無關系統的極數。對于式(5)所示延時表達，其共有2m+2n+2項，只要延時表達式中這2m+2n+2個隨機變量是統計獨立的，那么就可以應用以上方法評估延時變量的PDF。

4 本文算法復雜度分析

如果將PCA正交轉換、ICA矩陣生成及獨立隨機變量矩計算過程等當作一次性的預處理，那么本文SSTA流程的計算復雜度僅包含了時序圖拓撲遍歷中的求和及求極大值操作。若非高斯獨立隨機變量的數量為n，高斯獨立隨機變量的數量為m，則求和操作的時間復雜度為O(n+m)；同時，若用于評估各個隨機變量的矩的階數為2M，則求極大值操作的時間復雜度即為O(M(n+m))。實際操作中，因為M是有上界的，所以求極大值操作的時間復雜度也可以看作為O(n+m)。對于一個含有G個邏輯門的應用電路，因為其各個門的扇入個數有界，則基本操作的總體時間復雜度就為O((n+m)·G)。假設延時建模時片內方格數量為g，因為m, n與方格數量g成正比，O(m)=O(n)=O(m+n)=O(g )，那么本文基于空間關聯工藝偏差的SSTA總體時間復雜度就可以表示為O(g·G)。

5 實驗結果

基于美國明尼蘇達州立大學的MinnSSTA開源框架[7]，本文在Windows平臺下采用C++語言實現了所提算法。實驗的硬件平臺為：CPU 3.6 GHz，內存1.0 GB。算法所用測試電路來自于ISCAS89測試集[14]，之所以選擇ISCAS89，是因為：(1)學術界廣泛承認并使用；(2)ISCAS89測試集中兩個鎖存器之間的組合模塊非常有利于本文CSSTA的基本操作和延時評估。本文利用文獻[11]提出的方法實現了高斯變量的PCA轉換，利用FastICA軟件包[15]實現了非高斯變量的ICA轉換，同時對每個工藝參數，生成5000個隨機樣本。

在本文實驗中，工藝參數既有空間關聯也有空間獨立，既有高斯分布也有非高斯分布。對于邏輯門工藝參數，只考慮邏輯門長度Lg，邏輯門寬度Wg，柵氧化層厚度Tox及半導體摻雜濃度Na；對于互連線工藝參數，在每一金屬層l，只考慮金屬互連線寬度Wint,l，金屬互連線厚度Tint,l及金屬高度HILD,l；令Lg,Wg,Tox,Wint,l,Tint,l及HILD,l為空間關聯的工藝參數，令Na為空間獨立的工藝參數。基于方格模型，本文將各個方格內邏輯門的Lg,Wg及Tox表示為高斯分布，其參數取值范圍為[μ-3·σ,μ+3 ·σ]；將各個方格內互連線的Wint,l,Tint,l及HILD,l表示為非高斯分布(如均勻分布)，其參數取值范圍為[μ-3·σ,μ+3·σ]；將Na表示為泊松分布。各個參數的均值和3倍/3倍標準差取值如表1所示，其中μ為各個工藝參數的均值；3σ(片間/片內)為工藝參數Lg,Wg及Tox的3倍片間/片內標準差；3σ(片間/片內)為工藝參數Wint,l,Tint,l及HILD,l的3倍片間/片內標準差；nmos/pmos為工藝參數Na對應n/p型柵氧化管。

表1 本文實驗所用工藝參數

在分析工藝參數的空間關聯性時，需要知道邏輯門和互連線的物理位置信息，為此本文首先用UCLA大學的開源布局工具Capo[16]進行初始布局，然后再執行全局布線。依據不同的電路單元數，本文將芯片劃分為不同數量的方格，使得每個方格內的邏輯門或互連線段數量不超過100個。為簡化分析，本文忽略掉輸入信號斜率、輸出信號負載及路徑耦合噪聲對延時模型的影響，從而將邏輯門和互連線延時表示為工藝參數的二階泰勒展開式。

為了驗證空間關聯SSTA(CSSTA)的精確性，本文基于相同的方格模型運行了蒙特卡洛仿真(MC)。MC是MinnSSTA中的一段源代碼程序，為平衡精度和時間開銷，本文設置了10000次迭代，在每一次迭代時，程序首先隨機選擇一組工藝參數，通過更新這組工藝參數對應的引腳電容，計算時序圖上各條邊的電阻電容參數(RC)，來獲得各條邊的延時；然后再采用PERT拓撲方法，通過傳遞延時參數，以獲得最終的路徑總延時。MC的10000次迭代產生了10000個隨機的路徑延時結果，通過統計這些結果的最大值、最小值、平均值及方差信息，即可得到仿真的統計信息。另外，在計算邊的RC參數和延時變量時，本文使用到了矩陣分解，為此MC調用了MTALAB的數學計算源文件，限于篇幅，具體細節不再贅述。表2為本文CSSTA和MC的對比結果，其中#C, #G分別為測試集中各個電路對應的單元數和方格數。對于每個ISCAS89測試電路，表中列出了兩種方法對應的均值u(ps)，標準差sd(ps), 5%概率點5%Pt和95%概率點95%Pt (ps,5%Pt定義為存在一個延時值，使得p(x≤5%Pt) =5%；95%Pt定義為存在一個延時值，使得p(x≤95%Pt)=95%)及運行時間t(s)。從表2可以看出，兩種方法的結果非常相近，均值、標準差、5%Pt及95%Pt的平均相對誤差分別只有0.81%, -0.72%, 2.23%及-0.05%。這表明本文CSSTA具有相當高的精確度，足以匹配真實的延時分布。對于電路s38417，圖5給出了兩種方法下的延時PDF和CDF對比結果，其中三角塊線為考慮空間關聯且假設工藝參數同時服從高斯分布和非高斯分布的CSSTA結果，方塊線為相同方格模型下的MC結果，從圖中也可以看出，兩種方法對應的曲線具有較高的匹配度。另外，從表2也可以看出，雖然本文CSSTA采用了ICA和PCA轉換技術，但其運行時間相對于MC仍要小很多，除了電路s27的運行時間約為MC運行時間的1.29%外，其它電路的運行時間幾乎為MC運行時間的千分之幾；特別是對于電路s35932，本文CSSTA運行時間為10.65 s，而MC卻需要超過7 h。因此，根據表2可以計算出，本文9組電路的CSSTA平均運行時間約為MC平均運行時間的0.21%。

為了驗證SSTA非線性非高斯建模的合理性，本文與文獻[9]中的結果進行了比較，比較的對象為相對MC的偏離誤差。在文獻[9]中，作者雖然也將部分工藝參數假設為非高斯分布，但其延時依賴關系卻是線性的。表3給出了本文方法與文獻[9]方法的對比結果，表中沒有列出運行時間結果，這是因為：(1)表3關注的重點是兩種方法的精確程度；(2)兩種方法的運行時間相對MC都要小很多。從表3可以看出，若以MC為比較基準，本文方法的均值、標準差、5%Pt及95%Pt的平均相對誤差更小，這表明本文方法相比文獻[9]更為精確。

表2 本文空間關聯SSTA(CSSTA)方法與蒙特卡洛(Monte Carlo, MC)仿真的對比結果

圖5 電路s38417在空間關聯SSTA與MC方法下的延時PDF, CDF對比結果

表3 本文空間關聯SSTA方法與文獻[9]方法的對比結果

6 結束語

本文提出了一種考慮空間關聯工藝偏差的統計靜態時序分析方法。該方法首先分析了芯片內不同位置工藝參數之間的空間關聯性，并提出了一種考慮非高斯分布工藝參數的二階延時模型；然后通過執行非線性非高斯延時表達式的求和、求極大值操作，實現了延時變量的PDF評估。ISCAS89實驗結果驗證了本文SSTA方法的準確性和快速性。

[1] Tang Q, Rodriguez J, Zjajo A, et al.. Statistical transistorlevel timing analysis using a direct random differential equation solver[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(2): 210-223.

[2] Shi B and Srivastava A. Thermal stress aware 3D-IC statistical static timing analysis[C]. Proceedings of the 23rd ACM International Conference on Great Lakes Symposium on VLSI, Paris, France, 2013: 281-286.

[3] Li B, Chen N, Xu Y, et al.. On timing model extraction and hierarchical statistical timing analysis[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32(3): 367-380.

[4] Zhang Xiao-lin, Ye Jing, Hu Yu, et al.. Capturing post-silicon variation by layout-aware path-delay testing[C]. Proceedings of IEEE/EDAA Design, Automation & Test in Europe, Grenoble, France, 2013: 288-291.

[5] Wagner M and Wunderlich H. Efficient variation-aware statistical dynamic timing analysis for delay test applications [C]. Proceedings of IEEE/EDAA Design, Automation & Test in Europe, Grenoble, France, 2013: 276-281.

[6] Amin C, Menezes N, Killpack K, et al.. Statistical static timing analysis: how simple can we get?[C]. Proceedings of IEEE/ACM Design Automation Conference, San Diego, USA, 2005: 652-657.

[7] Chang H and Sapatnekar S. Statistical timing analysis considering spatial correlations using a single PERT-like traversal[C]. Proceedings of IEEE/ACM International Conference on Computer Aided Design, San Jose, USA, 2003: 621-625.

[8] Zhan Y, Strojwas A, Li X, et al.. Correlation-aware statistical timing analysis with non-Gaussian delay distributions[C]. Proceedings of IEEE/ACM Design Automation Conference, San Diego, USA, 2005: 77-82.

[9] Singh J and Sapatnekar S. A scalable statistical static timing analyzer incorporating correlated non-Gaussian and Gaussian parameter variations[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(1): 160-173.

[10] Kirkpatrick T and Clark N. PERT as an aid to logic design[J]. IBM Journal of Research and Development, 1966, 10(2):135-141.

[11] Morrison D. Multivariate Statistical Methods[M]. 2nd Edition, New York: McGraw-Hill, 1976: 170-179.

[12] Tony B. An ICA page-papers, code, demos and links[OL]. http://cnl.salk.edu/～tony/ica.html. 1996.11.

[13] Li X, Le J, Gopalakrishnan P, et al.. Asymptotic probability extraction for non-normal distributions of circuit performance[C]. Proceedings of IEEE/ACM International Conference on Computer Aided Design, San Jose, USA, 2004: 2-9.

[14] Brglez F, Bryan D, and Kozminski K. Combinational profiles of sequential benchmark circuits[C]. Proceeding of IEEE International Symposium on Circuits and Systems, Portland, USA, 1989: 1929-1943.

[15] Juha K. Independent component analysis and blind source separation[OL]. http://research.ics.aalto.fi/ica/fastica/. 2011. 2.

[16] Andrew C. Wire length-driven standard-cell placement[OL]. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/Placement/. 2000.6.

喻 偉： 男，1986年生，博士生，研究方向為大規模集成電路設計自動化技術.

楊海鋼： 男，1960年生，研究員，博士生導師，研究方向為高速可編程邏輯芯片設計技術、數模混合信號SOC設計技術.

劉 洋： 男，1983年生，博士，助理研究員，研究方向為大規模集成電路設計自動化技術.

黃 娟： 女，1983年生，博士，助理研究員，研究方向為大規模集成電路設計自動化技術.

蔡博睿： 男，1988年生，研究實習員，研究方向為大規模集成電路設計自動化技術.

陳 銳： 男，1986年生，博士生，研究方向為粗粒度可重構陣列結構方面的研究.

A Statistical Static Timing Analysis Incorporating Process Variations with Spatial Correlations

Yu Wei①②Yang Hai-gang①Liu Yang①Huang Juan①Cai Bo-rui①Chen Rui①②

①(Institute of Electronics, Chinese Academy of Sciences, Beijing 100190, China)
②(University of Chinese Academy of Sciences, Beijing 100086, China)

To evaluate effects of process variations on circuit delay accurately, this study proposes a Statistical Static Timing Analysis (SSTA) which incorporates process variations with spatial correlations. The algorithm applies a second order delay model that taking into account the non-Gaussian parameters - by inducting the notion of ‘conditional variables’, the 2D non-linear delay model is translated into 1D linear one; and by computing the tightness probability, mean, variance, second-order moment and sensitivity coefficients of the circuit arrival time, the sum and max operations of non-linear and non-Gaussian delay expressions are implemented. For the ISCAS89 benchmark circuits, as compared to Monte Carlo (MC) simulation, the average errors of 0.81%, -0.72%, 2.23% and -0.05%, in the mean, variance, 5% and 95% quantile points of the circuit delay are obtained respectively for the proposed method. The runtime of the proposed method is about 0.21% of the value of Monte Carlo simulation. The experimental results prove that the high accuracy of the SSTA is reliable.

Integrated Circuit (IC); Statistical Static Timing Analysis (SSTA); Spatial correlations; Nongaussianity and non-linearity; Process variations; Delay model

TN402

A

1009-5896(2015)02-0468-09

10.11999/JEIT140295

2014-03-06收到，2014-06-09改回

國家科技重大專項(2013ZX03006004)和國家自然科學基金(61106033)資助課題

*通信作者：楊海鋼 yanghg@mail.ie.ac.cn