云計(jì)算中一種帶任務(wù)重復(fù)機(jī)制的任務(wù)劃分策略

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

關(guān)鍵詞： 云計(jì)算;復(fù)雜DAG圖;調(diào)度算法;任務(wù)重復(fù);調(diào)度長(zhǎng)度

中圖分類(lèi)號(hào)： TP30 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.12.002

本文著錄格式：張銀娟. 云計(jì)算中一種帶任務(wù)重復(fù)機(jī)制的任務(wù)劃分策略[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 ?引言

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

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

1 ?D-ITPS算法

1.1 ?D-ITPS的簡(jiǎn)單抽象模型

圖1給出了本文提出算法的簡(jiǎn)單抽象模型。

圖1 ?任務(wù)抽象模型

Fig.1 ?Task abstract model

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

1.2 ?編碼及算法

1.2.1 ?編碼

在遺傳算法中，每個(gè)染色體用來(lái)表示問(wèn)題的一個(gè)解，染色體的編碼方式有很多，采用何種方式進(jìn)行編碼則有當(dāng)前問(wèn)題的需求來(lái)決定。該算法中采用如圖2的編碼方式。

V1 V3 V4 V2 V5 ···· V9

P2 P9 P3 P1 P8 ···· P25

圖2 ?單個(gè)染色體的簡(jiǎn)單編碼

Fig.2 ?Simple coding of a single chromosome

1.2.2 ?任務(wù)歸并階段

本文提出的算法首先對(duì)DAG圖中的一些任務(wù)進(jìn)行歸并，歸并后將歸并的任務(wù)看成一個(gè)大任務(wù)，其歸并后的大任務(wù)的計(jì)算時(shí)間和存儲(chǔ)空間均采用歸并的小任務(wù)的計(jì)算時(shí)間和存儲(chǔ)空間求和方式來(lái)計(jì)算。如公式（1）（2）所示。

若任務(wù)與任務(wù)滿(mǎn)足任務(wù)歸并條件，其中任務(wù)在各個(gè)處理器上的計(jì)算開(kāi)銷(xiāo)為 ，存儲(chǔ)開(kāi)銷(xiāo)為，任務(wù)在各個(gè)處理器上的計(jì)算開(kāi)銷(xiāo)為，存儲(chǔ)開(kāi)銷(xiāo)為，任務(wù)合并后形成新任務(wù)，其計(jì)算開(kāi)銷(xiāo)及存儲(chǔ)開(kāi)銷(xiāo)為：

（1）

（2）

任務(wù)歸并后其實(shí)質(zhì)還是兩個(gè)任務(wù)，僅僅是將兩個(gè)任務(wù)綁定，調(diào)度時(shí)調(diào)度到同一個(gè)處理器上。那如何才可以將任務(wù)進(jìn)行歸并？需同時(shí)滿(mǎn)足如下兩個(gè)條件：

（1）當(dāng)前任務(wù)有且僅有一個(gè)直接父任務(wù)并且該父任務(wù)也有且僅有一個(gè)直接子任務(wù)，即是該任務(wù);

（2）該任務(wù)與其直接父任務(wù)間的通信開(kāi)銷(xiāo)大于等于其在不同的處理器上的最大計(jì)算開(kāi)銷(xiāo)。

滿(mǎn)足上述條，將子任務(wù)歸并到父任務(wù)，將其看成一個(gè)大的任務(wù)，調(diào)度時(shí)調(diào)度到同一處理器上。

歸并算法如算法1.1所示。

算法1.1 ?歸并算法

Step 1： for DAG圖中所有任務(wù)do

Step 2： ? ?if（（當(dāng)前任務(wù)有且僅有一個(gè)父任務(wù)，即 ）&&（是父節(jié)點(diǎn)的唯一子任務(wù)，即））then

Step 3： ? ? ? ? ? ? if then

Step 4： ? ? ? ? ? ? ? ? ? 將任務(wù)歸并到父任務(wù)，歸并后的任務(wù)為

end if

end if

end for

1.2.3 ?任務(wù)劃分策略

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

任務(wù)劃分策略主要根據(jù)任務(wù)的通信時(shí)間及任務(wù)間的約束關(guān)系進(jìn)行劃分初步的任務(wù)包。首先將任務(wù)按照其通信時(shí)間的大小降序排列形成隊(duì)列，將排列在一起且滿(mǎn)足拓?fù)漤樞虻娜蝿?wù)劃分為一個(gè)包。劃分算法如算法1.2所示，首先將隊(duì)列中符合拓?fù)漤樞虻耐ㄐ艜r(shí)間小的任務(wù)劃分到通信時(shí)間大的任務(wù)包中，通信時(shí)間用任務(wù)輸出數(shù)據(jù)的大小除以資源間的帶寬，對(duì)于出口節(jié)點(diǎn)，該值為0。如公式（3）所示。

