云平臺上基于關(guān)鍵路徑截取的有向無環(huán)圖應(yīng)用調(diào)度算法

1云平臺上基于關(guān)鍵路徑截取的有向無環(huán)圖應(yīng)用調(diào)度算法*摘要：云計(jì)算虛擬機(jī)按需獲取并按使用量付費(fèi)的特性吸引著越來越多的大規(guī)模有向無環(huán)圖應(yīng)用科學(xué)應(yīng)用部署到云平臺上。由于云計(jì)算平臺提供多種類型的虛擬機(jī)并按時(shí)間周期計(jì)費(fèi)，使得這些科學(xué)應(yīng)用執(zhí)行容易產(chǎn)生虛擬機(jī)資源過剩、資源使用率低及費(fèi)用虛高的問題。針對此類問題，本文給出一種基于關(guān)鍵路徑截取的有向無環(huán)圖應(yīng)用調(diào)度算法。該算法采取關(guān)鍵路徑截取技術(shù)，循環(huán)找出最晚完成的未分配任務(wù)，從該任務(wù)出發(fā)，在所有未分配任務(wù)構(gòu)成的圖算法不關(guān)鍵詞：云計(jì)算平臺；關(guān)鍵路徑；虛擬機(jī)；有向無環(huán)圖；資源配置中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A文章編號：CriticalPathCutBasedDAGapplicationSchedulingStrategyOnCloudPlatformen在許多科學(xué)研究領(lǐng)域，例如高能物理學(xué)、生物信息學(xué)、大氣科學(xué)等，科學(xué)計(jì)算過程往往由成千上萬個(gè)子任務(wù)聚合而成，而且任務(wù)之間存在嚴(yán)格的依賴關(guān)系，這些子任務(wù)含有依賴關(guān)系的大規(guī)?？茖W(xué)應(yīng)用可以抽象為大規(guī)模有向無物理學(xué)應(yīng)用LIGO[1]，通常需要在復(fù)雜的分布式經(jīng)有很多成熟的算法，例如文獻(xiàn)[2]提出了一種集群上最小化資源使用。文獻(xiàn)[3]在費(fèi)用約束下DAG的執(zhí)行基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目()；國家公益行業(yè)專項(xiàng)計(jì)劃資助項(xiàng)目宋君強(qiáng)(通信作者)，男，研究員，碩士，博士生導(dǎo)師，2近年來，云計(jì)算的興起為大規(guī)模DAG科學(xué)應(yīng)用的高性價(jià)比執(zhí)行提供了潛力。云計(jì)算技術(shù)是一種共享基礎(chǔ)架構(gòu)的方法，它通過虛擬化技術(shù)將計(jì)算資源和存儲資源虛擬成一個(gè)資源戶提供資源。這種資源提供方式降低了供應(yīng)商運(yùn)行成本，同時(shí)用戶可以根據(jù)自己需求合理配置自己所需要的資源。因此，云計(jì)算吸引著越來越多的用戶將大規(guī)模DAG科學(xué)應(yīng)用遷移到云平臺上執(zhí)行。但同時(shí)，云計(jì)算的資源供應(yīng)模式和收費(fèi)模式，為大規(guī)模DAG科學(xué)應(yīng)用的運(yùn)行帶來了新的挑戰(zhàn)。TS[4]，PBTS算法將工作流截止期劃分為多個(gè)時(shí)間務(wù)調(diào)度完全由用戶負(fù)責(zé)的特點(diǎn)，文獻(xiàn)[6]提出了求取偏序關(guān)鍵路徑PCP，在截止時(shí)間約束下將中所有任務(wù)分配完畢。由于是按路徑分配任務(wù)，源使用率，相對的增加了用戶費(fèi)用。本文以最小化完成DAG所需費(fèi)用為目標(biāo)，通過分析大規(guī)模DAG科學(xué)應(yīng)用中任務(wù)的依賴關(guān)系，提出一種云平臺上基于關(guān)鍵路徑截取法采用路徑調(diào)度方法將多個(gè)任務(wù)聚合到性能匹任務(wù)填充到虛擬機(jī)的時(shí)間空閑槽。在路徑調(diào)度晚完成的未分配任務(wù)，從該任務(wù)出發(fā)，在所有未分配任務(wù)構(gòu)成的圖中找出最大連通子圖，并計(jì)算該子圖的關(guān)鍵路徑，然后將關(guān)鍵路徑上的任務(wù)集調(diào)度到性能匹配的虛擬機(jī)上執(zhí)行；在任務(wù)回填方法中，首先計(jì)算虛擬機(jī)時(shí)間空閑槽是時(shí)間空閑槽后對后續(xù)子任務(wù)的影響，如果后續(xù)任務(wù)依賴關(guān)系，按需配置的相應(yīng)的虛擬機(jī)集群G以提高資源使用率，有效減少執(zhí)行費(fèi)用。1模型定義及問題分析1.1.1應(yīng)用模型WVEVtiiV是頂點(diǎn)的集合，表示DAG應(yīng)用中任務(wù)集合；一步由五元組描務(wù)的最晚開始時(shí)間。信開銷，當(dāng)任務(wù)ti和tj調(diào)度到同一個(gè)虛擬機(jī)上時(shí)，通信開銷忽略不計(jì)。唯可以將所有入口任務(wù)和出口任務(wù)連接到一個(gè)零同時(shí)對系統(tǒng)性能并無影響。假設(shè)云計(jì)算平臺提供N種不同類型的虛擬price}，i=1,2…N。不同類型的VM參數(shù)值各不ce此種類型的虛擬機(jī)單個(gè)時(shí)間周期費(fèi)用。用戶通過租賃云計(jì)算平臺的虛擬機(jī)構(gòu)建虛擬機(jī)集群執(zhí)行科學(xué)工作流，虛擬機(jī)集群表示為3VMCvmiivmiid,vmType,rTime表示虛擬機(jī)當(dāng)前時(shí)間周期的剩余時(shí)間，考慮到現(xiàn)代虛擬化技術(shù)下虛擬機(jī)的啟動時(shí)間和關(guān)閉時(shí)間已經(jīng)達(dá)到秒級，因此本文假設(shè)虛擬機(jī)啟動時(shí)間和關(guān)閉時(shí)間可以忽略不計(jì)。用到的參數(shù)、符號進(jìn)行說明。tt5)0)t2)62)420)716)50)92ttttttt831時(shí)間略去。假設(shè)云平臺上有兩種類型的虛擬機(jī)，鐘(min)。虛擬機(jī)實(shí)例需要按小時(shí)申請。假設(shè)整1.2.1任務(wù)并行性任務(wù)并行性包括三個(gè)方面，多任務(wù)并行，單任務(wù)多核并行和單任務(wù)多虛擬機(jī)并行。其中多任務(wù)并行指不同任務(wù)在多個(gè)虛擬機(jī)可以在擁有多個(gè)VCPU上的虛擬機(jī)上并行執(zhí)行，如圖1中t1在單核虛擬機(jī)上執(zhí)行時(shí)間為擬機(jī)上通過并行執(zhí)行減少任務(wù)執(zhí)行時(shí)間。任務(wù)tfinish所需時(shí)間最長的一條路徑定義為關(guān)鍵路徑。DAG應(yīng)用的關(guān)鍵路徑?jīng)Q定了其最短執(zhí)行方式如下：(0,t=t(EST(t),t=t固定，那么關(guān)鍵路徑也可能發(fā)生變化。如圖1所示DAG，如果所有任務(wù)的都在單核虛擬機(jī)上為{tstart,t1,t5,t8,tfinish}。1.2.3截止時(shí)間圍需要在合理范圍之內(nèi)，本文采取以下取值方假設(shè)所有任務(wù)的實(shí)際執(zhí)行時(shí)間(ti)為其在間；假設(shè)所有任務(wù)的實(shí)際執(zhí)行時(shí)間(ti)為其在配鍵路徑上任務(wù)所需時(shí)間為δlong，即最慢完成時(shí)6<δshort，則無論如何調(diào)度，肯定需要配置高性能的虛擬機(jī)實(shí)例；如果long的虛擬機(jī)集群一般都是最低配置的虛擬機(jī)實(shí)例，以實(shí)現(xiàn)費(fèi)用最小化。DAG應(yīng)用在云計(jì)算平臺執(zhí)行時(shí)，調(diào)度算法需要解決以下幾個(gè)方面所面臨的問題。1)配置虛擬集群。既不能啟動大量VM，導(dǎo)致相當(dāng)一部分VM空轉(zhuǎn)，造成資源浪費(fèi)，也AG學(xué)應(yīng)用。調(diào)度算法必須合理規(guī)劃好每個(gè)VM的4ttt93ttt936tt85t類型、啟動時(shí)間和生存時(shí)間，在滿足整個(gè)DAG應(yīng)用截止時(shí)間約束的情況下最大化每個(gè)虛擬機(jī)得當(dāng)前虛擬機(jī)因?yàn)榈却渌摂M機(jī)上的父任務(wù)3)減少空閑時(shí)間槽，提高資源使用率。當(dāng)前大多數(shù)云計(jì)算平臺采用基于時(shí)間周期計(jì)費(fèi)的賃的虛擬機(jī)能夠在整數(shù)時(shí)間周期內(nèi)充分利用。tttvm81tnulltttvm81tnull51t724vmt7243vm3(a)IC-PCPD2算法aICPCPD2algorithmttvmt12147tttvmt121472vm2vm3vm3t3t69(b)新解決方案olution調(diào)度方案如圖2(a)所示。IC-PCPD2總共需要DAG任務(wù)，費(fèi)用可以節(jié)省25%。因此，為了進(jìn)一步提高虛擬機(jī)2.算法描述CPC算法吸取了IC-PCPD2路徑調(diào)度的思出所有邊的權(quán)重(ek)、用戶給出的截止時(shí)間6；算輸出為CPC算法生成的虛擬機(jī)集群及任務(wù)到具體虛擬機(jī)的調(diào)度方案。NameInput:wVEwe6OutputvmListvm…;vmidvmTypesTimeaTimeTTimescheTL1FOR2FORteVwtseqt*λvmType3kpELkpTLVE4exeTimeStekpTLwtSeekpELwe5IF667vmType8scheTLkpTL//taskscheduledon9,sTimeaTimeTTimevmList12ENDIF13EndFOR14remainTaskLis15WhiletremainTaskListFORteremainTaskListFORvmevmListENDFORENDFOR22remainTaskLis23ENDWhile第一個(gè)虛擬機(jī)實(shí)例vm1的類型；然后將關(guān)鍵路徑第三步(語句15-23)：首先采取任務(wù)回填方法，嘗試將未分配的單個(gè)任務(wù)調(diào)度到已存在的配的任務(wù)構(gòu)成的子圖中，計(jì)算出一條關(guān)鍵路徑，新增虛擬機(jī)實(shí)例來完成任務(wù)。嘗試將單個(gè)任務(wù)放到已經(jīng)申請的虛擬機(jī)空閑時(shí)5ikikNameInput:tvmwVEOutput2IFvmrTimewt3FOR三(vmscheTL(5vmscheTLt;6(7END(IF8END(FOR9(ELSE((((圖4任務(wù)回填算法其中canPlace(ti,j)計(jì)算是否能夠?qū)i放在iiiiiiiij當(dāng)單個(gè)任務(wù)無法回填到已有虛擬機(jī)的空閑完畢的時(shí)間點(diǎn)；語句10，從tmax出發(fā)，在計(jì)算該連通子圖的關(guān)鍵路徑，同時(shí)計(jì)算出該關(guān)鍵路徑的開始時(shí)間和結(jié)束時(shí)間；語句12-16，啟動一個(gè)新的VM以執(zhí)行連通子圖關(guān)鍵路徑上NameInput:remainTaskListvmListw(VE(6Output123456789(((((FOR(teemainTaskList(((END(FORIF((6remainTaskListEremainTaskListEchildGraph;//typechildCriticalPathnewVM:vm;vm(vmType,s(imeaTimerTimevm(scheTLchildCriticalPath//taskscheduledonvm((vm(List(END(IFENDFORtepvmttt4711eppm4mmmmmttttttttttttttttttt448893365577722222111111第一步：找到DAG中最晚完成的任務(wù)t7，未分配的任務(wù)中找到最晚完成的任務(wù)t8，然后從第四步：找到未分配任務(wù)中最晚完成的任務(wù)t9，擬機(jī)vm3，虛擬機(jī)類型為單核，生存時(shí)間為60min；任務(wù)分配完畢，算法結(jié)束。6typetype1type2type3.16$/h.32$/h.64$/h虛擬機(jī)類型進(jìn)行遍歷，由于可選類型一般不超O(n2)。第18句任務(wù)回填中需要計(jì)算所有任務(wù)度需要計(jì)算剩余任務(wù)的關(guān)鍵路徑，復(fù)雜度為O(k2)；那么15-23句的復(fù)雜度為3.算法驗(yàn)證3.1測試用例FITS天空本文采用云仿真工具CloudSim[7]對對云計(jì)特征進(jìn)行描述，并在VMScheduler類中實(shí)現(xiàn)不同的調(diào)度策略。 VM類型性能指標(biāo)價(jià)格type48VCPU,16G內(nèi)存，500G硬盤空間1.28$/hHEFT根據(jù)任務(wù)的平均執(zhí)行時(shí)間和通擇具有最大HEFT值的任務(wù)并將其調(diào)度到完成的虛擬機(jī)上。徑上任務(wù)放置到可將其完成的最便宜的虛擬機(jī)則為計(jì)算的偏序關(guān)鍵路徑上的任務(wù)的子截止時(shí)據(jù)其子截止時(shí)間進(jìn)行合理調(diào)度。IC-PCP總體費(fèi)用指完成同一個(gè)科學(xué)工作流所需的iiiii=1ipricevmvmi間的收費(fèi)標(biāo)準(zhǔn)，iiiCPU的實(shí)際使用占所申請的整體CPU資源的jj資源使用率=1vmvmj=1jjii=1影響實(shí)驗(yàn)中，可選虛擬機(jī)實(shí)例類型采用表1所間取6∈[δshort,δlong]，任務(wù)數(shù)量取值范圍為{50,7率用使源資率用使源資率用使源資DAG幾乎線性增加。由于時(shí)間周期為較長的60min，IC-PCP略優(yōu)，比IC-PCPD2費(fèi)用減少越2%；而CPC算法比001002003004005006007008000(a)(a)率0.6用HEFTHEFTPDCPC源0.4資100200300400500600700圖7任務(wù)數(shù)量變化對結(jié)果影響這是因?yàn)镃PC算法不僅采用關(guān)鍵路徑調(diào)間空閑槽，成功率高。因此CPC算法對虛擬機(jī)實(shí)例的空閑時(shí)間槽利用率高，提高資源使用率。DAG變化對結(jié)果的影響實(shí)驗(yàn)中，可選虛擬機(jī)實(shí)例類型采用表1所給，任務(wù)數(shù)量選取200，任務(wù)并行比例η服從[0.1,0.9]的均勻分布，虛擬機(jī)實(shí)例時(shí)間周期長度$費(fèi)60005000400030002000HEFTIC-PCPIC-PCPD2CPC1000ss+d