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

李艷生， 汪自云

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

0 引 言

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

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

1 模型定義

1.1 問題模型

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

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

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

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

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

(1)

其中：

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

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

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

T是每個子任務執(zhí)行時間開銷集合，Tik表示子任務Ti在處理機Nk上的執(zhí)行時間；

C是任務優(yōu)先DAG圖有向邊的通信開銷集合，Cij表示子任務Vi與Vj通過有向邊Eij的通信成本，當Vi和Vj分配在同一處理機上Cij=0時 。

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

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

1.2 解模型

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

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

(2)

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

2 算法設計

2.1 基本原理

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

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

(3)

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

(4)

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

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

(5)

(6)

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

(7)

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

2.2 算法實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

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

表1 幾種算法的實驗結(jié)果

從表1實驗結(jié)果可以看出，本文用蟻群算法求出的任務分配與調(diào)度最優(yōu)化解的質(zhì)量遠高于遺傳算法，但蟻群算法求解速度慢于遺傳算法?？梢娤伻核惴ㄔ谇蠼釴P完全問題中具有較大的優(yōu)勢，但求解速度有待改進。

4 結(jié) 語

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

[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]. 天津大學學報， 2004， 37(4): 373～276.

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

[7]張 勇，張曦煌.改進型蟻群算法的多處理機任務調(diào)度研究[J].計算機工程與應用，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]鐘求喜， 謝 濤， 陳火旺. 基于遺傳算法的任務分配與調(diào)度[J].計算機研究與發(fā)展，2000， 37(10): 1197～1203.