[發明專利]基于多電場模型的時鐘驅動FPGA芯片全局布局方法

有效

• 申請號: 202210205894.2
• 申請日: 2022-03-04
• 公開（公告）號: CN114330190B
• 公開（公告）日: 2022-05-20
• 發明（設計）人: 林亦波;麥景
• 申請（專利權）人: 北京大學
• 主分類號: G06F30/347
• 分類號: G06F30/347;G06F30/343
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

1.一種基于多電場模型的時鐘驅動FPGA芯片全局布局方法，分別對多種不同器件類型的密度分布建立電場模型；輸入邏輯綜合后得到的電路網表和FPGA芯片的布局限制，使得在全局布局階段生成有利于合法化階段滿足時鐘路由限制的布局結果；將帶約束非凸優化模型轉化為無約束非凸優化模型；采用嵌套優化框架方法統一對約束求解，即實現基于多電場模型的時鐘驅動FPGA芯片全局布局；包括如下步驟：

A．建立優化模型，包括：

將當前所有器件的橫縱坐標向量分別記為和；所有線網組成集合；其中線網；優化模型中的線網的線長項記為；

A1.計算得到近似布線線長；

A2. 分別對多種不同的器件類型的密度分布建立基于多電場的密度模型；

對于每種器件類型，分別對單個器件類型建立電場的密度分布模型，過程如下：

定義參數, 表示在除了類型器件可放的單元以外位置的背景電荷密度；類型器件可放的單元內的背景電荷密度為零；

將類型的器件表示為一個均勻帶電二維帶電體，即器件所帶電荷均勻分布在其所覆蓋的位置內；其中，，表示屬于類型的器件集合；

將背景電荷密度和所有類型器件所帶的電荷相加，即得到二維電路版圖上每一個點的電荷密度, 其中為二維電路版圖上任意一點的位置坐標；

利用麥克斯韋方程組，可得到器件類型所對應的電場系統中的電荷密度，表示為：；

A3. 建立二次罰函數時鐘懲罰項模型，包括：

A31.設計時鐘路由分配算法，根據當前器件位置，生成器件到可用時鐘區域的映射，使得生成的映射不僅滿足時鐘路由限制，而且對線長的擾動最小；

A32. 基于采用時鐘路由分配算法生成的器件到可用時鐘區域的映射，生成二次罰函數時鐘懲罰項；在優化目標中加入光滑化的二次時鐘罰函數項，將時鐘驅動的FPGA布局建模為帶約束非凸優化模型；

A4. 將FPGA芯片的全局布局建模為帶約束非凸優化模型，表示如下：

所述約束包括時鐘路由約束、器件可路由性約束和器件密度分布約束；

B．采用增廣拉格朗日方法將帶約束非凸優化模型轉化為無約束非凸優化模型；采用嵌套優化框架方法統一對約束求解，確定無約束優化模型中的時鐘乘子，器件面積和密度乘子；所述嵌套優化框架方法包括：

B1.判斷是否滿足時鐘路由約束，如不滿足時鐘路由約束則更新時鐘乘子；

B2.判斷是否存在路由擁塞，如不滿足器件可路由性約束則調整器件面積；

B3.判斷器件密度分布是否滿足器件密度分布約束，如不滿足器件密度分布約束則調整密度乘子；具體是：設置閾值，判斷器件密度分布是否小于設定的閾值；若當前器件密度大于閾值，通過加大密度乘子從而加強對密度分布約束的限制；

B4.采用內思特羅夫動量法對優化模型進行求解，直到優化模型完全收斂；

通過上述步驟，即實現基于多電場模型的時鐘驅動FPGA芯片全局布局，生成考慮到時鐘路由限制的FPGA芯片全局布局結果。

2.如權利要求1所述的基于多電場模型的時鐘驅動FPGA芯片全局布局方法，其特征是，步驟A1中，對于線網，具體是使用WAWL線長模型計算得到全局布局階段對最終布線線長的近似。

3.如權利要求1所述的基于多電場模型的時鐘驅動FPGA芯片全局布局方法，其特征是，步驟A2中定義參數, 對于具體的類型，所述LUT類型器件可放置在CLB單元中；則在LUT類型器件的電場系統中，CLB單元所在的位置背景電荷密度為零，CLB以外的位置背景電荷密度為。

4.如權利要求1所述的基于多電場模型的時鐘驅動FPGA芯片全局布局方法，其特征是，步驟A31中，所述時鐘路由分配算法的步驟包括：

S1. 在當前所有時鐘區域中搜索到時鐘信號數量最擁擠的時鐘區域；如果該最擁擠的時鐘區域滿足時鐘路由限制，則退出，結束操作；否則進入步驟S2；

S2. 搜索到所有出現在該最擁擠的時鐘區域的時鐘信號，分別計算得到禁止單個時鐘信號出現在該時鐘區域的近似代價；

S3.采用代價最少的禁止單個時鐘信號出現在該時鐘區域的映射方式，并把該區域內與該時鐘信號相連的所有器件移出；返回到步驟S1。