基于蟻群算法的并行任務(wù)分配與調(diào)度

李艷生， 汪自云

(1.湖北師范學(xué)院 省級(jí)電工電子實(shí)驗(yàn)教學(xué)示范中心，湖北 黃石 435002;2.湖北師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 黃石 435002)

0 引 言

現(xiàn)在正處于多核技術(shù)、網(wǎng)格計(jì)算、云計(jì)算的研究與發(fā)展階段，其中任務(wù)的分配與調(diào)度是這些技術(shù)共同的核心問(wèn)題。任務(wù)分配與調(diào)度是把一個(gè)計(jì)算任務(wù)分解成若干個(gè)彼此聯(lián)系的子任務(wù)，使得這些子任務(wù)盡可能地并行執(zhí)行， 從而使得所給定的計(jì)算任務(wù)能在最短的時(shí)間內(nèi)完成。在通常的情況下，子任務(wù)的數(shù)量多于處理機(jī)的數(shù)量，在提高處理機(jī)的使用效率的同時(shí)使計(jì)算任務(wù)在盡可能短的時(shí)間內(nèi)完成。高效的任務(wù)調(diào)度與分配是這些技術(shù)獲取高性能的關(guān)鍵因素之一，研究任務(wù)分配與調(diào)度的最優(yōu)化解對(duì)這些技術(shù)發(fā)展具有十分重大的意義。

任務(wù)分配與調(diào)度問(wèn)題已經(jīng)被證明是一個(gè)NP完全問(wèn)題[1]。近年來(lái)出現(xiàn)一些用啟發(fā)式算法(如模擬退火、遺傳算法、蟻群算法)來(lái)解決NP完全問(wèn)題，其中蟻群算法由于具有正反饋顯示出解決NP完全問(wèn)題的優(yōu)勢(shì)。用蟻群算法求解旅行商問(wèn)題TSP(Traveling Salesman Problem)[2]、分配問(wèn)題QAP(Quadratic Assignment Problem)[3]、調(diào)度問(wèn)題JSP(Job-Shop Scheduling Problem)[4]等都取得較好的解。文[5]用蟻群算法求解n個(gè)任務(wù)分配到n個(gè)處理器的問(wèn)題(一對(duì)一的關(guān)系)。文[6]用蟻群算法求解n個(gè)任務(wù)分配到m個(gè)處理器的問(wèn)題(多對(duì)多的關(guān)系)，但沒(méi)有考慮到任務(wù)之間約束關(guān)系。文[7]用蟻群算法求解n個(gè)任務(wù)分配到m個(gè)處理器的問(wèn)題(多對(duì)多的關(guān)系)，雖然提到了任務(wù)之間的約束關(guān)系，但沒(méi)有指出如何滿足在約束關(guān)系條件下求解過(guò)程。針對(duì)如何在滿足任務(wù)約束關(guān)系的條件下用蟻群算法求解任務(wù)分配與調(diào)度問(wèn)題，本文首先對(duì)任務(wù)的分配與調(diào)度問(wèn)題建立數(shù)學(xué)模型，然后在滿足子任務(wù)之間的約束關(guān)系的條件下用蟻群算法求出最優(yōu)解，最后把用蟻群算法與文[8][9]遺傳算法的最優(yōu)解進(jìn)行對(duì)比。通過(guò)仿真實(shí)驗(yàn)表明，蟻群算法比遺傳算法有較高的解的質(zhì)量，但蟻群算法的求解速度要慢于遺傳算法。

1 模型定義

1.1 問(wèn)題模型

在并行計(jì)算中，任務(wù)分配與調(diào)度的數(shù)學(xué)模型可描述如下：一個(gè)計(jì)算任務(wù)T可分為n個(gè)子任務(wù)，由m個(gè)處理機(jī)進(jìn)行處理。首先，假設(shè)每個(gè)子任務(wù)之間的依賴關(guān)系已知，一個(gè)任務(wù)依賴關(guān)系圖通常是有向無(wú)回路圖(DAG )，其 DAG圖如圖1所示。

圖1 任務(wù)優(yōu)先DAG圖

