云環境下基于通信開銷的并行任務調度策略

摘要：云環境下，任務的執行效率受限于任務間的通信時間和計算時間，通信時間是由于數據跨數據中心傳輸產生的，計算時間與任務所在集群的計算能力有關，有效減少任務因等待數據的到來而產生的時間開銷可提高任務的執行效率，進而降低用戶租賃云資源的費用，提出基于任務復制的調度策略，以提高任務的并行性。經性能分析，該策略在提高任務的執行效率方面有一定的貢獻。

關鍵詞：相關性；通信開銷；閾值；任務復制；任務調度

中圖分類號：TP301.6 文獻標識碼：A

文章編號：1009-3044（2019）10-0225-03

開放科學（資源服務）標識碼（OSID）：

Parallel Task Scheduling Strategy Based on Communication Overhead in Cloud

DUAN Ju

（Shandong Management University， Jinan 250357， China）

Abstract： In the cloud environment， the execution efficiency of tasks is limited by the communication time and computing time between tasks. Communication time is caused by data transmission across data centers. The computing time is related to the computing power of the cluster where the task is located. Effectively reduce the time overhead incurred by the task waiting for the arrival of data， which can improve the execution efficiency of the task. In turn， it can reduce the cost for users to rent cloud resources. A scheduling strategy based on task replication is proposed to improve the parallelism of tasks. Through performance analysis， this strategy has a certain contribution to improve the efficiency of task execution.

Key words： task correlation； communication overhead； threshold value； task replication； task scheduling

云計算[1]作為新時期的一種新技術發展迅速，其與大數據的研究應用更是關系密切，云計算為大數據提供了無限的存儲空間和計算能力，讓大數據的研究應用成為可能，而對大數據的處理是根據任務而定，即人們的需求決定了大數據的研究方向，而需求就是由一個個任務完成的，因此，如何提高任務的執行效率對于現實需求具有極大的研究意義。

根據前期的研究[2-4]可知，任務的執行離不開數據，相關任務之間存在數據相關性，任務的執行效率取決于數據到來的快慢，如果相關數據在相同的集群上，那么運行速度相對較快，但考慮到負載均衡[5]，不可能所有的數據都在一個集群上，因此如何使相關性大的數據在同一個集群上至關重要。

任務調度[6]問題是云計算環境下研究課題中的一個重要內容，眾多研究學者提出了很多任務調度的算法，算法研究的重點集中在如何減少任務間的時間開銷，而時間開銷主要是由于不同集群上任務的通信產生的。目前應用最廣泛的調度算法是基于啟發式的調度算法[7]，其中，由于基于任務復制的調度算法可以消除任務間的通信開銷，大大降低任務的等待時間，從而提高任務的執行效率，使得基于任務復制的調度算法得到了廣泛的關注。

目前任務復制算法已經有很多，基于復制的異構多核任務調度算法[8]，應用了二路復制方法，在減少任務因復制而導致的冗余量增大方面有極大的改善，從而減小了任務的調度長度； 基于任務復制的動態關鍵前驅調度算法 [9] 改進了粒度定義，優化了任務調度長度，找到了更優解；OSA[10]算法（Optimal Task Duplication based Scheduling Algorithm）將盡量多的父節點與子節點分配到同一個處理機上，來減少任務間的通信開銷，但是沒有考慮處理機的負載均衡問題。

隨著研究的不斷深入，任務復制算法也得到了很多改進。PTSAC算法[4]（Parallel Task Scheduling Algorithm based on Correlation）該算法在任務調度之前根據任務間的通信開銷進行隊列劃分，以提高任務劃分的效率；SWFEBC算法[2]（Scientific workflow execution optimization strategy based on Clustering）該算法對工作流中的任務進行靜態劃分，通過任務復制的方式減少任務簇之間的聯系，從而減少任務的等待時間，提高任務的執行效率；文獻[11]提出一種TDMCP算法（Task Duplication Multi Critical Path）主要考慮關鍵路徑上的任務對整體任務調度的影響，該方法只復制首任務來影響后續任務的執行，達到提高整體任務調度效率的目的。

