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

在審

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

1.一種基于擁塞協商的拆線重布方法，其特征在于，包括以下步驟：

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

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

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

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

2.根據權利要求1所述的基于擁塞協商的拆線重布方法，其特征在于，所述輸入版圖信息，根據多波擴展算法構造出所有線網的斯坦納樹的步驟，進一步包括，

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

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

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

3.根據權利要求2所述的基于擁塞協商的拆線重布方法，其特征在于，所述根據kruscal和dijkstra的多波擴展算法為每一個所述端口圖形維護一個優先隊列，選擇最小代價的結點進行擴展的步驟，進一步包括，根據最小代價結點依次連接兩個最近的端口圖形，當擴展結點穿越兩個相鄰的矩形塊時，構成一段布線路徑。

4.根據權利要求1所述的基于擁塞協商的拆線重布方法，其特征在于，所述根據布線生成的路徑記錄當前布線代價，根據標記設計規則檢測的類型懲罰標記邊，增加標記邊上網格點的擁塞代價的步驟，進一步包括，

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

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

5.根據權利要求1所述的基于擁塞協商的拆線重布方法，其特征在于，所述拆除已有布線，根據更新代價值進行多波擴展算法迭代重新布線的步驟，進一步包括，獲取更新代價值，根據多波擴展算法生成對應的解結構進行布線，擴展時判斷是否存在擁塞代價，若存在則返回所述根據布線生成的路徑記錄當前布線代價，根據標記設計規則檢測的類型懲罰標記邊，增加標記邊上網格點的擁塞代價的步驟。

6.根據權利要求1所述的基于擁塞協商的拆線重布方法，其特征在于，所述滿足迭代次數或DRC清零后布線結束的步驟，進一步包括，清空當前代價，檢查布線結果并輸出線長數據。

7.一種布線設備，其特征在于，包括存儲器和處理器，所述存儲器上儲存有在所述處理器上運行的計算機程序，所述處理器運行所述計算機程序時執行權利要求1至6任一項所述的基于擁塞協商的拆線重布方法步驟。

8.一種計算機可讀存儲介質，其上存儲有計算機程序，其特征在于，所述計算機程序運行時執行權利要求1至6任一項所述的基于擁塞協商的拆線重布方法步驟。