摘 ?要： 提出了一種帶任務重復的任務劃分策略算法D-ITPS（Improved task partitioning Strategy with duplication），該算法首先將DAG圖中的一些滿足歸并條件的任務進行歸并，然后將所有的任務按照劃分策略劃分為一個個包，將包按照Max-Min策略整體調度到處理器上執(zhí)行，在完成基本的映射后，檢測每個染色體是否可以通過任務重復來減少通信時間，若可以則在處理器的空閑時間隙重復任務以減少總調度長度。

關鍵詞： 云計算;復雜DAG圖;調度算法;任務重復;調度長度

中圖分類號： TP30 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.12.002

本文著錄格式：張銀娟. 云計算中一種帶任務重復機制的任務劃分策略[J]. 軟件，2019，40（12）：0612

A Task Partitioning Strategy With Task Repetition Mechanism in

Cloud Computing Environments

ZHANG Yin-juan

（Guangling College of Yangzhou University， YangZhou， Jiangsu， 225000）

【Abstract】： We presented an improved task partitioning strategy with duplication D-ITPS， the algorithm firstly merge tasks in DAG which meet merging conditions， then all of the tasks are divided into small packages， which are scheduled to processors according to Max-Min algorithm. After the completion of basic mapping， detecting whether each chromosome can reduce communication time by duplicating tasks， if possible， duplicate this task in the idle gap of processor to reduce the total schedule length.

【Key words】： Cloud computing; Complex DAG; Task scheduling; Task duplication; Makespan

0 ?引言

云計算[1-3]環(huán)境下工作流的調度研究是一個NP完全問題，針對此問題提出許多算法，至今也有一些基于元啟發(fā)式的算法用來解決NP問題，如：粒子群算法（PSO）[4]、禁忌搜索（TS）[5]，模擬退火（SA）[6]，遺傳算法（GA）[7]等。相較之下，GA被認為是優(yōu)化領域的一種好的方法且通過運用進化的原則在多項式時間內從大量搜索空間和并行搜索中獲得高質量的解決方案。它提供一些方法來估算有效參數。

本文主要借助于遺傳算法來求得調度的最優(yōu)解，現有的一些基于遺傳算法（GA）的算法，如文獻[8-10]提出了應用于工作流調度的算法，但是它們均沒有考慮到云計算中異構組件的特點，且并不適合云系統(tǒng)這樣的異構分布式計算系統(tǒng)。基于GA的算法，有的通過隨機選擇來選擇初始種群，有的在工作流的同一階段用優(yōu)化方法將任務排序，比如最先完成的任務，最小依賴的任務，最大依賴的任務，其中一些用具有至多兩個輸出節(jié)點的簡單圖來表示。文獻[11]中考慮到云環(huán)境下異構的特性，但是該論文提出的算法中使用的是簡單DAG圖，而云環(huán)境下的工作流任務間的關系復雜，轉換為DAG圖后任務間的分層不明顯，且每個任務的大小和其前后繼任務都各不相同，顯然簡單的DAG圖不能適用于云環(huán)境中。文獻[12]提出了異構啟發(fā)式算法（HSGA），它考慮到了異構環(huán)境下任務的復雜程度，采用復雜的DAG圖對任務進行描述和調度，但是其交叉率和變異率均固定，易造成“早熟”的現象。通過以上對國內外研究現狀的綜述，可以看出針對云計算環(huán)境下的調度問題，目前學術界提出的方法策略非常多[13-14]，大多數從優(yōu)化調度長度來考慮，也有從節(jié)能和負載平衡方面來考慮的。大部分學者將云計算環(huán)境中的工作流轉化成簡單的DAG圖來考慮，從云計算任務復雜的程度來看，簡單DAG圖顯然是不適用于云環(huán)境中的。本文通過對云環(huán)境下工作流進行處理，將其轉化為復雜的DAG圖并對其進行調度，同時考慮負載和計算資源性能的基礎上，盡可能減少調度長度。

1 ?D-ITPS算法

1.1 ?D-ITPS的簡單抽象模型

圖1給出了本文提出算法的簡單抽象模型。

圖1 ?任務抽象模型

Fig.1 ?Task abstract model