圖1中每個(gè)節(jié)點(diǎn)代表子任務(wù)，箭頭代表前驅(qū)與后繼的關(guān)系，即子任務(wù)Tj在它任一前驅(qū)子任務(wù)Ti完成之前而不能開(kāi)始，其中T1是最早開(kāi)始的子任務(wù)，Tn是最晚完成的子任務(wù)。

再次，假設(shè)每個(gè)子任務(wù)在m個(gè)節(jié)點(diǎn)的處理時(shí)間、節(jié)點(diǎn)之間的通信開(kāi)銷及有依賴關(guān)系的子任務(wù)之間的數(shù)據(jù)傳輸量已知。則異構(gòu)計(jì)算中并行程序可抽象為一個(gè)五元組

F=(V，E，N，T，C)

(1)

其中：

V是任務(wù)優(yōu)先DAG圖中節(jié)點(diǎn)集合，子任務(wù)數(shù)為n個(gè)；

E是任務(wù)優(yōu)先DAG 圖中有向邊Eij集合，邊Eij(Vi，Vj) 表示子任務(wù)Vj要在子任務(wù)Vi完成之后才能開(kāi)始；

N是異構(gòu)環(huán)境中可用的處理節(jié)點(diǎn)集合，處理機(jī)數(shù)為m個(gè)；

T是每個(gè)子任務(wù)執(zhí)行時(shí)間開(kāi)銷集合，Tik表示子任務(wù)Ti在處理機(jī)Nk上的執(zhí)行時(shí)間；

C是任務(wù)優(yōu)先DAG圖有向邊的通信開(kāi)銷集合，Cij表示子任務(wù)Vi與Vj通過(guò)有向邊Eij的通信成本，當(dāng)Vi和Vj分配在同一處理機(jī)上Cij=0時(shí) 。

要達(dá)到的目標(biāo)是， 在滿足任務(wù)處理時(shí)序和資源限制的條件下尋找一種合理的分配與調(diào)度策略， 將n個(gè)子任務(wù)指派到m個(gè)處理機(jī)上， 合理調(diào)度各個(gè)子任務(wù)的執(zhí)行順序， 使得各個(gè)任務(wù)在滿足依賴關(guān)系圖的約束下， 整個(gè)大任務(wù)的完成時(shí)間最短。

假設(shè)S為某個(gè)DAG 圖的一個(gè)分配與調(diào)度方案，Ts(Nk)表示在分配與調(diào)度S下，當(dāng)處理機(jī)Nk完成所有指派到本處理機(jī)上子任務(wù)所要花費(fèi)的總時(shí)間。設(shè)T(S)表示整個(gè)分配與調(diào)度S所要花費(fèi)的總時(shí)間，則有T(S)=?k(Max(Ts(Nk)))，(0≤k≤m-1).分配與調(diào)度的目標(biāo)就是尋找T(S) 最小的分配與調(diào)度方案S，即?S(Min(T(S))) .

1.2 解模型

本文采用一種排列方法[8]來(lái)表示DAG任務(wù)圖的分配與調(diào)度的解，每個(gè)處理機(jī)上所有任務(wù)排成一個(gè)列表， 排列的順序代表了各個(gè)子任務(wù)的先后執(zhí)行順序。對(duì)DAG的一個(gè)分配調(diào)度S，記S=(L0，L1，L2，…，Lm-1)其中Li=(Ti0，Ti1，Ti2，…，Ti(k-1))分別表示分配到處理機(jī)Ni上的k個(gè)子任務(wù)序列。

為了證明編碼的合法性，引入DAG 圖高度值H(Ti) ：

(2)

