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

摘 ?要： 提出了一種帶任務(wù)重復(fù)的任務(wù)劃分策略算法D-ITPS（Improved task partitioning Strategy with duplication），該算法首先將DAG圖中的一些滿足歸并條件的任務(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)。基于GA的算法，有的通過(guò)隨機(jī)選擇來(lái)選擇初始種群，有的在工作流的同一階段用優(yōu)化方法將任務(wù)排序，比如最先完成的任務(wù)，最小依賴的任務(wù)，最大依賴的任務(wù)，其中一些用具有至多兩個(gè)輸出節(jié)點(diǎn)的簡(jiǎn)單圖來(lái)表示。……