鬼佬大哥大
  • / 14
  • 下載費用:30 金幣  

多云環境下帶截止日期約束工作流的基于代價驅動調度方法.pdf

摘要
申請專利號:

CN201510418271.3

申請日:

2015.07.16

公開號:

CN105068863A

公開日:

2015.11.18

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 9/48申請日:20150716|||公開
IPC分類號: G06F9/48; G06Q10/04(2012.01)I 主分類號: G06F9/48
申請人: 福州大學
發明人: 郭文忠; 林兵; 陳國龍
地址: 350108福建省福州市閩侯縣上街鎮大學城學園路2號福州大學新區
優先權:
專利代理機構: 福州元創專利商標代理有限公司35100 代理人: 蔡學俊
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510418271.3

授權公告號:

||||||

法律狀態公告日:

2018.08.17|||2015.12.16|||2015.11.18

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明涉及并行和分布式高性能計算領域中一種多云環境下帶截止日期約束工作流的基于代價驅動調度方法。該方法根據工作流自身結構特點,迭代合并存在‘有向割邊’的相鄰子任務,減少算法執行時間并初步降低數據傳輸成本;設計一種工作流局部關鍵路徑查找策略,以保證滿足工作流截止日期約束和服務質量需求;基于局部關鍵路徑查找并整體調度‘關鍵’路徑,進一步壓縮數據傳輸時間和執行代價;根據多云環境特點,設計一種‘關鍵’路徑到執行實例之間的映射方案,保證滿足任務服務質量同時降低執行代價。該調度方法能夠在滿足現有真實工作流截止日期約束前提下,有效提高方法本身的執行效率,并大幅度減少工作流在多云環境下的執行代價。

權利要求書

