翁輝耀

摘 要：研究了芯片規(guī)模大結(jié)構(gòu)RC寄生參數(shù)的快速提取方法，然后提出一種模型降階方案。由于提取寄生電容過程需要考慮周圍臨近的互連線，芯片級集成電路有著千兆級以上的互連線，故需要一個相對優(yōu)化的結(jié)構(gòu)能夠快速準(zhǔn)確地找出符合條件的互連線，從而加快電容的提取的速度。因此介紹了各個空間管理結(jié)構(gòu)（K-D樹， 八叉樹， 網(wǎng)格劃分），進行深入研究并給出一個優(yōu)化方案，上層四叉樹下層K-D樹將獲得較優(yōu)的速度和使用較少的內(nèi)存。

關(guān)鍵詞：寄生參數(shù)提??；空間管理結(jié)構(gòu)；模型降階

中圖分類號：TN405 文獻標(biāo)識碼：A 文章編號：1671-2064（2018）21-0022-03

當(dāng)下，隨著芯片的設(shè)計越來越復(fù)雜，互連線的長度越來越長，數(shù)量越來越多，互連線之間的電磁耦合問題已成為電路設(shè)計中日益困難的問題。超大規(guī)模集成電路互連線的布線層數(shù)一般在8層及以上，故互連線帶來的延遲和寄生參數(shù)問題影響到電路性能，成為芯片設(shè)計首要考慮因素。IC設(shè)計也逐漸由以前的以邏輯功能為中心的模式變成功能與互聯(lián)性能并重的模式，設(shè)計的重點也逐漸由前端向后端轉(zhuǎn)移[1-2]。

1 互連線寄生參數(shù)基本理論

1.1 互連技術(shù)概念

所謂的互連技術(shù)，就是在集成電路芯片制造過程中，將各個獨立的元器件通過金屬線通孔等一定的方式，把它們連接成具有一定功能的電路模塊的一種技術(shù)。

在現(xiàn)代的高速超大集成電路芯片設(shè)計中，對信號經(jīng)過互連線后所產(chǎn)生的效應(yīng)進行準(zhǔn)確地定性定量地分析，仿真計算出結(jié)果并加以優(yōu)化控制已經(jīng)成為相應(yīng)計算機輔助設(shè)計工具關(guān)注的主要問題之一。隨著芯片規(guī)模越來越大，芯片面積卻越來越小，芯片設(shè)計者分析信號經(jīng)過互連線后所產(chǎn)生的效應(yīng)的難度和準(zhǔn)確性要求不斷提升。如果能夠精確地提取到互連線寄生參數(shù)，就可以對電路進行精確地綜合模擬，從而發(fā)現(xiàn)設(shè)計問題，進行性能優(yōu)化地布局布線，消除互連效應(yīng)。故一種快速的提取互連線寄生參數(shù)的方法，對于優(yōu)化集成電路設(shè)計有著十分重大的意義。

1.2 互連線寄生電阻提取

根據(jù)金屬導(dǎo)線電阻計算公式：

R=ρL/S=ρL/HW

以上公式中：ρ是物質(zhì)的電阻率，其單位是歐姆米（ohm*m）。L是長度，其單位是米（m）。S是截面積，其單位是平方米（m2），S可以通過導(dǎo)線的高度乘以寬度計算出。根據(jù)公式可以推導(dǎo)出，每個單元截面的傳輸線單位長度的電阻與頻率無關(guān)。

1.3 互連線寄生電容提取

當(dāng)前比較精確的三維寄生電容提取方法主要有：邊界元法[3-5]、半解析方法[6]、MEI[7-9]方法和隨機漫步法[10]。

因芯片內(nèi)互連線數(shù)據(jù)量巨大，大部分場效應(yīng)求解電容提取方法不適合實際應(yīng)用于芯片規(guī)模大數(shù)據(jù)結(jié)構(gòu)。所以在工作實踐中，利用平行板電容公式來計算寄生電容的方法以求簡化，并考慮邊緣效應(yīng)的誤差量和周邊環(huán)境的誤差量，以達到快速提取電容的目的。介紹寄生參數(shù)提取方法前，先對傳統(tǒng)的平行板電容結(jié)構(gòu)及概念進行說明：

電壓：V=φ1-φ2

