[發明專利]集成電路版圖驗證自適應掃描線解決方案

有效

• 申請號: 201010291055.4
• 申請日: 2010-09-26
• 公開（公告）號: CN102411643A
• 公開（公告）日: 2012-04-11
• 發明（設計）人: 宋德強;王小冷;丁豐慶
• 申請（專利權）人: 北京華大九天軟件有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明是一種使用于集成電路版圖驗證工具中的掃描線方案，所屬的技術領域是集成電路計算機輔助設計領域，尤其是涉及集成電路版圖的設計規則檢查(DRC)和版圖與原理圖的一致性檢查(LVS)領域。

背景技術

近30年來，集成電路技術一直按照“摩爾定律”向前發展。芯片的特征尺寸越來越小，單個芯片的集成度也越來越高。隨著芯片規模的擴大，在集成電路設計的各個階段所需驗證的設計規則也在不斷增多。其中集成電路版圖的設計規則檢查(DRC)以及集成電路版圖與原理圖的一致性檢查(LVS)變得越來越重要，它們對于消除錯誤、降低設計成本和減少設計失敗的風險具有重要作用。在超大規模集成電路設計中，版圖規模急劇膨脹，如何在有效時間內完成設計方案的驗證工作成為各大EDA廠商急需解決的問題。

掃描線方法最初是為解決線段相交問題而提出的。因為其高效率而在圖形運算中得到廣泛應用，是目前已知的最有效的版圖運算方法。其基本思想為：

(1)掃描線停頓點為線段的左、右端點及線段間的交點。

(2)垂直掃描線從左向右運動，在每一個停頓點處停留。起始于當前掃描線的所有線段進入當前工作表，終止于當前掃描線的所有線段從工作表中刪去，跨越當前掃描線的線段仍然保留。

(3)在當前掃描線狀態下，工作對象都在當前工作表中。

DRC不同于線段求交和圖形的邏輯、拓撲運算，其任務是幾何圖形的尺寸檢查。完成這一任務的關鍵是找出合適的檢查邊對，對此，掃描線方法具有獨到的優勢。掃描線方法是版圖驗證工具的核心技術，其性能的好壞直接影響集成電路版圖驗證工具的運行效率。

●新進邊：左端點在當前掃描線上的邊。

●離開邊：右端點在當前掃描線上的邊。

●變動邊：新進邊和離開邊。

●經過邊：當前掃描線上，非變動邊外的所有邊。經過邊與當前掃描線在非端點處相交。

●水平邊：邊斜率k＝＝0的邊。

●斜邊：邊斜率k！＝0的邊。

一般掃描線方法需要遍歷當前掃描線上所有的邊，這種方法效率比較低。實際上，在大規模版圖數據中，經過邊占93.3％，變動邊占6.7％；水平邊占93.9％，斜邊占6.1％。由此可見，非斜邊的經過邊的比例大概是87.6％(93.3％*93.9％)。而非斜邊的經過邊是不會對驗證命令結果產生影響的。自適應方案的核心內容就是減少對非斜邊經過邊的無用遍歷。

發明內容

本發明針對甚大規模集成電路版圖驗證過程中所面臨的運行速度過慢，運行時間過長，導致版圖驗證最終不可解的問題，提出了一種自適應的掃描線解決方案。此方案能夠正確的發揮歸并掃描線方法和索引掃描線方法的特征優勢，極大加速版圖驗證工具的運行速度，提高可驗證版圖規模。

本發明的主要技術方案包括以下六個方面：

第一，讀新進邊，更新離開邊鏈表。附圖1中的第1，2步。離開邊鏈表是一個二維鏈表，第一維存放掃描線坐標值，第二維存放該掃描線下的離開邊。每條新進邊都需要加入離開邊鏈表。離開邊會對驗證命令的輸出結果產生影響，需要在當前掃描線上重新計算結果。

第二，分析當前掃描線狀態，決定調用方式。附圖1中的第3步。這一步是自適應概念的集中體現。歸并掃描線方法在經過邊數量少，變動邊數量多的情況下效率高；而索引掃描線方法在經過邊數量多，變動邊數量少的情況下高效。本發明在以下兩種情況下調用歸并掃描線：

(1)經過邊數量大于變動邊數量10倍。

(2)索引掃描線連續執行次數超出了某一數值(步長)。

其他情況下調用索引掃描線方法。

第三，歸并掃描線方法。附圖1中的第4步。在歸并掃描線方法中，離開邊和經過邊存放在歷史邊鏈表中；新進邊在新進邊鏈表中。這兩個鏈表都是有序的，不同驗證命令，排序方式可能不同。在當前掃描線上遍歷邊計算結果與二路歸并排序是同時進行的。最終，新進邊鏈表中的邊會作為下一條掃描線中的歷史邊加入歷史邊鏈表。

索引掃描線需要依賴于歸并掃描線。歸并掃描線的另外兩項任務是為索引掃描線建立索引和清除不在當前掃描線上的歷史邊。

(1)為索引掃描線建立索引。歸并掃描線不使用索引，索引是專為索引掃描線準備的。在歸并遍歷過程中，每間隔一定數量S，取一條邊加入索引鏈表中。索引邊不能是斜邊，因為斜邊會調整排序位置。查找索引采用折半查找，遍歷兩條索引之間的邊采用順序查找。S的取值要適中。否則，如果S值過大，那查找就近似成為了順序遍歷，S取值過小，查找又近似成為折半查找。