用戶提交的作業(yè)轉為DAG圖后，對DAG圖中的一些滿足歸并條件的任務進行歸并，歸并完成后使用任務劃分策略將任務有效地劃分并分配到處理器上形成一個染色體。再根據 任務重復策略利用處理器上的空閑時間隙進行重復特定的父任務以減少總完成時間。任務重復策略結束后形成新的染色體，取一定數量的染色體進行隨機交叉、變異，得到一個最優(yōu)的調度方案，將該調度方案提交到云環(huán)境下進行計算調度長度、通信開銷等，最后對結果進行分析。

1.2 ?編碼及算法

1.2.1 ?編碼

在遺傳算法中，每個染色體用來表示問題的一個解，染色體的編碼方式有很多，采用何種方式進行編碼則有當前問題的需求來決定。該算法中采用如圖2的編碼方式。

V1 V3 V4 V2 V5 ···· V9

P2 P9 P3 P1 P8 ···· P25

圖2 ?單個染色體的簡單編碼

Fig.2 ?Simple coding of a single chromosome

1.2.2 ?任務歸并階段

本文提出的算法首先對DAG圖中的一些任務進行歸并，歸并后將歸并的任務看成一個大任務，其歸并后的大任務的計算時間和存儲空間均采用歸并的小任務的計算時間和存儲空間求和方式來計算。如公式（1）（2）所示。

若任務與任務滿足任務歸并條件，其中任務在各個處理器上的計算開銷為 ，存儲開銷為，任務在各個處理器上的計算開銷為，存儲開銷為，任務合并后形成新任務，其計算開銷及存儲開銷為：

（1）

（2）

任務歸并后其實質還是兩個任務，僅僅是將兩個任務綁定，調度時調度到同一個處理器上。那如何才可以將任務進行歸并？需同時滿足如下兩個條件：

（1）當前任務有且僅有一個直接父任務并且該父任務也有且僅有一個直接子任務，即是該任務;

（2）該任務與其直接父任務間的通信開銷大于等于其在不同的處理器上的最大計算開銷。

滿足上述條，將子任務歸并到父任務，將其看成一個大的任務，調度時調度到同一處理器上。

歸并算法如算法1.1所示。

算法1.1 ?歸并算法

Step 1： for DAG圖中所有任務do

Step 2： ? ?if（（當前任務有且僅有一個父任務，即 ）&&（是父節(jié)點的唯一子任務，即））then

Step 3： ? ? ? ? ? ? if then

Step 4： ? ? ? ? ? ? ? ? ? 將任務歸并到父任務，歸并后的任務為

end if

end if

end for

1.2.3 ?任務劃分策略

任務劃分主要目的在于最小化云計算環(huán)境中所有參與任務的總完成時間。任務的有效劃分對于最小化完成時間是有必要的。DAG圖調度中將任務映射到處理器上的時候要求要保有任務間的約束關系，這是一個NP問題。有效地分析任務之間的互斥關系有助于資源共享。在本算法中，將歸并后的任務劃分為一個個任務包的形式，再將任務包調度到處理器上執(zhí)行。

任務劃分策略主要根據任務的通信時間及任務間的約束關系進行劃分初步的任務包。首先將任務按照其通信時間的大小降序排列形成隊列，將排列在一起且滿足拓撲順序的任務劃分為一個包。劃分算法如算法1.2所示，首先將隊列中符合拓撲順序的通信時間小的任務劃分到通信時間大的任務包中，通信時間用任務輸出數據的大小除以資源間的帶寬，對于出口節(jié)點，該值為0。如公式（3）所示。

（3）

表示任務向任務輸出數據的大小，表示任務與任務所在處理器之間的帶寬。

算法1.2 ?劃分策略

Step 1：計算所有任務的通信開銷值comm_cost

Step 2： 按照comm_cost值將任務降序排列形成隊列

Step 3：for隊列中的每個任務do

Step 4： ? if（（ ）&&（與有約束關系） then

Step 5： ? ? ? ?合并任務

end if

end for

任務分為包后，定義包的幾個參數：

定義1.1 ?將DAG圖中的任務分為包后，在每個包中，類比于DAG圖中的任務將包定義為四元組形式：

（1）表示任務節(jié)點的集合;

（2）是邊的集合;

（3）與表示不同的兩個包。

