基于粒子群優(yōu)化算法的異構(gòu)多處理器任務(wù)調(diào)度

李靜梅，張 博

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001)

0 引言

多處理器系統(tǒng)由多個(gè)具有不同計(jì)算性能的處理器構(gòu)成。如何將不同的任務(wù)分配到不同計(jì)算能力的處理器上進(jìn)行處理便成為能否充分發(fā)揮多處理器性能的首要問題，這也是任務(wù)調(diào)度策略的研究成為多處理器技術(shù)研究熱點(diǎn)問題的原因。但是，目前比較成熟的任務(wù)調(diào)度算法研究大多基于同構(gòu)環(huán)境［1-2］，任務(wù)在同構(gòu)多處理器中每個(gè)處理器上的執(zhí)行時(shí)間相同，在任務(wù)調(diào)度時(shí)只需要將任務(wù)調(diào)度到上一任務(wù)完成時(shí)間最早的處理器上即可，而異構(gòu)多處理器上各處理器的處理能力各不相同，在分配任務(wù)時(shí)還要考慮任務(wù)在不同處理器上的執(zhí)行效率和處理器整體的執(zhí)行時(shí)間。因此，異構(gòu)多處理器上的任務(wù)調(diào)度問題相對更加復(fù)雜，采用同構(gòu)多處理器任務(wù)調(diào)度算法不能充分發(fā)揮每一個(gè)處理器的性能和整體的并行性。

任務(wù)調(diào)度已被證明是NP完全問題［3］，不能在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)找到最優(yōu)解。為求解此類NP完全問題，一些啟發(fā)式算法如遺傳算法 (genetic algorithm，GA)等，開始被應(yīng)用到任務(wù)調(diào)度研究［4-7］。

基于上述背景，本文提出了一種基于粒子群優(yōu)化 (particle swarm optimization，PSO)的任務(wù)調(diào)度算法——PSOASA算法，并在matlab仿真平臺上與異構(gòu)多處理器任務(wù)調(diào)度研究較多的遺傳算法進(jìn)行了性能比較測試，證明其收斂速度和求解精度均優(yōu)于現(xiàn)有算法。

1 任務(wù)調(diào)度問題描述

為了方便描述問題，定義多處理器系統(tǒng)包含m個(gè)不同的處理器，一個(gè)應(yīng)用程序被劃分成n個(gè)子任務(wù)并且子任務(wù)之間相互獨(dú)立，定義 T={T1，T2，…，Tn} (i=1，2，3，…，n)為n個(gè)獨(dú)立任務(wù)序列;P={P1，P2，…，Pm}(j=1，2，3，…，m)為m個(gè)處理器序列。當(dāng)n m時(shí)，即待執(zhí)行任務(wù)數(shù)小于處理器的數(shù)目，可以根據(jù)先到先服務(wù)規(guī)則分配任務(wù)到指定處理器上執(zhí)行。如果n＞m，則可以通過一些調(diào)度方案分配任務(wù)到相應(yīng)處理器執(zhí)行。本文僅考慮后一種情況。

任務(wù)i的計(jì)算量為Ti，任務(wù)i在處理器j上的執(zhí)行時(shí)間cptij已知，s代表一個(gè)調(diào)度方案，SL是任務(wù)序列T在處理器集合P上執(zhí)行的完成時(shí)間，SL(s)表示任意一個(gè)調(diào)度方案s下全部任務(wù)的完成時(shí)間，則任務(wù)調(diào)度問題就是求得一個(gè)最優(yōu)調(diào)度方案f，使SL(f)最小。任務(wù)調(diào)度問題數(shù)學(xué)描述為

2 粒子群優(yōu)化算法

PSO算法是一種基于群體智能理論的全局優(yōu)化方法，種群 (Swarm)中粒子通過相互間的合作與競爭進(jìn)行優(yōu)化搜索，種群是粒子的集合，種群大小或規(guī)模是集合中粒子的數(shù)目。種群中的粒子都有位置和速度兩個(gè)屬性，粒子的維數(shù)同問題解空間的維數(shù)相對應(yīng)。PSO算法從隨機(jī)解開始進(jìn)行迭代尋找最優(yōu)解，通過適應(yīng)度來評價(jià)解的質(zhì)量，粒子追隨當(dāng)前搜索到的最優(yōu)值尋找全局最優(yōu)。PSO算法實(shí)現(xiàn)容易、求解精度高、收斂速度快，在解決TSP、流水車間調(diào)度和路徑規(guī)劃等問題中展示了其良好的優(yōu)越性［8-9］。

