一種考慮空間關(guān)聯(lián)工藝偏差的統(tǒng)計(jì)靜態(tài)時(shí)序分析方法

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

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

②(中國(guó)科學(xué)院大學(xué) 北京 100086)

一種考慮空間關(guān)聯(lián)工藝偏差的統(tǒng)計(jì)靜態(tài)時(shí)序分析方法

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

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

②(中國(guó)科學(xué)院大學(xué) 北京 100086)

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

集成電路；統(tǒng)計(jì)靜態(tài)時(shí)序分析；空間關(guān)聯(lián)；非高斯非線性；工藝偏差；延時(shí)模型

1 引言

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

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

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

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

2 工藝參數(shù)的空間關(guān)聯(lián)與電路延時(shí)的非高斯非線性屬性

2.1 SSTA中的工藝參數(shù)空間關(guān)聯(lián)

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

圖1 工藝參數(shù)空間關(guān)聯(lián)的方格模型示意圖

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

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

不同方格內(nèi)工藝參數(shù)的空間關(guān)聯(lián)程度是由其共同的父方格所決定的，例如方格[2,1], [2,2]及[2,16]內(nèi)的邏輯門溝道長(zhǎng)度分別可以表示為

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

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

2.2 SSTA中的非高斯非線性

隨著工藝尺寸的減小，電路延時(shí)呈現(xiàn)出越來(lái)越多的非高斯屬性。實(shí)際分析時(shí)，一些工藝參數(shù)往往會(huì)極大地偏離高斯分布，如互連線的金屬寬度會(huì)呈現(xiàn)出非對(duì)稱的概率分布，半導(dǎo)體摻雜濃度會(huì)呈現(xiàn)出泊松分布等；同時(shí)由于片內(nèi)空間鄰近效應(yīng)的存在，這些非高斯分布工藝參數(shù)彼此空間關(guān)聯(lián)，若依據(jù)傳統(tǒng)的SSTA方法將這些工藝參數(shù)表示為高斯分布，則很可能會(huì)導(dǎo)致電路延時(shí)的PDF嚴(yán)重偏離實(shí)際情形。

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

針對(duì)SSTA中工藝參數(shù)的空間關(guān)聯(lián)性及延時(shí)表達(dá)的非高斯非線性，本文提出一種改進(jìn)的空間關(guān)聯(lián)統(tǒng)計(jì)靜態(tài)時(shí)序分析(Correlated Statistical Static Timing Analysis, CSSTA)方法，從而將這兩個(gè)問題考慮進(jìn)來(lái)。

3 CSSTA算法流程

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

3.1 基于工藝參數(shù)偏差的延時(shí)建模

圖2 CSSTA算法流程圖

為了描述工藝參數(shù)偏差對(duì)電路延時(shí)的非線性影響，本文采用基于截?cái)嗟奶├照归_多項(xiàng)式，將一階線性表達(dá)式擴(kuò)展為二階延時(shí)模型：

其中，D為對(duì)應(yīng)邏輯門延時(shí)或輸入端到達(dá)時(shí)間的隨機(jī)變量，d0為D的本征值，xi為空間關(guān)聯(lián)工藝參數(shù)高斯變量，yj為空間關(guān)聯(lián)工藝參數(shù)非高斯變量，z為空間獨(dú)立工藝參數(shù)隨機(jī)變量；,分別為第i個(gè)高斯分布工藝參數(shù)的一階、二階敏感度系數(shù)，,分別為第j個(gè)非高斯分布工藝參數(shù)的一階、二階敏感度系數(shù)，e為隨機(jī)變量z的敏感度系數(shù)；n和m分別為空間關(guān)聯(lián)高斯分布和非高斯分布工藝參數(shù)的個(gè)數(shù)。

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

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

接著，運(yùn)用PCA (ICA)技術(shù)，將空間關(guān)聯(lián)的高斯分布工藝參數(shù)向量x(空間關(guān)聯(lián)的非高斯分布工藝參數(shù)向量y)轉(zhuǎn)換為彼此獨(dú)立的高斯分布工藝參數(shù)向量X(彼此獨(dú)立的非高斯分布工藝參數(shù)向量Y)，將D進(jìn)一步表示為

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

3.2 非線性非高斯延時(shí)的統(tǒng)計(jì)操作

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

圖3 統(tǒng)計(jì)時(shí)序圖中求和、求極大值操作及延時(shí)分布傳遞

3.2.1 求和 因?yàn)榍蠛筒僮魇且粋€(gè)線性操作，所以求和結(jié)果應(yīng)該與輸入到達(dá)時(shí)間及門延時(shí)具有相同的表達(dá)式。參考式(5)，考慮兩個(gè)非線性非高斯延時(shí)表達(dá)式A和B：

