[發明專利]支持依賴和時間平衡的云工作流任務聚類方法

在審

• 申請號: 201710202595.2
• 申請日: 2017-03-30
• 公開（公告）號: CN106991006A
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 嚴偉;楊朔;楊威;呂躍華;陶礫;施揚朋
• 申請（專利權）人: 浙江天正信息科技有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 杜軍

本發明公開了一種支持依賴和時間平衡的云工作流任務聚類方法。本發明在對流程圖中同一層級的任務進行聚類時優先考慮了任務之間的數據依賴關系，并考慮了聚類之間的時間平衡，本發明在對同一層級的任務進行聚類時并不是簡單地將具有相同子任務的父任務聚集在一起，而是綜合考慮了這些任務共有的子任務以及它們各自特有的子任務，在此基礎上提出了任務關聯度的概念和計算公式來表征任務之間的依賴程度。同時，本發明在優先考慮任務之間的依賴關系的基礎上還考慮了各個任務的運行時間，同時保證了聚類的依賴平衡與時間平衡。通過與傳統聚類方法進行實驗比較可以發現，本發明對任務進行聚類可以更有效地減少工作流的完成時間。

技術領域

本發明屬于云工作流調度中的工作流運行時間優化技術。在對同一水平層級的任務進行聚類時，基于任務之間的數據依賴關系以及聚類之間的時間平衡，提出了支持依賴和時間平衡的云工作流任務聚類方法。

背景技術

在各種科學領域(如物理學、天文學和生物醫學)的研究中都需要運行大規模的應用程序來處理數據，這些大規模的應用程序通常為工作流應用。這些工作流應用由許多具有依賴關系的計算密集型任務組成，這些任務的計算量千差萬別，有些任務的運行時間只需要幾秒而有些則需要幾個小時。當在云計算環境中執行這些運行時間很短的任務時會存在顯著的調度開銷，調度開銷產生的額外時間遠遠超過任務本身的運行時間，從而影響整個流程的執行時間。

由于云環境是按使用量收費，額外的系統開銷也會增加成本。為了減少這種開銷的影響，任務聚類技術應用而生。它將細粒度任務分組為粗粒度任務，減少需要執行的任務數量同時也增加了任務的計算粒度。任務聚類是一種工作流運行時間優化技術，它將多個短任務合并到單個作業中，從而減少了調度開銷并縮短了流程的執行時間。

現有的任務聚類技術主要分為兩類：時間平衡聚類和依賴平衡聚類。前者往往只考慮了時間平衡性，而忽視了流程的結構特征以及任務之間的數據依賴關系。數據依賴性意味著在兩個任務之間存在數據傳輸(一個任務的輸出數據是另一個任務的輸入數據)。因此在聚類時應盡量將具有相同子任務的父任務聚集在一起，依賴性不平衡意味著下層任務必須等待更多的上層任務執行結束才能開始執行，這樣一個層級上的任務集會延遲下一層級(甚至后續層級)的任務的開始時間，從而影響任務執行的并行性。

同樣的，依賴平衡聚類往往會忽視聚類之間的時間平衡性。在流程圖中，同一層的任務可能會有不同的運行時間。不考慮運行時間的變化去合并任務會導致負載失衡。比如一些聚類可能由短任務組成，而其他聚類由長任務組成。這種時間上的不平衡會延遲下一級任務的開始時間。因此，良好的聚類策略應該保證每一個聚類的執行時間都盡可能相近。

發明內容

本發明針對現有技術的不足，提出了一種支持依賴和時間平衡的云工作流任務聚類方法。該方法在對流程圖中同一層級的任務進行聚類時優先考慮了任務之間的數據依賴關系，在此基礎上考慮了聚類之間的時間平衡，有效縮短了工作流的完成時間。

本發明方法的具體步驟是：

步驟(1).輸入流程圖中某一層待聚類的任務集taskList；流程圖是工作流W＝(T,E)的圖形化表示，通過有向無環圖(DAG)來描述；其中T＝{t1,t2,...,tm}是頂點的集合，代表流程中的任務；E是有向邊的集合，代表任務之間的依賴關系；流程圖中從開始任務到某個任務所經過的有向邊的條數稱為該任務所在的層數；

步驟(2).計算該層任務中任意兩個任務之間的關聯度cor(ti,tj)；

關聯度的計算公式如下：