[發明專利]一種GPU加速構建最小直角斯坦納樹的芯片布線方法

在審

• 申請號: 202211285801.8
• 申請日: 2022-10-20
• 公開（公告）號: CN115563927A
• 公開（公告）日: 2023-01-03
• 發明（設計）人: 林亦波;郭資政;谷豐
• 申請（專利權）人: 北京大學
• 主分類號: G06F30/394
• 分類號: G06F30/394;G06F30/398;G06F115/06
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

本發明公布了一種GPU加速構建最小直角斯坦納樹的芯片布線方法，屬于集成電路設計自動化技術領域，涉及集成電路芯片布線技術，設計了一種應用于芯片布線的GPU加速計算的最小直角斯坦納樹構建方法，使用GPU大規模并行加速多個線網的斯坦納樹搜索過程，包括：查找表初始化，獲得扁平化的斯坦納樹分支列表和分支查找表索引，并從CPU內存復制到GPU顯存；線網數據初始化，獲得線網的管腳列表和管腳起始位置索引，并從CPU內存復制到GPU顯存；線網并行分割，建立分層的線網分割森林；線網并行求解合并；本發明提供的技術方案提升了集成電路芯片布線的計算效率。

技術領域

本發明屬于集成電路設計自動化技術領域，涉及集成電路芯片布線技術中的斯坦納樹構建技術，具體涉及一種GPU加速計算的最小直角斯坦納樹構建方法用于芯片布線，使用GPU大規模并行加速多個線網的斯坦納樹搜索過程，提升了集成電路芯片布線的計算效率。

背景技術

布線是芯片設計的核心步驟，在這一步驟中，芯片設計自動化系統會為芯片中的每一個線網計算布線的方案。芯片中的線網是一個芯片管腳的集合，每個管腳是一個二維的坐標，代表它在芯片上的位置。芯片布線的任務就是使用金屬線將每個線網內部的管腳連接起來。在芯片設計的早期步驟中，布線的方案通常使用最小直角斯坦納樹（Rectilinear Steiner Minimum Tree, RSMT）進行近似。對于一個給定的線網，只使用橫線和豎線將線網的所有管腳連接起來，可以經過任意中轉點，就得到了一個直角斯坦納樹。最小直角斯坦納樹定義為總線長最短的直角斯坦納樹。

由于最小直角斯坦納樹構建問題很難精確求解，因此，現有方法在時間和求解精度上追求平衡。其中，快速查表估計法（Fast Look-Up Table Estimation, FLUTE）是最典型的方法，能夠在維持較優的求解精度同時，達到較高的計算效率。然而，隨著芯片設計規模的不斷提升，一次布線需要對數百萬個線網求解最小直角斯坦納樹，花費大量時間。包括FLUTE在內的現有方法僅支持CPU上運行，受限于多核CPU的并行能力和內存調度能力，也只能利用最多16線程的并行計算資源，難以高效完成大規模電路的快速布線估計。

發明內容

本發明的目的是提供一種GPU加速計算的最小直角斯坦納樹構建方法，高效地完成大規模電路的快速布線估計，以克服上述現有最小直角斯坦納樹構建方法存在的不足。

本發明通過將斯坦納樹搜索過程設計成為GPU友好的廣度優先計算流程，利用GPU的大規模數據并行計算能力來同時處理大量線網的最小直角斯坦納樹構建任務。在不降低求解精度的前提下，提升了最小直角斯坦納樹的構建效率，提升了集成電路芯片布線的計算效率。

本發明的技術方案是：

一種GPU加速計算構建最小直角斯坦納樹的芯片布線方法，包括步驟：查找表初始化，線網數據初始化，線網并行分割，線網并行求解合并。在查找表初始化過程中，使用快速查表估計法（FLUTE）對線網度數小于查找表閾值的所有線網，構建最小直角斯坦納樹查找表；將最小直角斯坦納樹查找表扁平化，獲得扁平化的斯坦納樹分支列表和分支查找表索引；將扁平化的斯坦納樹分支列表和分支查找表索引從CPU內存復制到GPU顯存。在線網數據初始化過程中，將輸入的線網扁平化，獲得線網的管腳列表和管腳起始位置索引，將管腳列表和起始位置索引從CPU內存復制到GPU顯存。在線網并行分割步驟中，在GPU上對線網的管腳列表和管腳起始位置索引進行迭代分割，建立分層的線網分割森林；在獲得的下一層線網管腳列表和管腳起始位置索引上重復進行分割操作，直至所有線網的管腳個數都小于查找表閾值。在線網并行求解合并過程中，在GPU上對分割的線網進行求解，若度數小于查找表閾值，則通過扁平化的斯坦納樹分支列表和分支查找表索引獲得線網的最小直角斯坦納樹，若度數大于查找表閾值，則從下層線網的求解結果合并得到本線網的最小直角斯坦納樹；對線網求解的順序是在分層的線網分割森林上從下層到上層；獲得頂層線網的合并結果，即為輸入線網的最小直角斯坦納樹求解結果。具體包含如下步驟：

A. 查找表初始化；