其中Pre(Ti)表示Ti的前驅(qū)集合，Φ表示空集。根據(jù)高度值H(Ti) ， 稱一個(gè)調(diào)度是合法分配與調(diào)度， 是指該調(diào)度中所有列表的任務(wù)是按高度值的升序排列的，即H(Ti0≤H(Ti1≤…≤H(Tik).

2 算法設(shè)計(jì)

2.1 基本原理

蟻群算法是由Dorigo M.教授在1991年首先提出的，其基本思想是螞蟻個(gè)體之間通過(guò)一種稱之為信息素的物質(zhì)進(jìn)行信息交互， 從而能相互協(xié)作， 完成最短路徑的尋址。螞蟻會(huì)在走過(guò)路徑上分泌信息素，路徑越短，單位時(shí)間里經(jīng)過(guò)此路徑的螞蟻越多，分泌的信息素也會(huì)越多，就會(huì)吸引更多的螞蟻選擇此路徑，從而找出最短路徑。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。

設(shè)有n個(gè)子任務(wù)，m個(gè)處理器，l只螞蟻，則第k只螞蟻把子任務(wù)i分配到處理器j的概率：

(3)

其中τ(i，j) 表示螞蟻k把子任務(wù)i分配到處理器j時(shí)產(chǎn)生的信息素，η(i，j)表示啟發(fā)式信息，α(0≤α≤1)，β(0≤β≤1) 體現(xiàn)信息素和啟發(fā)式信息對(duì)螞蟻選路的權(quán)重，Ak(i)表示螞蟻k分配子任務(wù)i時(shí)可以選擇的處理器集合，向處理器分配任務(wù)的原則是每個(gè)處理器達(dá)到平均負(fù)載時(shí)就不能再分配其它任務(wù)。

(4)

其中T(i，j)表示子任務(wù)i在處理器j上執(zhí)行時(shí)間。

τ(i，j)=(1-ρ)*τ(i，j)+△τ(i，j)

(5)

(6)

其中ρ(0<ρ<1) 表示信息素的揮發(fā)系數(shù)，τ(i，j)初始化值為處理器平均執(zhí)行時(shí)間的倒數(shù)，△τk(i，j) 表示螞蟻k在一次循環(huán)中把子任務(wù)i分配到合法的處理器j時(shí)產(chǎn)生的信息素， △τ(i，j)表示所有螞蟻在一次循環(huán)中把子任務(wù)i分配到合法的處理器j時(shí)產(chǎn)生的信息素。

(7)

其中Q是常數(shù)，Zk表示螞蟻k在本次循環(huán)中路徑長(zhǎng)度。

2.2 算法實(shí)現(xiàn)

要使解滿足子任務(wù)間的約束關(guān)系，則分配到各個(gè)處理器的子任務(wù)列表應(yīng)按DAG高度值H升序排列。首先把子任務(wù)按DAG高度值H升序排列一個(gè)表，螞蟻在尋路時(shí)按表順序把每個(gè)子任務(wù)分配到處理器，這樣的解即是合法解。初次循環(huán)時(shí)螞蟻系統(tǒng)隨機(jī)地把子任務(wù) 分配到合法的處理器j，然后螞蟻根據(jù)(3)把子任務(wù)i分配到合法的處理器j.每只螞蟻經(jīng)過(guò)n步循環(huán)一次產(chǎn)生一個(gè)合法解。其具體算法描述如下：

1)讀入任務(wù)優(yōu)先DAG 圖，并根據(jù)公式(2)計(jì)算每個(gè)節(jié)點(diǎn)的高度值H；

2)設(shè)置常數(shù)α，β，ρ，Q，Nc，其中Nc表示循環(huán)次數(shù)；

3)根據(jù)DAG圖把n個(gè)子任務(wù)按高度值H的升序排成一個(gè)表；

4)根據(jù)公式(4)設(shè)置啟發(fā)式信息η和初始化信息素τ；

5)判斷循環(huán)次數(shù)否已達(dá)到Nc或多次循環(huán)解無(wú)變化，如果是，轉(zhuǎn)14，否則轉(zhuǎn)6繼續(xù)；

6)把m個(gè)處理器加入Ak(i)集合；

7)判斷本次循環(huán)螞蟻k是否已經(jīng)過(guò)了n步，如果是，轉(zhuǎn)13，否則轉(zhuǎn)8；

8)根據(jù)處理器負(fù)載設(shè)置Ak(i) 集合；

9)判斷是否是第一次循環(huán)，如果是，轉(zhuǎn)10，否則轉(zhuǎn)11；