Q和-Q在上下板上，Q和V成比例。

比率被定義為C：C=Q/V。

如果板的面積比兩板之間的距離d大得多，有：

，

對于有限長的矩形平板，需要考慮平行板電容器的邊緣效應(yīng)。已有計及邊緣效應(yīng)時平行板電容器的電容值[11]。結(jié)果如圖1所示。

C0是考慮邊緣效應(yīng)實際電容值，C是理想電容值，h是極板的寬度，d是兩板的距離。

從圖上可知：在h/d=16.644時，C0/C=0.901。故只要極板寬度與間距之比大于16.644，用平行板電容器公式誤差不超過10%。

1.4 模型降階及簡化

隨著工藝提升，集成電路設(shè)計越來越復(fù)雜，互連線也就越來越長，條數(shù)越來越多。相對的寄生參數(shù)提取的等效矩陣也將越來越大，大大影響了計算的效率，不利于仿真分析。以現(xiàn)在的計算機的能力，對如此多的等效模型直接進行分析已基本不可能。必須要找到一種模型降階及簡化技術(shù)，使之能夠正確的對寄生參數(shù)提取的整體結(jié)果進行分析，得出較為正確的結(jié)果。

模型降階的本質(zhì)，是在保證精度的情況下，把復(fù)雜的系統(tǒng)簡化為一個等價的簡單的系統(tǒng)，以達到簡化模型，加速計算的目的，從而能夠高效準(zhǔn)確地對原問題求解。

模型降階的內(nèi)容包括，根據(jù)提取的各個節(jié)點之間的寄生參數(shù)列出方程組，然后求解這些方程組，建立描述電路特性的簡單又精確的宏模型。對于如何利用計算機快速并且運用較少內(nèi)存地求解線性代數(shù)方程組，這是一個純數(shù)學(xué)應(yīng)用問題，這也是一個很經(jīng)典的問題，已經(jīng)有很多關(guān)于計算機求解線性代數(shù)的研究，研究已比較成熟。

本文采用改進節(jié)點分析法（Modified Nodal Approach）進行電路方程的建立。節(jié)點法有一些存在的問題，改進節(jié)點法克服了這些問題。在節(jié)點法電壓作為方程未知變數(shù)外，還添加了支路電流作為新的未知變量。在保持原節(jié)點法的方程階數(shù)低、方法簡單的優(yōu)點的同時，克服了節(jié)點法不能直接處理獨立源支路、阻抗為零支路以及流控器件的弱點。正因為此，改進節(jié)點法得到了廣泛的應(yīng)用。許多知名的工具都是采用這個方法列方程的，例如美國著名的電路模擬程序SPICE[12]。而后用基于可觀測標(biāo)準(zhǔn)型的模型降階算法（Model Order Reduction using Observability Canonical form）建立簡單的宏模型，進行模型降階。

2 空間管理結(jié)構(gòu)與方法

基于平行板電容公式算法，對于寄生電容提取過程中，需要快速找出當(dāng)前金屬線所最臨近的金屬線或通孔，需要找出快速找出當(dāng)前金屬線固定距離范圍內(nèi)的所有的金屬線和通孔，用以計算寄生電容。由于互連線數(shù)量眾多（千兆級別），通過遍歷查找花費了過多的時間，不太合適，需要一種優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，保存互連線數(shù)據(jù)用以查找臨近線，以達到加快寄生電容提取的速度。

2.1 K-D樹

K-D樹（k-dimensional樹），是一種可以在K維數(shù)據(jù)空間的進行快速查找的數(shù)據(jù)結(jié)構(gòu)。K-D樹是二進制空間分割樹的特殊的情況，是對于二叉樹的拓展。二叉樹是對于一維空間一種有效的快速排序及查找的數(shù)據(jù)結(jié)構(gòu)，K-D樹是對于多個維度的二叉樹以各個維度循環(huán)排序的方式進行排序和查找的數(shù)據(jù)結(jié)構(gòu)。

研究中，由于互連線多為矩形（多邊形亦可拆分成多個矩形），擬用四維K-D樹，對芯片數(shù)據(jù)建立查找模型：

第一維：矩形左下角x坐標(biāo)；

第二維：矩形左下角y坐標(biāo)；

第三維：矩形右上角x坐標(biāo)；