假設(shè)PSO算法的搜索空間是d維，使用式 (2)表示第i個(gè)粒子的位置和速度矢量

PSO算法運(yùn)行時(shí)初始化為一群隨機(jī)粒子 (隨機(jī)解)，每個(gè)粒子在搜索空間內(nèi)不斷更新速度和位置，然后進(jìn)行迭代直到找到最優(yōu)解或達(dá)到最大迭代次數(shù)。每一次迭代過程中，粒子通過兩個(gè)極值的信息不斷更新自己的位置和速度。第一個(gè)是個(gè)體最優(yōu)解，是粒子上一次迭代本身所找到的最優(yōu)解，第i個(gè)粒子的個(gè)體最優(yōu)解記為pbesti=［pbesti1，pbesti2，…，pbestid］，另一個(gè)是整個(gè)種群找目前找到的最優(yōu)解，稱為全局最優(yōu)解，記為gbest= ［gbest1，gbest2，…，gbestd］。另外，粒子的所有鄰居中的最優(yōu)解是局部最優(yōu)解。

在找到個(gè)體最優(yōu)解和全局最優(yōu)解時(shí)，粒子根據(jù)狀態(tài)更新公式更新自己的速度和位置，PSO算法速度和位置更新公式［10］如下

式中:n——種群大小，t——迭代次數(shù)，c1和 c2——加速常數(shù)，一般取值為2;r1和 r2——0到1之間的隨機(jī)數(shù);ω——慣性權(quán)重，用于平衡收斂的全局性和收斂速度，計(jì)算方法見式 (4)

式中:N——最大迭代次數(shù)，ωmax和 ωmin——ω的最大值和最小值，通常取值為0.9和0.4，t——迭代次數(shù)。

PSO算法實(shí)際運(yùn)行過程中，由于粒子更新過程中總會考慮周圍粒子的信息，隨著迭代次數(shù)的增加就會產(chǎn)生“聚堆”現(xiàn)象，粒子會在問題過程中逐漸喪失多樣性，致使過早的收斂，容易陷入局部最優(yōu)。為了解決此問題，PSO算法多使用一些元啟發(fā)式算法進(jìn)行局部搜索，以加強(qiáng)PSO算法的收斂性能。

3 基于粒子群優(yōu)化的調(diào)度算法

3.1 粒子編碼方案

異構(gòu)多處理器環(huán)境中，任務(wù)調(diào)度算法需要解決的是在提高資源利用率和系統(tǒng)效率的同時(shí)，如何最大限度地減少完成時(shí)間。PSO算法是一種連續(xù)算法，算法的更新公式和過程是面向連續(xù)空間并為其設(shè)計(jì)的，而調(diào)度問題屬于離散問題。本文根據(jù)異構(gòu)多處理器調(diào)度問題特點(diǎn)，重新構(gòu)建粒子表達(dá)方式，對粒子的位置和速度進(jìn)行編碼，將PSO算法映射到離散空間，使其適用于解決任務(wù)調(diào)度問題。

