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

在審

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

1.一種GPU加速構建最小直角斯坦納樹的芯片布線方法，其特征是，包括步驟：

A. 查找表初始化，獲得扁平化的斯坦納樹分支列表和分支查找表索引，并從CPU內存復制到GPU顯存；包括：

A1.對芯片中線網度數小于查找表閾值的所有線網，構建最小直角斯坦納樹查找表；最小直角斯坦納樹查找表包含從線網管腳相對位置編碼到潛在最小直角斯坦納樹的映射；查找表閾值為常數；

A2.將最小直角斯坦納樹查找表扁平化，獲得扁平化的斯坦納樹分支列表和分支查找表索引；具體過程是將潛在最小直角斯坦納樹的所有分支按照管腳相對位置編碼順序存放在數組中，使得上一個斯坦納樹的最后一個分支與下一斯坦納樹的首個分支相鄰，得到的分支數組即為扁平化的斯坦納樹分支列表；計算每個潛在最小直角斯坦納樹的首個分支在數組中的下標，得到分支查找表索引；

A3.將扁平化的斯坦納樹分支列表和分支查找表索引從CPU內存復制到GPU顯存；

B. 線網數據初始化，獲得線網的管腳列表和管腳起始位置索引，并從CPU內存復制到GPU顯存；

B1.芯片中所有線網為輸入的線網，將輸入的線網扁平化，獲得線網的管腳列表和管腳起始位置索引，其中線網的管腳列表包含橫坐標列表和縱坐標列表；

B2.將管腳列表和起始位置索引從CPU內存復制到GPU顯存；

C. 線網并行分割，建立分層的線網分割森林；

在GPU上對線網的管腳列表和管腳起始位置索引進行迭代分割，建立分層的線網分割森林，線網分割森林由多個線網分割樹組成，每個線網分割樹的節點是線網，連接父節點和子節點的樹邊代表由父節點線網分割得到子節點線網，根節點為輸入的線網，葉子結點為無需繼續分割的線網，即管腳個數小于查找表閾值的線網；

迭代分割的具體過程包括：

C1.從輸入的線網開始進行分割操作，輸入的線網構成第一層線網；

C2.對本層內的每個線網，通過管腳起始位置索引獲得線網管腳列表中這個線網的管腳所在的區間；

C3.定義線網度數為線網中的管腳數量，對度數已經小于查找表閾值的線網，不做任何操作；對度數大于等于查找表閾值的線網，選擇其中的一個管腳作為分割點，將線網分割成兩個線網，即為當前線網在線網分割樹上的子節點；

D. 線網并行求解合并：在GPU上對分割的線網進行求解，求解的具體方式是：

D1.若線網度數小于查找表閾值，則通過扁平化的斯坦納樹分支列表和分支查找表索引獲得線網的最小直角斯坦納樹，具體方法是計算管腳的相對位置編碼，通過分支查找表索引獲得最小直角斯坦納樹的所有分支在分支列表中的區間，這些分支即構成本線網的最小直角斯坦納樹；

D2. 若線網度數大于查找表閾值，則從下層線網的求解結果合并得到本線網的最小直角斯坦納樹，具體方法是將下層線網的最小直角斯坦納樹在分割點處連接起來；對多個分割方案，取直角斯坦納樹總線長最小的方案作為本線網的分割方案；

D3. 對線網求解的順序是在分層的線網分割森林上從下層到上層，獲得頂層線網的合并結果，即為輸入線網的最小直角斯坦納樹求解結果；

E. 根據得到的輸入線網的最小直角斯坦納樹求解結果，實現GPU加速構建最小直角斯坦納樹的芯片布線。

2.如權利要求1所述GPU加速構建最小直角斯坦納樹的芯片布線方法，其特征是，步驟A3中，具體是通過在CUDA平臺調用cudaMemcpyAsync函數，將扁平化的斯坦納樹分支列表和分支查找表索引從CPU內存復制到GPU顯存。

3.如權利要求1所述GPU加速構建最小直角斯坦納樹的芯片布線方法，其特征是，步驟B1中，將輸入的線網扁平化，具體過程是將輸入的線網中所有管腳表示為橫坐標和縱坐標，將橫坐標和縱坐標分別按照線網編號順序存放在兩個數組中，得到橫坐標列表和縱坐標列表，即為線網的管腳列表；計算每個線網的首個管腳在橫坐標列表和縱坐標列表中的下標，得到管腳起始位置索引。

4.如權利要求1所述GPU加速構建最小直角斯坦納樹的芯片布線方法，其特征是，步驟B2中，具體是通過在CUDA平臺調用cudaMemcpyAsync函數，將管腳列表和起始位置索引從CPU內存復制到GPU顯存。