摘要：云環(huán)境下，任務(wù)的執(zhí)行效率受限于任務(wù)間的通信時(shí)間和計(jì)算時(shí)間，通信時(shí)間是由于數(shù)據(jù)跨數(shù)據(jù)中心傳輸產(chǎn)生的，計(jì)算時(shí)間與任務(wù)所在集群的計(jì)算能力有關(guān)，有效減少任務(wù)因等待數(shù)據(jù)的到來(lái)而產(chǎn)生的時(shí)間開銷可提高任務(wù)的執(zhí)行效率，進(jìn)而降低用戶租賃云資源的費(fèi)用，提出基于任務(wù)復(fù)制的調(diào)度策略，以提高任務(wù)的并行性。經(jīng)性能分析，該策略在提高任務(wù)的執(zhí)行效率方面有一定的貢獻(xiàn)。

關(guān)鍵詞：相關(guān)性；通信開銷；閾值；任務(wù)復(fù)制；任務(wù)調(diào)度

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）10-0225-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（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

云計(jì)算[1]作為新時(shí)期的一種新技術(shù)發(fā)展迅速，其與大數(shù)據(jù)的研究應(yīng)用更是關(guān)系密切，云計(jì)算為大數(shù)據(jù)提供了無(wú)限的存儲(chǔ)空間和計(jì)算能力，讓大數(shù)據(jù)的研究應(yīng)用成為可能，而對(duì)大數(shù)據(jù)的處理是根據(jù)任務(wù)而定，即人們的需求決定了大數(shù)據(jù)的研究方向，而需求就是由一個(gè)個(gè)任務(wù)完成的，因此，如何提高任務(wù)的執(zhí)行效率對(duì)于現(xiàn)實(shí)需求具有極大的研究意義。

根據(jù)前期的研究[2-4]可知，任務(wù)的執(zhí)行離不開數(shù)據(jù)，相關(guān)任務(wù)之間存在數(shù)據(jù)相關(guān)性，任務(wù)的執(zhí)行效率取決于數(shù)據(jù)到來(lái)的快慢，如果相關(guān)數(shù)據(jù)在相同的集群上，那么運(yùn)行速度相對(duì)較快，但考慮到負(fù)載均衡[5]，不可能所有的數(shù)據(jù)都在一個(gè)集群上，因此如何使相關(guān)性大的數(shù)據(jù)在同一個(gè)集群上至關(guān)重要。

任務(wù)調(diào)度[6]問題是云計(jì)算環(huán)境下研究課題中的一個(gè)重要內(nèi)容，眾多研究學(xué)者提出了很多任務(wù)調(diào)度的算法，算法研究的重點(diǎn)集中在如何減少任務(wù)間的時(shí)間開銷，而時(shí)間開銷主要是由于不同集群上任務(wù)的通信產(chǎn)生的。目前應(yīng)用最廣泛的調(diào)度算法是基于啟發(fā)式的調(diào)度算法[7]，其中，由于基于任務(wù)復(fù)制的調(diào)度算法可以消除任務(wù)間的通信開銷，大大降低任務(wù)的等待時(shí)間，從而提高任務(wù)的執(zhí)行效率，使得基于任務(wù)復(fù)制的調(diào)度算法得到了廣泛的關(guān)注。

目前任務(wù)復(fù)制算法已經(jīng)有很多，基于復(fù)制的異構(gòu)多核任務(wù)調(diào)度算法[8]，應(yīng)用了二路復(fù)制方法，在減少任務(wù)因復(fù)制而導(dǎo)致的冗余量增大方面有極大的改善，從而減小了任務(wù)的調(diào)度長(zhǎng)度； 基于任務(wù)復(fù)制的動(dòng)態(tài)關(guān)鍵前驅(qū)調(diào)度算法 [9] 改進(jìn)了粒度定義，優(yōu)化了任務(wù)調(diào)度長(zhǎng)度，找到了更優(yōu)解；OSA[10]算法（Optimal Task Duplication based Scheduling Algorithm）將盡量多的父節(jié)點(diǎn)與子節(jié)點(diǎn)分配到同一個(gè)處理機(jī)上，來(lái)減少任務(wù)間的通信開銷，但是沒有考慮處理機(jī)的負(fù)載均衡問題。

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