（3）

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

算法1.2 ?劃分策略

Step 1：計(jì)算所有任務(wù)的通信開(kāi)銷(xiāo)值comm_cost

Step 2： 按照comm_cost值將任務(wù)降序排列形成隊(duì)列

Step 3：for隊(duì)列中的每個(gè)任務(wù)do

Step 4： ? if（（ ）&&（與有約束關(guān)系） then

Step 5： ? ? ? ?合并任務(wù)

end if

end for

任務(wù)分為包后，定義包的幾個(gè)參數(shù)：

定義1.1 ?將DAG圖中的任務(wù)分為包后，在每個(gè)包中，類(lèi)比于DAG圖中的任務(wù)將包定義為四元組形式：

（1）表示任務(wù)節(jié)點(diǎn)的集合;

（2）是邊的集合;

（3）與表示不同的兩個(gè)包。

定義1.2 ?任務(wù)包與任務(wù)包之間有多條邊相連，包間的通信開(kāi)銷(xiāo)為其所有在包中節(jié)點(diǎn)間的通信時(shí)間的均值，計(jì)算公式如下：

（4）

表示連接包邊的權(quán)值之和，即所有在包中任務(wù)間的通信時(shí)間之和，表示連接兩包的邊的個(gè)數(shù)。

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

（5）

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

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

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

Step 1： 計(jì)算當(dāng)前所有包中任務(wù)的個(gè)數(shù)，按照升序進(jìn)行排列

Step 2：while所有未被分包的任務(wù)do

Step 3： ? ? ?取包中任務(wù)

Step 4： ? ? ?取包隊(duì)列中的第一個(gè)包，找出通信開(kāi)銷(xiāo)最大的任務(wù)

Step 5： ? ? ?if ?then

Step 6： ? ? ? ? ?標(biāo)記

Step 7： ? ? ? ? ?更新包的參數(shù)

Step 8： ? ? ? else

Step 9： ? ? ? ? 查找的MIIP任務(wù)

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

Step 11： ? ? ? ? ? ?標(biāo)記

Step 12： ? ? ? ? ? ?更新包的參數(shù)

Step 13： ? ? ? ? ?else

Step 14： ? ? ? ? ? ? 標(biāo)記

Step 15： ? ? ? ? ? ? 更新包的參數(shù)

end if

end if

Step 16： ? ?按照包中任務(wù)個(gè)數(shù)進(jìn)行升序排序

end while

在分包的過(guò)程中，要注意并行性及通信開(kāi)銷(xiāo)的平衡，如定理1.1。不能因?yàn)轭櫦巴ㄐ砰_(kāi)銷(xiāo)將大量的任務(wù)放到同一包中，這樣包中的任務(wù)會(huì)急劇增多，最壞的情況是所有任務(wù)集中到一個(gè)處理器上執(zhí)行，這樣就不能體現(xiàn)多處理器的優(yōu)點(diǎn)，即不能兼具并行性的優(yōu)點(diǎn)。當(dāng)然由于處理器個(gè)數(shù)的有限性，不能將任務(wù)盡可能分為多個(gè)包，導(dǎo)致每個(gè)包中的任務(wù)數(shù)量極少，這樣會(huì)造成資源的浪費(fèi)。

定理1.1 ?設(shè)是DAG圖中的任務(wù)，表示任務(wù)間的通信開(kāi)銷(xiāo)，用邊上權(quán)值表示。最優(yōu)的調(diào)度策略是根據(jù)Max-Min（最大并行性，最小通信時(shí)間）權(quán)衡。

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

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

（6）

（7）

在按照任務(wù)劃分策略將任務(wù)劃分為包后，將包分配到資源上使用Max-Min算法[17]來(lái)實(shí)現(xiàn)。Max-Min算法首先計(jì)算任務(wù)包在每個(gè)處理器上的完成時(shí)間，按照各個(gè)包的完成時(shí)間將包進(jìn)行降序排列，將虛擬機(jī)列表按照計(jì)算能力進(jìn)行降序排列，然后按照包的排列順序及虛擬機(jī)列表的排列順序?qū)⒏鱾€(gè)包分配到處理器上。算法實(shí)現(xiàn)如算法1.4所示：

算法1.4 ?Max-Min算法

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

Step 2：對(duì)于任務(wù)包隊(duì)列中所有包，求出映射到所有處理器上的最早完成時(shí)間

Step 3：找出有最大最早完成時(shí)間的任務(wù)包并找出對(duì)應(yīng)的處理器

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

