陳俊宇
關(guān)鍵詞:云環(huán)境;數(shù)據(jù)密集型;分層調(diào)度;最大傳輸路徑
中圖法分類號:TP393 文獻(xiàn)標(biāo)識碼:A
1引言
云平臺一直以來為眾多工作流應(yīng)用程序的調(diào)度提供高效的執(zhí)行環(huán)境,大量研究者對云環(huán)境下數(shù)據(jù)密集型工作流調(diào)度問題展開相關(guān)工作和研究。秦生輝提出了基于流程分割的數(shù)據(jù)密集型工作流調(diào)度方法,滿足了執(zhí)行中跨節(jié)點跨數(shù)據(jù)傳輸?shù)膬?yōu)化需求。杜清華等提出了一種高效的跨平臺工作流優(yōu)化方法,基于GGFN的成本模型和延遲貪婪剪枝方法縮短運行時間。李敬偉等提出了一種基于局部數(shù)據(jù)位置感知資源管理的調(diào)度方法,在提高資源利用率的同時,大幅度提高工作流的調(diào)度效率。
本文提出了一種基于最大數(shù)據(jù)傳輸路徑的數(shù)據(jù)密集型工作流調(diào)度方法,先對工作流中所有任務(wù)進(jìn)行分層排列,并尋找工作流中的最大數(shù)據(jù)傳輸量路徑,分配完最大數(shù)據(jù)傳輸量路徑上的任務(wù)后開始逐層調(diào)度,對其余任務(wù)進(jìn)行調(diào)度。
2數(shù)據(jù)密集型工作流調(diào)度流程
2.1工作流定義
本文調(diào)度的工作流通過有向無環(huán)圖表示。具體如定義1所示。
定義1 (W).W=
W為工作流。
T={t|i=1…n},T表示W(wǎng)中的任務(wù)集合,t表示工作流W的第i個任務(wù)。
D={d,j=1…n},D表示W(wǎng)中任務(wù)之間傳輸數(shù)據(jù)量的集合,其中d表示t向t傳輸?shù)臄?shù)據(jù)量。
2.2服務(wù)商定義
若干個云服務(wù)商參與工作流的調(diào)度,不同服務(wù)商調(diào)度任務(wù)會產(chǎn)生一定的執(zhí)行時間,對于有直接數(shù)據(jù)依賴的2個任務(wù),若同時分配至相同的服務(wù)商,則傳輸時間可忽略不計。
4實驗分析
本文對比算法選擇HEFT算法[5]和Min-Min算法,并隨機(jī)生成工作流作為實驗輸入。
(1)驗證數(shù)據(jù)傳輸量對工作流完成時間的影響,任務(wù)傳輸量設(shè)置[200,400]、[400,600]、[600,800]、[800,1000]4個區(qū)間,任務(wù)數(shù)量為50,服務(wù)商數(shù)量為10,服務(wù)商執(zhí)行任務(wù)時間設(shè)置為[ 400,500],從實驗數(shù)據(jù)得出,任務(wù)之間的傳輸量在[10,200]內(nèi),優(yōu)化力度較小,當(dāng)任務(wù)之間的傳輸量在[ 800,1000]內(nèi),分層調(diào)度法在完成時間上,相比于HEFT算法降低了14%,相比于Min-Min降低了23.5%。
(2)按照任務(wù)數(shù)量來比較,工作流任務(wù)的數(shù)量設(shè)置為[20,30,40,50],每種任務(wù)數(shù)量將對應(yīng)隨機(jī)生成依賴關(guān)系不同的工作流,任務(wù)之間的傳輸量設(shè)置為[400,600],服務(wù)商個數(shù)為10,服務(wù)商執(zhí)行任務(wù)時間設(shè)置為[100,200],從實驗數(shù)據(jù)得出,當(dāng)傳輸量比重大于執(zhí)行時間時,任務(wù)數(shù)量越多,分層調(diào)度法在完成時間上,優(yōu)化力度越大,相比于HEFT最高降低了15%,相比于Min-Min最高降低了19%。
(3)按照執(zhí)行時間來進(jìn)行比較,執(zhí)行時間范圍設(shè)置為[ 100,200]、[200,300].[300,400]、[400,500]4個區(qū)間,傳輸量設(shè)置為[200,300],任務(wù)個數(shù)為20,服務(wù)商個數(shù)為10,生成結(jié)果取平均值,從實驗數(shù)據(jù)得出,當(dāng)傳輸量比重大于執(zhí)行時間時,任務(wù)數(shù)量越多,分層調(diào)度法在完成時間上,優(yōu)化力度越大,相反,當(dāng)傳輸量比重小于執(zhí)行時間時,分層調(diào)度法不具有優(yōu)勢。
5結(jié)束語
本文提出了一種基于最大數(shù)據(jù)傳輸路徑的數(shù)據(jù)密集型工作流調(diào)度方法,首先對工作流進(jìn)行分層,找出工作流中最大數(shù)據(jù)傳輸量路徑并對該路徑進(jìn)行分配工作。然后對其余任務(wù)分配服務(wù)商,以此縮短工作流的完成時間。最后通過具體實驗證實了本文方法的可行性,并通過算法對比驗證了本文方法的有效性。在今后的工作中,我們將考慮對預(yù)算受限的工作流進(jìn)行更深入的研究。