[發明專利]基于分支定界法的電路通道布線方法、裝置及電子設備

有效

• 申請號: 202110508171.5
• 申請日: 2021-05-11
• 公開（公告）號: CN112989751B
• 公開（公告）日: 2021-08-06
• 發明（設計）人: 魏迎梅;韓貝貝;竇錦身;楊雨璇;萬珊珊;馮素茹
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F30/3953
• 分類號: G06F30/3953;G06F111/04
• 代理公司: 北京風雅頌專利代理有限公司 11403
• 代理人: 曾志鵬

1.一種基于分支定界法的電路通道布線方法，其特征在于，包括：

在布線空間內構建二維網格；

在所述二維網格中標記電路圖中各個引腳的坐標；

將所述電路圖中相連的引腳作為引腳對，其中，所述電路圖包含多個引腳對；

根據分支定界法確定所述電路圖中的多個引腳對對應的布線路徑，具體包括：以所述引腳對中的一個引腳的坐標為基準點，以另一個引腳的坐標為終結點；從所述基準點可移動的至少一個方位點中確定距離所述終結點最近的方位點作為位移點，并舍棄其余方位點，以所述位移點為新的基準點，不斷迭代該過程直至位移至所述終結點，確定出目標引腳對對應的至少一個位移路線；將確定出的至少一個位移路線作為所述引腳對的布線路徑；

根據各個引腳對的布線路徑繪制電路布線圖；

所述引腳對未找到對應的布線路徑，確定所述引腳對為不可達引腳對，利用多層布線空間進行布線，并預先設置通孔集合為空集；則所述根據分支定界法確定所述電路圖中的多個引腳對對應的布線路徑，具體還包括：

確定所述通孔集合為非空集，從所述通孔集合中查找所述不可達引腳對的兩個引腳能夠到達的通孔坐標作為所述不可達引腳對的通孔坐標；或者，

確定所述通孔集合為空集或確定所述通孔集合中未找到所述不可達引腳對的通孔坐標，利用回溯法為所述不可達引腳對確定對應的通孔坐標，將所述通孔坐標添加至所述通孔集合中；

確定所述不可達引腳對的兩個引腳分別到達所述通孔坐標的路徑為第一層布線空間的布線路徑，以及兩個通孔坐標的連接路徑為第二層布線空間的布線路徑，其中，第二層布線空間指代除第一層布線空間之外的其他至少一個布線空間；

利用分支定界算法查找下一個引腳對的布線路徑，直至所述電路圖中的引腳對全部確定出對應的布線路徑。

2.根據權利要求1所述的方法，其特征在于，所述根據分支定界法確定所述電路圖中的多個引腳對對應的布線路徑，具體包括：

從多個引腳對中選取一個目標引腳對，并利用分支定界法確定所述目標引腳對的布線路徑；

獲取下一個目標引腳對，利用分支定界法確定所述下一個目標引腳對滿足設定條件的布線路徑，并不斷迭代該過程直至所述電路圖中的引腳對全部確定出對應的布線路徑。

3.根據權利要求2所述的方法，其特征在于，在所述獲取下一個目標引腳對，利用分支定界法確定所述下一個目標引腳對滿足設定條件的布線路徑，并不斷迭代該過程直至所述電路圖中的引腳對全部確定出對應的布線路徑之前，所述方法還包括：

設置所述設定條件為：；

其中，、分別表示一個引腳對的上引腳坐標和下引腳坐標，、分別表示在所述二維網絡內的橫向坐標和縱向坐標，、表示在所述二維網絡內的橫向坐標和縱向坐標，表示引腳對的布線路徑距離，表示電路圖包含的引腳對的個數，為正整數，s_n1j和s_n2j表示兩個相鄰上引腳的坐標，e_n1j和e_n2j表示兩個相鄰下引腳的坐標。

4.根據權利要求2或3所述的方法，其特征在于，以所述目標引腳對的布線路徑為父節點，所述下一個目標引腳對的布線路徑為子節點，所述目標引腳對代指電路圖包含的多個引腳對中的任意一個；

則所述利用分支定界法確定所述下一個目標引腳對的布線路徑，具體包括：

確定利用分支定界法得到的子節點的布線路徑為零個，以所述父節點為子節點利用回溯法向上查找對應的上一個父節點，并將所述父節點刪除，直至確定上一個父節點存在多個子節點，則從剩余子節點中選取一個子節點作為父節點，利用分支定界法確定對應子節點的布線路徑。