任務分配是為了更好的完成任務調度，遺傳算法是一種啟發式的算法在任務調度中得到了廣泛使用，由于自身存在早熟等不足，本文采用改進的遺傳算法進行任務調度。為了提高云環境下任務的執行效率降低執行費用，本文提出了一種基于通信開銷的并行任務調度策略。

1 問題模型分析

1.1 相關定義

一般來講，多個任務協作完成一個工作流，任務之間是有相互聯系的，這種制約關系可以用DAG圖來表示，即G={V，E，M，C}，其中：

V={ti|ti是工作流中的任務，i=1，2，3，…，n}；

E={eij| eij表示ti、tj間的邊，ti是tj 的父節點，表明ti、tj間有通信}；

M={mij| mij表示ti與tj間的通信開銷，ti是tj的父節點}；

C={ci| ci表示ti的計算開銷}。

定義1：通信開銷mij表示任務i和任務j在任務調度處理中要進行通信，任務i是任務j的一個前驅，j在執行過程中要用到i的處理結果，M的值越大表示兩任務間的通信開銷越大即兩任務相關性越大；

定義2：計算開銷ci表示執行任務i時在處理器中除了通信開銷以外的一切開銷，計算開銷越大說明任務越大越煩瑣；

用來描述通信開銷與計算開銷之間的關系，由M和C的差值來計算，結果有三種情況分別為大于0、等于0、小于0，TSV越大說明通信開銷占主導地位即任務間的相關性越大，TSV小于0時的絕對值越大說明計算開銷占主導地位即任務本身煩瑣與其他任務相關性小，根據這三種情況對任務采取不同的分配策略。

為了更清晰的表述，下面通過舉例方式進行說明，系統任務間的關系圖可用DAG圖來表示，如圖1所示。

圖中圓圈表示任務頂點，在圓圈中的1到15表示任務T1-T15，每個任務都有計算開銷，有的任務間有通信開銷；計算開銷用C（Ti）來表示，通信開銷用M（Ti，Tj）來表示，在圖中用二元組（C，M）來表示，即有向線段上的二元組（2，1）表示任務i的計算開銷是2，任務i與任務j之間的通信開銷是1。

1.2 任務分配

為了減少不同處理機上任務之間的通信開銷，在分配任務時相互間通信開銷大的任務分配到同一個處理機上以提高任務執行效率。根據二元組中第二個元素的值進行分配。廣度優先遍歷DAG圖，圖1中任務1、任務2、任務3都沒有前驅，所以把任務分成三個隊列{T1}{T2}{T3}，T4的前驅只有T1所以把T4加入隊列1{T1，T4}，以此類推，把T7、T11也加入隊列1{T1，T4，T7，T11}，當出現兩個前驅的時候，則比較二元組中第二個元素M值，加入值大的前驅所在隊列，所以T12加入隊列1，最終的三個隊列分別為{T1，T4，T7，T11，T12，T14}、{T2，T5，T8，T13，T15}、{T3，T6，T9，T10}。如圖2所示：

1.3 基于通信開銷的任務復制

任務復制主要是把不同隊列中通信開銷大的任務進行復制。不同的隊列分配到不同的處理器上，處理器間的通信開銷比同一個處理器上的通信開銷要大，為了降低通信開銷提高任務執行效率要對不同處理器上的相關性大的任務進行復制，當然不是把所有的有關聯的任務都進行復制，相關任務的全部復制不僅會增加計算開銷而且會增加空間資源的開銷，代價太高。本文采用基于閥值的任務復制方案，該方案能減少因任務全部復制而引起的空間資源浪費同時可以達到降低通信開銷的目的。同構的系統上所有處理單元的運算能力相同，所以本文假定所有的系統是同構的。

設置閥值與復制任務的目的就是使得總開銷最小，開銷包括時間開銷與空間開銷，時間開銷包括通信開銷和計算開銷。復制相關任務會降低通信時間開銷但會增加計算開銷和空間開銷，是用空間換取時間所以要權衡兩者的利弊。