求和結(jié)果C=A+B可以表示為

其中

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

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

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

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

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

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

同時(shí)，由于XiL的概率分布可以簡(jiǎn)單地等效為XiN,YjL及YjN的聯(lián)合概率分布：

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

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

令Cappr的方差為var(Cappr)，則Cappr的相關(guān)參數(shù)為

為了突出本文非線性非高斯延時(shí)表達(dá)式與傳統(tǒng)線性高斯延時(shí)表達(dá)式求極大值操作的對(duì)比結(jié)果，圖4給出了包含兩個(gè)隨機(jī)變量的max(A,B)近似示意圖，其中圖4(a)為線性高斯情形，圖4(b)為本文非線性非高斯情形。在圖4(b)中，虛曲線分別為非線性表達(dá)式A, B，彎折實(shí)曲線為準(zhǔn)確的max(A,B)，光滑實(shí)曲線為近似的Cappr?？梢钥闯?，光滑實(shí)曲線Cappr和彎折實(shí)曲線max(A,B)具有較高的擬合度，證明本文參數(shù)化表達(dá)式的近似擬合結(jié)果具有一定的合理性。若把各個(gè)隨機(jī)變量從1維擴(kuò)展到多維，這種圖示方法仍然適用，只不過圖中曲線變成了曲面。

3.3 基于矩匹配的延時(shí)評(píng)估

在計(jì)算延時(shí)或到達(dá)時(shí)間的PDF(CDF)時(shí)，本文采用了文獻(xiàn)[13]提出的概率提取流程算法(Asymptotic Probability Extraction, APEX)。算法首先將一個(gè)隨機(jī)變量的二階矩作為輸入，采用漸進(jìn)波形評(píng)估技術(shù)來(lái)匹配這個(gè)隨機(jī)變量的2M階矩，從而生成一個(gè)M階的線性無(wú)關(guān)系統(tǒng)；接著利用這個(gè)M階線性無(wú)關(guān)系統(tǒng)的沖激響應(yīng)(階躍響應(yīng))來(lái)近似擬合隨機(jī)變量的PDF (CDF)。

圖4 max(A,B)的準(zhǔn)確表達(dá)與近似表達(dá)示意圖

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

因?yàn)閃和L的所有i階矩可按文獻(xiàn)[9]所提方法求得，所以根據(jù)式(18)計(jì)算得到的2M矩后，利用M階線性無(wú)關(guān)系統(tǒng)的沖激響應(yīng)即可近似擬合的實(shí)際PDF。

式(19)中，ri, ρi為M階線性無(wú)關(guān)系統(tǒng)的極數(shù)。對(duì)于式(5)所示延時(shí)表達(dá)，其共有2m+2n+2項(xiàng)，只要延時(shí)表達(dá)式中這2m+2n+2個(gè)隨機(jī)變量是統(tǒng)計(jì)獨(dú)立的，那么就可以應(yīng)用以上方法評(píng)估延時(shí)變量的PDF。

4 本文算法復(fù)雜度分析

如果將PCA正交轉(zhuǎn)換、ICA矩陣生成及獨(dú)立隨機(jī)變量矩計(jì)算過程等當(dāng)作一次性的預(yù)處理，那么本文SSTA流程的計(jì)算復(fù)雜度僅包含了時(shí)序圖拓?fù)浔闅v中的求和及求極大值操作。若非高斯獨(dú)立隨機(jī)變量的數(shù)量為n，高斯獨(dú)立隨機(jī)變量的數(shù)量為m，則求和操作的時(shí)間復(fù)雜度為O(n+m)；同時(shí)，若用于評(píng)估各個(gè)隨機(jī)變量的矩的階數(shù)為2M，則求極大值操作的時(shí)間復(fù)雜度即為O(M(n+m))。實(shí)際操作中，因?yàn)镸是有上界的，所以求極大值操作的時(shí)間復(fù)雜度也可以看作為O(n+m)。對(duì)于一個(gè)含有G個(gè)邏輯門的應(yīng)用電路，因?yàn)槠涓鱾€(gè)門的扇入個(gè)數(shù)有界，則基本操作的總體時(shí)間復(fù)雜度就為O((n+m)·G)。假設(shè)延時(shí)建模時(shí)片內(nèi)方格數(shù)量為g，因?yàn)閙, n與方格數(shù)量g成正比，O(m)=O(n)=O(m+n)=O(g )，那么本文基于空間關(guān)聯(lián)工藝偏差的SSTA總體時(shí)間復(fù)雜度就可以表示為O(g·G)。