PSO算法中每一個(gè)粒子都代表一個(gè)任務(wù)調(diào)度問題的潛在解。粒子位置矢量定義為一個(gè)n(m矩陣X，每一列代表一個(gè)任務(wù)分配情況，每一行代表一個(gè)處理器執(zhí)行情況。式(5)為粒子位置編碼方案，約束條件為式 (6)

根據(jù)約束條件 (6):位置矩陣X的元素xi，j取值為0或1;每一行可以有多個(gè)1出現(xiàn);每一列任意一個(gè)元素都可以為1;每一列只允許僅有一個(gè)元素值為1。即:

(1)其中xi，j=1表示任務(wù)Ti分配到處理器Pj上執(zhí)行，否則 xi，j=0;

(2)每一個(gè)處理器都可以執(zhí)行多個(gè)任務(wù);

(3)任務(wù)可以分配到任意一個(gè)處理器上執(zhí)行且任務(wù)必須被分配到一個(gè)處理器上執(zhí)行;

(4)一個(gè)任務(wù)不允許同時(shí)分配到多個(gè)處理器上，即任務(wù)執(zhí)行不能被中斷。

速度定義為粒子達(dá)到目標(biāo)狀態(tài)所需要對其當(dāng)前位置執(zhí)行的基本交換次序。速度V為n(n矩陣，如式 (7)所示，速度矩陣V中的元素vij只取值為0或1

此時(shí)，粒子的位置和速度狀態(tài)不再是同維連續(xù)失量。粒子的速度和位置不能再參照式 (3)進(jìn)行更新，為了利用此編碼方式，本文重新定義粒子速度和狀態(tài)更新公式中的加減法、乘法運(yùn)算規(guī)則:

(1)定義PSO算法中的加減法操作為交換操作，即vij=1表示交換位置矩陣X里第i列和第j列值為1的元素的位置，即相互任務(wù)i和任務(wù)j所分配的處理器，根據(jù)速度約束條件 (8)，速度矩陣以對角線為對稱軸，不能為對稱矩陣，避免了一次更新過程中無效的重復(fù)交換現(xiàn)象。

(2)定義速度與隨機(jī)數(shù)的數(shù)乘為依隨機(jī)數(shù)對應(yīng)概率值決定是否按照速度矩陣進(jìn)行交換操作。

重新定義的運(yùn)算規(guī)則使用符號“⊕”表示，則重新定義后的粒子狀態(tài)更新公式為式 (9)，各變量含義同式 (3)

式 (10)所示的位置和速度狀態(tài)進(jìn)行位置更新的結(jié)果見式(11)

由此可見，粒子的這種編碼方案和約束簡單明了，符合異構(gòu)多處理器任務(wù)調(diào)度規(guī)則，能夠表示出所有可能的任務(wù)調(diào)度方案，并且將粒子搜索空間和任務(wù)調(diào)度方案一一映射起來，同時(shí)避免了冗余搜索。

3.2 適應(yīng)度

粒子位置好壞的評價(jià)標(biāo)準(zhǔn)根據(jù)粒子的適應(yīng)度進(jìn)行評價(jià)。粒子適應(yīng)度通過適應(yīng)度函數(shù)計(jì)算得到，本文使用粒子的makespan作為其適應(yīng)度評價(jià)標(biāo)準(zhǔn)，粒子的makespan是指粒子中全部任務(wù)的最晚完成的時(shí)間，makespan越小粒子位置越接近最優(yōu)粒子，其所代表的潛在調(diào)度方案越好。第y個(gè)粒子適應(yīng)度值計(jì)算方法如下

其中，j為處理器編號makespan(pj)表示第j個(gè)處理器上所有任務(wù)的完成時(shí)間。makespan(pj)通過式 (13)計(jì)算得到

由式 (12)、(13)得到適應(yīng)度函數(shù)為

3.3 異構(gòu)多處理器任務(wù)調(diào)度算法流程

針對PSO算法容易陷入局部最優(yōu)解的問題，本文融入了模擬退火 (simulated annealing，SA)算法進(jìn)行局部搜索，以保證PSO算法的收斂性能，提出PSOASA算法。

PSOASA算法在PSO算法每次迭代后使用SA算法重復(fù)局部迭代以選擇更好的解，同時(shí)也允許算法通過一定的概率接受比較差的解使PSO算法避免局部最優(yōu)。當(dāng)初始溫度、溫度下降速度、終止溫度達(dá)到一定條件時(shí)，SA算法已經(jīng)被證明一定收斂于全局最優(yōu)［11］。

初溫T0的設(shè)置對PSOASA算法的性能具有一定的影響，初溫公式如式 (15)，f(gbestini)表示初始種群的全局最優(yōu)粒子的適應(yīng)度值

退溫函數(shù)采用線性退溫，即

λ為退溫速率，其中Tt為第 t次迭代時(shí) SA算法的溫度。

SA算法隨機(jī)選擇gbest的一個(gè)鄰居gbest＇，為避免陷入局部最優(yōu)，SA算法以一定的概率接受差的解，用粒子中選擇出來的gbest＇來以一定的概率取代全局最優(yōu)解gbest，讓算法跳出局部最優(yōu)。因此通過使用PSO算法的目標(biāo)函數(shù)(14)計(jì)算 Δ =f(gbest＇)－f(gbest)判 斷 gbest＇是 否 取代gbest，如果Δ≤0，則從 gbest移動到 gbest＇，否則以概率 η移動到gbest＇，概率η計(jì)算方法為

PSOASA算法借助SA的突跳能力對部分較好的個(gè)體進(jìn)行優(yōu)化，利用PSO算法的收斂速度快、SA算法依概率突跳能力以及收斂到全局最優(yōu)解等特點(diǎn)。通過這兩種算法的協(xié)同搜索，增加了種群多樣性，有效地克服PSO算法的“早熟”現(xiàn)象，既提高了收斂速度，又保證了全局最優(yōu)解的質(zhì)量。

PSOASA算法完整流程可以概括如下:

步驟1 初始化;設(shè)置有關(guān)PSOASA算法參數(shù):隨機(jī)初始化每個(gè)粒子的位置矢量和速度矢量;設(shè)定粒子群的規(guī)模;設(shè)定SA算法的初始溫度和退溫系數(shù)λ;結(jié)束條件溫度;

步驟2 使用式 (14)計(jì)算粒子的適應(yīng)值，初始化粒子的個(gè)體最優(yōu)解和種群的全局最優(yōu)解，設(shè)置粒子當(dāng)前位置為pbest，種群最佳位置為全局最優(yōu)值gbest;

步驟3 運(yùn)用式 (9)更新粒子的位置和速度;

步驟4 使用適應(yīng)度函數(shù) (14)計(jì)算出每一個(gè)粒子的適應(yīng)度值;

步驟5 找出個(gè)體最優(yōu)粒子和全局最優(yōu)粒子，并將求得的適應(yīng)度分別與pBest和gBest的適應(yīng)度比較，若較好，則更新pBest或gBest;

步驟6 判斷gbest是否滿足SA算法抽樣準(zhǔn)則，滿足則接受gbest，否則以概率η執(zhí)行下一步，否則由gbest產(chǎn)生新的狀態(tài)，按抽樣準(zhǔn)則確定新狀態(tài)并執(zhí)行退溫操作并在次判斷;

步驟7 判斷是否達(dá)到SA算法終止條件，是則執(zhí)行步驟8，否則執(zhí)行式 (16)，更新溫度參數(shù)，并轉(zhuǎn)到步驟6;

步驟8 判斷是否滿足結(jié)束條件 (達(dá)到最大迭代次數(shù))，如果滿足，執(zhí)行步驟10;否則，繼續(xù)下一步;

步驟9 更新迭代變量:t=t+1;

步驟10 輸出gbest，算法運(yùn)行結(jié)束。

4 仿真實(shí)驗(yàn)

本文在matlab仿真環(huán)境中，對PSOASA算法和目前多處理器任務(wù)調(diào)度研究較多的GA算法進(jìn)行性能［12］對比驗(yàn)證。基準(zhǔn)測試用例采用Watson等［13］提出基準(zhǔn)測試套件進(jìn)行調(diào)度算法的性能測試。表1給出了PSOASA和GA的實(shí)驗(yàn)參數(shù)設(shè)置。為了抵消數(shù)據(jù)隨機(jī)性對測試結(jié)果的影響，更好的反應(yīng)算法的性能，全部任務(wù)完成時(shí)間取10次測試中得到最優(yōu)解的平均值。

本文實(shí)驗(yàn)中測試了100、200、300、400、500個(gè)任務(wù)在5個(gè)處理器上調(diào)度的結(jié)果。圖1為使用PSOASA算法和GA算法在100個(gè)任務(wù)和5個(gè)處理器條件下進(jìn)行任務(wù)調(diào)度的完成時(shí)間-迭代次數(shù)曲線。

圖1可以看出，相對于GA算法，PSOASA算法的找到最優(yōu)值的迭代次數(shù)更少，解的質(zhì)量更高，即適應(yīng)度更低，全部任務(wù)執(zhí)行完成的時(shí)間更少。這是因?yàn)檫z傳算法復(fù)雜的交叉和變異操作增加了算法的時(shí)間復(fù)雜度，算法后期容易錯過最優(yōu)解;PSOASA算法具有PSO算法的收斂速度快的特點(diǎn)，同時(shí)SA算法對質(zhì)量較好解進(jìn)行擾動，增加了種群多樣性，提高算法的求解質(zhì)量。

圖2為不同任務(wù)數(shù)情況下，算法的平均執(zhí)行時(shí)間變化曲線。通過圖2可以看出，任務(wù)數(shù)較少時(shí)，PSOASA算法的執(zhí)行時(shí)間稍優(yōu)于GA算法，但隨著任務(wù)數(shù)目的增加，二者差距越來越明顯。在任務(wù)數(shù)較多時(shí)，PSOASA算法具有更短的執(zhí)行時(shí)間，性能明顯優(yōu)于GA算法，這是因?yàn)镚A算法在任務(wù)數(shù)較多時(shí)，交叉和變異操作的多樣性會受到限制，效率低下;而PSO算法受問題維數(shù)的影響更小，并且具有更好的并行搜索性能。因此，PSOASA算法更適合于大規(guī)模并行任務(wù)調(diào)度。

