[發明專利]云計算環境下基于分布式估計算法的工作流執行優化方法

在審

• 申請號: 201911259945.4
• 申請日: 2019-12-10
• 公開（公告）號: CN111026533A
• 公開（公告）日: 2020-04-17
• 發明（設計）人: 謝毅;桂奉獻;孫鶴
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/455
• 代理公司: 杭州浙科專利事務所(普通合伙) 33213
• 代理人: 吳秉中

1.一種云計算環境下基于分布式估計算法的工作流執行優化方法，其特征在于：包括以下步驟：

步驟1：獲取云工作流執行優化所需的信息；

獲取任務集T＝{t₁,...,t_I}，t_i表示任務i，即編號為i的任務；其中I是需要調度的任務數量；

獲取任務間的時序關系：任務i的父任務集PR_i，任務i的子任務集SC_i，其中i＝1,…,I；

獲取任務相關參數：任務i的長度len_i，即任務i被虛擬機處理時需要耗費的指令數量，處理任務i時需要的輸入文件列表IFL_i、任務i被處理后產生的輸出文件列表OFL_i、及文件列表中文件file的大小file.size，其中：i＝1,…,I；任務i是任務i⁺的父任務的充要條件為：存在一個文件file，file是任務i的輸出文件同時又是任務i⁺的輸入文件，即：

獲取云計算環境下的虛擬機類型集VM＝{vm₁,vm₂,…,vm_J}，其中J是虛擬機的類型數量，vm_j表示j類虛擬機；

獲取虛擬機相關參數：j類虛擬機的計算能力ps_j，j類虛擬機的帶寬bw_j，j類虛擬機的單位時間成本vc_j，j類虛擬機的固定起租成本fc_j，j類虛擬機的最小計費時間單位ut_j，j類虛擬機的最小起租時間ft_j；租用j類虛擬機的成本計算如下：其中：lt為租用時間，j＝1,2…,J；

獲取云計算環境下工作流執行的成本約束Budget與時間約束Deadline；若沒有成本約束則設置Budget＝MBV，若沒有時間約束則設置Deadline＝MDV；其中：MBV為成本上限，MDV為時間上限；

步驟2：計算任務的層次值；

對于沒有父任務的開始任務i，其層次值為：

lvl_i＝1 (1)

其它任務的層次值采用如下遞歸公式進行計算：

步驟3：初始化當代種群，令BtCh＝Null；

基于層次和效益比生成1個個體，對初始概率模型進行N-1次采樣生成N-1個個體，形成初始當代種群；其中N是種群規模；

所述個體編碼方法如下：ch＝{gr₁,…,gr_I；gs₁,…,gs_I；gt₁,…,gt_I}，其中{gr₁,…,gr_I}是任務調度順序列表，為任務編號的一個拓撲排序；{gs₁,…,gs_I}是虛擬機分配列表，gs_i表示給第i個調度的任務分配的虛擬機實例編號，其中：gs₁＝1，gs_i≤max{gs₁,…,gs_i-1}+1；{gt₁,…,gt_I}是虛擬機類型列表，gt_i表示編號為i的虛擬機實例的類型，gt₁,…,gt_I的取值為1到J之間的整數值；

所述基于層次和效益比生成1個個體包括如下步驟：

步驟A1：根據任務層次值從小到大隨機排列任務，即層次值小的排在大的前面，具有相同層次值的則隨機排列，形成個體的任務調度順序列表{gr₁,…,gr_I}；

步驟A2：基于效益比生成個體的虛擬機分配列表{gs₁,…,gs_I}和虛擬機類型列表{gt₁,…,gt_I}；獲得所有任務的執行時間和完成時間：et_i、f_i，i＝1,…,I；

步驟A3：輸出一個個體ch₁＝{gr₁,…,gr_I；gs₁,…,gs_I；gt₁,…,gt_I}，及其所有任務的執行時間和完成時間：et_i、f_i，i＝1,2…,I，并計算其工作流響應時間rs₁，操作結束；

所述概率模型包括任務調度順序概率模型PMS(g)、虛擬機分配概率模型PMA(g)和虛擬機類型概率模型PMT(g)；

其中β_i,i′(g)表示在第g代第i′個調度的任務是t_i的概率，

其中α_i,k(g)表示在第g代給第i個調度的任務分配編號為k的虛擬機實例的概率，

其中δ_k,j(g)表示在第g代編號為k的虛擬機實例其類型是j的概率；

初始任務調度順序概率模型為：

其中：STS_ρ＝{t_i|ξ_i<ρ≤I-ζ_i}是可以安排在第ρ個調度的任務集，ζ_i是任務i的子孫任務的數量，ξ_i是任務i的祖先任務的數量；

標記值

所述子孫任務和祖先任務的定義描述如下：如果存在一個任務序列滿足是的父任務，其中1≤k<n，那么是的祖先任務，是的子孫任務；

初始虛擬機分配概率模型為：

