[發明專利]大規模集成電路版圖非結構網格偏心中點生成方法和系統

有效

• 申請號: 202010912374.6
• 申請日: 2020-09-03
• 公開（公告）號: CN112052641B
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 唐章宏;鄒軍;黃承清;汲亞飛;王芬
• 申請（專利權）人: 北京智芯仿真科技有限公司
• 主分類號: G06F30/392
• 分類號: G06F30/392
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 李興林

本發明涉及一種大規模集成電路版圖非結構網格偏心中點生成方法和系統。該大規模集成電路版圖非結構網格偏心中點生成方法和系統，通過采用偏心中點恢復法對丟失邊進行恢復，采用偏心中點消除法消除被侵蝕的邊。在丟失邊的恢復過程中嵌套有被侵蝕邊的消除，在被侵蝕邊的消除過程中嵌套有丟失邊的恢復，以保證消除所有丟失的邊和被侵蝕的邊。并且，針對丟失的邊和被侵蝕的邊生成的偏心中點形成的夾角正好為預先設定的定義三角形質量的三角形的最小角閾值，以使得在保證生成的網格質量滿足要求的同時，減少網格節點，以能夠在提高數值計算的速度的同時，減小計算內存。

技術領域

本發明涉及電路版圖非結構網格剖分領域，特別是涉及一種超大規模集成電路復雜版圖非結構網格偏心中點生成方法和系統。

背景技術

非結構網格剖分廣泛用于許多領域，如復雜電氣結構的電磁場數值計算、三維重建、計算機圖形學等領域。在多層超大規模集成電路的后端驗證電磁場仿真方面，非結構網格剖分更是起到非常重要的作用，因為多層超大規模集成電路的電源層通常具有非常復雜的走線和版圖，傳統的傳輸線法或有限差分法無法處理尺度范圍為厘米級到納米級的多尺度結構的集成電路，這就需要采用非結構網格精準識別并采用高質量網格單元剖分超大規模集成電路的版圖區域，進而采用電磁場數值計算方法計算得到電磁場在超大規模集成電路的分布。

針對超大規模集成電路版圖的特點，可采用二維非結構三角形網格將每層版圖及不同層之間的耦合區域進行網格剖分。由于版圖結構異常復雜，因此在對版圖區域進行網格剖分時，既需要高質量的三角形網格單元，又需要盡可能少的節點和網格單元。在現有技術中，三角形的質量被定義為：三角形外接圓的半徑與最短邊的長度之比。這個比值越大，三角形質量越差。通常，設定一個比值的閾值，在這個比值大于該閾值時，認為這個三角形的質量未達到要求，需要進一步插入新的節點進行細分，以改善三角形單元的質量。由于定義的三角形單元質量的比值等于1/(2sinθ_min)，這里θ_min為三角形的最小角，因此也可以通過三角形的最小角定義三角形單元的質量，與比值閾值對應的，定義三角形的質量達到要求的三角形的最小角閾值為θ_threshold，如果三角形的最小角小于最小角閾值θ_threshold，認為這個三角形的質量未達到要求。

現有技術中，生成二維的Delaunay三角剖分的方法包括消除網格剖分中丟失或被侵蝕的邊及改善網格單元質量兩個步驟。如果存在丟失或被侵蝕的邊，傳統算法會將邊的中點插入當前的Delaunay三角剖分中，并將該邊分為兩個子邊，重復操作直到不存在丟失或被侵蝕的邊。這里丟失的邊指：這個邊定義了集成電路版圖的邊界，但這個邊卻不在三角形網格中(不是三角形網格任一三角形單元的邊)。而被侵蝕的邊則是指：如果以這個邊為直徑的圓包含某些其他網格節點，那么這個邊稱為被侵蝕的邊(被所包含的網格節點侵蝕)。在判斷不存在丟失或被侵蝕的邊后，再次通過插入新的節點以改善網格剖分中三角形單元的質量。

基于傳統的這一算法可以發現，在消除網格剖分中丟失或被侵蝕的邊的過程中，不論是什么情況，都一律重復的在丟失或被侵蝕的邊的中點插入新的節點到網格中去，將該邊一分為二，直到不存在丟失或被侵蝕的邊。

以上這些算法特征，雖然能確保消除網格剖分中丟失或被侵蝕的邊，但在后續生成高質量二維非結構三角形網格過程中，會導致在某些局部區域生成過于密集的網格的問題，使得數值計算需要更多的計算時間和更大的內存的同時，其精度卻不會有顯著的提高。

因此，提供一種能夠減少高質量二維非結構三角形網格生成的網格節點，以在提高數值計算的速度的同時，減小計算內存的大規模集成電路版圖非結構網格偏心中點生成方法或系統，是本領域亟待解決的技術難題。

發明內容

本發明的目的是提供一種能夠減少高質量二維非結構三角形網格生成的網格節點，在提高數值計算的速度的同時，減小計算內存的大規模集成電路版圖非結構網格偏心中點生成方法和系統。

為實現上述目的，本發明提供了如下方案：