5 結(jié)束語

為提升異構(gòu)多處理器系統(tǒng)中的任務(wù)調(diào)度效率，本文提出了基于PSO算法的PSOASA算法求得全部任務(wù)最短完成時(shí)間。PSOASA算法充分利用了PSO算法收斂速度快和并行性的特點(diǎn)，通過建立粒子編碼方式和重新定義粒子更新公式，使連續(xù)的PSO算法適用于異構(gòu)多處理器任務(wù)調(diào)度，并融入了SA算法克服了PSO算法容易陷入局部最優(yōu)的缺點(diǎn)。通過與多處理器任務(wù)調(diào)度研究中較多采用的遺傳算法進(jìn)行性能測試比較，本文的算法能在更少的迭代次數(shù)內(nèi)搜索到最優(yōu)解，并且最優(yōu)解的質(zhì)量更高，算法的執(zhí)行速度也優(yōu)于遺傳算法，很好的解決了異構(gòu)多處理器系統(tǒng)中的任務(wù)調(diào)度問題，在大規(guī)模運(yùn)算環(huán)境中有很好的研究價(jià)值和應(yīng)用前景。

［1］ZHAO Peng，YAN Ming，LI Sikun.Performance optimization of application algorithms for heterogeneous multi-processor system-onchips［J］.Journal of Software，2011，22(7):1475-1487(in Chinese).［趙鵬;嚴(yán)明;李思昆.異構(gòu)多處理器SoC的應(yīng)用算法性能優(yōu)化方法 ［J］.軟件學(xué)報(bào)，2011，22(7):1475-1487.］

