[發明專利]基于數據密集型科學工作流的任務調度與虛擬機整合方法

在審

• 申請號: 201810465028.0
• 申請日: 2018-05-16
• 公開（公告）號: CN108628665A
• 公開（公告）日: 2018-10-09
• 發明（設計）人: 熊聰聰;馮闊;趙青
• 申請（專利權）人: 天津科技大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/48
• 代理公司: 天津盛理知識產權代理有限公司 12209
• 代理人: 王利文

1.一種基于數據密集型科學工作流的任務調度與虛擬機整合方法，其特征在于包括以下步驟：

步驟1、讀取數據密集型科學工作流，構造以任務為節點、任務間的數據依賴關系為邊的有向無環圖DAG；

步驟2、確定工作流虛擬機：通過獲取每個任務執行的確切處理時間選擇出該工作流相對最適合的虛擬機，并用CPLEX方法進行虛擬機類型的求解；

步驟3、工作流截止期劃分：首先將工作流按照數據量大小相似和虛擬機類型相同的任務進行聚類形成n個任務包，然后采用基于浮動區間的方法求得工作流截止期；

步驟4：初始化任務調度：在工作流截止期劃分的基礎上，采用基于深度的任務調度順序方法；

步驟5、虛擬機租賃成本優化：采用加權融合新租賃時間片預期利用率的PHD方法進行任務調度。

2.根據權利要求1所述的基于數據密集型科學工作流的任務調度與虛擬機整合方法，其特征在于：所述步驟2的具體實現方法為：

設α_k(k＝1,2,...,N)和分別表示任務選取了第K種虛擬機以及該虛擬機的價格在截止期劃分階段，虛擬機采用的計費方式為精確計費而非按區間進行計費，E表示的是采用區間計費模式時虛擬機服務的計費區間的長度，執行任務v_i在虛擬機類型α上所需要的總處理時間為T_i,α，此時任務v_i在虛擬機類型α上的成本計算方式為P_i,α，Ω_i,α＝1代表任務v_i選擇的虛擬機類型α，反之Ω_i,α＝0，E_i表示的是執行任務v_i完畢的結束時間，上述的整數規劃模型表示如下：

該式表示最小化虛擬機總租賃成本；

∑_α∈NΩ_i,α＝1,1≤i≤N，該式表示每個任務只選擇一種類型的虛擬機；

E_i≤E_j-∑_α∈NtT_i,αΩ_j,α,該式表示任務間的偏序約束關系；

E₀≥∑_α∈NT_0,αΩ_0,α，該式表示任務間的偏序約束關系；

Ω_i,α∈{0,1},α∈M，該式表示任務是否選擇某個類型的虛擬機；

E_N≤D，該式表示保證工作流總執行時間滿足截止期約束；

用CPLEX方法進行虛擬機類型的求解法為：設定特定比例avigap＝0.25％，如果某一時刻該任務的最優解和分支限界法的下界之間的差值小于avigap，CPLEX則立刻停止執行，那么此時的最好解將被取為CPLEX的近似解并用符號θ表示，θ_vi表示的是任務v_i在解θ中選擇虛擬機的類型。