[發明專利]帶時序約束的FPGA時序驅動布局方法

有效

• 申請號: 201210248903.2
• 申請日: 2012-07-18
• 公開（公告）號: CN102768506A
• 公開（公告）日: 2012-11-07
• 發明（設計）人: 來金梅;李華岡;王元;王鍵;王臻
• 申請（專利權）人: 復旦大學
• 主分類號: G05B19/05
• 分類號: G05B19/05
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

1.帶時序約束的FPGA時序驅動布局方法，其特征在于具體步驟如下：

（1）隨機產生一個初始布局，將各個布局單元隨機放置到FPGA的具體位置；

（2）初始化退火溫度T：假設共有N個布局單元，對這N個單元進行隨機移動，計算這些移動造成的成本函數的標準偏差c，初始溫度設定為20c?；

（3）初始化交換距離R：布局開始時，交換距離R設定為整個芯片的陣列大小；

（4）構建延遲查找矩陣：依據交換距離的大小構建延遲查找表Delay?=?F(Δx,Δy)，得到各種交換距離下的延遲值，得到延遲矩陣，用于時序分析；??

（5）時序約束等效處理：將四種時序約束進行等效處理；

（6）構建時序圖并進行時序分析：根據時序路徑上的單元建立時序連接圖，再根據第（4）步中延遲矩陣，得出相鄰單元的延遲，最后計算各條時序路徑的延遲值，得出關鍵路徑上的最大延遲；

（7）通過代價函數計算本次布局的代價；

（8）選定輸入網表中某個布局單元，在最大交換距離范圍內，將其交換到另一個可行的位置，從而得到新的布局并計算該布局的代價；

（9）將第（8）步中得到的新代價函數與前一次代價函數比較，若代價函數值減小即ΔC為負數，說明布局質量變好了，則接受這一次的布局結果；若是代價函數變大即ΔC為正數，則以概率進行判斷是否接受本次布局，判斷標準為：首先，得到一個隨機值r，0?<?r?<?1，將r與e^-ΔC/T進行比較，ΔC為代價函數變化量，T為退火溫度值，若r小于e^-ΔC/T??則接受布局，否則放棄這次布局結果；

（10）將當前交換次數與該溫度下交換次數上限值進行比較：每個溫度點下的交換次數的上限值為：MaxMoves?=?CN^4/3??，C?為常數10，N為交換單元的總數目；

（11）更新退火溫度：T_new?=?λT_old??，λ為一動態變化參數，它取決于在原T_old溫度點時接受移動的百分比α，溫度更新策略如下表：

接受移動百分比αλα> 0.960.50.8 <α≤ 0.960.90.15 <α≤ 0.80.95α≤ 0.150.8

????（12）更新交換距離：R_new?=?R_old(1-0.44+α)，R_old為原交換距離；

????（13）判斷是否滿足退火條件：退火結束條件為Pd(i)?<?C(i)，?Pd(i)是該條時序路徑的實際延遲，C(i)為該時序路徑的約束值，0?<?i?<?n,?n為帶有時序約束的路徑的總數目，當所有的約束值C(i)都滿足時，退出退火過程；若是一直有某C(i)不滿足，則考慮第二個退出條件：T?<?C*Cost/N_nets,?C為經驗常數0.005，Cost為當前代價的大小，T為當前溫度，N_nets為電路中線網的總數；上述條件滿足，退出退火過程，得到最終布局結果。

2.根據權利要求1所述的帶時序約束的FPGA時序驅動布局方法，其特征在于第（5）步中所述的四種時序約束為：時鐘周期約束，輸入輸出延遲約束，特定時序路徑約束，線網延遲約束。

3.根據權利要求2所述的帶時序約束的FPGA時序驅動布局方法，其特征在于第（7）步中計算本次布局代價的代價函數由三部分構成：時序代價Timing_Cost，線網代價Wiring_Cost，用戶約束代價User_Constraint_Cost，最終的代價函數的形式如下：

??

其中，x,y,z分別為各項的權重，且x+y+z?=?1，ΔTiming_Cost?代表時序代價的變化量，Previous_Timing_Cost是上一次時序代價的大小；ΔWiring_Cost?代表線網代價的變化量，Previous_Wiring_Cost是上一次線網代價的大小；ΔUser_Constraint_Cost?代表用戶約束代價函數的變化量，Previous_User_Constraint_Cost是上一次用戶約束代價的大小；ΔC代表總目標函數的變化量。