基于粒子群優化算法的異構多處理器任務調度

李靜梅，張 博

(哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001)

0 引言

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

任務調度已被證明是NP完全問題［3］，不能在多項式時間復雜度內找到最優解。為求解此類NP完全問題，一些啟發式算法如遺傳算法 (genetic algorithm，GA)等，開始被應用到任務調度研究［4-7］。

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

1 任務調度問題描述

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

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

2 粒子群優化算法

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

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

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

在找到個體最優解和全局最優解時，粒子根據狀態更新公式更新自己的速度和位置，PSO算法速度和位置更新公式［10］如下

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

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

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

3 基于粒子群優化的調度算法

3.1 粒子編碼方案

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

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

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

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

(2)每一個處理器都可以執行多個任務;

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

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

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

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

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

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

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

式 (10)所示的位置和速度狀態進行位置更新的結果見式(11)

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

3.2 適應度

粒子位置好壞的評價標準根據粒子的適應度進行評價。粒子適應度通過適應度函數計算得到，本文使用粒子的makespan作為其適應度評價標準，粒子的makespan是指粒子中全部任務的最晚完成的時間，makespan越小粒子位置越接近最優粒子，其所代表的潛在調度方案越好。第y個粒子適應度值計算方法如下

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

由式 (12)、(13)得到適應度函數為

3.3 異構多處理器任務調度算法流程

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

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

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

退溫函數采用線性退溫，即

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

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

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

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

步驟1 初始化;設置有關PSOASA算法參數:隨機初始化每個粒子的位置矢量和速度矢量;設定粒子群的規模;設定SA算法的初始溫度和退溫系數λ;結束條件溫度;

步驟2 使用式 (14)計算粒子的適應值，初始化粒子的個體最優解和種群的全局最優解，設置粒子當前位置為pbest，種群最佳位置為全局最優值gbest;

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

步驟4 使用適應度函數 (14)計算出每一個粒子的適應度值;

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

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

步驟7 判斷是否達到SA算法終止條件，是則執行步驟8，否則執行式 (16)，更新溫度參數，并轉到步驟6;

步驟8 判斷是否滿足結束條件 (達到最大迭代次數)，如果滿足，執行步驟10;否則，繼續下一步;

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

步驟10 輸出gbest，算法運行結束。

4 仿真實驗

本文在matlab仿真環境中，對PSOASA算法和目前多處理器任務調度研究較多的GA算法進行性能［12］對比驗證。基準測試用例采用Watson等［13］提出基準測試套件進行調度算法的性能測試。表1給出了PSOASA和GA的實驗參數設置。為了抵消數據隨機性對測試結果的影響，更好的反應算法的性能，全部任務完成時間取10次測試中得到最優解的平均值。

本文實驗中測試了100、200、300、400、500個任務在5個處理器上調度的結果。圖1為使用PSOASA算法和GA算法在100個任務和5個處理器條件下進行任務調度的完成時間-迭代次數曲線。

圖1可以看出，相對于GA算法，PSOASA算法的找到最優值的迭代次數更少，解的質量更高，即適應度更低，全部任務執行完成的時間更少。這是因為遺傳算法復雜的交叉和變異操作增加了算法的時間復雜度，算法后期容易錯過最優解;PSOASA算法具有PSO算法的收斂速度快的特點，同時SA算法對質量較好解進行擾動，增加了種群多樣性，提高算法的求解質量。

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

5 結束語

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

［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).［趙鵬;嚴明;李思昆.異構多處理器SoC的應用算法性能優化方法 ［J］.軟件學報，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).［姚麗麗，史海波，劉昶.基于遺傳算法的混合流水線車間調度多目標求解 ［J］.計算機應用研究，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).［宋繼光，秦勇，史健芳.粒子群算法及其在路由優化中的研究［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］.計算機工程與設計，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).［李鵬超.基于模擬退火算法和支持向量回歸的網格資源預測［D］.吉林:吉林大學碩士學位論文，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.