1.一種多云環境下帶截止日期約束工作流的基于代價驅動調度方法,其特征在于,包括以下步驟:步驟S1:輸入工作流w,用有向無環圖G(Vertex,Edge)來表示工作流w,其中Vertex是一個含有n個任務節點的有限點集{t1,t2,...,tn},而Edge則用來表示任務之間數據傳輸依賴關系的有限邊集{e12,e13,...,eij},每條數據依賴邊eij=(ti,tj)代表任務ti和任務tj之間存在數據傳輸依賴關系,其中任務ti是任務tj的直接父節點,而任務tj則是任務ti的直接子節點,eij的大小表示任務ti到任務tj的數據傳輸量;在工作流調度過程中,一個任務必須在其所有父節點都已被執行完畢后,該任務才能開始執行,沒有父節點的任務稱為入任務,沒有子節點的任務稱為出任務;步驟S2:執行調度策略前預先分別加入一個零代價的偽入任務節點t偽入任務和偽出任務節點t偽出任務,將偽入任務與真實入任務通過零依賴邊相連,將真實出任務與偽出任務通過零依賴邊相連;步驟S3:迭代合并其中存在有向割邊相鄰任務,所述有向割邊的為一條有向邊,其出節點的出度為1,且其入節點的入度為1;步驟S4:確認不同服務提供商P={p,q,...,r}所提供的有效計算服務類型Sp={sp1,sp2,...,spm};步驟S5:計算工作流w中所有任務的EFT(ti)、EST(ti)、LFT(ti)及LST(ti);所述EFT(ti)表示在任務ti未調度前的理想最早完成時間,其計算公式如下:,;其中Texe(ti,spj)表示任務ti在實例spj上的執行時間;Tboot(vmpj)表示實例spj的初始化啟動時間;EFT(tj)表示EFT(tj)表示在任務tj未調度前的理想最早完成時間;TE(eji,p)表示數據依賴邊eji在云服務提供商preP_E(tj)和p之間的數據傳輸時間;preP_E(ti)表示已計算EFT(ti)的任務ti對應的最早傾向云,最早傾向云為在云服務提供商集合P中使任務ti取得最小EFT(ti)對應的提供商;EST(ti)表示未調度任務ti的最早開始時間LFT(ti)表示任務ti最遲完成時間,,其中LST(ti)表示任務ti未被調度前的理想最遲開始時間;preP_L(ti)表示已計算LST(ti)的任務ti對應的最遲傾向云,最遲傾向云為所有云服務提供商集合P中使任務ti取得最大LST(ti)對應的提供商;LST(ti)計算公式:,TL(eij,p)表示數據依賴邊eij在云服務提供商ppreP_L(tj)之間的數據傳輸時間;D(w)為整個工作流w能在其對應的截止日期;步驟S6:標記t偽入任務及t偽出任務為已調度任務;步驟S7:若任務ti不存在未調度直接父任務直接輸出調度方案,若存在未調度直接父任務執行步驟S8;步驟S8:查找任務ti的局部關鍵路徑PCP(ti),整體調度PCP(ti)到其對應的最佳實施例sp,j,k,標記PCP(ti)上每個任務為tj已調度;步驟S9:更新tj所有未調度父任務的LSTs及LFTs,更新ti所有未調度子任務的LSTs及LFTs,返回步驟S7。2.根據權利要求1所述的多云環境下帶截止日期約束工作流的基于代價驅動調度方法,其特征在于:所述步驟S3包括以下具體步驟:構造一個父親兒子圖矩陣father-son[][]判定父節點是否僅有一個兒子節點,且該兒子節點入度為1,并以該兒子節點為新的父節點迭代尋找新的有向割邊;將尋找到的有向割邊刪除,合并對應的兩個任務,更新新任務的數據傳輸量和相應執行時間,重新掃描全局,直到新生成的工作流中不存在有向割邊。3.根據權利要求1所述的多云環境下帶截止日期約束工作流的基于代價驅動調度方法,其特征在于:所述步驟S5中當出現兩個以上提供商使任務ti取得對應最早完成時間,則選取編號小的提供商作為任務ti的最早傾向云。4.根據權利要求1所述的多云環境下帶截止日期約束工作流的基于代價驅動調度方法,其特征在于:所述步驟S8中整體調度PCP(ti)到其對應的最佳實施例sp,j,k需要同時滿足以下條件:條件1:sp,j,k對應于局部關鍵路徑PCP(ti)的執行代價增值Cgrow(sp,j,k,PCP)最低,,其中T1是實例sp,j,k在執行PCP(ti)之前,其已運行的窗口時間,T2是在執行PCP(ti)之后實例sp,j,k所運行的總窗口時間,Cdata為增值的數據傳輸代價;條件2:對于某個局部關鍵路徑PCP(ti),如果存在兩個或兩個以上實例滿足條件1,則選擇產生Cdata最小的實例sp,j,k作為最佳實際;條件3:對于某個局部關鍵路徑PCP(ti),如果存在兩個或兩個以上實例同時滿足條件1和條件2,則選擇剩余時間最多,即當前窗口時間減去實際執行時間的差值最多的實例sp,j,k作為最佳實例。5.根據權利要求1所述的多云環境下帶截止日期約束工作流的基于代價驅動調度方法,其特征在于:算法的更新調度局部關鍵路徑包括以下步驟:輸入一條帶局部截止日期約束的局部關鍵路徑PCP,更新當前多云環境中虛擬資源和所有未調度子任務的狀態,整體調度PCP到相應的最佳實例上,并在對應的局部截止日期前執行完成PCP上的所有任務。6.根據權利要求5所述的多云環境下帶截止日期約束工作流的基于代價驅動調度方法,其特征在于:整體調度PCP到相應的最佳實例上包括以下步驟:利用貪心選擇策略尋找執行PCP代價增值最低的運行中可用實例,若不存在代價增值最低的運行中可用實例,則啟動一個新的最便宜計算服務實例,該實例能夠在滿足該PCP局部截止日期前提下執行完成其上的全部任務;所述可用實例滿足:在路徑PCP被調度到該實例上執行時,路徑PCP上的所有任務都可以在其相應的子截止日期前完成;該實例的執行代價增值,包括實例執行代價和數據傳輸代價,必須低于初始化一個同樣計算服務實例來調度該路徑PCP的執行代價。

說明書

多云環境下帶截止日期約束工作流的基于代價驅動調度方法

技術領域

本發明屬于并行和分布式高性能計算領域的工作流調度方法,具體涉及一種
多云環境下帶截止日期約束工作流基于代價驅動和局部關鍵路徑特征的調度方
法。

背景技術

近年來隨著云計算技術的普及,當前云市場上出現了許多不同的云服務提供
商,如GoGrid,AmazonEC2和Rackspace。根據具體服務提供內容的差異,服
務類型可分為:基礎設施即服務(InfrastructureasaService,IaaS),軟件
即服務(SoftwareasaService,SaaS)和平臺即服務(PlatformasaService,
PaaS)。終端用戶通過與服務提供商之間訂立的服務等級協議(ServiceLevel
Agreements,SLAs)來保證自身應用的服務質量,并以按需付費的方式支付相應
的執行費用。云計算強大的并行計算能力,使許多科研工作者著手研究大規模科
學工作流在云計算環境中的優化調度問題,云平臺中工作流調度效果的優劣直接
影響到整個系統的作業性能。任務調度本身就是一個NP完全問題,由于不同服
務提供商之間存在許多差異(如實例類型,要價機制,傳輸帶寬等),所以終端
用戶需要一種良好的調度策略來保證其工作流約束前提下,盡可能降低用戶代
價,這是一個帶約束的單目標優化問題。雖然許多相關研究工作已在傳統分布式
環境中展開,但涉及云環境的工作流調度研究工作卻相對較少,特別是在IaaS
多云環境中處理帶截止日期約束的復雜工作流調度問題。

