[發明專利]考慮總線和非總線線網的層分配方法

有效

• 申請號: 202010096468.0
• 申請日: 2020-02-17
• 公開（公告）號: CN111291525B
• 公開（公告）日: 2022-04-08
• 發明（設計）人: 劉耿耿;朱偉大;郭文忠;陳國龍
• 申請（專利權）人: 福州大學
• 主分類號: G06F30/39
• 分類號: G06F30/39;G06F30/392
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 陳明鑫;蔡學俊

1.一種考慮總線和非總線線網的層分配方法，其特征在于，包括以下步驟：

步驟S1:考慮線長和引腳數的啟發式代價函數,決定第一階段線網的層分配順序；

步驟S2:基于最小化通孔的層分配算法進行通孔最小化層分配，得到初始層分配結果；

步驟S3:基于初始層分配結果，構建偏差查找表；

步驟S4:根據偏差查找表，將存在偏差的總線線網和所有非總線線網全部拆除；

步驟S5:考慮線長、引腳數、信號數和總線線長偏差四個要素組合的啟發式代價函數，確定第二階段線網的層分配順序；

步驟S6:基于最小化通孔的層分配算法進行通孔最小化層分配,得到層分配結果；

步驟S7:采用總線線網應用總線最大時序優化算法,優化總線線長偏差，得到優化后的層分配結果；

步驟S8:判斷是否存在總線線長偏差，若無偏差則輸出優化后的層分配結果，并作為最終層分配結果；若有偏差，則基于查找表的層調整策略進行調整，得到最終層分配結果；

所述步驟S1具體為：第一階段線網的層分配優先級只需評估引腳數和線長，優先級P1的計算公式如下：

其中，P_cost是線網N_i的引腳數，e¹_ij是邊的基本代價，e是線網N_i的邊；

所述步驟S5具體為：第二階段的層分配的目的是通過合理地利用通孔來優化總線線長偏差，以在獲得較少的線長偏差的同時不產生過多的通孔，優先級P2的計算公式如下：

其中，α和β是用戶自定義的系數，e¹_ij是邊的基本代價，e是線網N_i的邊，BD_i是第i個總線B_i的線長偏差，P_cost是線網N_i的引腳數，q是第i個總線B_i的信號數。

2.根據權利要求1所述的一種考慮總線和非總線線網的層分配方法，其特征在于所述最小化通孔的層分配算法具體為：

(1)使用深度優先搜索(DFS)對線網進行預處理，將出現環路2D布線結果進行拆環，從而轉化成一棵布線樹；

(2)隨機選擇一個節點作為根節點，再使用深度優先搜索形成一個有向圖，得到了動態規劃下所有邊的層分配順序；

(3)根據有向圖邊的層分配順序的逆序，得到了節點的遍歷順序；

(4)遍歷節點父邊的所有分配情況，計算該節點的最小通孔數，確定該節點的父邊應放置的層；

(5)回溯所有節點的父節點所在層，構建最終的層分配結果。

3.根據權利要求1所述的一種考慮總線和非總線線網的層分配方法，其特征在于：所述基于查找表的層調整策略包括層數限制的層調整策略和層數不限制的層調整策略。

4.根據權利要求3所述的一種考慮總線和非總線線網的層分配方法，其特征在于，所述層數限制的層調整策略具體為：

(1)從偏差查找表找出需要調整的匯引腳；

(2)遍歷源引腳到需要調整的匯引腳的邊，找到一個度數大于1的節點；

(3)計算該節點某個信號放置的最大層號、最小層號以及附近邊所使用的通孔數；

(4)在最小層號與最大層號之間移動所連接的邊，保證其通孔數不會超過原通孔數；

(5)選擇偏差最小的層，將邊調整到該層。