第四維：矩形右上角y坐標(biāo)。

K-D樹模型在建立二維空間的互連線查找模型中的優(yōu)勢是十分突出的。它使用內(nèi)存少，建立時間短，查找時間短。缺點是在維度比較深的時候，運行速度會降低。

2.2 八叉樹

八叉樹（Octree），是針對在三維空間中的點的一種有效的劃分方法，三維空間分割恰是2^3=8，對于一個節(jié)點不是0個元素就是8個元素，對于這8個元素可以再繼續(xù)分割直至元素數(shù)量可被接受。

由于芯片設(shè)計是二維模型，所以芯片建?？梢岳盟牟鏄?。由于互連線是矩形，如果有多個互連線穿越多個象限，會有一些重復(fù)數(shù)據(jù)需要保存，使用的內(nèi)存相對于K-D樹就會更多。

2.3 網(wǎng)格劃分

即把空間分割成等距離的小塊，例如1um。每個小塊中存放對應(yīng)的數(shù)據(jù)。查找時，查找范圍內(nèi)對應(yīng)小塊直接取出或一一比較即可。這種方法相當(dāng)于只有一層的n*m叉樹（n和m為橫向和縱向的網(wǎng)格數(shù)）。

此方法，和四叉樹同理，如果有多個互連線穿越多個區(qū)域，會有一些重復(fù)數(shù)據(jù)需要保存，使用的內(nèi)存相對于K-D樹就會更多，甚至多過八叉樹。因查找時，需要經(jīng)歷查找范圍內(nèi)的對應(yīng)小塊，故對于查找區(qū)域較大，劃分較細的情況，速度會相對較慢；同時劃分較粗的情況，需要遍歷小塊中每個數(shù)據(jù)查找，速度會相對較慢。

3 實驗

為了驗證空間管理結(jié)構(gòu)對于提取寄生電容效率的影響，作者將建立不同的空間管理結(jié)構(gòu)進行效率比較及結(jié)果的比較，來驗證上一節(jié)提到的利用各種空間管理結(jié)構(gòu)所帶來的性能優(yōu)化以及結(jié)果的準(zhǔn)確性。

提取芯片寄生參數(shù)流程如圖2所示。

實驗輸入數(shù)據(jù)：芯片中的物理信息及其連接關(guān)系及工藝信息。包括所有金屬線（wire）物理位置信息；所有通孔（via）物理位置信息；所有節(jié)點（node）物理位置信息；每一層的工藝（tech）信息，其中包括每一層上面的電阻率，相對介電常數(shù)，層的高度，上下層信息。

實驗輸出數(shù)據(jù)：提取的寄生電容電阻參數(shù)信息，包括有關(guān)聯(lián)的兩兩節(jié)點之間的寄生電容電阻數(shù)據(jù)。

處理過程：對于每一層的數(shù)據(jù)，建立空間管理結(jié)構(gòu)。查找同層金屬線左右兩側(cè)最近的平行金屬線，分別計算與左側(cè)、與右側(cè)線與線的寄生電容，同理查找上層，下層最近的平行金屬線，分別計算線與線的寄生電容，而后將線與線的寄生電容轉(zhuǎn)換計算成點與點之間的寄生電容。

因數(shù)據(jù)量巨大，寄生電容套用平行板電容公式以求簡化。

C= ε*A/D

ε是介質(zhì)層的相對介電常數(shù)。A是重疊部分面積。D是兩塊板之間的距離。同時考慮上一章所提及的平行板的邊緣效應(yīng)對于實際結(jié)果的影響。芯片中的電容示意圖如圖3所示。

根據(jù)不同的互連線情況，各個數(shù)據(jù)結(jié)構(gòu)所需要的時間是不同的。本實驗使用了三個實例分別是三個有著不同互連線數(shù)目的實際電路設(shè)計。實驗結(jié)果如表1所示。

經(jīng)驗證實驗中利用各種空間管理結(jié)構(gòu)的最終查找臨近線的結(jié)果完全一致且正確。

對于兆級別量的互連線數(shù)據(jù)，使用遍歷的方法去尋找臨近線提取電容，消耗時間上遠遠大于使用空間管理結(jié)構(gòu)的方法，所以遍歷的方法不可行。

