[發(fā)明專利]一種基于差分約束系統(tǒng)與迭代模的高層次綜合調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201410608978.6
• 申請日: 2014-10-31
• 公開（公告）號: CN104360906B
• 公開（公告）日: 2017-10-13
• 發(fā)明（設(shè)計）人: 陳弟虎;王自鑫;涂玏;李靜波
• 申請（專利權(quán)）人: 中山大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 廣州嘉權(quán)專利商標(biāo)事務(wù)所有限公司44205
• 代理人: 鄭瑩

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

步驟S1、獲取輸入的電路描述后構(gòu)建對應(yīng)的控制數(shù)據(jù)流圖；

步驟S2、將控制數(shù)據(jù)流圖劃分為循環(huán)部分和非循環(huán)部分；

步驟S3、采用迭代模調(diào)度算法對控制數(shù)據(jù)流圖的循環(huán)部分進(jìn)行調(diào)度；

步驟S4、采用差分約束系統(tǒng)調(diào)度算法對控制數(shù)據(jù)流圖的非循環(huán)部分進(jìn)行調(diào)度；

步驟S5、對步驟S3和S4中得到的調(diào)度結(jié)果進(jìn)行數(shù)學(xué)整合后，獲得綜合調(diào)度結(jié)果；

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

步驟S31、對控制數(shù)據(jù)流圖的循環(huán)部分進(jìn)行最小迭代啟動間隔時間計算；

步驟S32、將計算得到的最小迭代啟動間隔時間作為初始的迭代啟動間隔時間，使用列表調(diào)度算法對控制數(shù)據(jù)流圖的循環(huán)部分進(jìn)行調(diào)度；

步驟S33、迭代進(jìn)行調(diào)度嘗試直到滿足以下條件時，繼續(xù)執(zhí)行步驟S34：調(diào)度成功或者調(diào)度的迭代嘗試次數(shù)大于預(yù)設(shè)上限閾值；

步驟S34、判斷是否調(diào)度完畢，若是，則結(jié)束，反之增加迭代啟動間隔時間后，繼續(xù)使用列表調(diào)度算法進(jìn)行下一輪調(diào)度，并返回執(zhí)行步驟S33；

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

步驟S41、對控制數(shù)據(jù)流圖的非循環(huán)部分的節(jié)點(diǎn)構(gòu)建相應(yīng)的調(diào)度變量；

步驟S42、根據(jù)調(diào)度變量，將所有調(diào)度約束都轉(zhuǎn)化為對應(yīng)的差分約束公式后，將獲得的所有差分約束公式轉(zhuǎn)化成整形規(guī)劃矩陣；

步驟S43、根據(jù)高層次綜合的需求結(jié)果，構(gòu)建相應(yīng)的目標(biāo)函數(shù)；

步驟S44、將整形規(guī)劃矩陣作為目標(biāo)函數(shù)的約束條件，進(jìn)行線性規(guī)劃求解，判斷是否能求解獲得目標(biāo)函數(shù)的最優(yōu)值，若否，則返回執(zhí)行步驟S43，反之獲得該目標(biāo)函數(shù)的最優(yōu)值，同時獲得對應(yīng)的整形規(guī)劃矩陣的值，進(jìn)而獲得每個節(jié)點(diǎn)的調(diào)度值。

2.根據(jù)權(quán)利要求1所述的一種基于差分約束系統(tǒng)與迭代模的高層次綜合調(diào)度方法，其特征在于，所述步驟S2，包括：

步驟S21、使用深度優(yōu)先算法對控制數(shù)據(jù)流圖中的所有操作節(jié)點(diǎn)進(jìn)行排序；

步驟S22、采用支配圖迭代算法將排序后的控制數(shù)據(jù)流圖的節(jié)點(diǎn)構(gòu)建成對應(yīng)的支配樹；

步驟S23、檢測提取支配樹中的所有回邊后，獲取由回邊構(gòu)成的所有回路作為控制數(shù)據(jù)流圖的循環(huán)部分，進(jìn)而獲得控制數(shù)據(jù)流圖的非循環(huán)部分；

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

步驟S221、將控制數(shù)據(jù)流圖的入口節(jié)點(diǎn)的支配集合初始化為該入口節(jié)點(diǎn)，同時將控制數(shù)據(jù)流圖的其它節(jié)點(diǎn)的支配集合均初始化為全集；

步驟S222、針對控制數(shù)據(jù)流圖的除了入口節(jié)點(diǎn)外的任一節(jié)點(diǎn)，求取該節(jié)點(diǎn)的支配集合與其前驅(qū)結(jié)點(diǎn)的支配集合的交集后，將該節(jié)點(diǎn)與該交集的并集作為該節(jié)點(diǎn)的支配集合；

步驟S223、重復(fù)執(zhí)行步驟S222，直到所有節(jié)點(diǎn)的支配集合均不再變動后，根據(jù)所有節(jié)點(diǎn)的支配集合構(gòu)建支配樹。

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