芯片規模大結構RC寄生參數提取和低階建模

翁輝耀

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

關鍵詞：寄生參數提取；空間管理結構；模型降階

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

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

1 互連線寄生參數基本理論

1.1 互連技術概念

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

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

1.2 互連線寄生電阻提取

根據金屬導線電阻計算公式：

R=ρL/S=ρL/HW

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

1.3 互連線寄生電容提取

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

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

電壓：V=φ1-φ2

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

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

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

，

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

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

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

1.4 模型降階及簡化

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

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

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

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

2 空間管理結構與方法

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

2.1 K-D樹

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

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

第一維：矩形左下角x坐標；

第二維：矩形左下角y坐標；

第三維：矩形右上角x坐標；

第四維：矩形右上角y坐標。

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

2.2 八叉樹

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

由于芯片設計是二維模型，所以芯片建模可以利用四叉樹。由于互連線是矩形，如果有多個互連線穿越多個象限，會有一些重復數據需要保存，使用的內存相對于K-D樹就會更多。

2.3 網格劃分

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

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

3 實驗

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

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

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

實驗輸出數據：提取的寄生電容電阻參數信息，包括有關聯的兩兩節點之間的寄生電容電阻數據。

處理過程：對于每一層的數據，建立空間管理結構。查找同層金屬線左右兩側最近的平行金屬線，分別計算與左側、與右側線與線的寄生電容，同理查找上層，下層最近的平行金屬線，分別計算線與線的寄生電容，而后將線與線的寄生電容轉換計算成點與點之間的寄生電容。

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

C= ε*A/D

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

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

經驗證實驗中利用各種空間管理結構的最終查找臨近線的結果完全一致且正確。

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

業界內主流仿真工具，對于查找臨近線是使用的K-D樹的數據結構。因此可以根據實驗結果和K-D樹查找數據結果比較，得出一些結論。

根據實驗數據，對于實例1、2使用四叉樹會以較多的內存得到較優的運算效率（約多用10%內存，加速40%），對于實例3上層四叉樹+下層K-D樹有最優的運算效率（約相似的內存使用，加速50%）。總體的結論有，在數據量不是特別大的時候（兆級別），K-D樹使用較少的內存，四叉樹有較快的效率；在數據量比較大的時候（百兆級別），使用上層四叉樹，下層K-D樹的結構能夠獲得較優的速度和較少的內存。

4 結語

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

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

參考文獻

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

[2]陳中憲.超大規模集成電路互連線分析與綜合[M].北京：清華大學出版社，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，Fast Capacitance Extraction of General Three-Dimensional Structures[J].IEEE TRANSACTIONS ON MICROWAVE THEORY AND TECHNIQUES. 1992，40（7）：1496-1505

[5]喻文健，王澤毅.三維VLSI互連線寄生電容提取的研究進展[J].計算機輔助設計與圖形學學報，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，Fast 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]喻文健，王習仁.面向集成電路電阻電容提取的高級場求解器技術[M].北京：清華大學出版社，2014：179-183.

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

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