定義1.2 ?任務包與任務包之間有多條邊相連，包間的通信開銷為其所有在包中節(jié)點間的通信時間的均值，計算公式如下：

（4）

表示連接包邊的權值之和，即所有在包中任務間的通信時間之和，表示連接兩包的邊的個數。

定義1.3 ?任務包在處理器上的執(zhí)行時間取所有任務執(zhí)行時間和的平均值。

（5）

表示任務包中任務的個數，表示包中所有任務在處理器上的平均執(zhí)行時間之和，表示所有處理器的個數。

使用算法1.2后任務大致分為幾個包，對未被分配到包中的任務，采用算法1.3將任務劃分到各個包中。其基本思想是先按照所有包中任務的個數對包進行升序排列形成隊列，對于未被分到包中的任務，查找隊列中第一個包中的主要任務，即通信時間最大的任務。若主要任務是任務的父任務，則將歸入包中，更新包的相關參數。否則將查找任務的主要父任務MIIP所在的包，將歸入到包中。

算法1.3 ?后續(xù)劃分策略

Step 1： 計算當前所有包中任務的個數，按照升序進行排列

Step 2：while所有未被分包的任務do

Step 3： ? ? ?取包中任務

Step 4： ? ? ?取包隊列中的第一個包，找出通信開銷最大的任務

Step 5： ? ? ?if ?then

Step 6： ? ? ? ? ?標記

Step 7： ? ? ? ? ?更新包的參數

Step 8： ? ? ? else

Step 9： ? ? ? ? 查找的MIIP任務

Step 10： ? ? ? ? if 已在包中 then

Step 11： ? ? ? ? ? ?標記

Step 12： ? ? ? ? ? ?更新包的參數

Step 13： ? ? ? ? ?else

Step 14： ? ? ? ? ? ? 標記

Step 15： ? ? ? ? ? ? 更新包的參數

end if

end if

Step 16： ? ?按照包中任務個數進行升序排序

end while

在分包的過程中，要注意并行性及通信開銷的平衡，如定理1.1。不能因為顧及通信開銷將大量的任務放到同一包中，這樣包中的任務會急劇增多，最壞的情況是所有任務集中到一個處理器上執(zhí)行，這樣就不能體現多處理器的優(yōu)點，即不能兼具并行性的優(yōu)點。當然由于處理器個數的有限性，不能將任務盡可能分為多個包，導致每個包中的任務數量極少，這樣會造成資源的浪費。

定理1.1 ?設是DAG圖中的任務，表示任務間的通信開銷，用邊上權值表示。最優(yōu)的調度策略是根據Max-Min（最大并行性，最小通信時間）權衡。

證明：根據Babb[15]“由誰來處理大任務包取決于所在系統(tǒng)結構的不同。”總之，大粒度任務包意味著在執(zhí)行過程中要處理的底層人物的數量較多[16]。任務包用于減少通信時間的開銷，同時在任務處理器數量一定的情況下減少了處理器的負載。任務包的順序執(zhí)行降低系統(tǒng)的并行性。任務包的大小由其包含的任務的大小決定。如果任務包的過小則由于包間上下文交換會加重處理器的負載，反之若包的顆粒過大，則并行性降低。并行性與通信開銷的大小要采用Max-Min權衡來控制。

綜上，為權衡并行性與包的顆粒大小，定義兩個閾值與來控制包中任務的個數，若包中任務個數小于，則優(yōu)先向該包中添加任務，若包中任務個數大于，則在分配未分配的任務時，將該包從包隊列中移除。在本文中與的取值為：

（6）

（7）

在按照任務劃分策略將任務劃分為包后，將包分配到資源上使用Max-Min算法[17]來實現。Max-Min算法首先計算任務包在每個處理器上的完成時間，按照各個包的完成時間將包進行降序排列，將虛擬機列表按照計算能力進行降序排列，然后按照包的排列順序及虛擬機列表的排列順序將各個包分配到處理器上。算法實現如算法1.4所示：

算法1.4 ?Max-Min算法

Step 1：判斷任務包隊列是否為空，不為空，執(zhí)行Step2，否則執(zhí)行Step 7

Step 2：對于任務包隊列中所有包，求出映射到所有處理器上的最早完成時間