任務(wù)分配是為了更好的完成任務(wù)調(diào)度，遺傳算法是一種啟發(fā)式的算法在任務(wù)調(diào)度中得到了廣泛使用，由于自身存在早熟等不足，本文采用改進(jìn)的遺傳算法進(jìn)行任務(wù)調(diào)度。為了提高云環(huán)境下任務(wù)的執(zhí)行效率降低執(zhí)行費(fèi)用，本文提出了一種基于通信開銷的并行任務(wù)調(diào)度策略。

1 問題模型分析

1.1 相關(guān)定義

一般來(lái)講，多個(gè)任務(wù)協(xié)作完成一個(gè)工作流，任務(wù)之間是有相互聯(lián)系的，這種制約關(guān)系可以用DAG圖來(lái)表示，即G={V，E，M，C}，其中：

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

E={eij| eij表示ti、tj間的邊，ti是tj 的父節(jié)點(diǎn)，表明ti、tj間有通信}；

M={mij| mij表示ti與tj間的通信開銷，ti是tj的父節(jié)點(diǎn)}；

C={ci| ci表示ti的計(jì)算開銷}。

定義1：通信開銷mij表示任務(wù)i和任務(wù)j在任務(wù)調(diào)度處理中要進(jìn)行通信，任務(wù)i是任務(wù)j的一個(gè)前驅(qū)，j在執(zhí)行過(guò)程中要用到i的處理結(jié)果，M的值越大表示兩任務(wù)間的通信開銷越大即兩任務(wù)相關(guān)性越大；

定義2：計(jì)算開銷ci表示執(zhí)行任務(wù)i時(shí)在處理器中除了通信開銷以外的一切開銷，計(jì)算開銷越大說(shuō)明任務(wù)越大越煩瑣；

用來(lái)描述通信開銷與計(jì)算開銷之間的關(guān)系，由M和C的差值來(lái)計(jì)算，結(jié)果有三種情況分別為大于0、等于0、小于0，TSV越大說(shuō)明通信開銷占主導(dǎo)地位即任務(wù)間的相關(guān)性越大，TSV小于0時(shí)的絕對(duì)值越大說(shuō)明計(jì)算開銷占主導(dǎo)地位即任務(wù)本身煩瑣與其他任務(wù)相關(guān)性小，根據(jù)這三種情況對(duì)任務(wù)采取不同的分配策略。

為了更清晰的表述，下面通過(guò)舉例方式進(jìn)行說(shuō)明，系統(tǒng)任務(wù)間的關(guān)系圖可用DAG圖來(lái)表示，如圖1所示。

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

1.2 任務(wù)分配

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

1.3 基于通信開銷的任務(wù)復(fù)制

任務(wù)復(fù)制主要是把不同隊(duì)列中通信開銷大的任務(wù)進(jìn)行復(fù)制。不同的隊(duì)列分配到不同的處理器上，處理器間的通信開銷比同一個(gè)處理器上的通信開銷要大，為了降低通信開銷提高任務(wù)執(zhí)行效率要對(duì)不同處理器上的相關(guān)性大的任務(wù)進(jìn)行復(fù)制，當(dāng)然不是把所有的有關(guān)聯(lián)的任務(wù)都進(jìn)行復(fù)制，相關(guān)任務(wù)的全部復(fù)制不僅會(huì)增加計(jì)算開銷而且會(huì)增加空間資源的開銷，代價(jià)太高。本文采用基于閥值的任務(wù)復(fù)制方案，該方案能減少因任務(wù)全部復(fù)制而引起的空間資源浪費(fèi)同時(shí)可以達(dá)到降低通信開銷的目的。同構(gòu)的系統(tǒng)上所有處理單元的運(yùn)算能力相同，所以本文假定所有的系統(tǒng)是同構(gòu)的。

設(shè)置閥值與復(fù)制任務(wù)的目的就是使得總開銷最小，開銷包括時(shí)間開銷與空間開銷，時(shí)間開銷包括通信開銷和計(jì)算開銷。復(fù)制相關(guān)任務(wù)會(huì)降低通信時(shí)間開銷但會(huì)增加計(jì)算開銷和空間開銷，是用空間換取時(shí)間所以要權(quán)衡兩者的利弊。