工作流調度是一個傳統的優化問題,它是在滿足某些給定的約束前提下,將
工作流中的每個任務按序分配到對應資源中,從而獲得最佳的預期結果。早期的
研究工作主要基于較為傳統的多機處理時代,現有研究工作大多是針對共享社區
環境(如社區網格)的工作流調度問題而展開。無論是多機處理時代,還是社區
網格環境,涉及工作流的研究工作主要是考慮最小化工作流執行時間或滿足用戶
服務質量需求,并未涉及工作流執行代價的研究。

傳統分布式環境的工作流調度科研成果為云環境下工作流研究提供一定的
借鑒作用。然而,它們并非完全適用于按區間要價并以利益為驅動的云計算環境。
現有云環境下的研究工作主要是基于代價優化目標而展開。然而許多研究工作僅
僅在多云環境下追求代價最優,而忽略其他約束條件,如截止日期;或者僅在單
云環境下考慮帶約束條件的工作流代價優化調度,并未涉及不同帶寬的多云環境
對工作流執行代價影響;或者忽略任務間的復雜依賴關系而僅考慮多云環境下批
任務調度問題;或者在追求工作流代價最優過程中,沒有考慮云環境按需付費,
按區間要價的基本性質。因此,多云環境下,帶截止日期約束的大規模工作流執
行代價的優化調度問題仍未得到妥善解決。

發明內容

本發明的目的是提供一種在多云環境下基于工作流自身結構和執行特性,以
及當前云資源環境等相關因素考慮的工作流調度方法,該方法基于局部關鍵路徑
思想,壓縮數據傳輸路徑和任務間的數據傳輸時間,有效整合虛擬化資源,在滿
足工作流截止日期約束的前提下,優化資源利用率,有效提高方法本身的執行效
率,并大幅度減少工作流在多云環境下的執行代價。

本發明采用以下技術方案實現:一種多云環境下帶截止日期約束工作流的基
于代價驅動調度方法,其特征在于,包括以下步驟:步驟S1:輸入工作流w,
用有向無環圖G(Vertex,Edge)來表示工作流w,其中Vertex是一個含有n個任務
節點的有限點集{t1,t2,...,tn},而Edge則用來表示任務之間數據傳輸依賴關系的
有限邊集{e12,e13,...,eij},每條數據依賴邊eij=(ti,tj)代表任務ti和任務tj之間存
在數據傳輸依賴關系,其中任務ti是任務tj的直接父節點,而任務tj則是任務ti
的直接子節點,eij的大小表示任務ti到任務tj的數據傳輸量;在工作流調度過
程中,一個任務必須在其所有父節點都已被執行完畢后,該任務才能開始執行,
沒有父節點的任務稱為入任務,沒有子節點的任務稱為出任務;步驟S2:執行
調度策略前預先分別加入一個零代價的偽入任務節點t偽入任務和偽出任務節點t偽出
任務,將偽入任務與真實入任務通過零依賴邊相連,將真實出任務與偽出任務通過
零依賴邊相連;步驟S3:迭代合并其中存在有向割邊相鄰任務,所述有向割邊
的為一條有向邊,其出節點的出度為1,且其入節點的入度為1;步驟S4:確認
不同服務提供商P={p,q,...,r}所提供的有效計算服務類型Sp={sp1,sp2,...,spm};
步驟S5:計算工作流w中所有任務的EFT(ti)、EST(ti)、LFT(ti)及LST(ti);所述
EFT(ti)表示在任務ti未調度前的理想最早完成時間,其計算公式如下:

其中Texe(ti,spj)表示任務ti在實例spj上的執行時間;
Tboot(vmpj)表示實例spj的初始化啟動時間;EFT(tj)表示EFT(tj)表示在任務tj未調
度前的理想最早完成時間;TE(eji,p)表示數據依賴邊eji在云服務提供商preP_E(tj)
和p之間的數據傳輸時間;preP_E(ti)表示已計算EFT(ti)的任務ti對應的最早傾
向云,最早傾向云為在云服務提供商集合P中使任務ti取得最小EFT(ti)對應的
提供商;EST(ti)表示未調度任務ti的最早開始時間,
EST(ti)=EFT(ti)-MET(ti,preP_E(ti));LFT(ti)表示任務ti最遲完成時間,
LFT(ti)=LST(ti)+MET(ti,preP_L(ti)),其中LST(ti)表示任務ti未被調度前的理想
最遲開始時間;preP_L(ti)表示已計算LST(ti)的任務ti對應的最遲傾向云,最遲傾
向云為所有云服務提供商集合P中使任務ti取得最大LST(ti)對應的提供商;LST(ti)
計算公式:TL(eij,
p)表示數據依賴邊eij在云服務提供商p和preP_L(tj)之間的數據傳輸時間;D(w)
為整個工作流w能在其對應的截止日期;