Step 3：找出有最大最早完成時間的任務包并找出對應的處理器

Step 4：將任務包映射到該處理器，更新任務包列表

Step 5：更新處理器的預期就緒時間

Step 6：更新其余包在處理器上的最早完成時間，返回Step1

Step 7：按照圖2中的編碼方式輸出調度序列

在將任務按照圖2的編碼方式編碼后，繼續(xù)執(zhí)行算法1.5直至求出最優(yōu)的調度方案。

1.2.4 ?任務重復階段

本階段中任務對算法1.4中輸出的調度序列進行處理，在調度過程中，如果存在空閑時間隙，將利用這些空閑時間隙來執(zhí)行重復任務和候選節(jié)點，以期將任務總完成時間提前。

當一個任務調度到處理器上時，通常將此時間定義為任務的到達時間。但是任務的實際開始時間并不是任務的到達時間，還需考慮處理器是否空閑以及其所有前驅任務的數據均傳輸到處理器上。在準備執(zhí)行任務前需等待其所有直接前驅任務將數據傳達以此來遵守DAG圖優(yōu)先關系約束。

DAG圖中優(yōu)先級和通信延遲的約束使得處理器上產生空閑時間隙，無法實現數據提前傳達。如何判斷是否存在合適的空閑時間隙定義1.4給出了方法描述：

定義1.4 ?[18]給出一組任務將其調度到處理器上，存在空閑時間隙（在任務和之間）滿足如下條件即可容納任務，

（8）

其中，和分別表示時間隙的開始時間和結束時間。表示任務在當前處理器上的執(zhí)行時間。表示任務在處理器上的開始執(zhí)行時間。假設沒有合適的空閑時間隙，任務調度到處理器上，其開始時間決定于處理器的空閑時間，如圖3所示。

定義1.5 ?（MIIP[19]，Most ?Important immediate parent）任務的所有直接父任務中最晚到達的任務稱為最重要的直接父任務，用符號表示，因為它阻礙了任務的開始時間。

所有任務的MIIP任務數據到達時間計算公式如下：

（9）

表示任務前驅任務的集合， 表示前驅任務與當期那任務在同一處理器上執(zhí)行，則此時的為0。表示前驅任務與子任務不在同一處理器上執(zhí)行，則計算如公式（10）所示。

（10）

圖3 ?空閑時間隙與重復任務

Fig.3 ?Idel gap and repetitive tasks

由于受父任務的數據到達時間影響，任務的開始時間受到一定限制。前驅任務的數據到達子任務所在處理器有兩種途徑：

（1）在合適的空閑時間隙重復重要直接前驅任務，減少任務之間數據的傳輸開銷;

（2）將子任務盡可能調度到直接父任務所在的處理器，從而避免通信開銷。

第二種方法顯然會導致同一處理器上的任務過多，負載過重，從而處理器的計算能力下降，導致任務的總完成時間并不能提前。

任務重復算法主要從在空閑時間隙重復任務著手，主要按照兩種規(guī)則重復任務，如下：

（1）優(yōu)先重復直接父節(jié)點中出度最大的任務。重復出度最大的父任務是因為父任務的出度大，它影響最多的子任務的開始時間，將出度最大的父任務重復執(zhí)行，則不僅僅可以提前當前子任務的開始時間，其余的該父任務的子任務的開始時間也會相應的提前。

（2）重復直接父節(jié)點中的MIIP任務。重復MIIP任務是因為MIIP任務的完成時間限制當前任務的開始時間，將其在子任務所在的處理器上重復執(zhí)行，則當前任務的開始時間提前。

為避免冗余重復，只重復有重要數據輸出的父節(jié)點。在每次重復任務后，任務的總完成時間重新更新，若重復該任務，總完成時間不改變則刪除該重復任務，處理器一直重復此操作直至無MIIP任務或出度最大的父任務，或者無空閑時間隙。所有處理器均執(zhí)行檢查時間隙，重復任務，計算完成時間的操作，直至所有任務均被檢查和調度完成。

當前處理器上任務執(zhí)行完成時間和其直接前驅的數據到達時間，計算公式如（11）：

（11）

表示第一個可容納執(zhí)行任務的空閑時間隙，表示處理器空閑時間。

