[發明專利]一種基于差分約束系統與迭代模的高層次綜合調度方法

有效

• 申請號: 201410608978.6
• 申請日: 2014-10-31
• 公開（公告）號: CN104360906B
• 公開（公告）日: 2017-10-13
• 發明（設計）人: 陳弟虎;王自鑫;涂玏;李靜波
• 申請（專利權）人: 中山大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 廣州嘉權專利商標事務所有限公司44205
• 代理人: 鄭瑩

技術領域

本發明涉及一種高層次綜合調度方法，特別是一種基于差分約束系統與迭代模的高層次綜合調度方法。

背景技術

高層次綜合的目標是在目標集合中得到一個滿足既定的數字系統的算法級行為描述、約束條件等條件的基礎上的結構結果。高層次綜合流程包括：編譯與轉換、算子調度、資源分配、寄存器分配、連線網絡生成與優化。其中，算子調度即調度算法是為編譯轉換生成的控制數據流圖中的每一個操作和運算分配到各個控制步，從而實現滿足約束條件下的最優或較優算子調度方案，是高層次綜合流程中最為重要的一個步驟。高層次調度方法中基本分為兩類，一類是循環調度，一類是非循環調度，目前的高層次調度方法中，并沒有明確地對這兩種情況進行區分，都是采用現有技術中的構造法、變換法或整數線性規劃法等方法進行調度，調度過程較為復雜，而且無法及時、全面地進行調度，調度效率低，漸漸不能滿足集成電路設計的發展需求。

發明內容

為了解決上述的技術問題，本發明的目的是提供一種基于差分約束系統與迭代模的高層次綜合調度方法。

本發明解決其技術問題所采用的技術方案是：

一種基于差分約束系統與迭代模的高層次綜合調度方法，包括：

S1、獲取輸入的電路描述后構建對應的控制數據流圖；

S2、將控制數據流圖劃分為循環部分和非循環部分；

S3、采用迭代模調度算法對控制數據流圖的循環部分進行調度；

S4、采用差分約束系統調度算法對控制數據流圖的非循環部分進行調度；

S5、對步驟S3和S4中得到的調度結果進行數學整合后，獲得綜合調度結果。

進一步，所述步驟S2，包括：

S21、使用深度優先算法對控制數據流圖中的所有操作節點進行排序；

S22、采用支配圖迭代算法將排序后的控制數據流圖的節點構建成對應的支配樹；

S23、檢測提取支配樹中的所有回邊后，獲取由回邊構成的所有回路作為控制數據流圖的循環部分，進而獲得控制數據流圖的非循環部分。

進一步，所述步驟S3，包括：

S31、對控制數據流圖的循環部分進行最小迭代啟動間隔時間計算；

S32、將計算得到的最小迭代啟動間隔時間作為初始的迭代啟動間隔時間，使用列表調度算法對控制數據流圖的循環部分進行調度；

S33、迭代進行調度嘗試直到滿足以下條件時，繼續執行步驟S34：調度成功或者調度的迭代嘗試次數大于預設上限閾值；

S34、判斷是否調度完畢，若是，則結束，反之增加迭代啟動間隔時間后，繼續使用列表調度算法進行下一輪調度，并返回執行步驟S33。

進一步，所述步驟S4，包括：

S41、對控制數據流圖的非循環部分的節點構建相應的調度變量；

S42、根據調度變量，將所有調度約束都轉化為對應的差分約束公式后，將獲得的所有差分約束公式轉化成整形規劃矩陣；

S43、根據高層次綜合的需求結果，構建相應的目標函數；

S44、將整形規劃矩陣作為目標函數的約束條件，進行線性規劃求解，判斷是否能求解獲得目標函數的最優值，若否，則返回執行步驟S43，反之獲得該目標函數的最優值，同時獲得對應的整形規劃矩陣的值，進而獲得每個節點的調度值。

進一步，所述步驟S42中所述調度約束包括依賴約束、時序約束以及資源約束。

進一步，所述依賴約束包括由電路描述中的數據依賴性引起的數據依賴約束以及由電路描述中的控制依賴性引起的控制依賴約束；

所述調度約束為數據依賴約束時，采用以下公式將其轉化為對應的差分約束公式：

上式中，sv_beg(v_j)表示節點V_j的調度變量起始值，sv_end(v_i)表示節點V_i的調度變量結束值，節點V_i和節點V_j是具有數據依賴約束的兩個操作節點且節點V_i必須在節點V_j調度前就調度完畢，e(v_i,v_j)表示節點V_i和節點V_j的數據依賴約束邊，E_d表示控制數據流圖中的所有數據依賴約束邊的集合；

所述調度約束為控制依賴約束時，采用以下公式將其轉化為對應的差分約束公式：