基於gpu的集成電路電容參數提取系統及方法
2023-06-15 16:06:31 1
專利名稱：基於gpu的集成電路電容參數提取系統及方法
技術領域：
本發明涉及VLSI (Very Large Scale Integrated circuits,超大規模集成電路)物理設計領域，特別是關於集成電路互連電容參數的提取與電路時延分析。
背景技術：
集成電路的設計流程中首先要提出功能描述，然後經過邏輯設計、版圖設計得到描述半導體工藝尺寸、結構的版圖，最後進行版圖驗證，即通過計算機軟體模擬來驗證上述設計是否滿足要求。若滿足要求，則進行下一步的生產製造。否則，若不滿足要求，則返回邏輯設計、版圖設計進行必要的修正。在版圖驗證中，一個重要的環節是「互連寄生參數提取」。隨著集成電路製造技術的發展，電路規模不斷增大、特徵尺寸不斷縮小，當今很多晶片已含有幾千萬乃至上億個器件。然而，集成電路中互連線的寄生效應造成互連線對電路延時的影響已超過了器件對電路延時的影響。因此，需要對互連線的電容、電阻等參數進行準確的計算，以保證電路模擬與驗證的正確有效性。為了提高計算精度，互連線之間的電容參數提取需要使用三維提取方法，即利用三維場求解器進行求解。場求解器的計算往往耗時較多，對其算法的優化與加速研究意義很大。在集成電路電容參數提取的場求解器方法中，隨機行走電容提取算法是一種比較流行的方法。申請人在第十七屆國際會議Asia and South Pacific Design AutomationConference 2012 發表的論文「Fast Floating Random Walk Algorithm for CapacitanceExtraction with Numerical Characterization of Green’s Function，，中，公開了一種集成電路多層介質工藝隨機行走電容提取方法。該方法在給定集成電路多層介質工藝的條件下(即導體周圍為多層介質)，預計算隨機行走算法中需要的信息(如多層介質層轉移區域的轉移概率分布以及相應權值分布數據)並應用於隨機行走算法中，從而在多層介質情況下進行電容參數提取時能進行跨介質層的跳轉操作。然而，所述論文中提取電容參數的方法仍然耗時較多，因此，其效率有待提高。
發明內容
鑑於以上內容，有必要提供一種基於GPU的集成電路電容參數提取系統與方法，能夠快速計算集成電路中主導體與每個環境導體之間的電容參數。一種基於GPU的集成電路電容參數提取系統，運行於計算設備中，該計算設備包括存儲設備、CPU及GPU，所述存儲設備存儲集成電路版圖、預先建立的格林函數庫及權值向量，該系統包括:初始化模塊，用於(a)設置目標精度q、GPU線程數threadNum、GPU線程塊的數目blockNum及總目標路徑數pathGoal,其中blockNum是threadNum的約數；(b)從所述存儲設備中讀取集成電路版圖、格林函數庫及權值向量；(c)在CPU的內存及GPU的全局存儲器中分配電容參數提取所需的存儲空間並初始化變量；(d)在所述集成電路版圖中建立一個包圍主導體的高斯面，高斯面內僅包含主導體並且不與任何環境導體相交；及(e)根據GPU線程數threadNum、GPU線程塊的數目blockNum及總目標路徑數pathGoal,計算每個GPU線程塊的最小目標路徑數blockWalkMin與每個GPU線程的最大目標路徑數threadWalkMax ;隨機行走開始模塊,用於(f)並行地運行threadNum個GPU線程,每個GPU線程根據建立的高斯面及讀取的格林函數庫生成threadWalkMax個行走起始點,根據讀取的權值向量查找行走起始點對應的權值，並將行走起始點的坐標及行走起始點對應的權值存儲到GPU的全局存儲器中；隨機行走跳轉模塊，用於(g)並行地運行blockNum個GPU線程塊，GPU線程塊中的每個GPU線程不斷地從GPU的全局存儲器中讀取行走起始點進行隨機行走，直到GPU線程執行了 threadWalkMax次行走，或者整個GPU線程塊執行了 blockWalkMin次行走，每次行走從一個行走起始點開始，直到擊中某一導體，將每次行走擊中導體的編號存儲到GPU的全局存儲器中，當所有GPU線程塊都執行了 blockWalkMin次行走，本模塊結束；隨機行走統計模塊，用於(h)並行地運行threadNum個GPU線程，從GPU的全局存儲器中讀取隨機行走跳轉模塊存儲的擊中導體的編號及相應的行走起始點對應的權值，根據讀取的擊中導體的編號及相應的行走起始點對應的權值計算主導體與每個環境導體的累計電容值及累計電容平方和，並將計算的主導體與每個環境導體的累計電容值及累計電容平方和存儲到GPU的全局存儲器中；及控制模塊，用於(i)將GPU的全局存儲器中存儲的主導體與每個環境導體的累計電容值及累計電容平方和複製到CPU的內存中；及(j)根據CPU的內存中存儲的主導體與每個環境導體的累計電容值及累計電容平方和計算主導體的自電容的相對誤差relError,若relError小於等於目標精度q，則計算主導體與每個環境導體之間的耦合電容及主導體的自電容，否則，若relError大於目標精度q，則更新總目標路徑數pathGoal，更新後的總目標路徑數即達到目標精度還需行走的路徑數。—種基於GPU的集成電路電容參數提取方法，應用於計算設備中，該計算設備包括存儲設備、CPU及GPU，所述存儲設備存儲集成電路版圖、預先建立的格林函數庫及權值向量，該方法包括:(a)設置目標精度q、GPU線程數threadNum及總目標路徑數pathGoal,其中blockNum是threadNum的約數；(b)從所述存儲設備中讀取集成電路版圖、格林函數庫及權值向量；(c)在CPU的內存及GPU的全局存儲器中分配電容參數提取所需的存儲空間並初始化變量；(d)在所述集成電路版圖中建立一個包圍主導體的高斯面，高斯面內僅包含主導體並且不與任何環境導體相交；(e)根據GPU線程數threadNum、GPU線程塊的數目blockNum及總目標路徑數pathGoal，計算每個GPU線程塊的最小目標路徑數blockWalkMin與GPU線程的最大目標路徑數threadWalkMax ； (f)並行地運行threadNum個GPU線程，每個GPU線程根據建立的高斯面及讀取的格林函數庫生成threadWalkMax個行走起始點，根據讀取的權值向量查找行走起始點對應的權值，並將行走起始點的坐標及行走起始點對應的權值存儲到GPU的全局存儲器中；(g)並行地運行blockNum個GPU線程塊，GPU線程塊中的每個GPU線程不斷地從GPU的全局存儲器中讀取行走起始點進行隨機行走，每次行走從一個行走起始點開始，直到擊中某一導體，將每次行走擊中導體的編號存儲到GPU的全局存儲器中，直到GPU線程執行了 threadWalkMax次行走，或者整個GPU線程塊執行了 blockWalkMin次行走，當所有GPU線程塊都執行了 blockWalkMin次行走，本步驟結束；(h)並行地運行threadNum個GPU線程，從GPU的全局存儲器中讀取步驟(g)中存儲的擊中導體的編號及相應的行走起始點對應的權值，根據讀取的擊中導體的編號及相應的行走起始點對應的權值計算主導體與每個環境導體的累計電容值及累計電容平方和，並將計算的主導體與每個環境導體的累計電容值及累計電容平方和存儲到GPU的全局存儲器中；(i)將GPU的全局存儲器中存儲的主導體與每個環境導體的累計電容值及累計電容平方和複製到CPU的內存中；(j)根據CPU的內存中存儲的主導體與每個環境導體的累計電容值及累計電容平方和計算主導體的自電容的相對誤差relError,若relError小於等於目標精度q，則計算主導體與每個環境導體之間的耦合電容及主導體的自電容，否則，若relError大於目標精度q，則更新總目標路徑數pathGoal，然後返回步驟(e)，更新後的總目標路徑數即達到目標精度還需行走的路徑數。本發明利用GPlKGraphic Processing Unit,圖形處理器)的並行處理能力來加快隨機行走電容提取算法的計算速度。目前，GPU已成為具有眾多計算核心的通用計算設備，GTO採用單指令多數據(SMD)的並行計算方式。使用GPU進行並行計算時，多個線程被組織成線程塊(thread block)，整個線程塊中的線程按SMD方式並行執行。而且，在並行計算資源調度中，GPU線程塊是基本單元。本發明將隨機行走算法分成三個不同的模塊，不同的模塊之間通過在GPU全局存儲器上的存儲空間進行數據交換。通過模塊分割，本發明能夠有效減少GPU上不同線程的指令分歧，從而有效提高並行計算效率。此外，本發明通過整體迭代與估算剩餘的隨機行走路徑數目，能根據所設目標精度自動確定所需的隨機行走路徑數，達到了加快收斂過程、減少總計算時間的效果。
圖1是本發明基於GPU的集成電路電容參數提取系統較佳實施例的運行環境示意圖。圖2是集成電路的導體分布示意圖。圖3是本發明基於GPU的集成電路電容參數提取方法的示意圖。圖4是圖1中基於GPU的集成電路電容參數提取系統的功能模塊圖。圖5是本發明基於GPU的集成電路電容參數提取方法較佳實施例的流程圖。圖6是圖5中步驟S506的細化流程圖。圖7是圖5中步驟S507的細化流程圖。圖8是圖5中步驟S508的細化流程圖。圖9是圖5中步驟S510的細化流程圖。主要元件符號說明
權利要求
1.一種基於GPU的集成電路電容參數提取系統，運行於計算設備中，該計算設備包括存儲設備、CPU及GPU，所述存儲設備存儲集成電路版圖、預先建立的格林函數庫及權值向量，其特徵在於，該系統包括: 初始化模塊，用於(a)設置目標精度q、GPU線程數threadNum、GPU線程塊的數目blockNum及總目標路徑數pathGoal,其中blockNum是threadNum的約數；(b)從所述存儲設備中讀取集成電路版圖、格林函數庫及權值向量；(c)在CPU的內存及GPU的全局存儲器中分配電容參數提取所需的存儲空間並初始化變量；(d)在所述集成電路版圖中建立一個包圍主導體的高斯面,高斯面內僅包含主導體並且不與任何環境導體相交；及(e)根據GPU線程數threadNum、GPU線程塊的數目blockNum及總目標路徑數pathGoal,計算每個GPU線程塊的最小目標路徑數blockWalkMin與每個GPU線程的最大目標路徑數threadWalkMax ；隨機行走開始模塊，用於(f)並行地運行threadNum個GPU線程，每個GPU線程根據建立的高斯面及讀取的格林函數庫生成threadWalkMax個行走起始點,根據讀取的權值向量查找行走起始點對應的權值，並將行走起始點的坐標及行走起始點對應的權值存儲到GPU的全局存儲器中； 隨機行走跳轉模塊，用於(g)並行地運行blockNum個GPU線程塊，GPU線程塊中的每個GPU線程不斷地從GPU的全局存儲器中讀取行走起始點進行隨機行走，直到GPU線程執行了 threadWalkMax次行走,或者整個GPU線程塊執行了 blockWalkMin次行走,每次行走從一個行走起始點開始，直到擊中某一導體，將每次行走擊中導體的編號存儲到GPU的全局存儲器中，當所有GPU線程塊都執行了 blockWalkMin次行走，本模塊結束； 隨機行走統計模塊，用於(h)並行地運行threadNum個GPU線程，從GPU的全局存儲器中讀取隨機行走跳轉模塊存儲的擊中導體的編號及相應的行走起始點對應的權值，根據讀取的擊中導體的編號及相 應的行走起始點對應的權值計算主導體與每個環境導體的累計電容值及累計電容平方和，並將計算的主導體與每個環境導體的累計電容值及累計電容平方和存儲到GPU的全局存儲器中；及 控制模塊，用於(i)將GPU的全局存儲器中存儲的主導體與每個環境導體的累計電容值及累計電容平方和複製到CPU的內存中；及(j)根據CPU的內存中存儲的主導體與每個環境導體的累計電容值及累計電容平方和計算主導體的自電容的相對誤差relError，若relError小於等於目標精度q，則計算主導體與每個環境導體之間的耦合電容及主導體的自電容，否則，若relError大於目標精度q，則更新總目標路徑數pathGoal，更新後的總目標路徑數即達到目標精度還需行走的路徑數。
2.如權利要求1所述的基於GPU的集成電路電容參數提取系統，其特徵在於，所述(f)中每個行走起始點的生成包括步驟: (Π)從建立的高斯面上隨機選取一個點，以選取的點為中心，構造一個極大的不包含任何導體的立方體轉移區域；及 (f2)在轉移區域的表面，根據讀取的格林函數庫，選取一個點作為行走起始點。
3.如權利要求1所述的基於GPU的集成電路電容參數提取系統，其特徵在於，所述(e)中GPU線程塊的最小目標路徑數blockWalkMin與GPU線程的最大目標路徑數threadWalkMax根據以下公式計算:
4.如權利要求1所述的基於GPU的集成電路電容參數提取系統，其特徵在於，所述總目標路徑數pathGoal根據以下公式更新:
5.一種基於GPU的集成電路電容參數提取方法，應用於計算設備中，該計算設備包括存儲設備、CPU及GPU，所述存儲設備存儲集成電路版圖、預先建立的格林函數庫及權值向量，其特徵在於，該方法包括: (a)設置目標精度q、GPU線程數threadNum及總目標路徑數pathGoal,其中blockNum是threadNum的約數； (b)從所述存儲設備中讀取集成電路版圖、格林函數庫及權值向量； (c)在CPU的內存及GPU的全局存儲器中分配電容參數提取所需的存儲空間並初始化變量； (d)在所述集成電路版圖中建立一個包圍主導體的高斯面，高斯面內僅包含主導體並且不與任何環境導體相交； (e)根據GPU線程數threadNum、GPU線程塊的數目blockNum及總目標路徑數pathGoal,計算每個GPU線程塊的最小目標路徑數blockWalkMin與GPU線程的最大目標路徑數 threadWalkMax ； (f)並行地運行threadNum個GPU線程，每個GPU線程根據建立的高斯面及讀取的格林函數庫生成threadWalkMax個行走起始點,根據讀取的權值向量查找行走起始點對應的權值，並將行走起始點的坐標及行走起始點對應的權值存儲到GPU的全局存儲器中； (g)並行地運行blockNum個GPU線程塊，GPU線程塊中的每個GPU線程不斷地從GPU的全局存儲器中讀取行走起始點進行隨機行走，每次行走從一個行走起始點開始，直到擊中某一導體，將每次行走擊中導體的編號存儲到GPU的全局存儲器中，直到GPU線程執行了threadWalkMax次行走,或者整個GPU線程塊執行了 blockWalkMin次行走，當所有GPU線程塊都執行了 blockWalkMin次行走,本步驟結束； (h)並行地運行threadNum個GPU線程,從GPU的全局存儲器中讀取步驟(g)中存儲的擊中導體的編號及相應的行走起始點對應的權值，根據讀取的擊中導體的編號及相應的行走起始點對應的權值計算主導體與每個環境導體的累計電容值及累計電容平方和，並將計算的主導體與每個環境導體的累計電容值及累計電容平方和存儲到GPU的全局存儲器中； (i)將GPU的全局存儲器中存儲的主導體與每個環境導體的累計電容值及累計電容平方和複製到CPU的內存中；(j)根據CPU的內存中存儲的主導體與每個環境導體的累計電容值及累計電容平方和計算主導體的自電容的相對誤差relError,若relError小於等於目標精度q，則計算主導體與每個環境導體之間的耦合電容及主導體的自電容，否則，若relError大於目標精度q，則更新總目標路徑數pathGoal，然後返回步驟(e)，更新後的總目標路徑數即達到目標精度還需行走的路徑數。
6.如權利要求5所述的基於GPU的集成電路電容參數提取方法，其特徵在於，所述GPU線程塊的最小目標路徑數blockWalkMin與GPU線程的最大目標路徑數threadWalkMax根據以下公式計算:
7.如權利要求5所述的基於GPU的集成電路電容參數提取方法，其特徵在於，步驟(f)中每個行走起始點的生成包括步驟: (Π)從建立的高斯面上隨機選取一個點，以選取的點為中心，構造一個極大的不包含任何導體的立方體轉移區 域；及 (f2)在轉移區域的表面，根據讀取的格林函數庫，選取一個點作為行走起始點。
8.如權利要求5所述的基於GPU的集成電路電容參數提取方法，其特徵在於，步驟(g)中每次行走包括步驟: (gl)從GPU的全局存儲器中讀取一個行走起始點作為當前行走點； (g2)以當前行走點為中心，構造一個極大的不包含導體的立方體轉移區域； (g3)根據讀取的格林函數庫，在當前行走點的轉移區域的表面隨機選取一個點作為下一個行走點； (g4)判斷下一個行走點是否擊中導體，若未擊中導體，則跳轉到步驟(g2);及(g5)否則，若下一個行走點擊中導體，將本次行走擊中導體的編號存儲到GPU的全局存儲器中。
9.如權利要求5所述的基於GPU的集成電路電容參數提取方法，其特徵在於，所述步驟(j)包括: (jl)計算累計已行走的路徑數pathNum ; (J2)根據CPU的內存中存儲的主導體與每個環境導體的累計電容值及累計電容平方和計算主導體和每個環境導體之間的耦合電容的誤差； (J3)根據主導體與每個環境導體的累計電容值及主導體和每個環境導體之間的耦合電容的誤差計算主導體的自電容的相對誤差relError ； (J4)判斷主導體的自電容的相對誤差relError是否小於等於目標精度q ； (j5)若relError小於等於目標精度q，則計算主導體與每個環境導體之間的耦合電容及主導體的自電容，並輸出主導體和每個環境導體之間的耦合電容的誤差、主導體的自電容的相對誤差relError、主導體與每個環境導體之間的耦合電容及主導體的自電容；及(j6)若relError大於目標精度q，根據當前累計已行走的路徑數pathNum及主導體的自電容的相對誤差relError更新總目標路徑數pathGoal。
10.如權利要求5所述的基於GPU的集成電路電容參數提取方法，其特徵在於，所述總目標路徑數pathGoal根據以下公式更新:
全文摘要
一種基於GPU的集成電路電容參數提取系統及方法，該系統包括隨機行走開始模塊、隨機行走跳轉模塊及隨機行走統計模塊。各模塊在GPU的全局存儲器上進行數據交換。每個模塊並行運行多個GPU線程。隨機行走開始模塊中，每個GPU線程生成指定數量的行走起始點並獲得行走起始點對應的權值。隨機行走跳轉模塊中，每個GPU線程進行指定次數隨機行走，獲得每次行走擊中導體的編號。隨機行走統計模塊中，每個GPU線程讀取指定數量的擊中導體的編號及相應的行走起始點對應的權值用以計算累計電容值及累計電容平方和。若主導體自電容的相對誤差未達到目標精度，則估算還需行走的路徑數。本發明能夠實現集成電路電容參數的快速提取。
文檔編號G06F17/50GK103198177SQ20131007617
公開日2013年7月10日 申請日期2013年3月11日 優先權日2013年3月11日
發明者喻文健, 翟匡亞, 莊昊 申請人:清華大學