Step 5：更新處理器的預(yù)期就緒時(shí)間

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

Step 7：按照?qǐng)D2中的編碼方式輸出調(diào)度序列

在將任務(wù)按照?qǐng)D2的編碼方式編碼后，繼續(xù)執(zhí)行算法1.5直至求出最優(yōu)的調(diào)度方案。

1.2.4 ?任務(wù)重復(fù)階段

本階段中任務(wù)對(duì)算法1.4中輸出的調(diào)度序列進(jìn)行處理，在調(diào)度過(guò)程中，如果存在空閑時(shí)間隙，將利用這些空閑時(shí)間隙來(lái)執(zhí)行重復(fù)任務(wù)和候選節(jié)點(diǎn)，以期將任務(wù)總完成時(shí)間提前。

當(dāng)一個(gè)任務(wù)調(diào)度到處理器上時(shí)，通常將此時(shí)間定義為任務(wù)的到達(dá)時(shí)間。但是任務(wù)的實(shí)際開(kāi)始時(shí)間并不是任務(wù)的到達(dá)時(shí)間，還需考慮處理器是否空閑以及其所有前驅(qū)任務(wù)的數(shù)據(jù)均傳輸?shù)教幚砥魃稀Ｔ跍?zhǔn)備執(zhí)行任務(wù)前需等待其所有直接前驅(qū)任務(wù)將數(shù)據(jù)傳達(dá)以此來(lái)遵守DAG圖優(yōu)先關(guān)系約束。

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

定義1.4 ?[18]給出一組任務(wù)將其調(diào)度到處理器上，存在空閑時(shí)間隙（在任務(wù)和之間）滿(mǎn)足如下條件即可容納任務(wù)，

（8）

其中，和分別表示時(shí)間隙的開(kāi)始時(shí)間和結(jié)束時(shí)間。表示任務(wù)在當(dāng)前處理器上的執(zhí)行時(shí)間。表示任務(wù)在處理器上的開(kāi)始執(zhí)行時(shí)間。假設(shè)沒(méi)有合適的空閑時(shí)間隙，任務(wù)調(diào)度到處理器上，其開(kāi)始時(shí)間決定于處理器的空閑時(shí)間，如圖3所示。

定義1.5 ?（MIIP[19]，Most ?Important immediate parent）任務(wù)的所有直接父任務(wù)中最晚到達(dá)的任務(wù)稱(chēng)為最重要的直接父任務(wù)，用符號(hào)表示，因?yàn)樗璧K了任務(wù)的開(kāi)始時(shí)間。

所有任務(wù)的MIIP任務(wù)數(shù)據(jù)到達(dá)時(shí)間計(jì)算公式如下：

（9）

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

（10）

圖3 ?空閑時(shí)間隙與重復(fù)任務(wù)

Fig.3 ?Idel gap and repetitive tasks

由于受父任務(wù)的數(shù)據(jù)到達(dá)時(shí)間影響，任務(wù)的開(kāi)始時(shí)間受到一定限制。前驅(qū)任務(wù)的數(shù)據(jù)到達(dá)子任務(wù)所在處理器有兩種途徑：

（1）在合適的空閑時(shí)間隙重復(fù)重要直接前驅(qū)任務(wù)，減少任務(wù)之間數(shù)據(jù)的傳輸開(kāi)銷(xiāo);

（2）將子任務(wù)盡可能調(diào)度到直接父任務(wù)所在的處理器，從而避免通信開(kāi)銷(xiāo)。

第二種方法顯然會(huì)導(dǎo)致同一處理器上的任務(wù)過(guò)多，負(fù)載過(guò)重，從而處理器的計(jì)算能力下降，導(dǎo)致任務(wù)的總完成時(shí)間并不能提前。

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

（1）優(yōu)先重復(fù)直接父節(jié)點(diǎn)中出度最大的任務(wù)。重復(fù)出度最大的父任務(wù)是因?yàn)楦溉蝿?wù)的出度大，它影響最多的子任務(wù)的開(kāi)始時(shí)間，將出度最大的父任務(wù)重復(fù)執(zhí)行，則不僅僅可以提前當(dāng)前子任務(wù)的開(kāi)始時(shí)間，其余的該父任務(wù)的子任務(wù)的開(kāi)始時(shí)間也會(huì)相應(yīng)的提前。

（2）重復(fù)直接父節(jié)點(diǎn)中的MIIP任務(wù)。重復(fù)MIIP任務(wù)是因?yàn)镸IIP任務(wù)的完成時(shí)間限制當(dāng)前任務(wù)的開(kāi)始時(shí)間，將其在子任務(wù)所在的處理器上重復(fù)執(zhí)行，則當(dāng)前任務(wù)的開(kāi)始時(shí)間提前。

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