步驟S6:標記t偽入任務及t偽出任務為已調度任務;步驟S7:若任務ti不存在未調
度直接父任務直接輸出調度方案,若存在未調度直接父任務執行步驟S8;步驟
S8:查找任務ti的局部關鍵路徑PCP(ti),整體調度PCP(ti)到其對應的最佳
實施例sp,j,k,標記PCP(ti)上每個任務為tj已調度;步驟S9:更新tj所有未調
度父任務的LSTs及LFTs,更新ti所有未調度子任務的LSTs及LFTs,返回步驟
S7。

在本發明一實施例中,所述步驟S3包括以下具體步驟:構造一個父親兒子
圖矩陣father-son[][]判定父節點是否僅有一個兒子節點,且該兒子節點入度為1,
并以該兒子節點為新的父節點迭代尋找新的有向割邊;將尋找到的有向割邊刪
除,合并對應的兩個任務,更新新任務的數據傳輸量和相應執行時間,重新掃描
全局,直到新生成的工作流中不存在有向割邊。

在本發明一實施例中,所述步驟S5中當出現兩個以上提供商使任務ti取得
對應最早完成時間,則選取編號小的提供商作為任務ti的最早傾向云。

在本發明一實施例中,所述步驟S8中整體調度PCP(ti)到其對應的最佳實
施例sp,j,k需要同時滿足以下條件:條件1:sp,j,k對應于局部關鍵路徑PCP(ti)的
執行代價增值Cgrow(sp,j,k,PCP)最低,Cgrow(sp,j,k,PCP)=cpj·(T2-T1)+Cdata,其
中T1是實例sp,j,k在執行PCP(ti)之前,其已運行的窗口時間,T2是在執行PCP(ti)
之后實例sp,j,k所運行的總窗口時間,Cdata為增值的數據傳輸代價;條件2:對
于某個局部關鍵路徑PCP(ti),如果存在兩個或兩個以上實例滿足條件1,則選擇
產生Cdata最小的實例sp,j,k作為最佳實際;條件3:對于某個局部關鍵路徑
PCP(ti),如果存在兩個或兩個以上實例同時滿足條件1和條件2,則選擇剩余時
間最多,即當前窗口時間減去實際執行時間的差值最多的實例sp,j,k作為最佳實
例。

在本發明一實施例中,算法的更新調度局部關鍵路徑包括以下步驟:輸入一
條帶局部截止日期約束的局部關鍵路徑PCP,更新當前多云環境中虛擬資源和所
有未調度子任務的狀態,整體調度PCP到相應的最佳實例上,并在對應的局部
截止日期前執行完成PCP上的所有任務。

進一步的,整體調度PCP到相應的最佳實例上包括以下步驟:利用貪心選
擇策略尋找執行PCP代價增值最低的運行中可用實例,若不存在代價增值最低
的運行中可用實例,則啟動一個新的最便宜計算服務實例,該實例能夠在滿足該
PCP局部截止日期前提下執行完成其上的全部任務;所述可用實例滿足:在路徑
PCP被調度到該實例上執行時,路徑PCP上的所有任務都可以在其相應的子截
止日期前完成;該實例的執行代價增值,包括實例執行代價和數據傳輸代價,必
須低于初始化一個同樣計算服務實例來調度該路徑PCP的執行代價。

本發明基于局部關鍵路徑思想,從工作流自身結構特點和多云環境的全局角
度設計以代價驅動的調度方法。與現有技術相比,本發明具有以下優點:根據工
作流自身結構特點,迭代合并存在‘有向割邊’的相鄰子任務,減少算法執行時
間并初步降低數據傳輸成本;設計一種工作流局部關鍵路徑查找策略,以保證滿
足工作流截止日期約束和服務質量需求;基于局部關鍵路徑查找并整體調度‘關
鍵’路徑,進一步壓縮數據傳輸時間和執行代價;根據多云環境特點,設計一種
‘關鍵’路徑到執行實例之間的映射方案,保證滿足任務服務質量同時降低執行
代價。該調度方法能夠在滿足現有真實工作流截止日期約束前提下,有效提高方
法本身的執行效率,并大幅度減少工作流在多云環境下的執行代價。

附圖說明

圖1是多云環境下帶截止日期約束工作流的基于代價驅動調度的流程圖。

圖2是本發明一實施例原工作流結構圖。

圖3是圖2加入零代價依賴邊的工作流結構圖。

圖4是壓縮有向割邊示意圖。

圖5是預處理前后的LIGO工作流結構圖。

具體實施方式

下面結合附圖和具體實施方式對本發明做進一步說明。

