[發(fā)明專利]一種云環(huán)境下截止期-預算驅(qū)動的科學工作流調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201911089637.1
• 申請日: 2019-11-08
• 公開（公告）號: CN110825527B
• 公開（公告）日: 2022-01-04
• 發(fā)明（設計）人: 夏元清;陶思遠;葉玲娟;戴荔;張金會;劉坤;翟弟華;鄒偉東;崔冰;郭澤華;閆莉萍;孫中奇
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/48;G06Q10/04;G06Q10/10;G06N3/00
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 溫子云;郭德忠

1.一種云環(huán)境下截止期-預算驅(qū)動的科學工作流調(diào)度方法，其特征在于，包括以下步驟：

步驟1、設定科學工作流的截止期；設定蟻群算法中的螞蟻數(shù)量、最大迭代次數(shù)N，N為大于或等于1的正整數(shù)；蟻群算法中的啟發(fā)式信息為科學工作流的有向無環(huán)圖(DAG)中任務節(jié)點的任務優(yōu)先級，所述任務優(yōu)先級采用設定的任務節(jié)點的計算數(shù)據(jù)量、任務節(jié)點間通信傳輸數(shù)據(jù)量、計算資源池的平均帶寬、計算性能評級為最高級的計算資源的計算速率及設定的概率參數(shù)計算得到；蟻群算法中的信息素蹤跡為所述DAG圖中連接任務節(jié)點的邊的賦值，令所述賦值均取相等的值；

步驟2、每個螞蟻根據(jù)所述啟發(fā)式信息及截止期，計算得到任務節(jié)點的子截止時間；根據(jù)所述啟發(fā)式信息及信息素蹤跡，生成DAG圖中任務節(jié)點的調(diào)度優(yōu)先序列；

按照所述調(diào)度優(yōu)先序列，順序為任務節(jié)點選擇計算資源進行調(diào)度，計算所述調(diào)度優(yōu)先序列的計算時間及花費，包括以下步驟：

步驟2.1、計算當前任務節(jié)點對應的工作流剩余預算及當前任務預算；

步驟2.2、在計算資源池中選擇執(zhí)行當前任務的花費小于或等于所述當前任務預算的計算資源，形成當前任務節(jié)點的可用計算資源集合；

步驟2.3、當所述集合不為空時，則在所述集合中選擇計算時間滿足當前任務節(jié)點的子截止時間要求且計算速率最快的計算資源；若所述集合中不存在計算時間滿足當前任務節(jié)點的子截止時間要求的計算資源時，則選擇所述集合中計算速率最快的計算資源，如果所述集合中計算速率最快的計算資源的計算性能評級不是最高級，則對其進行升級；

當所述集合為空且所述工作流剩余預算大于或等于0時，則在所述計算資源池中選擇計算速率最快的計算資源，如果該計算資源的計算性能評級不是最高級，則對其進行升級；

當所述集合為空且工作流剩余預算小于0時，則在所述計算資源池中選擇計算時間滿足當前任務節(jié)點的子截止時間要求且花費最小的計算資源；若所述計算資源池中不存在計算時間滿足當前任務節(jié)點的子截止時間要求的計算資源時，則在所述計算資源池中選擇花費最小的計算資源，如果該計算資源的計算性能評級不是最高級，則對其進行升級；

步驟2. 4 、將步驟2.2中得到所有任務節(jié)點的計算時間及花費進行求和，得到所述調(diào)度優(yōu)先序列的計算時間及花費；

步驟3、在所有螞蟻計算得到的所述調(diào)度優(yōu)先序列中，按照比較原則確定局部最優(yōu)調(diào)度優(yōu)先序列；再按照所述比較原則，比較所述局部最優(yōu)調(diào)度優(yōu)先序列與當前全局最優(yōu)調(diào)度優(yōu)先序列，確定本次迭代的當前全局最優(yōu)調(diào)度優(yōu)先序列；

判斷當前迭代次數(shù)是否大于或等于N，如果是，則執(zhí)行完畢，且當前全局最優(yōu)調(diào)度優(yōu)先序列即為最終的全局最優(yōu)調(diào)度優(yōu)先序列；

否則，對所述局部最優(yōu)調(diào)度優(yōu)先序列所對應的DAG圖中各邊的信息素蹤跡，進行信息素蹤跡沉積及等比例蒸發(fā)操作，得到更新后的信息素蹤跡，將所述更新后的信息素蹤跡作為下一代的信息素蹤跡；其中，若當前迭代次數(shù)小于設定的最大松弛代數(shù)，則對所述截止期進行松弛處理形成松弛后的截止期，將所述松弛后的截止期作為下一代的截止期；令當前迭代次數(shù)自加1；執(zhí)行步驟2。

2.根據(jù)權利要求1所述的方法，其特征在于，所述比較原則為：當兩個所述調(diào)度優(yōu)先序列的計算時間均小于所述截止期時，則選擇其中花費較小的；當兩個所述調(diào)度優(yōu)先序列的計算時間相等時，則選擇其中花費較小的；當兩個所述調(diào)度優(yōu)先序列的計算時間不等，且其中至少一個所述調(diào)度優(yōu)先序列的計算時間大于或等于截止期時，則選擇其中計算時間較少的。

3.根據(jù)權利要求2所述的方法，其特征在于，所述比較原則采用ε－對比法實現(xiàn)。

4.根據(jù)權利要求1所述的方法，其特征在于，所述松弛處理采用如下公式：

其中，D_ε(k)為第k次迭代的松弛后的截止期；D為設定的所述截止期；M_base為當所述科學工作流中的全部任務節(jié)點均選擇計算性能評級為最低級的計算資源時，所述科學工作流的計算時間；k_T為最大迭代次數(shù)設定最大松弛代數(shù)；k 為當前迭代次數(shù)，且0≤kk_T；cp為控制截止期松弛的變化曲線的參數(shù)。

5.根據(jù)權利要求1所述的方法，其特征在于，所述調(diào)度優(yōu)先序列采用Kahn算法生成。