當(dāng)前處理器上任務(wù)執(zhí)行完成時(shí)間和其直接前驅(qū)的數(shù)據(jù)到達(dá)時(shí)間，計(jì)算公式如（11）：

（11）

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

任務(wù)的完成時(shí)間計(jì)算公式如下：

（12）

算法的總完成時(shí)間為：

（13）

查找并重復(fù)任務(wù)的算法表示如算法1.5所示。

算法1.5

Begin

Repeat

{

Step 1： ? ←查找任務(wù)在處理器上的開(kāi)始時(shí)間

Step 2：

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

Step 4： ←任務(wù)的MIIP任務(wù)

Step 5： if（和均不存在或均已調(diào)度到當(dāng)前處理器上）

返回值

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

←計(jì)算任務(wù)在處理器上的完成時(shí)間

←計(jì)算任務(wù)在處理器上的完成時(shí)間

if

在處理器上重復(fù)任務(wù)

else if

在處理器上重復(fù)任務(wù)

else

返回

}

else

返回

}

End

表1 ?參數(shù)表

Tab.1 ?Parameters

類(lèi)型 參數(shù) 取值范圍

資源參數(shù) 資源個(gè)數(shù) 30

資源速度 500-1000（MIPS）

資源間帶寬 10-100（mps）

CCR值 0.25

任務(wù)參數(shù) 任務(wù)個(gè)數(shù) 30-100

任務(wù)長(zhǎng)度 12-72（× MI）

任務(wù)失敗率 -

算法參數(shù) 種群大小 20

交叉率 0.5

變異率 0.5

精英選擇率 0.75

任務(wù)迭代次數(shù) 20

2 ?D-ITPS算法仿真實(shí)驗(yàn)

2.1 ?仿真環(huán)境

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

2.2 ?仿真結(jié)果與分析

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

圖4 ?任務(wù)的NSL性能分析

Fig.4 ?NSL performance analysis of tasks

圖5中隨著任務(wù)數(shù)量的增長(zhǎng)，平均NSL值會(huì)有所變化。在任務(wù)數(shù)在150-300時(shí)，提出的算法的平均NSL值小于另兩種算法。

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

圖5 ?任務(wù)的平均NSL性能分析

Fig.5 ?Average NSL performance analysis of tasks

圖6 ?任務(wù)的Efficiency性能分析

Fig.6 ?Efficiency performance analysis of tasks

3 ?總結(jié)與展望

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

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

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

（1）算法中均提出了任務(wù)的調(diào)度模型，但是與真實(shí)的云計(jì)算模型相比仍過(guò)于簡(jiǎn)單，存在一定的差距。

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

（3）任務(wù)劃分策略中，劃分任務(wù)包時(shí)并行性與顆粒大小的衡量采用閾值來(lái)定義，閾值的大小取值并不能保證最好地權(quán)衡并行性與包的粒度大小。

針對(duì)以上問(wèn)題未來(lái)將進(jìn)一步研究

（1）對(duì)算法中提出的任務(wù)調(diào)度模型進(jìn)一步完善，對(duì)任務(wù)及虛擬機(jī)進(jìn)行建模，在調(diào)度任務(wù)時(shí)，按照實(shí)際情況考慮將任務(wù)調(diào)度到不同性能不同狀態(tài)的虛擬機(jī)上，且虛擬機(jī)的個(gè)數(shù)能夠進(jìn)行動(dòng)態(tài)調(diào)整。

（2）D-ITPS算法中可以根據(jù)當(dāng)前調(diào)度到處理器上的任務(wù)與以后要調(diào)度到處理器上的任務(wù)決定要重復(fù)任務(wù)，不需要在重復(fù)任務(wù)后查找刪除對(duì)總完成時(shí)間無(wú)影響的重復(fù)任務(wù)。

（3）任務(wù)劃分策略中根據(jù)處理器的性能與任務(wù)的參數(shù)進(jìn)行并行性與任務(wù)包粒度的權(quán)衡，而任務(wù)的個(gè)數(shù)僅為其中的參數(shù)而不是唯一決定的參數(shù)。

參考文獻(xiàn)

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

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

[3]丁順， 陳世平. 云計(jì)算中基于包簇映射的多目標(biāo)蟻群資源分配算法[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)任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)應(yīng)用研究， 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]武濤. 基于云計(jì)算的并行動(dòng)態(tài)路徑搜索算法研究[J]. 軟件， 2015， 36（4）： 128-132.

[14]趙辰吟， 姚文斌. 基于一種改進(jìn)免疫算法的云計(jì)算任務(wù)調(diào)度策略研究[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.