5 實(shí)驗(yàn)結(jié)果

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

在本文實(shí)驗(yàn)中，工藝參數(shù)既有空間關(guān)聯(lián)也有空間獨(dú)立，既有高斯分布也有非高斯分布。對(duì)于邏輯門工藝參數(shù)，只考慮邏輯門長(zhǎng)度Lg，邏輯門寬度Wg，柵氧化層厚度Tox及半導(dǎo)體摻雜濃度Na；對(duì)于互連線工藝參數(shù)，在每一金屬層l，只考慮金屬互連線寬度Wint,l，金屬互連線厚度Tint,l及金屬高度HILD,l；令Lg,Wg,Tox,Wint,l,Tint,l及HILD,l為空間關(guān)聯(lián)的工藝參數(shù)，令Na為空間獨(dú)立的工藝參數(shù)?；诜礁衲Ｐ?，本文將各個(gè)方格內(nèi)邏輯門的Lg,Wg及Tox表示為高斯分布，其參數(shù)取值范圍為[μ-3·σ,μ+3 ·σ]；將各個(gè)方格內(nèi)互連線的Wint,l,Tint,l及HILD,l表示為非高斯分布(如均勻分布)，其參數(shù)取值范圍為[μ-3·σ,μ+3·σ]；將Na表示為泊松分布。各個(gè)參數(shù)的均值和3倍/3倍標(biāo)準(zhǔn)差取值如表1所示，其中μ為各個(gè)工藝參數(shù)的均值；3σ(片間/片內(nèi))為工藝參數(shù)Lg,Wg及Tox的3倍片間/片內(nèi)標(biāo)準(zhǔn)差；3σ(片間/片內(nèi))為工藝參數(shù)Wint,l,Tint,l及HILD,l的3倍片間/片內(nèi)標(biāo)準(zhǔn)差；nmos/pmos為工藝參數(shù)Na對(duì)應(yīng)n/p型柵氧化管。

表1 本文實(shí)驗(yàn)所用工藝參數(shù)

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

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

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

表2 本文空間關(guān)聯(lián)SSTA(CSSTA)方法與蒙特卡洛(Monte Carlo, MC)仿真的對(duì)比結(jié)果

圖5 電路s38417在空間關(guān)聯(lián)SSTA與MC方法下的延時(shí)PDF, CDF對(duì)比結(jié)果

表3 本文空間關(guān)聯(lián)SSTA方法與文獻(xiàn)[9]方法的對(duì)比結(jié)果

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

本文提出了一種考慮空間關(guān)聯(lián)工藝偏差的統(tǒng)計(jì)靜態(tài)時(shí)序分析方法。該方法首先分析了芯片內(nèi)不同位置工藝參數(shù)之間的空間關(guān)聯(lián)性，并提出了一種考慮非高斯分布工藝參數(shù)的二階延時(shí)模型；然后通過執(zhí)行非線性非高斯延時(shí)表達(dá)式的求和、求極大值操作，實(shí)現(xiàn)了延時(shí)變量的PDF評(píng)估。ISCAS89實(shí)驗(yàn)結(jié)果驗(yàn)證了本文SSTA方法的準(zhǔn)確性和快速性。

[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年生，博士生，研究方向?yàn)榇笠?guī)模集成電路設(shè)計(jì)自動(dòng)化技術(shù).

楊海鋼： 男，1960年生，研究員，博士生導(dǎo)師，研究方向?yàn)楦咚倏删幊踢壿嬓酒O(shè)計(jì)技術(shù)、數(shù)模混合信號(hào)SOC設(shè)計(jì)技術(shù).

劉 洋： 男，1983年生，博士，助理研究員，研究方向?yàn)榇笠?guī)模集成電路設(shè)計(jì)自動(dòng)化技術(shù).

黃 娟： 女，1983年生，博士，助理研究員，研究方向?yàn)榇笠?guī)模集成電路設(shè)計(jì)自動(dòng)化技術(shù).

蔡博睿： 男，1988年生，研究實(shí)習(xí)員，研究方向?yàn)榇笠?guī)模集成電路設(shè)計(jì)自動(dòng)化技術(shù).

陳 銳： 男，1986年生，博士生，研究方向?yàn)榇至６瓤芍貥?gòu)陣列結(jié)構(gòu)方面的研究.

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改回

國(guó)家科技重大專項(xiàng)(2013ZX03006004)和國(guó)家自然科學(xué)基金(61106033)資助課題

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