業(yè)界內(nèi)主流仿真工具，對于查找臨近線是使用的K-D樹的數(shù)據(jù)結(jié)構(gòu)。因此可以根據(jù)實驗結(jié)果和K-D樹查找數(shù)據(jù)結(jié)果比較，得出一些結(jié)論。

根據(jù)實驗數(shù)據(jù)，對于實例1、2使用四叉樹會以較多的內(nèi)存得到較優(yōu)的運算效率（約多用10%內(nèi)存，加速40%），對于實例3上層四叉樹+下層K-D樹有最優(yōu)的運算效率（約相似的內(nèi)存使用，加速50%）?？傮w的結(jié)論有，在數(shù)據(jù)量不是特別大的時候（兆級別），K-D樹使用較少的內(nèi)存，四叉樹有較快的效率；在數(shù)據(jù)量比較大的時候（百兆級別），使用上層四叉樹，下層K-D樹的結(jié)構(gòu)能夠獲得較優(yōu)的速度和較少的內(nèi)存。

4 結(jié)語

對于文中提出的利用各種空間管理結(jié)構(gòu)提高芯片級大規(guī)模寄生電容提取的效率及減少內(nèi)存的方法得到了實驗驗證。實驗使用了多種空間管理結(jié)構(gòu)以及其各種組合結(jié)構(gòu)進行實際比較，結(jié)果表明針對于不同情況的實例，可以應(yīng)用不同的空間管理結(jié)構(gòu)以獲取較快的效率和較少的內(nèi)存。對于互連線數(shù)量小于等于兆級別，互連線長度不長，使用四叉樹空間管理結(jié)構(gòu)會以多消耗一些內(nèi)存的代價達到更優(yōu)化的速度；對于互連線數(shù)量百兆級別，使用上層四叉樹，下層K-D樹結(jié)構(gòu)保存數(shù)據(jù)，既能消耗不多的內(nèi)存，又能得到更快的查找速度。

為獲取更準(zhǔn)確的寄生電容值，后面的研究將會更深入的考慮平行板電容器邊緣效應(yīng)及周圍環(huán)境所造成的影響。

參考文獻

[1]喻文健，王習(xí)仁.面向集成電路電阻電容提取的高級場求解器技術(shù)[M].北京：清華大學(xué)出版社，2014：1-2.

[2]陳中憲.超大規(guī)模集成電路互連線分析與綜合[M].北京：清華大學(xué)出版社，2008：1-2.

[3]Keith Nabors， Jacob White， FastCap： A Multipole Accelerated 3-D Capacitance Extraction Program[J].IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN，1991，10（11）：1447-1459.

[4]Keith Nabors，Songmin Kim，Jacob White，F(xiàn)ast Capacitance Extraction of General Three-Dimensional Structures[J].IEEE TRANSACTIONS ON MICROWAVE THEORY AND TECHNIQUES. 1992，40（7）：1496-1505

[5]喻文健，王澤毅.三維VLSI互連線寄生電容提取的研究進展[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2003，15（1）：21-26.

[6]J Tausch，J White.A multiscale method for fast capacitance extraction[J].In Proceedings of Design Automation Conference，New Orleans.1999：537-542.

[7]K K Mei，R Pous，Z Chen，et al.Measured equation of invariance：a new concept in field computations[J]，IEEE Transactions on Antennas and Propagation.1994，42（3）：320-328.

[8]W Sun，WM Dai，W Hong，F(xiàn)ast parameter extraction of general interconnects using geometry independent measured equation of invariance[J].IEEE Transactions on Microwave Theory and Techniques.1997， 45（5）：827-836.

[9]EA Dengi，RA Rohrer，Hierarchical 2D field solution for capacitance extraction for VLSI interconnect modeling[J].In Proceedings of the 34th Annual Conference on Design Automation Conference，Anaheim，1997：127-132.

[10]喻文健，王習(xí)仁.面向集成電路電阻電容提取的高級場求解器技術(shù)[M].北京：清華大學(xué)出版社，2014：179-183.

[11]朱益清，徐堅宏.計及邊緣效應(yīng)的平行板電容器的電容計算[J].工科物理，1998，8（1）：7-9.

[12]楊華中，羅嶸，汪蕙.電子電路的計算機輔助分析與設(shè)計方法[M].第2版，北京：清華大學(xué)出版社，2008：24-25.