本發明考慮工作流自身結構特點和執行特性,通過迭代合并工作流中存在
‘有向割邊’相鄰子任務的預處理操作,減少算法執行時間并初步降低數據傳輸
成本;根據當前云資源執行不同任務的情況以及工作流相應的截止日期要求,設
計一種工作流局部關鍵路徑查找策略,以保證滿足工作流截止日期約束和服務質
量需求;為提高虛擬資源的整體利用率,設計一種同時考慮數據傳輸代價和虛擬
機執行成本的最佳實例選擇方案;考慮云環境按區間要價的特點,在實際調度階
段設計一種帶更新機制的關鍵路徑到最佳執行實例之間的映射方案,保證滿足任
務服務質量同時降低執行代價。

一種多云環境下帶截止日期約束工作流的基于代價驅動調度方法,其特征在
于,一種多云環境下帶截止日期約束工作流的基于代價驅動調度方法,其特征在
于,包括以下步驟:步驟S1:輸入工作流w,用有向無環圖G(Vertex,Edge)來表
示工作流w,其中Vertex是一個含有n個任務節點的有限點集{t1,t2,...,tn},而
Edge則用來表示任務之間數據傳輸依賴關系的有限邊集{e12,e13,...,eij},每條數
據依賴邊eij=(ti,tj)代表任務ti和任務tj之間存在數據傳輸依賴關系,其中任務ti
是任務tj的直接父節點,而任務tj則是任務ti的直接子節點,eij的大小表示任
務ti到任務tj的數據傳輸量;在工作流調度過程中,一個任務必須在其所有父節
點都已被執行完畢后,該任務才能開始執行,沒有父節點的任務稱為入任務,沒
有子節點的任務稱為出任務;步驟S2:執行調度策略前預先分別加入一個零代
價的偽入任務節點t偽入任務和偽出任務節點t偽出任務,將偽入任務與真實入任務通過
零依賴邊相連,將真實出任務與偽出任務通過零依賴邊相連;步驟S3:迭代合
并其中存在有向割邊相鄰任務,所述有向割邊的為一條有向邊,其出節點的出度
為1,且其入節點的入度為1;步驟S4:確認不同服務提供商P={p,q,...,r}所
提供的有效計算服務類型Sp={sp1,sp2,...,spm};步驟S5:計算工作流w中所有
任務的EFT(ti)、EST(ti)、LFT(ti)及LST(ti);所述EFT(ti)表示在任務ti未調度前的
理想最早完成時間,其計算公式如下:

其中Texe(ti,spj)表示任務ti在實例spj上的執行時間;
Tboot(vmpj)表示實例spj的初始化啟動時間;EFT(tj)表示EFT(tj)表示在任務tj未調
度前的理想最早完成時間;TE(eji,p)表示數據依賴邊eji在云服務提供商preP_E(tj)
和p之間的數據傳輸時間;preP_E(ti)表示已計算EFT(ti)的任務ti對應的最早傾
向云,最早傾向云為在云服務提供商集合P中使任務ti取得最小EFT(ti)對應的
提供商;EST(ti)表示未調度任務ti的最早開始時間,
EST(ti)=EFT(ti)-MET(ti,preP_E(ti));LFT(ti)表示任務ti最遲完成時間,
LFT(ti)=LST(ti)+MET(ti,preP_L(ti)),其中LST(ti)表示任務ti未被調度前的理想
最遲開始時間;preP_L(ti)表示已計算LST(ti)的任務ti對應的最遲傾向云,最遲傾
向云為所有云服務提供商集合P中使任務ti取得最大LST(ti)對應的提供商;LST(ti)
計算公式:TL(eij,
p)表示數據依賴邊eij在云服務提供商p和preP_L(tj)之間的數據傳輸時間;D(w)
為整個工作流w能在其對應的截止日期;

步驟S6:標記t偽入任務及t偽出任務為已調度任務;步驟S7:若任務ti不存在未調
度直接父任務直接輸出調度方案,若存在未調度直接父任務執行步驟S8;步驟
S8:查找任務ti的局部關鍵路徑PCP(ti),整體調度PCP(ti)到其對應的最佳
實施例sp,j,k,標記PCP(ti)上每個任務為tj已調度;步驟S9:更新tj所有未調
度父任務的LSTs及LFTs,更新ti所有未調度子任務的LSTs及LFTs,返回步驟
S7。主要流程圖參見圖1。

在本發明一實施例中,所述步驟S3包括以下具體步驟:構造一個父親兒子
圖矩陣father-son[][]判定父節點是否僅有一個兒子節點,且該兒子節點入度為1,
并以該兒子節點為新的父節點迭代尋找新的有向割邊;將尋找到的有向割邊刪
除,合并對應的兩個任務,更新新任務的數據傳輸量和相應執行時間,重新掃描
全局,直到新生成的工作流中不存在有向割邊。

在本發明一實施例中,所述步驟S5中當出現兩個以上提供商使任務ti取得
對應最早完成時間,則選取編號小的提供商作為任務ti的最早傾向云。