任務的完成時間計算公式如下：

（12）

算法的總完成時間為：

（13）

查找并重復任務的算法表示如算法1.5所示。

算法1.5

Begin

Repeat

{

Step 1： ? ←查找任務在處理器上的開始時間

Step 2：

Step 3： ?←任務所有任務中出度最大的父任務節(jié)點，存在幾個以上相同出度，比較完成時間，完成時間最大的任務

Step 4： ←任務的MIIP任務

Step 5： if（和均不存在或均已調度到當前處理器上）

返回值

else if（處理器上存在適合執(zhí)行或的空閑時間隙）{

←計算任務在處理器上的完成時間

←計算任務在處理器上的完成時間

if

在處理器上重復任務

else if

在處理器上重復任務

else

返回

}

else

返回

}

End

表1 ?參數表

Tab.1 ?Parameters

類型 參數 取值范圍

資源參數 資源個數 30

資源速度 500-1000（MIPS）

資源間帶寬 10-100（mps）

CCR值 0.25

任務參數 任務個數 30-100

任務長度 12-72（× MI）

任務失敗率 -

算法參數 種群大小 20

交叉率 0.5

變異率 0.5

精英選擇率 0.75

任務迭代次數 20

2 ?D-ITPS算法仿真實驗

2.1 ?仿真環(huán)境

本文中提出了一種改進的帶任務重復機制的劃分策略D-ITPS算法，為驗證該算法的有效性，將其與HEFT[20]算法和OTPSD算法[21]進行比較。

2.2 ?仿真結果與分析

圖4對比三種算法，NSL參數中總完成時間作為其中的一個變化因子，本文中提出的D-ITPS算法的總完成時間最少且NSL性能最優(yōu)，但隨著CCR值的增大，即任務間的通信量變多，通信時間延長。在劃分包的時候雖然會減少一定的通信時間，但是由于并行性和負載均衡的限制，以及包粒度的定義和劃分策略的局限性，總完成時間會有所增大，但總體相較于HEFT算法和OTPSD算法有所提升。

圖4 ?任務的NSL性能分析

Fig.4 ?NSL performance analysis of tasks

圖5中隨著任務數量的增長，平均NSL值會有所變化。在任務數在150-300時，提出的算法的平均NSL值小于另兩種算法。

隨著任務通信時間的延長，D-ITPS算法的性能高于其余兩種算法的性能。在本算法中任務處理器個數一定，在多處理上執(zhí)行的時間越短，Efficiency值越大，性能越優(yōu)。

圖5 ?任務的平均NSL性能分析

Fig.5 ?Average NSL performance analysis of tasks

圖6 ?任務的Efficiency性能分析

Fig.6 ?Efficiency performance analysis of tasks

3 ?總結與展望

本文提出了任務劃分的策略及任務重復機制，采用另一種方式將任務進行預處理。首先將DAG圖中的任務進行歸并，歸并后按照劃分策略將任務劃分到包，將包整體調度到處理器上，劃分包的主要目的在于減少任務間的通信時間。再利用處理器的空閑時間隙重復關鍵父任務進一步減少通信時間，優(yōu)化總完成時間。

實驗證明本文中提出的算法在總完成時間的優(yōu)化上有一定的效果，同時在資源負載以及任務失敗率上有一定的成效。

然而，在算法中仍存在一些不足：

（1）算法中均提出了任務的調度模型，但是與真實的云計算模型相比仍過于簡單，存在一定的差距。

（2）D-ITPS算法中規(guī)定了重復的任務，主要重復最晚完成時間的父任務和最大出度的父任務，固定地重復任務并不一定能很好地利用時間隙，重復的任務有可能是對總完成時間沒有影響的。

（3）任務劃分策略中，劃分任務包時并行性與顆粒大小的衡量采用閾值來定義，閾值的大小取值并不能保證最好地權衡并行性與包的粒度大小。

針對以上問題未來將進一步研究

（1）對算法中提出的任務調度模型進一步完善，對任務及虛擬機進行建模，在調度任務時，按照實際情況考慮將任務調度到不同性能不同狀態(tài)的虛擬機上，且虛擬機的個數能夠進行動態(tài)調整。