［2］Fatih Tasgetirena M，LIANG Yunchia，Sevkli Mehmet.Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem ［J］.International Journal of Production Research，2006，44(22):4737-4754.

［3］Thanushkodi K，Deeba K.On performance analysis of hybrid algorithm(improved PSO with simulated annealing)with GA，PSO for multiprocessor job scheduling［J］.WSEAS Transactions on Computers，2011，10(9):287-300.

［4］WENYun，XUHua，YANGJiadong.A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks ［J］.Journal of Parallel and Distributed Computing，2011，71(11):1518-1531.

［5］Ebrahimi Moghaddam，Mohsen Bonyadi，Mohammad Reza.An immune-based genetic algorithm with reduced search space co-ding for multiprocessor task scheduling problem ［J］.International Journal of Parallel Programming，2011，40(2):225-257.

［6］YAO Lili，SHI Haibo，LIU Chang.Solving multi-objective hybrid flow-shop scheduling problem based on genetic algorithm ［J］.Application Research of Computers，2011，28(9):3264-3271(in Chinese).［姚麗麗，史海波，劉昶.基于遺傳算法的混合流水線車間調(diào)度多目標(biāo)求解 ［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(9):3264-3271.］

［7］Abdel-Kader，Rehab F.An improved discrete PSOwith GA operators for efficient QoS-multicast routing［J］.International Journal of Hybrid Information Technology，2011，4(2):23-38.

［8］SONG Jiguang，QIN Yong，SHI Jianfang.Study of PSO algorithm and its application for routing optimization［J］.Computer Engineering and Design，2011，31(9):1905-1919(in Chinese).［宋繼光，秦勇，史健芳.粒子群算法及其在路由優(yōu)化中的研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，31(9):1905-1919.］

［9］LI Shuhong，ZHANG Qiaorong.Application of binary particle swarm optimization algorithm in path planning［J］.Computer Engineering and Design，2009，30(21):4953-5009(in Chinese).［李淑紅，張巧榮.二進(jìn)制粒子群算法在路徑規(guī)劃中的應(yīng)用［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(21):4953-5009.］

［10］YANG Fan，HU Chunping，YAN Xuefeng.Particle swarm optimization algorithm of self-adaptive parameter based on ant system and its application［J］.Control Theory ＆ Applications，2010，27(11):1479-1488.

［11］LI Pengchao.Grid resource prediction based on support vector regression and simulated annealing algorithms ［D］.Jilin:Master＇s graduation thesis of University of Jilin，2010(in Chinese).［李鵬超.基于模擬退火算法和支持向量回歸的網(wǎng)格資源預(yù)測［D］.吉林:吉林大學(xué)碩士學(xué)位論文，2010.］

［12］LI Zhiqiang.Optimization for the parallel test task scheduling based on GA ［C］//2nd International Conference on Information Science and Engineering.Hangzhou，China:2011:5223-5226.

［13］Jean-Paul Watson，Christopher Beck J.A hybrid constraint programming/local search approach to the job-shop scheduling problem ［J］.Lecture Notes in Computer Science，2008，50(15):263-277.