[發(fā)明專利]一種云環(huán)境下截止期約束的科學(xué)工作流調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201910693745.3
• 申請日: 2019-07-30
• 公開（公告）號(hào): CN110609736B
• 公開（公告）日: 2021-04-20
• 發(fā)明（設(shè)計(jì)）人: 鄧科峰;曹書錦;宋君強(qiáng);任開軍;李小勇;任小麗;黃浩煒;周翱隆;張家灝
• 申請（專利權(quán)）人: 中國人民解放軍國防科技大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/455
• 代理公司: 長沙大珂知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 43236
• 代理人: 伍志祥

本發(fā)明公開了一種云環(huán)境下截止期約束的科學(xué)工作流調(diào)度方法，將任務(wù)集合T中的任務(wù)按照拓?fù)浣Y(jié)構(gòu)進(jìn)行排序得到T′；為T′中的任務(wù)計(jì)算向上排序值；根據(jù)所述的向上排序值為中每個(gè)任務(wù)分配子截止期；將T′中任務(wù)根據(jù)子截止期的緊急情況進(jìn)行排序；根據(jù)所述的排序先后次序?yàn)槿蝿?wù)分配虛擬機(jī)；對初始調(diào)度方案進(jìn)行虛擬機(jī)升/降級(jí)優(yōu)化。本發(fā)明方法實(shí)現(xiàn)了云環(huán)境下的截止期約束下費(fèi)用最小化的科學(xué)工作流調(diào)度，一方面通過虛擬機(jī)類型改變、任務(wù)回填等策略對虛擬機(jī)的占用率進(jìn)行優(yōu)化，提高了虛擬機(jī)使用率，另一方面通過截止期約束下的費(fèi)用開銷優(yōu)化，為整個(gè)調(diào)度方案節(jié)省費(fèi)用開銷。

技術(shù)領(lǐng)域

本發(fā)明屬于網(wǎng)絡(luò)工作流調(diào)度領(lǐng)域，具體涉及一種云環(huán)境下截止期約束的科學(xué)工作流調(diào)度方法。

背景技術(shù)

近年來，IaaS(基礎(chǔ)設(shè)施即服務(wù))云計(jì)算平臺(tái)在為松散耦合的科學(xué)應(yīng)用構(gòu)建靈活，高效和低成本的執(zhí)行環(huán)境方面顯示出巨大潛力。一方面，當(dāng)IaaS云通過虛擬機(jī)(VM)提供資源時(shí)，科學(xué)家可以根據(jù)特定于應(yīng)用程序的要求定制執(zhí)行環(huán)境。另一方面，與傳統(tǒng)的批處理系統(tǒng)(如高性能集群)相比，科學(xué)家可以按需租賃和發(fā)布各種類型的云資源。通過這種方式，科學(xué)家們無需部署和維護(hù)自己的基礎(chǔ)設(shè)施。此外，云計(jì)算的即付即用計(jì)費(fèi)模式允許科學(xué)家使用信用卡訪問無限資源，這大大降低了高性能科學(xué)計(jì)算的門檻。由于上述優(yōu)點(diǎn)，越來越多的科學(xué)家被吸引來將科學(xué)工作流從本地集群遷移到IaaS云。

科學(xué)工作流可以表示為有向無環(huán)圖DAG，而DAG類型的并行應(yīng)用作為傳統(tǒng)分布式集群環(huán)境下的一類典型應(yīng)用，其調(diào)度問題受到了學(xué)術(shù)界的廣泛研究。隨著云數(shù)據(jù)中心逐漸成為科學(xué)計(jì)算的重要基礎(chǔ)設(shè)施，云環(huán)境下的截止期約束費(fèi)用優(yōu)化成為當(dāng)前科學(xué)計(jì)算、并行與分布式系統(tǒng)等領(lǐng)域的研究熱點(diǎn)，許多有價(jià)值的調(diào)度算法也相繼被提出來。科學(xué)工作流調(diào)度作為NP難問題，截止期劃分仍存在一定的改進(jìn)空間，并且如何對全局調(diào)度方案進(jìn)行調(diào)整以降低工作流調(diào)度費(fèi)用仍值得研究。目前IaaS云計(jì)算新型環(huán)境下高效執(zhí)行科學(xué)工作流還面臨著資源利用率較低，以及任務(wù)調(diào)度效率不高等問題。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明的目的在于提出一種云環(huán)境下截止期約束的科學(xué)工作流調(diào)度方法，用于提高科學(xué)工作流的資源利用率和任務(wù)調(diào)度效率。

基于上述目的，本發(fā)明提供的一種云環(huán)境下截止期約束的科學(xué)工作流調(diào)度方法，包括以下步驟：

步驟1，將任務(wù)集合T中的任務(wù)按照拓?fù)浣Y(jié)構(gòu)進(jìn)行排序得到T′；

步驟2，為T′中的任務(wù)計(jì)算向上排序值；

步驟3，根據(jù)所述的向上排序值為中每個(gè)任務(wù)分配子截止期；

步驟4，將T′中任務(wù)根據(jù)子截止期的緊急情況進(jìn)行排序；

步驟5，根據(jù)所述的排序先后次序?yàn)槿蝿?wù)分配虛擬機(jī)。

進(jìn)一步地，步驟5中分配虛擬機(jī)包括以下步驟：

步驟501，若存在滿足任務(wù)t_i子截止期的虛擬機(jī)集合{VM}，則將任務(wù)t_i分配到開銷最小的虛擬機(jī)VM_k；

步驟502，若不存在滿足t_i子截止期的虛擬機(jī)，則選擇最快的虛擬機(jī)VM_fast執(zhí)行，并將超出截止期的時(shí)間σ算入后繼任務(wù)；

由此，獲得工作流初始調(diào)度方案S′和租用虛擬機(jī)集合R。

進(jìn)一步地，所述的科學(xué)工作流調(diào)度方法還包括步驟6，對所述的初始調(diào)度方案S′進(jìn)行優(yōu)化，所述的優(yōu)化包括虛擬機(jī)升級(jí)優(yōu)化和虛擬機(jī)降級(jí)優(yōu)化。

具體地，所述的虛擬機(jī)升級(jí)優(yōu)化包括以下步驟：

步驟601，對每個(gè)虛擬機(jī)VM_k∈R，將該虛擬機(jī)升級(jí)為VM_k′，并重新計(jì)算該虛擬機(jī)上任務(wù)的執(zhí)行時(shí)間，節(jié)約的時(shí)間開銷記為gain_k；