基于直接邊界元的三維互連電容增量式快速模式建庫方法

基于直接邊界元的三維互連電容增量式快速模式建庫方法

目前，vlasi中相鄰導(dǎo)線的連接寬度和距離已經(jīng)進(jìn)入納米水平，高寬比接近3，同一層的干擾強度正在改善。同時，連接層的數(shù)量為7.9層，介質(zhì)層主要為納米和深亞微米，垂直合并密度隨著精細(xì)裂紋的形成而提高，結(jié)果表明，相鄰耦合矩陣具有嚴(yán)格意義上的三維特性，需要精確提取。另一方面，芯片規(guī)模急劇擴大，單個片段可以包含上億根棍子。由于規(guī)模大，提取電致電容的難度應(yīng)該受到影響。近年來，隨著微細(xì)過程的快速發(fā)展，核電站生產(chǎn)工藝的控制受到了不確定性，導(dǎo)致了生產(chǎn)線寬度、線高和線距離的技術(shù)參數(shù)的波動，以及在同一層中提取形容詞的新困難。基于有限差分,有限元和邊界元技術(shù)的數(shù)值模擬方法能精確地提取任意復(fù)雜三維互連電容結(jié)構(gòu),常稱作場求解器(fieldsolver).但這些提取器十分耗時,即使已得到諸如多極加速,層次式計算和虛擬多介質(zhì)等多種快速計算技術(shù)的支持,仍難以勝任快速提取芯片級三維互連電容的要求.因此,解析模型法和基于模式匹配的查表法可用作大規(guī)模實際版圖寄生電容估計與提取的方法被廣泛使用.文獻(xiàn)指出,盡管這2種方法各有優(yōu)缺點,但它們都需要通過數(shù)值模擬或?qū)嶒灉y量方法來獲取一些基本三維互連結(jié)構(gòu)的寄生電容值,并存入庫中.這些基本的三維互連結(jié)構(gòu)被稱為模式,獲取它們的電容值是一個模式建庫的過程.事實上,當(dāng)前工藝的極端微細(xì)化與結(jié)構(gòu)的高復(fù)雜性使數(shù)值模擬成為模式建庫近乎唯一的方法.以查表法為例,首先是模式建庫;之后在進(jìn)行芯片級提取時,可根據(jù)庫中模式對版圖進(jìn)行劃分和匹配.如果匹配合適,庫中結(jié)果就可以直接使用;否則,可以通過插值等數(shù)學(xué)方法近似計算得到.為了盡量避免或減少插值的情況,庫中的模式數(shù)目需要比較多,用于建庫所需時間往往較長.VLSI設(shè)計進(jìn)入深亞微米以后,由于在芯片生產(chǎn)過程中存在刻蝕不均勻、掩膜板難以精確對齊等不確定因素,造成芯片上晶體管的實際尺寸、連線的實際寬度W與高度T等工藝參數(shù)與期望值有一定差別.這些工藝參數(shù)會有大約±10%的變動,我們稱之為工藝變動.工藝參數(shù)的變動會對電路的性能產(chǎn)生影響,嚴(yán)重的可導(dǎo)致電路性能惡化或功能喪失.因此,在考慮工藝參數(shù)變動的基礎(chǔ)上,需要對庫中模式進(jìn)行快速、準(zhǔn)確的電容提取,并對電路在有工藝參數(shù)變動的情況下進(jìn)行模擬驗證.本文討論3種典型的工藝變動參數(shù):線寬、線間距和線高.在模式建庫時,對于每一個模式,須將各種工藝參數(shù)變動的極值加以組合,產(chǎn)生出多種工藝參數(shù)的變動組合.例如,每種參數(shù)可有±10%的變動范圍,每種參數(shù)允許取最小值、最大值和不變3種情況,可得到33=27種變動組合.用場求解器計算出各種參數(shù)變動組合的電容值,便可得出寄生電容的變動范圍,從而可以模擬最壞情況.如果已知一個版圖的實際工藝變動量,即可對極值變動組合的電容值進(jìn)行插值,得出實際工藝變動后三維互連結(jié)構(gòu)的寄生電容值.在模式建庫過程中,如果對每一種工藝參數(shù)變動組合都重新計算它們的寄生電容,將是非常耗時的,會是原有建庫時間的數(shù)十至上百倍.這對查表法影響尤為顯著,因為在查表法中,庫里模式很多,而每個模式又會有很多工藝參數(shù)變動組合,使建庫時間大大增加.文獻(xiàn)提出一種基于解析公式的方法,它推導(dǎo)出各種模式下寄生電容對各工藝參數(shù)變動的導(dǎo)數(shù),進(jìn)而可根據(jù)工藝參數(shù)的變動量和理論值快速地求出參數(shù)變動后的電容值.但由于解析公式推導(dǎo)本身帶有誤差,又僅采用一階近似,當(dāng)工藝變動較大時,誤差也較明顯.文獻(xiàn)提出一種基于直接邊界元的增量式方法,當(dāng)版圖僅作小范圍局部修改時,它能準(zhǔn)確、快速地提取三維寄生電容與電阻,這與考慮工藝參數(shù)變動的模式建庫在原理上有相通之處,具有啟發(fā)意義.本文將文獻(xiàn)提出的增量計算思想用于工藝參數(shù)變動下的模式建庫.首先,對工藝在理論值(即工藝未變動)時的模式算出寄生電容,并保留所解方程組的系數(shù)矩陣與右端項;然后根據(jù)工藝變動對系數(shù)矩陣與右端項進(jìn)行局部修改,并對工藝未變動時所得到的解合理預(yù)測后作為初值進(jìn)行迭代求解,從而得到工藝變動后的寄生電容值.計算結(jié)果表明,這種方法可明顯減少模式建庫所需時間.1區(qū)域邊界的離散化直接邊界元法是常用作場求解器的數(shù)值方法,下面簡單介紹其電容計算原理.在三維情形下,待解域Ω由M個介質(zhì)組成,Ω=∪Ωi(i=1,…,M),Ω中帶混合邊界條件的拉普拉斯方程可以轉(zhuǎn)化為直接邊界積分方程csus+∫?Ωiq*udΓ=∫?Ωiu*qdΓ(i=1???Μ)(1)csus+∫?Ωiq?udΓ=∫?Ωiu?qdΓ(i=1???M)(1)其中,us是源點s的電勢,cs是與源點附近邊界幾何形狀有關(guān)的常數(shù).u為邊界上一點的電勢,q=?u??n為邊界上一點的法向電場強度,u*=14πr是拉普拉斯方程基本解,其沿外法向n的方向?qū)?shù)q*=?u*??n=-(r,n)4πr3,r為源點到積分點的距離;?Ωi是介質(zhì)i的邊界.對區(qū)域邊界進(jìn)行離散化,即將介質(zhì)Ωi(i=1,…,M)的邊界?Ωi離散為Ni個邊界元(介質(zhì)交界面上的元同時屬于相鄰的2種介質(zhì)).本文采用常數(shù)元,取每個元的中心點為源點及變量配置點,可得到積分方程式(1)的離散化形式ckuk+Νi∑j=1(∫Γjq*dΓ)uj=Νi∑j=1(∫Γju*dΓ)qj(k=1???Νi；i=1???Μ)(2)ckuk+∑j=1Ni(∫Γjq?dΓ)uj=∑j=1Ni(∫Γju?dΓ)qj(k=1???Ni；i=1???M)(2)其中,Γj表示?Ωi上的第j個邊界元,式(2)中各項積分可視作邊界元Γk與邊界元Γj之間的相互作用.這樣總共可列出Ν=Μ∑i=1ΝiN=∑i=1MNi個方程.將邊界條件及介質(zhì)交界面上電勢和電位移連續(xù)條件代入式(2),將含未知量的項移到等式左邊,常量移到右邊,可得一個線性代數(shù)方程組Ax=f(3)求解方程組式(3),可得強加邊界上的法向電場強度q,然后用C=∫ΓuεqdΓ可求得電容C,其中ε為介質(zhì)的介電常數(shù).2線寬和線間距的a一個模式建庫過程,首先需選擇若干基本三維互連結(jié)構(gòu)以產(chǎn)生各種模式.圖1所示為一種典型且簡單的構(gòu)建三維模式的常用結(jié)構(gòu).下面以它為例,說明考慮工藝參數(shù)變動的三維電容快速模式建庫方法.在圖1所示結(jié)構(gòu)中,可引入多個參數(shù)以構(gòu)造不同模式.為簡單起見,中間主導(dǎo)體層的線高可設(shè)為固定值,只將線寬W,線間距S取作參數(shù);除此之外,緊鄰主導(dǎo)體上下2層的線密度D(density)也可取作參數(shù),如圖2所示.D取值在0和1之間,代表主導(dǎo)體上下2層導(dǎo)體的數(shù)目N與按照當(dāng)前工藝的最小線寬和線間距在這2層布滿了導(dǎo)體時的導(dǎo)體數(shù)目Nmax的比值.當(dāng)這2層布滿了導(dǎo)體時,D取值為1;當(dāng)這2層有Nmax2個導(dǎo)體時,D取值為0.5;當(dāng)這2層沒有導(dǎo)體時,D取值為0.如線寬W取0.2,0.4,0.8,1.2μm,線間距S取0.21,0.31,0.41,…,5,7,10μm,再加上密度D取0.2,0.4,…,1.0,上述3個參數(shù)的各種組合可構(gòu)造出一系列模式.在模式建庫時必須考慮工藝參數(shù)變動.這里考慮線寬W、線間距S和線高T3種參數(shù),每種參數(shù)有±10%的變動范圍.如果各取-10%,0和10%3個變動點,可得到33=27種參數(shù)變動組合;如果各取-10%,-5%,0,5%和10%5個變動點,則變動組合數(shù)達(dá)53=125.也就是說,對一個模式要用場求解器計算幾十至上百遍,是相當(dāng)耗時的.為此,本文算法先就一個模式在工藝參數(shù)未變動時的原始結(jié)構(gòu)作一次完全提取,并將系數(shù)矩陣等加以保存;然后便可在前一次計算的基礎(chǔ)上逐次、快速地提取緊鄰工藝變動組合的電容.算法1.直接邊界元法對庫中模式提取寄生電容Step1.讀取一個模式的工藝和版圖信息.Step2.生成三維幾何結(jié)構(gòu).Step3.生成邊界元網(wǎng)格.Step4.形成線性方程組Ax=f.Step5.解方程并求出電容.算法1已在我們課題組研發(fā)的三維互連寄生電容提取軟件QBEM中實現(xiàn).QBEM基于直接邊界元法,并得到虛擬多介質(zhì)快速算法的支持.同時,本文所提工藝參數(shù)變動下的模式快速提取方法已在QBEM基礎(chǔ)上實現(xiàn),其計算步驟如圖3所示.目前,已實現(xiàn)線寬W、線間距S和線高T3種工藝參數(shù)變化的快速電容提取.下面著重描述圖3中(3),(4)2個步驟.2.1建立新系數(shù)矩陣與右端項所需時間的區(qū)別首先討論圖3中的第(3)步.由式(2)看出,對一個含M種介質(zhì)的三維結(jié)構(gòu),按文獻(xiàn)所采用的源點及變量排序方法,同一介質(zhì)中邊界元間相互作用將構(gòu)成系數(shù)矩陣的一些特定項,并形成非零元分布很有規(guī)律的稀疏塊矩陣.這就是說,當(dāng)2個邊界元的基本特征與屬性不變時,它們對應(yīng)于系數(shù)矩陣的特定項也不變.同時也注意到,對一個模式來說,2個緊鄰變動組合結(jié)構(gòu)的差別一般是極其微小的,二者的邊界元劃分可以保持最大相似性.因此,假如將一個模式在工藝參數(shù)不變時所產(chǎn)生的邊界元劃分、系數(shù)矩陣及右端項等信息加以保存,則只要找出緊鄰工藝變動組合結(jié)構(gòu)在邊界元劃分的改變,便可據(jù)此對系數(shù)矩陣與右端項的極少數(shù)對應(yīng)項加以修改,從而顯著地減少形成新系數(shù)矩陣與右端項所需時間.圖4所示為一個簡單例子線寬變動前后及其所對應(yīng)系數(shù)矩陣示意圖.圖4a,4b中,陰影塊表示導(dǎo)體,白色塊表示介質(zhì);圖4c,4d中,點狀塊表示非零元素,標(biāo)記×的矩陣塊表示需要修改的矩陣部分,n為矩陣階數(shù),m為標(biāo)記×的塊寬度,p為右下角分塊矩陣的列數(shù),q為行數(shù).我們以圖4所示含2種介質(zhì)與多塊導(dǎo)體的結(jié)構(gòu)為例,描述一下線寬變動后系數(shù)矩陣的變化情況.這個結(jié)構(gòu)的側(cè)視圖如圖4a所示,生成的分塊系數(shù)矩陣A如圖4c所示,線寬變大后的結(jié)構(gòu)側(cè)視圖如圖4b?所示,并假定在新結(jié)構(gòu)的邊界元劃分中,除相關(guān)的少量邊界元在大小略有改變外,整體劃分不變,則新生成的分塊系數(shù)矩陣如圖4d所示,標(biāo)記×的塊表示原系數(shù)矩陣需要局部重新計算的部分.對線間距和線高的工藝參數(shù)變動,系數(shù)矩陣的修改與線寬變動時的情況類似.在工藝參數(shù)變動后,邊界元的數(shù)目增加或者減小的情況下,只要在原系數(shù)矩陣中增加或者刪除相應(yīng)的行和列就可以了.下面討論系數(shù)矩陣局部修改所需時間.在圖4c中,假設(shè)系數(shù)矩陣維度為n,則對原始模式結(jié)構(gòu)生成系數(shù)矩陣的時間是t0=O(n2).假設(shè)工藝變動影響到了m個邊界元,那么標(biāo)記×部分的矩陣元素數(shù)目為mp+mq-mm<2mn-mm.所以,重新計算這一部分矩陣元素所需要的時間為t=O(2mn-mm).圖5所示為t?t0和m?n的關(guān)系,在m?n<110的情況下,t?t0對m?n可以認(rèn)為是線性的.并且當(dāng)介質(zhì)層數(shù)較多時,所需修改的僅僅是工藝變動所在層以及緊鄰層對應(yīng)部分的矩陣元素,局部重新計算的時間t遠(yuǎn)小于完整生成全部系數(shù)矩陣元素的時間t0.需要指出,從本課題組與美國EDA公司Synopsys合作研發(fā)基于直接邊界元法的三維互連寄生電容提取軟件B3D與QBEM看,應(yīng)用GMRES迭代法求解,基本未遇到迭代不收斂的情況.明顯地,上述局部修改得到的系數(shù)矩陣與經(jīng)由結(jié)構(gòu)描述、邊界元網(wǎng)格生成等步驟直接形成的系數(shù)矩陣基本相同.因此,本文增量式算法所形成系數(shù)矩陣的迭代收斂性不會下降.本文在大量實例計算中,均未發(fā)現(xiàn)迭代不收斂的情況.2.2選擇正確的選擇策略式(3)的求解是三維電容提取中另一主要耗時環(huán)節(jié).本文采用有效的GMRES迭代法,一般取全0向量作為迭代初值x0.在考慮工藝變動的模式電容提取中,我們同樣注意到,工藝參數(shù)變動范圍不大(±10%)可以為減少方程求解時間帶來好處.本文提出一種迭代初值的選擇策略,分為2個步驟:Step1.將一個模式在工藝參數(shù)未變動時的解作為緊鄰工藝變動組合迭代初值的候選值x′0.Step2.根據(jù)緊鄰工藝變動組合與工藝參數(shù)未變動時在結(jié)構(gòu)上的差別,運用靜電學(xué)原理對候選值x′0加以修正后得到最終迭代初值x0.將Step1,Step2結(jié)合起來使用所得到的迭代初值x0,可以明顯地減少迭代法的求解時間.對任一模式,在工藝參數(shù)變動的種類已知且變動范圍也不大的情況下,可以在上次迭代結(jié)果的基礎(chǔ)上對變動后的值做出粗略預(yù)測.例如,在圖6中,2個鄰近導(dǎo)體因為工藝變動導(dǎo)致線間距增大,d′=(1+10%)d.根據(jù)平板電容器公式C=εS?d,則導(dǎo)體相對2個面之間的電容變?yōu)镃′area=(1011)Carea;然后,再將這個修正分配到初值候選向量的相應(yīng)分量中.這種修正是比較粗略的,但對迭代法加速收斂有相當(dāng)幫助.3數(shù)值實驗3.1qbem中元素變化量的計算本文選取3個模式,對其線寬W、線間距S和線高T中僅一個參數(shù)變化,另2個保持不變的單參數(shù)變動情況做了數(shù)值實驗.在圖1所示模式生成結(jié)構(gòu)中,選擇結(jié)構(gòu)參數(shù)不同的3個模式進(jìn)行實驗,它們的結(jié)構(gòu)參數(shù)和特征數(shù)據(jù)如表1所示.對上面3個測試模式分別采用3種工藝變動(線寬W、線間距S和線高T)中的一種,而且每次變動總?cè)∑錁O值(-10%或10%).用QBEM所得結(jié)果如表2所示.表2中,t0表示QBEM對模式原始結(jié)構(gòu)作電容提取所需時間,括號里數(shù)字是GMRES迭代法求解線性代數(shù)方程組的迭代次數(shù);t表示考慮工藝變動后,QBEM采用前述增量式提取及初值策略進(jìn)行提取所需時間,括號里是相應(yīng)的迭代次數(shù);元素變化量表示局部修改的邊界元數(shù)占總邊界元數(shù)的百分比;誤差表示采用前述多種算法改進(jìn)策略后的QBEM計算結(jié)果與準(zhǔn)確解之差,其中準(zhǔn)確解是指用QBEM對相應(yīng)結(jié)構(gòu)的精確提取.可以看到,在計算誤差很小的情況下,本文算法對有單個工藝參數(shù)變動下的計算速度提高了5倍左右.從表2還可看出,元素變化量越小的加速比越大.這是因為元素變化量越小,矩陣修改和迭代求解所需時間也越少.例如,在表2最后一行,元素變動量為0.9%,加速比為5.55,是加速比最大的一個.3.2組織模式分析在實際中,工藝參數(shù)變動下的模式計算一般是針對多個工藝參數(shù)同時變化的情形.這里仍以線寬W、線間距S和線高T3個參數(shù)同時變化的組合為例,在一個模式中,允許3個工藝參數(shù)同時變化以產(chǎn)生多個變動組合并計算.以表1中編號2的模式為例,對線寬、線間距和線高各取5個變動點{-10%,-5%,0,5%,10%},并對所產(chǎn)生的125種工藝變動組合采用改進(jìn)后的算法進(jìn)行求解.在組織計