在本發明一實施例中,所述步驟S8中整體調度PCP(ti)到其對應的最佳實
施例sp,j,k需要同時滿足以下條件:條件1:sp,j,k對應于局部關鍵路徑PCP(ti)的
執行代價增值Cgrow(sp,j,k,PCP)最低,Cgrow(sp,j,k,PCP)=cpj·(T2-T1)+Cdata,其
中T1是實例sp,j,k在執行PCP(ti)之前,其已運行的窗口時間,T2是在執行PCP(ti)
之后實例sp,j,k所運行的總窗口時間,Cdata為增值的數據傳輸代價;條件2:對
于某個局部關鍵路徑PCP(ti),如果存在兩個或兩個以上實例滿足條件1,則選擇
產生Cdata最小的實例sp,j,k作為最佳實際;條件3:對于某個局部關鍵路徑
PCP(ti),如果存在兩個或兩個以上實例同時滿足條件1和條件2,則選擇剩余時
間最多,即當前窗口時間減去實際執行時間的差值最多的實例sp,j,k作為最佳實
例。

在本發明一實施例中,算法的更新調度局部關鍵路徑包括以下步驟:輸入一
條帶局部截止日期約束的局部關鍵路徑PCP,更新當前多云環境中虛擬資源和所
有未調度子任務的狀態,整體調度PCP到相應的最佳實例上,并在對應的局部
截止日期前執行完成PCP上的所有任務。

進一步的,整體調度PCP到相應的最佳實例上包括以下步驟:利用貪心選
擇策略尋找執行PCP代價增值最低的運行中可用實例,若不存在代價增值最低
的運行中可用實例,則啟動一個新的最便宜計算服務實例,該實例能夠在滿足該
PCP局部截止日期前提下執行完成其上的全部任務;所述可用實例滿足:在路徑
PCP被調度到該實例上執行時,路徑PCP上的所有任務都可以在其相應的子截
止日期前完成;該實例的執行代價增值,包括實例執行代價和數據傳輸代價,必
須低于初始化一個同樣計算服務實例來調度該路徑PCP的執行代價。

在本發明一具體實施例中,本發明用有向無環圖G(Vertex,Edge)來表示工作
流w,其中Vertex是一個含有n個任務節點的有限點集{t1,t2,...,tn},而Edge則
用來表示任務之間數據傳輸依賴關系的有限邊集{e12,e13,...,eij},如圖2所示。
每條數據依賴邊eij=(ti,tj)代表任務ti和任務tj之間存在數據傳輸依賴關系,其中
任務ti是任務tj的直接先驅(父)節點,而任務tj則是任務ti的直接后繼(子)
節點,另外,eij的大小表示任務ti到任務tj的數據傳輸量。在工作流調度過程中,
一個任務必須在其所有父節點都已被執行完畢后,該任務才能開始執行。在某個
給定的代表工作流的有向無環圖中,把沒有父節點的任務稱為‘入任務’,同理,
把沒有子節點的任務稱為‘出任務’。本發明設計的工作流調度方法僅考慮唯一
一個‘入任務’和‘出任務’的工作流,所以在執行調度策略前預先分別加入一
個零代價的‘偽入任務’節點和‘偽出任務’節點,然后把‘偽入任務’與真實
‘入任務’通過零依賴邊相連,同樣地,把真實‘出任務’與‘偽出任務’通過
零依賴邊相連,該變化如圖3所示,該處理不會對調度結果產生任何影響。

對有向割邊定義:一條有向邊,其出節點的出度為1,且其入節點的入度
為1,則稱該有向邊為‘有向割邊’,其結構如圖4所示。

在完成工作流初始零依賴邊加入變化后,基于當前工作流自身結構特點,迭
代合并其中存在‘有向割邊’相鄰任務。本發明‘有向割邊’的定義區別于傳統
割邊,壓縮‘有向割邊’可以有效降低數據傳輸量。首先,在輸入工作流過程中
記錄每個任務相應的出度和入度;然后,為了減少尋找‘有向割邊’的時間復雜
度,本發明構造一個父親兒子圖矩陣father-son[][]來直接判定父節點是否僅有一
個兒子節點,且該兒子節點入度為1,并以該兒子節點為新的父節點迭代尋找新
的‘有向割邊’;將尋找到的‘有向割邊’刪除,合并對應的兩個任務,更新新
任務的數據傳輸量和相應執行時間,反復處理直到不存在‘有向割邊’。試驗表
明,經過預處理的工作流,可以大幅度減少任務數量,特別是存在大量‘有向割
邊’的工作流,從而縮短算法執行時間,降低工作流執行代價。圖5展示了LIGO
工作流在預處理前后的自身結構變化。