初始虛擬機類型概率模型為：

J是虛擬機的類型數量；

對概率模型PMS(g)、PMA(g)和PMT(g)進行1次采樣生成1個個體包括如下步驟：

步驟B1：虛擬機類型的采樣：

步驟B1.1：令變量k＝1；

步驟B1.2：獲取編號為k的虛擬機實例的類型是j的概率A_k,j＝δ_k,j(g)，j＝1,…,J；計算累計概率：

步驟B1.3：產生1個隨機數λ∈[0,1)，如果那么選擇類型j，令gt_k＝j；

步驟B1.4：令k＝k+1；如果k≤I，轉到步驟B1.2，否則已獲得虛擬機類型列表，轉到步驟B2；

步驟B2：系統狀態初始化：

步驟B2.1：令所有虛擬機可得時間段列表vatl_k＝{[0,∞]}，k＝1,…,I；

步驟B2.2：令任務的就緒時間rt_i＝0、任務集P(t_i)＝PR_i，i＝1,…,I；令任務集任務集UT＝T；

步驟B2.3：把UT中的t_i移到RT中；令變量q＝1、變量MI＝1；

步驟B3：根據[β_1,q(g)…β_I,q(g)]^T采用輪盤賭法從RT中隨機選擇一個任務，不妨設為t_i；令gr_q＝i；

步驟B4：根據[α_q,1(g)…α_q,I(g)]采用輪盤賭法在[1,MI]之間隨機選擇一個虛擬機實例編號，不妨設為k，令gs_q＝k；如果k＝MI，則MI＝MI+1；

步驟B5：把t_i分配給編號為k的虛擬機實例：

步驟B5.1：計算t_i的執行時間

步驟B5.2：在vatl_k中從早到晚找出一個空閑時段[ν_k,υ_k]，滿足υ_k-ν_k≥et_i和υ_k-et_i≥rt_i；

步驟B5.3：t_i的開始時間s_i＝max{ν_k,rt_i}，t_i的結束時間f_i＝s_i+et_i；

步驟B5.4：更新t_i的子任務的就緒時間

步驟B5.5：在虛擬機可得時間段列表vatl_k中刪除[ν_k,υ_k]，插入區間長度大于0的[ν_k,s_i]和[f_i,υ_k]；

步驟B5.6：在所有中刪除t_i，在RT中刪除t_i；

步驟B5.7：把UT中的t_i移到RT中；

步驟B6：如果RT不為空，則q＝q+1，轉到步驟B3，否則轉到步驟B7；

步驟B7：獲得一個個體ch_n＝{gr₁,…,gr_I；gs₁,…,gs_I；gt₁,…,gt_I}及其所有任務的執行時間和完成時間：et_i、f_i，i＝1,2…,I，計算其工作流響應時間rs_n，n∈{2,…,N}，操作結束；步驟4：對當代種群中的每個個體采用FBI&D進行解碼與改進，獲得每個個體的工作流執行成本和響應時間，然后計算所有不可行個體的相對適應度值和可行個體的絕對適應度值；如果BtCh＝Null或當代種群中的最優個體優于BtCh中保存的個體，則用最優個體替換保存在BtCh中的內容；

對于種群中的每個個體ch_n＝{gr₁,…,gr_I；gs₁,…,gs_I；gt₁,…,gt_I}，n＝1,…,N；所述FBI&D包括如下步驟：

步驟C1：形成反向個體

步驟C1.1：根據任務完成時間f_i從大到小重新排列任務調度順序列表{gr₁,…,gr_I}，即把任務調度順序列表中的第i個基因值設置為倒數第i個完成的任務編號，i＝1,…,I；形成

步驟C1.2：為維持原資源配置方案和編碼的合法性，調整虛擬機實例列表{gs₁,…,gs_I}和虛擬機類型列表{gt₁,…,gt_I}，形成

步驟C1.2.1：令變量ε＝1、變量δ＝1；令標記值flg₁＝…＝flg_I＝0；令k＝max{gs₁,…,gs_I}+1,…,I；

步驟C1.2.2：如果flg_ε＝0，那么轉到步驟C1.2.3；否則轉到步驟C1.2.5：

步驟C1.2.3：找出任務在{gr₁,…,gr_I}中的調度順序，不妨設為在ch_n中找出使用編號為的虛擬機實例的任務編號集在中找出ST中對應任務的調度順序集

步驟C1.2.4：對于所有的i∈SI，令flg_i＝1；令令δ＝δ+1；

步驟C1.2.5：令ε＝ε+1；如果ε≤I，則轉到步驟C1.2.2，否則轉到步驟C2；

步驟C2：采用基于插入模式的串行反向個體解碼方法對反向個體進行解碼，獲得所有任務反向完成時間及其工作流反向響應時間若小于rs_n，則轉到步驟C3，否則，轉到步驟C5；

