[發明專利]一種基于擁塞協商的拆線重布方法、設備及可讀存儲介質

在審

• 申請號: 202011218755.0
• 申請日: 2020-11-04
• 公開（公告）號: CN112149378A
• 公開（公告）日: 2020-12-29
• 發明（設計）人: 黃海山;張亞東;葉錦濤;陳家瑞;陳建利;劉偉平;李起宏;陸濤濤
• 申請（專利權）人: 深圳華大九天科技有限公司
• 主分類號: G06F30/394
• 分類號: G06F30/394;G06F30/3947;G06F119/20
• 代理公司: 北京德崇智捷知識產權代理有限公司 11467
• 代理人: 王金雙

一種基于擁塞協商的拆線重布方法、設備及可讀存儲介質，所述方法包括以下步驟：輸入版圖信息，根據多波擴展算法構造出所有線網的斯坦納樹；根據布線生成的路徑記錄當前布線代價，根據標記設計規則檢測的類型懲罰標記邊，增加標記邊上網格點的擁塞代價；拆除已有布線，根據更新代價值進行多波擴展算法迭代重新布線；滿足迭代次數或DRC清零后布線結束。本發明的基于擁塞協商的拆線重布方法，設備及可讀存儲介質，能夠利用歷史布線信息指導解決詳細布線階段的擁塞問題，將之前布線結果中擁塞的線網逐漸散開，獲取高質量的布線結果。

技術領域

本發明涉及VLSI設計自動化技術領域，特別是涉及一種超大規模集成電路（VLSI）多線網（net）的詳細布線擁塞解決方法。

背景技術

在VLSI詳細布線階段，需要確定每條net的具體走線。布線結果的好壞直接影響整個芯片的性能，該問題是一個 NP-完全問題。近年來, 隨著集成電路制造工藝的迅速發展,芯片集成度和復雜性不斷增加。通常一次詳細布線后往往會造成局部的擁塞，導致很多net不符合連接性約束，如不滿足Short（重疊）約束、Open（連通）約束，以及不符合設計規則檢測（DRC）約束，如Spacing（間距）約束等。因此在詳細布線階段往往需要進行多次的布線，花費大量的計算時間并且布線的質量不夠理想。因此，設計能夠有效處理VLSI多線網詳細布線的擁塞解決方法已成為VLSI設計自動化的關鍵問題之一。

人們提出了一些擁塞解決方法。有一類是基于多商品流和整數線性規劃的布線模型, 這類方法往往非常耗時, 甚至無法求解。因此，亟待出現一種高效的用于VLSI多線網詳細布線的擁塞解決方法。

發明內容

為了解決現有技術存在的不足，本發明的目的在于提供一種基于擁塞協商的拆線重布方法、設備及可讀存儲介質，能夠利用歷史布線信息指導解決詳細布線階段的擁塞問題，將之前布線結果中擁塞的線網逐漸散開，從而解決擁塞，獲取高質量的布線結果。

為實現上述目的，本發明提供的一種基于擁塞協商的拆線重布方法，包括以下步驟，

輸入版圖信息，根據多波擴展算法構造出所有線網的斯坦納樹；

根據布線生成的路徑記錄當前布線代價，根據標記設計規則檢測的類型懲罰標記邊，增加標記邊上網格點的擁塞代價；

拆除已有布線，根據更新代價值進行多波擴展算法迭代重新布線；

滿足迭代次數或DRC清零后布線結束。

進一步地，所述輸入版圖信息，根據多波擴展算法構造出所有線網的斯坦納樹的步驟，進一步包括，

讀入布線輸入版圖信息中所有線網的端口圖形，包括端口圖形的大小、層次以及各層的間隔規則；

根據網格將布線區域構造為行乘列的棋盤地圖結構，所述端口圖形分布在所述棋盤地圖內；

根據kruscal和dijkstra的多波擴展算法為每一個所述端口圖形維護一個優先隊列，選擇最小代價的結點進行擴展。

進一步地，所述根據kruscal和dijkstra的多波擴展算法為每一個所述端口圖形維護一個優先隊列，選擇最小代價的結點進行擴展的步驟，進一步包括，根據最小代價結點依次連接兩個最近的端口圖形，當擴展結點穿越兩個相鄰的矩形塊時，構成一段布線路徑。

進一步地，所述根據布線生成的路徑記錄當前布線代價，根據標記設計規則檢測的類型懲罰標記邊，增加標記邊上網格點的擁塞代價的步驟，進一步包括，

獲取當前設計規則檢測的標記類型，若產生重疊約束類型，增加當前標記邊結點擁塞代價；

若產生間距約束類型，將標記邊向擁塞方向膨脹二分之一線寬后，增加相應標記邊結點擁塞代價。