[發明專利]一種云環境下截止期約束的科學工作流調度方法有效

申請號：	201910693745.3	申請日：	2019-07-30
公開（公告）號：	CN110609736B	公開（公告）日：	2021-04-20
發明（設計）人：	鄧科峰;曹書錦;宋君強;任開軍;李小勇;任小麗;黃浩煒;周翱隆;張家灝	申請（專利權）人：	中國人民解放軍國防科技大學
主分類號：	G06F9/48	分類號：	G06F9/48;G06F9/455
代理公司：	長沙大珂知識產權代理事務所(普通合伙) 43236	代理人：	伍志祥
地址：	410003 湖***	國省代碼：	湖南;43
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	一種環境截止約束科學工作流調度方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

本發明公開了一種云環境下截止期約束的科學工作流調度方法，將任務集合T中的任務按照拓撲結構進行排序得到T′；為T′中的任務計算向上排序值；根據所述的向上排序值為中每個任務分配子截止期；將T′中任務根據子截止期的緊急情況進行排序；根據所述的排序先后次序為任務分配虛擬機；對初始調度方案進行虛擬機升/降級優化。本發明方法實現了云環境下的截止期約束下費用最小化的科學工作流調度，一方面通過虛擬機類型改變、任務回填等策略對虛擬機的占用率進行優化，提高了虛擬機使用率，另一方面通過截止期約束下的費用開銷優化，為整個調度方案節省費用開銷。

技術領域

本發明屬于網絡工作流調度領域，具體涉及一種云環境下截止期約束的科學工作流調度方法。

背景技術

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

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

發明內容

有鑒于此，本發明的目的在于提出一種云環境下截止期約束的科學工作流調度方法，用于提高科學工作流的資源利用率和任務調度效率。

基于上述目的，本發明提供的一種云環境下截止期約束的科學工作流調度方法，包括以下步驟：

步驟1，將任務集合T中的任務按照拓撲結構進行排序得到T′；

步驟2，為T′中的任務計算向上排序值；

步驟3，根據所述的向上排序值為中每個任務分配子截止期；

步驟4，將T′中任務根據子截止期的緊急情況進行排序；

步驟5，根據所述的排序先后次序為任務分配虛擬機。

進一步地，步驟5中分配虛擬機包括以下步驟：

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

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

由此，獲得工作流初始調度方案S′和租用虛擬機集合R。