多云環境下包含多個不同的IaaS服務提供商P={p,q,...,r},每個服務提供
商p向終端用戶提供一組含有不同CPUs數量、內存容量的計算服務Sp={sp1,
sp2,...,spm},當前主要的商業云服務提供商,通常的要價區間是按1小時收費,
用戶按1小時的區間按需付費。局部關鍵路徑思想,它區別于以任務為基本單元
的傳統調度方式,根據云環境按區間要價的特性,它是把同一關鍵路徑上的局部
所有未調度任務當作一個基本單元而進行統一調度。試驗表明,這樣可以有效壓
縮相互依賴任務之間的數據傳輸量,從而減少傳輸代價。對于某個任務ti,它對
應的局部關鍵路徑PCP(ti)定義如下:
其中CP(ti)表示
任務ti的關鍵直接父任務,它是任務ti的所有直接未調度父任務中,數據預估最
遲時刻傳輸到達任務ti的對應父任務,具體定義如下所示:

其中EFT(tj)表示在任務tj未調度前,任務tj的理想最早完成時間,其定義如下:

其中Texe(ti,spj)表示任務ti在實例spj上的執行時間,
Tboot(vmpj)表示實例spj的初始化啟動時間。本發明中,每個已計算EFT(ti)的任
務ti都有一個對應的最早傾向云preP_E(ti),它是在所有云服務提供商集合P中,
使任務ti取得最小EFT(ti)對應的提供商。如果出現兩個以上提供商使任務ti取得
對應最早完成時間,則選取編號小的提供商作為任務ti的最早傾向云。TE(eji,p)
表示數據依賴邊eji在云服務提供商preP_E(tj)和p之間的數據傳輸時間。另外,
數據依賴邊eij在服務提供商p和q之間的傳輸時間TTinter(eij,spi,sqj)表示如下:
其中Data(eij)表示依賴邊eij的數據傳輸量,
即任務ti在任務tj執行前,傳輸到tj的數據量。Binter(spi,sqj)表示服務提供商p的
計算服務spi到服務提供商q的計算服務sqj的傳輸帶寬速度。另外,未調度任務
ti的最早開始時間EST(ti)定義如下:EST(ti)=EFT(ti)-MET(ti,preP_E(ti))。
path(way,ti)表示一條局部關鍵路徑,way是一條路徑(可能僅含一個節點)。因
此,在局部關鍵路徑PCP(ti)上的任何一個任務,到達它的下一個后繼任務的傳
輸時間都是最遲的。

算法的最佳實例選擇:云服務提供商所提供的所有計算服務中的某個實例,
或者是已有任務在其上執行的,或者是剛剛啟動的,如果能被選定為某個局部關
鍵路徑對應的最佳實例,它能在該路徑對應的局部截止日期前完成其上的所有任
務,即路徑上的每個任務ti必須在其對應的理想最遲完成時間LFT(ti)前被執行完
成。最遲完成時間LFT(ti)是任務未調度前被計算的,其定義如下:
LFT(ti)=LST(ti)+MET(ti,preP_L(ti))。其中LST(ti)表示任務ti未被調度前的理
想最遲開始時間。為確保整個工作流w能在其對應的截止日期D(w)前完成,任
務ti必須在其最遲開始時間LST(ti)前被分配并開始執行。未調度任務ti的最遲開
始時間LST(ti)定義如下:

其中每個已計算
LST(ti)的任務ti都有一個對應的最遲傾向云preP_L(ti),它是在所有云服務提供商
集合P中,使任務ti取得最大LST(ti)對應的提供商。TL(eij,p)表示數據依賴邊eij
在云服務提供商p和preP_L(tj)之間的數據傳輸時間。另外,該最佳實例需要同
時滿足以下三種條件的具體實例sp,j,k:

條件1:該實例sp,j,k對應于局部關鍵路徑PCP(ti)的執行代價增值Cgrow(sp,j,k,
PCP)最低,sp,j,k的執行代價增值包括在該PCP(ti)分配到sp,j,k上時所帶來新的實
例計算代價和數據傳輸代價。執行代價增值Cgrow(sp,j,k,PCP)的定義如下:
Cgrow(sp,j,k,PCP)=cpj·(T2-T1)+Cdata,其中T1是實例sp,j,k在執行PCP(ti)之前,
其已運行的窗口時間(即向上整合時間區間,如果已運行61分鐘,則按2個小
時計算)。同理,T2是在執行PCP(ti)之后實例sp,j,k所運行的總窗口時間。如果sp,j,k
是一個剛剛啟動的實例,則T1為0,而T2則表示在執行PCP(ti)之后實例sp,j,k總
共運行的窗口時間,該時間包括啟動實例所花銷的時間。另外,增值的數據傳輸
代價Cdata,是該局部關鍵路徑上剛被分配的子任務與已被分配的其他子任務之
間,由于分配在不同云服務提供商之間而產生的新數據傳輸代價。

條件2:對于某個局部關鍵路徑PCP(ti),如果存在兩個或兩個以上實例滿足
條件1,則選擇產生數據傳輸代價最小的實例sp,j,k作為最佳實際,試驗表明條件
2的加入可以平均減少5%的執行代價;

