[發明專利]一種云環境下截止期-預算驅動的科學工作流調度方法

有效

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

本發明公開了一種云環境下截止期?預算驅動的科學工作流調度方法，通過同時考慮截止期和預算兩個約束，在將截止期轉換為任務節點的子截止時間的基礎上，引入當前任務預算和工作流剩余預算，通過對計算資源花費的限制，能夠降低任務節點在子截止時間內完成計算所需的成本，從而降低科學工作流的調度成本，使科學工作流的調度時間、時間成本在截止期、預算約束情況下均能成功調度。

技術領域

本發明屬于工作流調度技術領域，具體涉及一種云環境下截止期-預算驅動的科學工作流調度方法。

背景技術

云計算是由分布式計算、并行計算和網格計算發展而來的新興的商業計算模式。云環境可以提供大量計算資源組成資源池，按需所用，靈活便利。隨著科學技術的深入研究，需要進行大量信息處理和數據計算的科學工作流應運而生，例如：Montage、LIGO、CyberShake、Epigenomic等。針對這一問題，云資源為大規模科學工作流的計算需求提供了有力的保障。

科學工作流調度是云計算中的關鍵問題。工作流的復雜度高和規模大對存儲和計算都有很高的要求，立足于云計算技術的發展，云工作流調度被提出。云工作流調度利用云計算的優勢，建立了具有強大計算能力的智能調度系統。

云計算使調度系統可以制定復雜工作流的調度方案，能夠判斷工作流調度的可行性，根據工作流的特點、目的和條件約束選擇不同的調度算法，調度匹配工作流中的任務和計算資源，利用云資源實際調度任務。

調度算法在調度系統對云工作流中任務與計算資源進行匹配的過程中起到了至關重要的作用，尤其是在具有截止期和預算限制的云工作流調度中，它在為科學工作者高效提供工作成果、為企業管理人員提供業務調度方案方面有著重要影響。設計任務與計算資源的匹配方式調度算法研究的關鍵問題。現有技術主要包括ProLiS、L-ACO算法等，主要采用基于截止期分配并與在子截止時間內滿足最早完成時間的計算資源的匹配方式，這類方式存在的主要問題是：任務與計算資源匹配過程中因進行升級操作產生過多花費的缺陷，導致調度成本升高。

發明內容

有鑒于此，本發明提供了一種云環境下截止期-預算驅動的科學工作流調度方法，實現了在截止期和預算的限制條件下對科學工作流進行成功調度并有效降低了調度成本。

本發明提供的一種云環境下截止期-預算驅動的科學工作流調度方法，包括以下步驟：

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

步驟2、每個螞蟻根據所述啟發式信息及截止期，計算得到任務節點的子截止時間；根據所述啟發式信息及信息素蹤跡，生成DAG圖中任務節點的調度優先序列；

按照所述調度優先序列，順序為任務節點選擇計算資源進行調度，計算所述調度優先序列的計算時間及花費，包括以下步驟：

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

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

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