[發明專利]基于數據密集型科學工作流的任務調度與虛擬機整合方法

在審

• 申請號: 201810465028.0
• 申請日: 2018-05-16
• 公開（公告）號: CN108628665A
• 公開（公告）日: 2018-10-09
• 發明（設計）人: 熊聰聰;馮闊;趙青
• 申請（專利權）人: 天津科技大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/48
• 代理公司: 天津盛理知識產權代理有限公司 12209
• 代理人: 王利文

本發明涉及一種基于數據密集型科學工作流的任務調度與虛擬機整合方法，包括以下步驟：讀取數據密集型科學工作流，構造以任務為節點、任務間的數據依賴關系為邊的有向無環圖；確定工作流虛擬機：通過獲取每個任務執行的確切處理時間選擇出該工作流相對最適合的虛擬機，并用CPLEX方法進行虛擬機類型的求解；工作流截止期劃分：首先將工作流按照數據量大小相似和虛擬機類型相同的任務進行聚類形成n個任務包，然后采用基于浮動區間的方法求得工作流截止期；初始化任務調度：在工作流截止期劃分的基礎上，采用基于深度的任務調度順序方法；虛擬機租賃成本優化：采用加權融合新租賃時間片預期利用率的PHD方法進行任務調度。

技術領域

本發明屬于數據密集型科學工作流技術領域，尤其是一種基于數據密集型科學工作流的任務調度與虛擬機整合方法。

背景技術

隨著計算機網絡技術的發展，云計算技術給大數據處理提供了新的技術支持和發展契機。數據密集型數據密集型模式是一種以數據為核心的模式，其特性是執行過程中需要不斷獲取、共享、更新、存儲大規模數據，對于某個數據密集型任務，它所要訪問的數據甚至可以遍布大型數據中心的任何地方，所以它的執行效率要很大一部分受制于物理主機和存儲結點之間的帶寬。因為帶寬瓶頸、數據訪問延遲以及未加優化的數據遷移機制而使得現有的云系統在滿足數據密集型應用方面不盡如人意。

迄今為止，人們已經提出許多數據密集型科學工作流，2009年，Ghafarian等提出將數據密集型工作流先進行子工作流的劃分，然后最小化工作流的數據依賴性。然后根據資源的親密度進行子工作流的分配。2015年，Zhao等提出了一種用于面向數據密集型應用的能量和最后期限的任務調度方法。在該方法中，首先，數據關聯聚類方法將數據集和任務建模為一個二叉樹。因此，可以大大減少全球數據傳輸量，有利于降低SLA違背率。其次，“樹”基于任務需求程度的計算任務調度方法(TRD)提出，通過減少主動機的數量，降低全局數據傳輸的時間消耗，優化計算資源和網絡帶寬的利用率，提高整個云系統的能源利用率。2016年，Zhao等提出了一種改進的基于數據相關聚類的數據布局方法。在初始化階段，提出了一種基于數據相關聚類和遞歸劃分的數據聚類方法，并與已有的方法相比較，引入了數據大小因子，提出了一種新的矩陣劃分方法。以上方法只是通過對任務進行聚類，從而減少deadline，進而提高虛擬機的利用率。但是總體效果不是很理想。

可見，以上經典的方法都存在許多局限性，劃分結果并不理想，而且復雜度較高，難以滿足大型數據密集型工作流調度和虛擬機成本減低的要求。2015年，Cai等提出了在基于非共享服務的工作流調度與優化。該方法從Pareto解集中挑選成本最低的解作為原關鍵路徑優化問題的解。通過迭代優化多條全關鍵路徑，最小化工作流應用的非共享服務租賃總成本為了增強云環境的各項性能，增加云資源的利用率。2017年，Cai等提出了結合云計算中服務按區間計費的特點，通過對已租賃時間片進行重用，提高資源利用率提出一個任務右移策略和URH方法。實驗結果證明這兩張策略和規則都能夠降低特點類型工作流的資源租賃成本。

然而，由于許多工作流應用存在時效性，也就是具有截止期。長期租賃充足的資源雖然能夠滿足應用需求，但是容易造成大量的資源浪費。綜上所述，現有的數據密集型工作流調度方法在準確度和時間復雜度上都存在很大的提升空間。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于數據密集型科學工作流的任務調度與虛擬機整合方法，該方法有利于提高deadline的精確度和降低數據密集型科學工作流的資源租賃成本。

本發明解決其技術問題是采取以下技術方案實現的：

一種基于數據密集型科學工作流的任務調度與虛擬機整合方法，包括以下步驟：

步驟1、讀取數據密集型科學工作流，構造以任務為節點、任務間的數據依賴關系為邊的有向無環圖DAG；