1.4 并行任務(wù)調(diào)度模型

任務(wù)的調(diào)度模型如圖4所示：

經(jīng)過(guò)任務(wù)復(fù)制和任務(wù)分配操作后，每個(gè)處理機(jī)上的任務(wù)隊(duì)列基本都是相互獨(dú)立的，還有少數(shù)的有關(guān)聯(lián)但對(duì)多個(gè)處理機(jī)進(jìn)行并行處理沒有太大影響。這樣就可以在每個(gè)處理機(jī)上獨(dú)立應(yīng)用任務(wù)調(diào)度算法，只有在遇到個(gè)別任務(wù)時(shí)才需要與其他處理機(jī)進(jìn)行通信大大降低了通信開銷，提高了任務(wù)執(zhí)行效率。本文采用文獻(xiàn)[3]中改進(jìn)的遺傳算法進(jìn)行任務(wù)調(diào)度。

2 性能分析評(píng)價(jià)

衡量算法的優(yōu)劣一般從時(shí)間和空間兩個(gè)方面來(lái)評(píng)價(jià)，本文也采用這兩個(gè)標(biāo)準(zhǔn)。任務(wù)的總執(zhí)行時(shí)間包括通信時(shí)間、處理時(shí)間以及閥值比較時(shí)間和任務(wù)復(fù)制時(shí)間，而通信時(shí)間是決定總執(zhí)行時(shí)間的關(guān)鍵因素，通過(guò)任務(wù)復(fù)制可以減少通信時(shí)間但會(huì)增加處理時(shí)間，如果減少的時(shí)間不能抵消增加的時(shí)間那么任務(wù)復(fù)制是沒有意義的只會(huì)增加存儲(chǔ)單元的使用，而閥值就是為了避免這種情況的發(fā)生并且使用簡(jiǎn)單的函數(shù)來(lái)做比較是高效的。這樣分配到每個(gè)處理機(jī)上的任務(wù)與其他處理機(jī)上的任務(wù)基本是獨(dú)立的只有很少的通信開銷，然后可以并行任務(wù)調(diào)度，可見使用閥值進(jìn)行任務(wù)復(fù)制可以提升任務(wù)調(diào)度的整體性能。任務(wù)總執(zhí)行時(shí)間的表示如下：

3 總結(jié)

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

參考文獻(xiàn)：

[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] 段菊， 陳旺虎， 王潤(rùn)平， et al. 云環(huán)境下基于聚簇的科學(xué)工作流執(zhí)行優(yōu)化策略[J]. 計(jì)算機(jī)應(yīng)用， 2015， 35（6）：1580-1584.

[3] 陳旺虎， 段菊， 俞茂義. 允許違反局部時(shí)間約束的科學(xué)工作流調(diào)度策略[J]. 計(jì)算機(jī)工程與科學(xué)， 2016（11）：2165-2171.

[4] 段菊， 于治國(guó). 云環(huán)境下基于相關(guān)性的并行任務(wù)調(diào)度策略[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2018， 28（06）：178-183.

[5] 喻莉， 阮文濤. 負(fù)載均衡技術(shù)的研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2007， 17（8）：120-122.

[6] 劉少偉， 孔令梅， 任開軍，等. 云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略[J]. 計(jì)算機(jī)學(xué)報(bào)， 2011， 34（11）：002121-2130.

[7] 賈麗云， 張向利， 張紅梅. 分布式系統(tǒng)下的啟發(fā)式任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2017， 53（12）：63-69.

[8] 周超群， 周亦敏. 一種改進(jìn)的基于復(fù)制的異構(gòu)多核任務(wù)調(diào)度算法[J]. 電子科技， 2017（06）：63-68.

[9] 何琨， 趙勇， 黃文奇. 基于任務(wù)復(fù)制的分簇與調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 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] 李靜梅， 尤曉非， 韓啟龍. 基于任務(wù)復(fù)制的多關(guān)鍵路徑任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2014， 35（5）：1639-1645.

【通聯(lián)編輯：梁書】