步驟C3：形成正向個體ch_n＝{gr₁,…,gr_I；gs₁,…,gs_I；gt₁,…,gt_I}：

步驟C3.1：根據任務反向完成時間從大到小重新排列任務調度順序列表即把任務調度順序列表中的第i個基因值設置為倒數第i個完成的任務編號，i＝1,…,I；形成{gr₁,…,gr_I}；

步驟C3.2：為維持原資源配置方案和編碼的合法性，調整虛擬機實例列表和虛擬機類型列表形成{gs₁,…,gs_I}、{gt₁,…,gt_I}：

步驟C3.2.1：令變量ε＝1、變量δ＝1；令標記值flg₁＝...＝flg_I＝0；令

步驟C3.2.2：如果flg_ε＝0，那么轉到步驟C3.2.3；否則轉到步驟C3.2.5：

步驟C3.2.3：找出任務gr_ε在中的調度順序，不妨設為在中找出使用編號為的虛擬機實例的任務編號集在{gr₁,…,gr_I}中找出ST中對應任務的調度順序集SI＝{i|gr_i∈ST}；

步驟C3.2.4：對于所有的i∈SI，令gs_i＝δ、flg_i＝1；令令δ＝δ+1；

步驟C3.2.5：令ε＝ε+1；如果ε≤I，則轉到步驟C3.2.2，否則轉到步驟C4；

步驟C4：采用基于插入模式的串行正向個體解碼方法對正向個體ch_n進行解碼，獲得所有任務的完成時間f₁,…,f_I及其工作流響應時間rs_n；如果rs_n小于則轉到步驟C1，否則，轉到步驟C5；

步驟C5：輸出正向個體ch_n及其工作流響應時間rs_n，計算其工作流執行成本ct_n，操作結束；

所述基于插入模式的串行反向個體解碼方法對反向個體進行解碼包括如下步驟：

步驟D1：令所有任務的反向就緒時間是任務輸出給共享數據庫的輸出文件集，即令虛擬機可得時間段列表令變量ε＝1；

步驟D2：選取編號為的任務；

步驟D3：基于插入模式把任務i分配給編號為的虛擬機實例：

步驟D3.1：在vatl_k中從早到晚找出一個空閑時段[ν_k,υ_k]，滿足υ_k-ν_k≥et_i和

步驟D3.2：計算任務i的反向開始時間反向完成時間

步驟D3.3：更新任務i的父任務的反向就緒時間

步驟D3.4：在虛擬機可得時間段列表vatl_k中刪除[ν_k,υ_k]，插入區間長度大于0的和

步驟D4：令ε＝ε+1，如果ε≤I，則轉到步驟D2，否則步驟D5；

步驟D5：獲得所有任務的反向完成時間及其工作流反向響應時間操作結束；

所述基于插入模式的串行正向個體解碼方法對正向個體ch_n進行解碼包括如下步驟：

步驟E1：令所有任務的就緒時間rt_i＝0，i＝1,…,I；令變量ε＝1；令所有虛擬機實例的可得時間段列表vatl_k＝{[0,∞]}，k＝1,…,max{gs₁,…,gs_I}；

步驟E2：選取編號為i＝gr_ε的任務；

步驟E3：基于插入模式把任務i分配給編號為k＝gs_ε的虛擬機實例；

步驟E3.1：在vatl_k中從早到晚找出一個空閑時段[ν_k,υ_k]，滿足υ_k-ν_k≥et_i和υ_k-et_i≥rt_i；

步驟E3.2：計算任務i的開始時間s_i＝max{ν_k,rt_i}，完成時間f_i＝s_i+et_i；

步驟E3.3：更新任務i的子任務的就緒時間

步驟E3.4：在虛擬機可得時間段列表vatl_k中刪除[ν_k,υ_k]，插入區間長度大于0的[ν_k,s_i]和[f_i,υ_k]；

步驟E4：令ε＝ε+1，如果ε≤I，則轉到步驟E2，否則步驟E5；

步驟E5：獲得所有任務的結束時間f_i，i＝1,…,I，計算其工作流響應時間rs_n，操作結束；

步驟5：如果終止條件不滿足，轉到步驟6；否則轉到步驟8；

所述終止條件為迭代到指定的代數TG或連續迭代GG代保存在BtCh中的最優個體沒有改進；

步驟6：構建精英種群，更新概率模型；

從當代種群從優到劣選出個個體作為當代精英種群POP_e，其中：N_e為精英種群規模，r_e∈(0,1)為精英率；

更新概率模型方法如下：

標記值

標記值

標記值

分別為虛擬機分配概率模型、任務調度順序概率模型、虛擬機類型概率模型的更新速率；

步驟7：對當前概率模型PMS(g)、PMA(g)和PMT(g)進行N次采樣生成N個個體，形成的新種群，令新種群為當代種群；轉到步驟4；

步驟8：如果BtCh中保存的是可行個體，則輸出其對應的執行方案作為優化方案；否則無可行執行方案。