[發明專利]一種基于層次化劃分的布圖規劃方法

在審

• 申請號: 202011640319.2
• 申請日: 2020-12-31
• 公開（公告）號: CN112668276A
• 公開（公告）日: 2021-04-16
• 發明（設計）人: 姬朋立;何琨;王正理;金燕;武繼剛
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F30/392
• 分類號: G06F30/392;G06F30/398;G06F115/06
• 代理公司: 浙江千克知識產權代理有限公司 33246
• 代理人: 周希良

1.一種基于層次化劃分的布圖規劃方法，其特征在于：包括以下幾個步驟：

步驟1：模塊粗略排布；對原問題進行層次化劃分，每次劃分先使用圖分割方法將模塊分為兩部分使得兩部分間的模塊連接盡量的少，再平行于電路板的短邊，按照兩部分模塊面積比例分割電路板；迭代劃分直至每個子問題均只包含一個模塊，將每個模塊放置到它對應的子電路板上，生成一個所有模塊均勻放置在電路板上，但模塊可能存在重疊或超出電路板的初始化布圖；

步驟2：布圖合法化調整；基于模塊間的重疊面積大小和模塊超出電路板的程度構造勢能函數，采用L-BFGS-B優化勢能函數，當勢能函數可以減小到零時，合法化調整成功，跳轉到步驟4；合法化識別時，若前期還未調用過步驟3，則跳轉到步驟3，否則跳轉到步驟4；

步驟3：模塊精細排布；結合步驟1生成的初始布圖，先將問題中尺寸超大的模塊固定在電路板上，之后再采用問題層次劃分的方式將剩余的非超大模塊均勻排布到電路板上剩余的空間中，從而生成模塊排布更加均勻的初始化布圖；跳轉到步驟2；

步驟4：布圖輸出；輸出計算所得布圖。

2.根據權利要求1所示的基于層次化劃分的布圖規劃方法，其特征在于，所述步驟2中，布圖合法化調整，具體包括以下幾個步驟：

步驟2.1；查找存在重疊關系的模塊；本發明采用的quadtree的方式查找所有的重疊；Quadtree的構造中，每個頂點對應一個子電路板和該子電路板重疊的所有模塊，初始的根節點對應于初始的電路板和所有模塊，之后進行迭代地四劃分；對于每個模塊，遍歷查找所有包含該模塊的葉子節點，并與對應葉子節點內的所有模塊進行重疊性檢查，找出所有存在重疊的模塊；

步驟2.2；計算布圖總勢能；本發明中提出水平/豎直嵌入深度和水平/豎直超出幅度的概念，并基于兩個概念提出了一種評估模塊重疊和模塊超出電路板程度的勢能函數；

步驟2.3；使用L-BFGS-B算法對勢能函數進行梯度下降優化。

3.根據權利要求1所示的基于層次化劃分的布圖規劃方法，其特征在于，所述步驟3中，模塊精細排布，具體包括以下幾個步驟：

步驟3.1；固定超大模塊；基于步驟1劃分生成的葉子問題，每個超大模塊會分配了一個子電路板，將該子電路板所對應的區域作為它的固定區域；根據模塊面積和對應固定區域邊的特性，選取要固定的模塊，之后再根據邊的特性選取要固定模塊對應的固定區域的一個角，將選取的超大模塊放置到對應角；

步驟3.2；非超大模塊排布；本發明的非超大模塊排布采用問題迭代二分策略，直至劃分生成的每個子問題中只包含一個模塊，將模塊放置到分配的對應區域內，生成初始布圖；在問題劃分過程中，如果當前問題中電路板因為超大模塊的固定不是規則的矩形，則在問題劃分時，不再是固定的先分割模塊，再分割電路板的順序；而是根據電路板上空間的輪廓，考慮到劃分生成的兩個子問題的電路板上盡量不要有狹窄的空間不易于模塊的放置，動態判定模塊與電路板分割的先后順序。

4.根據權利要求1所示的基于層次化劃分的布圖規劃方法，其特征在于，所述步驟3.2中，非超大模塊排布，具體包括以下幾個步驟：

步驟3.2.1將非超大模塊和固定超大模塊后電路板組成的問題，放入到問題隊列中；

步驟3.2.2從隊列中取出一個問題，根據候選切割線、切割系數、切割線距離和切割距離，確定問題中電路板的切割線；

步驟3.2.3：使用步驟3.2.2選取的切割線將電路板分割成兩部分；

步驟3.2.4：將模塊分割成固定面積比例的兩份。通過hMeits分割工具中UBfactor參數的自動設置和虛擬模塊的設置，使用hMetis進行模塊固定面積比例分配；

步驟3.2.5：先分割模塊再分割電路板的方式將問題分割成子問題；

步驟3.2.6：針對步驟3.2.2中生成的所有只含有一個模塊的子問題，將其中的模塊放置到對應的子電路板上，生成初始化布圖。