1.4 并行任務調度模型

任務的調度模型如圖4所示：

經過任務復制和任務分配操作后，每個處理機上的任務隊列基本都是相互獨立的，還有少數的有關聯但對多個處理機進行并行處理沒有太大影響。這樣就可以在每個處理機上獨立應用任務調度算法，只有在遇到個別任務時才需要與其他處理機進行通信大大降低了通信開銷，提高了任務執行效率。本文采用文獻[3]中改進的遺傳算法進行任務調度。

2 性能分析評價

衡量算法的優劣一般從時間和空間兩個方面來評價，本文也采用這兩個標準。任務的總執行時間包括通信時間、處理時間以及閥值比較時間和任務復制時間，而通信時間是決定總執行時間的關鍵因素，通過任務復制可以減少通信時間但會增加處理時間，如果減少的時間不能抵消增加的時間那么任務復制是沒有意義的只會增加存儲單元的使用，而閥值就是為了避免這種情況的發生并且使用簡單的函數來做比較是高效的。這樣分配到每個處理機上的任務與其他處理機上的任務基本是獨立的只有很少的通信開銷，然后可以并行任務調度，可見使用閥值進行任務復制可以提升任務調度的整體性能。任務總執行時間的表示如下：

3 總結

本文提出的任務復制策略是以增加空間資源消耗為代價來消減通信開銷，設置閥值是為了盡量減少空間資源的使用，在增加的計算開銷和消減的通信開銷能夠相互抵消或者低于時才進行任務復制，先進行任務分配使得每個處理機上的任務隊列基本都是相互獨立的，不同處理機間通信很少，這樣既能減少因任務全部復制而引起的空間資源浪費同時可以達到降低通信開銷的目的，然后在每個處理機上用改進的遺傳算法進行任務調度。

參考文獻：

[1] CHEN W， ALTINTAS I， WANG J， et al. Enhancing smart re-run of Kepler scientific workflows based on near optimum provenance caching in cloud[C]//Services （SERVICES）， 2014 IEEE World Congress on. IEEE， 2014： 378-384.

[2] 段菊， 陳旺虎， 王潤平， et al. 云環境下基于聚簇的科學工作流執行優化策略[J]. 計算機應用， 2015， 35（6）：1580-1584.

[3] 陳旺虎， 段菊， 俞茂義. 允許違反局部時間約束的科學工作流調度策略[J]. 計算機工程與科學， 2016（11）：2165-2171.

[4] 段菊， 于治國. 云環境下基于相關性的并行任務調度策略[J]. 計算機技術與發展， 2018， 28（06）：178-183.

[5] 喻莉， 阮文濤. 負載均衡技術的研究與實現[J]. 計算機技術與發展， 2007， 17（8）：120-122.

[6] 劉少偉， 孔令梅， 任開軍，等. 云環境下優化科學工作流執行性能的兩階段數據放置與任務調度策略[J]. 計算機學報， 2011， 34（11）：002121-2130.

[7] 賈麗云， 張向利， 張紅梅. 分布式系統下的啟發式任務調度算法[J]. 計算機工程與應用， 2017， 53（12）：63-69.

[8] 周超群， 周亦敏. 一種改進的基于復制的異構多核任務調度算法[J]. 電子科技， 2017（06）：63-68.

[9] 何琨， 趙勇， 黃文奇. 基于任務復制的分簇與調度算法[J]. 計算機學報， 2008， 31（5）：733-740.

[10] PARK C I， CHOE T Y. An optimal scheduling algorithm based on task duplication[C]//Parallel and Distributed Systems， 2001. ICPADS 2001. Proceedings. Eighth International Conference on. IEEE， 2001： 9-14.

[11] 李靜梅， 尤曉非， 韓啟龍. 基于任務復制的多關鍵路徑任務調度算法[J]. 計算機工程與設計， 2014， 35（5）：1639-1645.

【通聯編輯：梁書】