10)螞蟻k隨機(jī)地把子任務(wù)i分配到合法的處理器j；

11)根據(jù)公式(3)計(jì)算pk(i，j) ，再根據(jù)pk(i，j)選擇處理器j；

12)根據(jù)公式(5)(6)(7)更新信息素 ；

13)判斷是否所有螞蟻都到達(dá)終點(diǎn)，如果是，轉(zhuǎn)5進(jìn)入下一次循環(huán)，否則轉(zhuǎn)6處理下一只螞蟻；

14)輸出最優(yōu)化解。

3 實(shí)驗(yàn)分析

根據(jù)建立的模型和設(shè)計(jì)的蟻群算法，進(jìn)行相應(yīng)的仿真實(shí)驗(yàn)。軟件開(kāi)發(fā)環(huán)境采用Java6開(kāi)發(fā)，硬件運(yùn)行環(huán)境為P3 866MHz/192MB.實(shí)驗(yàn)參數(shù)設(shè)置如下：α=0.8，β=0.2，ρ=0.01，Q=200，Nc=100，螞蟻數(shù)量l為100只。DAG 圖隨機(jī)生成的，每個(gè)結(jié)點(diǎn)有1～ 4個(gè)后繼，估計(jì)運(yùn)行時(shí)間為1～ 20間的隨機(jī)數(shù)， 各處理機(jī)間數(shù)據(jù)傳輸延時(shí)也是隨機(jī)生成的。其實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 幾種算法的實(shí)驗(yàn)結(jié)果

從表1實(shí)驗(yàn)結(jié)果可以看出，本文用蟻群算法求出的任務(wù)分配與調(diào)度最優(yōu)化解的質(zhì)量遠(yuǎn)高于遺傳算法，但蟻群算法求解速度慢于遺傳算法。可見(jiàn)蟻群算法在求解NP完全問(wèn)題中具有較大的優(yōu)勢(shì)，但求解速度有待改進(jìn)。

4 結(jié) 語(yǔ)

蟻群算法雖然出現(xiàn)的時(shí)間并不長(zhǎng)，用蟻群算法解決NP完全問(wèn)題在解的質(zhì)量方面具有明顯優(yōu)勢(shì)。但尚需解決所存在的求解速度慢問(wèn)題，如果考慮引入分布蟻群尋徑策略(多蟻群尋徑)，在面向一類NP完全問(wèn)題求解過(guò)程實(shí)現(xiàn)多算法協(xié)同，將有待進(jìn)一步研究。

[1]Correa R C， FerreiraA， Rebreyend P. Scheduling Multiprocessor Tasks with Genetic Algorithms[J]. IEEE Transactions on Parallel and Distributed Systems， 1999， 10(8): 825～837.

[2]Dorigo M，Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactionson Evolutionary Computation，1997，1(1):53～66.

[3]Gambardella L M，Taillard E，Dorigo M.Ant colonies for the quadratic assignment problem[J].Journal of the Operational Research Society， 1999，50:167～176.

[4]Colorni A，Dorigo M，Maniezzo V.Ant system for job-shop scheduling[J].Belgian Journal of Operations Research，Statistics and ComputerScience，1994，34(1):39～54.

[5]楊 冬，王正歐. 改進(jìn)的螞蟻算法求解任務(wù)分配問(wèn)題[J]. 天津大學(xué)學(xué)報(bào)， 2004， 37(4): 373～276.

[6]王靈霞，張遠(yuǎn)平，吳佩莉.蟻群算法求解分布式系統(tǒng)任務(wù)分配問(wèn)題[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2008，29(6):1472～1474.

[7]張 勇，張曦煌.改進(jìn)型蟻群算法的多處理機(jī)任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(35):75:76.

[8]Edwin S H，Hou N An sari.Genetic Algorithm for Multiprocessor Scheduling[J]. IEEE Trans on Parallel and Distributed Systems，1994，5(2):113～120.

[9]鐘求喜， 謝 濤， 陳火旺. 基于遺傳算法的任務(wù)分配與調(diào)度[J].計(jì)算機(jī)研究與發(fā)展，2000， 37(10): 1197～1203.