條件3:對于某個局部關鍵路徑PCP(ti),如果存在兩個或兩個以上實例同時
滿足條件1和條件2,則選擇剩余時間最多(即當前窗口時間減去實際執行時間
的差值)的實例sp,j,k作為最佳實例。試驗表明,具有同等計算能力的兩個實例,
相對于剩余時間少得實例,剩余時間較多的實例更容易通過以上執行代價增值的
定義方式來調度相應的局部關鍵路徑,從而提高虛擬資源的整體利用率。

以上選擇條件均以代價驅動貪心策略為出發點,使選擇的最佳實例在保證能
夠完成相應任務前提下,降低執行代價。

算法的更新調度局部關鍵路徑:輸入一條帶局部截止日期約束的局部關鍵路
徑PCP,更新當前多云環境中虛擬資源和所有未調度子任務的狀態,整體調度
PCP到相應的最佳實例上,并在對應的局部截止日期前執行完成PCP上的所有
任務。調度整條局部關鍵路徑PCP到最佳實例中的過程以一條帶局部截止日期
的路徑作為其輸入值。首先,利用貪心選擇策略尋找執行PCP代價增值最低的
運行中‘可用’實例。一個運行中的實例如果是一條帶局部截止日期路徑PCP
的‘可用’實例,必須滿足以下兩個條件:

條件1:當路徑PCP被調度到該實例上執行時,路徑PCP上的所有任務都
可以在其相應的子截止日期前完成。

條件2:該實例的執行代價增值,包括實例執行代價和數據傳輸代價,必須
低于初始化一個同樣計算服務實例來調度該路徑PCP的執行代價。這意味著,
這個新的PCP調度必須占用已運行實例中一部分的剩余窗口時間。

在運行的實例中尋找‘可用’實例,必須注意以下3點:

注意1:由于路徑PCP上的所有任務都被分配到同一個實例上執行,所以它
們之間的數據傳輸時間變為0,但它們與非該路徑PCP上的任務之間的數據傳輸
時間依然存在。假設路徑PCP上某個任務的直接父(子)任務已被分配到實例
sp,j,k上執行,如果該路徑在后續調度過程中也被分配到實例sp,j,k上,則該任務與
其直接父(子)任務之間的數據傳輸時間為0。同樣地,如果路徑PCP上某個任
務與其直接父(子)任務被分配到同一個云服務提供商的不同實例上,則它們之
間的數據傳輸時間將變為TTintra(eij,spi,spj),其定義如下:

TT i n t r a ( e i j , s p i , s p j ) = D a t a ( e i j ) B int r a ( s p i , s p j ) , ]]>

其中Bintra(spi,spj)表示服務提供商p的計算服務spi到計算服務spj的傳輸帶寬。最
后,如果路徑PCP上某個任務與其直接父(子)任務被分配到不同的云服務提
供商實例上,則它們之間的數據傳輸時間將變為TTinter(eij,spi,sqj),且它們之間的
數據傳輸代價必須要考慮其中。

注意2:利用實例的剩余窗口時間執行整條路徑PCP的代價增值為0。當存
在多個增長執行代價相等的實例,則利用上一小節中介紹的方法選擇一個最佳運
行中實例。

注意3:本發明考慮運行中的實例上每個已調度相鄰任務之間的空閑時間槽
(即后一個任務實際開始時間與前一個任務實際完成時間之間的差值)。當某個
時間槽滿足路徑PCP要求,則將整條PCP插入該槽中,否則將該PCP調度到該
實例上的第一個任務之前或最后一個任務之后執行。

如果不存在代價增值最低的運行中‘可用’實例,則啟動一個新的最便宜計
算服務實例,該實例能夠在滿足該PCP局部截止日期前提下執行完成其上的全
部任務。在該PCP被調度到最佳實例上之后,需要更新一些與該PCP上所有任
務相關的參數,如選擇的服務實例,被調度任務的實際開始時間和相應的調度狀
態。

當PCP上的某個任務被調度完成,則該任務對應的實際開始時間和實際完
成時間將被確定,相應地,它將影響其所有未調度先驅任務的最遲完成時間
LFT(ti)和最遲開始時間LST(ti),以及其所有未調度后繼任務的最早開始時間
EST(ti)和最早完成時間EFT(ti)。因此,與該PCP上所有任務相關的這些參數,
在調度完成后要進行更新操作。

本領域技術人員可以在不違背本發明的原理和實質的前提下對本具體實施
例做出各種修改或補充或者采用類似的方式替代,但是這些改動均落入本發明的
保護范圍。因此本發明技術范圍不局限于上述實施例。

關 鍵 詞:
多云 環境 截止 日期 約束 工作流 基于 代價 驅動 調度 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:多云環境下帶截止日期約束工作流的基于代價驅動調度方法.pdf
鏈接地址:http://www.wwszu.club/p-6385869.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大