（2）D-ITPS算法中可以根據當前調度到處理器上的任務與以后要調度到處理器上的任務決定要重復任務，不需要在重復任務后查找刪除對總完成時間無影響的重復任務。

（3）任務劃分策略中根據處理器的性能與任務的參數進行并行性與任務包粒度的權衡，而任務的個數僅為其中的參數而不是唯一決定的參數。

參考文獻

[1]甘云志. 并行計算的一體化研究現狀與發(fā)展趨勢[J]. 電子技術與軟件工程， 2019（7）： 134.

[2]卜曉波. 試論大數據云計算環(huán)境下的數據安全[J]. 軟件， 2018， 39（2）： 197-199.

[3]丁順， 陳世平. 云計算中基于包簇映射的多目標蟻群資源分配算法[J]. 軟件， 2018， 39（11）： 01-06.

[4]Pandey， S. Scheduling and management of data intensive application workflows in grid and cloud computing environments[J]. Doctoral thesis， Department of Computer Science and Software Engineering， the University ofMelbourne， Australia， 2010， 42（8）： 386-474.

[5]Porto， S.， Ribeiro， C. A tabu search approach to task scheduling on heterogeneous processors under precedence constraints[J]. International Journal of High Speed Computing， 1995， 7（1）： 45-71.

[6]Kalashnikov A V， Kostenko V A. A parallel algorithm of simulated annealing for multiprocessor scheduling[J]. Journal of Computer & Systems Sciences International， 2008， 47（3）： 455-463.

[7]K. Zhu， H. Song， L. Liu， et al. Hybrid Genetic Algorithm for Cloud Computing Applications[C]// Services Computing Con ference. IEEE， 2014：182-187.

[8]Yoo M. Real-time task scheduling by multiobjective genetic algorithm[J]. Journal of Systems & Software， 2009， 82（4）： 619-628.

[9]Omara F A， Arafa M M. Genetic Algorithms for Task Scheduling Problem[J]. Journal of Parallel & Distributed Computing， 2010， 70（1）： 13-22.

[10]Yu J， Buyya R， Ramamohanarao K. Workflow Scheduling Algorithms for Grid Computing[M]// Metaheuristics for Scheduling in Distributed Computing Environments[M]. Springer Berlin Heidelberg， 2008.

[11]李靜梅， 孫冬微， 吳艷霞. 一種全局較優(yōu)的靜態(tài)任務調度算法[J]. 計算機應用研究， 2014， 31（4）： 1027-1030.

[12]Delavar A G， Aryan Y. HSGA： a hybrid heuristic algorithm for workflow scheduling in cloud systems[J]. Cluster Computing， 2014， 17（1）： 129-137.

[13]武濤. 基于云計算的并行動態(tài)路徑搜索算法研究[J]. 軟件， 2015， 36（4）： 128-132.

[14]趙辰吟， 姚文斌. 基于一種改進免疫算法的云計算任務調度策略研究[J]. 軟件， 2015， 36（12）： 149-153.

[15]Babb R G I. Parallel Processing with Large-Grain Data Flow Techniques[J]. Computer， 1984， 17（7）： 55-61.

[16]Kruatrachue B， Lewis T. Grain Size Determination for Parallel Processing[J]. IEEE Software， 1988， 5（1）： 23-32.

[17]Mckellips A L， Verdu? S. Maximin Performance of Binary- Input Channels with Uncertain Noise Distributions[J]. Information Theory IEEE Transactions on， 1998， 44（3）： 947-972.

[18]Bansal S， Kumar P， Singh K. Dealing with heterogeneity through limited duplication for scheduling precedence constrained task graphs[J]. Journal of Parallel & Distributed Computing， 2005， 65（4）： 479-491.

[19]Agarwal N， Gupta C， Khare A. Task scheduling through limited duplication with processor utilization in grid computing system[C]// IEEE International Conference on Parallel Distributed and Grid Computing. 2012： 921-926.

[20]Tang X， Li K， Liao G， et al. List scheduling with duplication for heterogeneous computing systems[J]. Journal of Parallel & Distributed Computing， 2010， 70（4）： 323-329.

[21]Ali J. Optimal task partitioning strategy with duplication （OTPSD） in parallel computing environments[J]. International Journal of Computers & Distributed Systems， 2013， 4（1）： 7-15.