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

在審

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

本發明涉及一種基于層次化劃分的布圖規劃方法，包括以下幾個步驟：步驟1使用一個模塊粗略排布方法，通過對原始問題的遞歸劃分生成一組只含有一個模塊的子問題構造初始布圖；步驟2針對布圖非法的兩個因素模塊重疊和模塊超出電路板構造勢能函數，并使用對變量帶上下界約束的擬牛頓法優化勢能函數將初始布圖轉化為合法布圖；如果以上合法化失敗，步驟3模塊精細排布方法先將大模塊固定在電路板上，再將剩余小模塊放置到電路板上，并使用最后使用布圖合法化工具將布圖調整為合法；步驟4輸出最終的布圖結果；本發明為二維布圖規劃問題提供了一種連線長度更小的布圖算法。

技術領域

本發明屬于集成電路電子自動化設計(VLSI EDA)技術領域，尤其涉及一種基于層次化劃分的布圖規劃方法。

背景技術

集成電路電子自動化設計采用的是層次化結構，依次進行結構、功能、邏輯和電路和物理設計，最后一步的物理設計需要將將元件的電路表示轉換為幾何表示、將連接元件的線網轉換成幾何連線圖形。布圖規劃(Floorplanning)是物理設計的一個核心步驟，將元件抽象成幾何模塊互不嵌入的布圖到芯片上，同時優化芯片面積、連線長度和能耗等。布圖規劃處于物理設計的早期階段，一方面可以提供前期階段的反饋數據，指導系統架構的調整，另外一方面在布圖過程中可以考慮后續布線階段的需求，在優化模塊布局的同時對布線中的擁塞和時延目標進行初步優化，可以看到布圖規劃在保證模塊合法放置的同時，在整個EDA設計流程中起到了承上啟下的作用是非常關鍵的一個步驟。

因為布圖規劃問題是一個NP-hard問題，當問題規模達到百級以上時，精確算法不能在有效的時間求解，因此當前對該問題的求解主要是采用了啟發式求解算法。當前研究方法整體上可以分為三類：基于模擬退火和遺傳的元啟發式方法、基于圖分割的方法和基于力引導的方法。其中基于元啟發式的方法存在求解速度慢的問題，當模塊規模達到上百時，求解質量較差；當前基于圖分割的方法只對問題進行了較少層次的分割，且分割中未考慮整體模塊間的連接關系，未能最大程度發揮圖分割算法的能力。當前表現最優的是基于力引導的方法。

針對以上技術問題，故需對其進行改進。

發明內容

基于現有技術中存在的上述不足，本發明提供了一種基于層次化劃分的布圖規劃方法QinFer。

為了達到以上目的，本發明所采用的技術方案是：一種基于層次化劃分的布圖規劃方法，其特征在于：包括以下幾個步驟：

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

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

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

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

作為本發明的一種優選方案，所述步驟2中，布圖合法化調整，具體包括以下幾個步驟：

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