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

有效

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

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

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

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

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

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

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

所述步驟S3，包括步驟S31～S34：

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

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

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

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

所述步驟S4，包括步驟S41～S44：

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

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

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

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

2.根據權利要求1所述的一種基于差分約束系統與迭代模的高層次綜合調度方法，其特征在于，所述步驟S2，包括：

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

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

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

所述步驟S22，包括步驟S221～S223：

步驟S221、將控制數據流圖的入口節點的支配集合初始化為該入口節點，同時將控制數據流圖的其它節點的支配集合均初始化為全集；

步驟S222、針對控制數據流圖的除了入口節點外的任一節點，求取該節點的支配集合與其前驅結點的支配集合的交集后，將該節點與該交集的并集作為該節點的支配集合；

步驟S223、重復執行步驟S222，直到所有節點的支配集合均不再變動后，根據所有節點的支配集合構建支配樹。

3.根據權利要求1所述的一種基于差分約束系統與迭代模的高層次綜合調度方法，其特征在于，所述步驟S42中所述調度約束包括依賴約束、時序約束以及資源約束。