田 輝

(桂林理工大學 機械與控制工程學院,桂林 541006)

混合粒子群算法的異構(gòu)多核處理器間任務調(diào)度

田 輝

(桂林理工大學 機械與控制工程學院,桂林 541006)

針對異構(gòu)多核處理器間的任務調(diào)度問題，為了更好地發(fā)揮異構(gòu)多核處理器間的平臺優(yōu)勢，提出一種基于將有關聯(lián)的且不在同一處理器上的任務進行復制的思想，從而使每個異構(gòu)多核的處理器能獨立執(zhí)行任務，來減少不同處理器之間的通信開銷，并且通過混合粒子群算法(HPSO)來調(diào)度異構(gòu)多核處理器中的任務，避免由于當任意一個異構(gòu)多核處理器由于任務分配過多而導致計算機不能及時且準確地得出結(jié)果。最后實驗證明，對比傳統(tǒng)的啟發(fā)式分配方案和常見的遺傳算法(GA)，基于任務復制思想分配方案和混合粒子群算法(HPSO)具有更好的求解能力，并且可以提供執(zhí)行時間更少的調(diào)度分配方案，具有較好的應用價值。

異構(gòu)多核處理器；任務調(diào)度；混合粒子群算法

引 言

目前異構(gòu)多核處理器是處理器發(fā)展的前沿方向，而且一個計算機里也同時包含著多個異構(gòu)多核處理器。在多個異構(gòu)多核處理器平臺下，如何將不同的任務分配到不同的合理處理器上以獲得最小的運行時間或者最大的輸出權重，是多核處理器能否發(fā)揮性能優(yōu)勢的首要問題。目前任務調(diào)度問題已經(jīng)被證明為NP-hard問題，無法在多項式內(nèi)求得最優(yōu)解。所以異構(gòu)多核處理器環(huán)境下的任務調(diào)度問題成為了異構(gòu)多核技術方面的研究熱點。目前在異構(gòu)多核處理器間任務調(diào)度的研究方向大多采用了啟發(fā)式算法、布谷鳥算法等。楊輝華、張曉鳳提出了基于布谷鳥搜索的多處理器任務調(diào)度算法[5]；劉朝華、張英杰、吳建輝提出了一種求解TSP問題的改進克隆選擇算法[9]，用來求解處理器中的多任務優(yōu)化組合問題；徐成等人結(jié)合遺傳算法的交叉、變異操作改進了標準蟻群算法[4]，并應用于異構(gòu)多核平臺下的周期多幀任務模型的調(diào)度問題。

而上述提出的算法在處理器面對被分配的任務數(shù)量過多時，處理器不能快速有效地求出準確的結(jié)果。因此本文提出了在任務分配環(huán)節(jié)，通過將不在同一處理器的任務，但與任務之間存在著聯(lián)系，通過任務復制的思想將任務復制到有關聯(lián)的處理器內(nèi)進行處理，從而減少處理器間的任務通信開銷，并且每一個相互獨立的處理器采用混合粒子群算法來對各自的任務進行調(diào)用，避免當處理器任務量過大時，導致不能迅速、準確地求出相應的結(jié)果。為了驗證本文提出的混合粒子群算法(HPSO)在異構(gòu)多核處理器間的任務調(diào)度算法，并在MATLAB仿真平臺進行實驗不失一般性，與比較經(jīng)典的遺傳算法(GA)進行了對比分析。

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

異構(gòu)多核處理器系統(tǒng)任務調(diào)度的研究主要集中在具有約束關系的任務模型，一般使用 DAG 表達任務的約束關系，不失一般性。假設一個具有3個異構(gòu)多核處理器和14個有約束任務關系的系統(tǒng)模型，DAG圖的節(jié)點表示任務，邊反映了任務間的數(shù)據(jù)依賴性，如圖1所示。

圖1 具有14個任務的DAG例圖

以圖1為例，節(jié)點框內(nèi)的數(shù)據(jù)表示任務編號和任務執(zhí)行所需時間，有向邊上的數(shù)據(jù)表示其一個任務到另一個任務間的通信開銷。為了方便理解，分別給出了各個任務在相應處理器上的處理時間。T0、T1、T2、T3、T4、T5、T6屬于進程P0，被分配給處理器R0；T7、T8、T9、T10屬于進程P1，被分配給處理器R1；T11、T12、T13屬于進程P2，被分配給處理器R3。3個處理器的有些任務存在相互聯(lián)系，本文在研究異構(gòu)多核處理器間的任務調(diào)度問題時認為同一個異構(gòu)多核處理器之間的內(nèi)核是緊耦合的，它們之間通過共享Cache或高速通信通道的內(nèi)連接緊密聯(lián)系在一起，而不同處理器之間內(nèi)核的連接并不緊密，它們之間的通信時間要遠遠大于緊耦合內(nèi)核之間的通信開銷，所以設定T0到T1間的10、0分別表示內(nèi)核間通信次數(shù)為10，通信開銷為0。T11和T8之間的4、11分別表示通信次數(shù)為4，內(nèi)核間通信開銷為11。

由圖1可知，在不同處理器中的任務之間,必然存在相互聯(lián)系，為了減少不同處理節(jié)點間的任務之間通信所帶來的開銷，本文采用任務復制思想原則，將不在同一處理器上的任務復制到另一個處理器上執(zhí)行，其實質(zhì)就是增加處理器的計算量來消除不同處理器間的通信開銷。例如圖2所示的一個任務DAG圖，存在不同處理器間的任務通信，對于這種結(jié)構(gòu)的DAG圖采用通常的任務調(diào)度算法進行執(zhí)行，其節(jié)點之間的通信開銷不可小視，因此采用任務復制思想來消除任務節(jié)點間的通信開銷。

圖2 存在不同任務之間通信的DAG圖

經(jīng)過任務復制后的DAG圖如圖3所示。

圖3 經(jīng)過任務復制后的DAG圖

如圖3所示，處理器R0的T4任務與處理器R1的T3任務之間有聯(lián)系，但是任務復制必須尋找最短的路徑進行復制，而且必須從任務的入口節(jié)點到起始節(jié)點全部復制到另一個處理器上，而在處理器R0上，與T4處理器節(jié)點有關的起始節(jié)點有兩個，分別為T0和T1,而進行復制有3條選擇，分別為：T0→T2→T4,T1→T2→T4,T1→T3→T4，而這三條路徑的任務執(zhí)行開銷分別為：5+4+1=10，2+4+1=7，2+1+1=4，所以選擇復制的路徑為T1→T3→T4。

因此將上述任務分配的方案總結(jié)為：首先，為了減少任務之間所需的通信時間，將頻繁通信的任務分配到同一處理節(jié)點上；其次，所有屬于同一個進程的任務必須分配到同一個節(jié)點上，這是同一個進程共享同一個存儲單元，并且各個處理節(jié)點都是相互獨立的；最后要保證處理節(jié)點和負載是相互平衡的。其任務復制的思想就是在任務被分配完之后，對于兩個任務之間存在通信但不在同一處理器上，將從任務的入口節(jié)點到起始節(jié)點的最短路徑復制到另一個處理器上。

2 任務的調(diào)度

目前任務調(diào)度問題已經(jīng)被證明為NP-hard問題，經(jīng)過上訴的任務分配方案，將任務合理地分配到相應異構(gòu)多核處理器中，本文提出的調(diào)度算法是在上述任務分配完成后，針對每一個相互獨立的異構(gòu)多核處理器中的任務調(diào)度。由于現(xiàn)在處理器處理的任務有時在上百個以上，而目前王嘉平提出的多核系統(tǒng)中實時任務調(diào)度算法的研究，楊輝華、張曉鳳[5]提出了基于布谷鳥搜索的多處理器任務調(diào)度算法，劉朝華、張英杰、吳建輝[9]提出了一種求解TSP問題的改進克隆選擇算法，用來求解處理器中的多任務優(yōu)化組合問題，當處理器任務量過大時，運用他們提出的算法不能迅速而準確地求出處理結(jié)果。因此本文采用了任務間的旅行商組合優(yōu)化方案，并提出通過混合粒子群算法來解決當處理器被分配的任務量過大時的問題。本文提出的混合粒子群算法借鑒了前人研究的成果并加以改進。以下算法的調(diào)度是針對獨立的異構(gòu)多核處理器中的任務調(diào)度，并且為了方便理解，本文認為每個獨立的處理器被分配的任務為12個。

算法的實現(xiàn)過程如下：

(1) 任務個體的編碼

圖4 GA和HPSO在任務數(shù)N=14時優(yōu)化過程對比圖

編碼采用整數(shù)編碼的方法，每個數(shù)字表示一個被執(zhí)行完的任務，如上述算法中本文假設執(zhí)行的12個任務，每個任務的編碼為[4,6,7,10,3,5,11,8,2,9,1,12],表示執(zhí)行任務從任務4開始，經(jīng)過4,6,7，.....最終返回任務4，從而完成全部任務的執(zhí)行。

(2) 適應度值

任務適應度值為執(zhí)行完全部任務時間的長短，表示為：

其中n為任務數(shù)量；Di,j表示執(zhí)行i任務到j任務所需時間。

(3) 交叉操作

將全部任務中的隨機個體分別和執(zhí)行所需時間最長的任務和全部任務中所需執(zhí)行時間最短的任務進行交叉來獲得更新，交叉方法同樣采用整數(shù)交叉法。首先選擇兩個交叉位置，其次把隨機任務和執(zhí)行所需最少任務進行交叉，假定選取的交叉任務為10和12，其交叉操作為：

個體[4,6,7,10,3,5,11,8,2,9,1,12]和極值 [4,2,8,10,3,5,11,7,6,9,1,12] 進行交叉操作過程得到的新個體為新任務，其新任務序列為:[4,6,8,10,3,5,11,8,2,9,1,12]，同時對與產(chǎn)生的任務中重復的編碼進行調(diào)整，調(diào)整為[4,6,8,10,3,5,11,7,2,9,1,12]，然后采用保留優(yōu)秀任務序列策略，只有當新執(zhí)行路徑比舊執(zhí)行路徑短時才選擇更新。

(4) 變異操作

采用任務內(nèi)部兩兩位置互換原則，首先隨機確定兩個任務位置，例如位置8和2進行互換，變異過程為：[4,6,7,10,3,5,11,8,2,9,1,12]→[4,6,7,10,3,5,11,2,8,9,1,12]，然后仍然保留優(yōu)秀個體策略，只有當新執(zhí)行路徑比舊執(zhí)行路徑短才選擇更新。

3 任務調(diào)度性能測試以及對比分析

3.1.1 任務調(diào)度算法在VisualStudio2010平臺上的測試實驗

模擬調(diào)度問題模型基礎設置如下：考慮到任務的隨機性和多樣性，為了表示任務的不一樣性和準確性，本文將任務用算法隨機給得坐標來表示它的不一樣性。同時此次測試實驗分為三個部分，當任務數(shù)N=14、N=50、N=130時，混合粒子群算法利用Visual studio 2010中的可變處理器個數(shù)和自帶OpenMP多線程并行計算來對多處理器上的調(diào)度結(jié)果。測試實驗平臺處理器個數(shù)設置為3，混合粒子群算法(HPSO)中的參數(shù)分別取為: 學習因子c1、c2分別取2，最大權重w取0.9，最小權重w取0.4；遺傳算法(GA)中的參數(shù)分別取為：pc(交叉概率)取0.9;pm(變異概率)取0.05；GGAP(個體間的代溝)取0.9，為了使數(shù)據(jù)準確，本測試每組實驗反復測試30次，最后取各個任務調(diào)度算法的最好處理結(jié)果。

① 當任務數(shù)取N=14時，種群數(shù)目為100，迭代數(shù)為200，測試結(jié)果如圖4所示。

② 當任務數(shù)取N=50時，種群數(shù)目為100，迭代數(shù)為1000，測試結(jié)果如圖5所示。

圖5 GA和HPSO在任務數(shù)N=50時優(yōu)化過程對比圖

③ 當任務數(shù)取N=130時，種群數(shù)目為100，迭代數(shù)為3000，測試結(jié)果如圖6所示。

圖6 GA和HPSO在任務數(shù)N=130時優(yōu)化過程對比圖

3.1.2 實驗總結(jié)

在使用混合粒子群算法進行任務調(diào)度時，當任務數(shù)N=14時，處理完任務所走的路程為608；當任務數(shù)N=50時，處理完這些任務所走的路程為1688；當任務數(shù)N=130時，處理完任務所走的路程為5 605。

在使用遺傳算法進行任務調(diào)度時，當任務數(shù)N=14時，處理完任務所走的路程為最小為428，最大為561，其最后結(jié)果不穩(wěn)定。當任務數(shù)N=50時，處理完這些任務所走的路程為1784。當任務數(shù)N=130時，處理完任務所走的路程為5 605。

當任務數(shù)N=14時，遺傳算法所走的路程比混合粒子群算法少，但是遺傳算法沒有混合粒子群算法最后處理的結(jié)果穩(wěn)定。

當任務數(shù)N=50時，遺傳算法所走的路程比混合粒子群算法多。

當任務數(shù)N=130時，遺傳算法所走的路程和混合粒子群算法所走的路程一樣。

測試表明，遺傳算法和混合粒子群算法都能在多處理器上并行計算，但是混合粒子群算法不論在多少個任務下執(zhí)行時，都優(yōu)于遺傳算法而且穩(wěn)定，但是當N=130時，遺傳算法和混合粒子群算法表現(xiàn)的性能一樣，而且穩(wěn)定。

3.2 任務調(diào)度算法在Matlab上仿真實驗

為了驗證HPSO算法的優(yōu)點，本文將遺傳算法和混合粒子群算法在Matlab上進行了三次仿真實驗。本文挑選在進行了多次試驗后的兩種算法的最好的結(jié)果仿真圖進行對比，并采用國際上通用的 TSPLIB[1]庫中的標準測試集burma14、st70、ch130分別進行三組實驗，對任務N分別取14、50、130時的兩個算法的比較，為了保證數(shù)據(jù)的準確性，每組實驗分別進行30次，然后取平均值。采用本文提出的HPSO調(diào)度算法與本文對比的調(diào)度算法GA算法對任務進行調(diào)度，對調(diào)度的結(jié)果進行對比分析。

本實驗中混合粒子群算法(HPSO)中的參數(shù)分別取為: 學習因子c1、c2分別取2，最大權重w取0.9，最小權重w取0.4；遺傳算法(GA)中的參數(shù)分別取為：pc(交叉概率)取0.9;pm(變異概率)取0.05；GGAP(個體間的代溝)取0.9。

3.2.1 實驗仿真

① 當線程數(shù)取N=14時，種群數(shù)目為100，迭代數(shù)為200，其任務的標準burma14位置坐標為以下坐標，如圖7所示。

圖7 當任務N=14時的任務分布圖

其兩種算法的仿真結(jié)果如表1所列。

表1 GA和HPSO算法在N=14時的數(shù)據(jù)結(jié)果

當任務N=14時,HPSO和GA算法的仿真對比圖如圖8所示。

圖8 GA和HPSO在任務數(shù)N=14時優(yōu)化過程對比圖

② 當任務數(shù)取N=50時，種群數(shù)目為100，迭代數(shù)為1000，由于任務量過大就不列舉位置坐標。

其根據(jù)任務坐標仿真結(jié)果如圖9所示。

圖9 當任務N=50時的任務分布圖

其兩種算法的處理結(jié)果如表2所列。

表2 GA和HPSO算法在N=50時的數(shù)據(jù)結(jié)果

當任務N=50時,HPSO和GA算法的仿真對比圖如圖10所示。

圖10 GA和HPSO在任務數(shù)N=50時優(yōu)化過程對比圖

③ 當任務數(shù)取N=130時，種群數(shù)目為100，迭代數(shù)為3 000，其兩種算法的處理結(jié)果如表3所列。

表3 GA和HPSO算法在N=130時的數(shù)據(jù)結(jié)果

N=130時的任務分布圖如圖11所示。

圖11 當任務N=130時的任務分布圖

當任務N=130時仿真對比圖如圖12所示。

圖12 GA和HPSO在任務數(shù)N=130時優(yōu)化過程對比圖

3.2.2 實驗總結(jié)

① 當任務N=14時，從圖9可以看出GA算法在當?shù)?00代的時候穩(wěn)定了，而HPSO當?shù)?0代的時候已經(jīng)穩(wěn)定了，同時從表1可以看出，當任務N=14時，其GA算法和HPSO算法在最優(yōu)解方面分別為30.878和30.881，在最差解方面為31.208和30.881，在平均值方面分別為31.013和30.881，在調(diào)度的時間上為9.87和2.43。通過以上數(shù)據(jù)可以得出，當任務N=14時，無論在最優(yōu)解還是最差解、調(diào)度的時間方面，HPSO算法都要比GA算法優(yōu)越，而且HPSO算法也很穩(wěn)定。

② 當任務N=50時，從圖10可以看出GA算法在當?shù)?30代的時候才穩(wěn)定下來，而HPSO當?shù)?00代的時候已經(jīng)開始穩(wěn)定了，同時從表2可以看出，當任務N=50時，其GA算法和HPSO算法在最優(yōu)解方面分別為568.412和553.596，在最差解方面為644.112和604.837，在平均值方面分別為606.262和579.217，在調(diào)度的時間上為31.52和12.05。通過以上數(shù)據(jù)可以得出，當任務N=50時，無論在最優(yōu)解還是最差解、調(diào)度的時間方面，HPSO算法都要比GA算法優(yōu)越，而且HPSO算法也很穩(wěn)定。

③ 當任務N=130時，從圖13可以看出，GA算法在當?shù)?000代的時候也沒有開始穩(wěn)定下來，而HPSO當?shù)?700的時候已經(jīng)開始穩(wěn)定了，同時從表3可以看出，當任務N=50時，其GA算法在最優(yōu)解和最差解方面不能求出準確值，而HPSO算法的最優(yōu)解為6467.69、最差解位7000.198、平均值為6733.944，在調(diào)度的時間上為240.52。通過以上數(shù)據(jù)可以得出，當任務N=130時，GA算法已經(jīng)不能調(diào)度并處理任務了，而HPSO算法可以求出準確值，所以當任務量大的時候，HPSO算法能夠合理地對大任務量進行調(diào)度。

所以通過上述三組實驗比較，可以得出HPSO算法無論在算法的時間復雜度、調(diào)度的成功率和任務執(zhí)行的加速比率上都要比GA算法優(yōu)越。

結(jié) 語

為優(yōu)化異構(gòu)多核處理器環(huán)境下任務調(diào)度性能，本文提出一種基于將有關聯(lián)的且不在同一處理器上的任務進行復制思想，從而使每個異構(gòu)多核的處理器能獨立地執(zhí)行任務，來減少不同處理器之間的通信開銷，并且通過混合粒子群算法(HPSO)來調(diào)度異構(gòu)多核處理器中的任務，避免由于當任意一個異構(gòu)多核處理器由于任務分配過多而導致處理器不能及時且準確地處理出結(jié)果。

[1] Gupta S，Agarwal G，Kumar V.Task scheduling in multi-processor system using genetic algorithm[C]//Proc of the 2nd International Conference on Machine Learning and Computing,2012:267-271．

[2] 李靜梅,張博.基于粒子群優(yōu)化算法的異構(gòu)多處理器任務調(diào)度[J].計算機工程與設計,2013,34(2) : 627-631.

[3] Kaur R,Singh G.Genetic algorithm solution for scheduling jobs inmultiprocessor environment[C]//Proc of Annual IEEE India Confe-rence,2012:968-973.

[4] 徐成,王培磊,楊志邦.基于改進蟻群算法的周期多幀任務分配[J].計算機應用研究,2012,29(9):3251-3254．

[5] 楊輝華,張曉鳳.基于布谷鳥搜索的多處理器任務調(diào)度算法[J].計算機科學,2015(1).

[6] Ebrahimi J,Hosseinian S H,Gharehpetian G B.Unit commitment problem solution using shuffled frog leaping algorithm[J].IEEE Trans on Power Systems,2011,26(2):573-581．

[7] 徐雨明,朱寧波,歐陽艾嘉,等．異構(gòu)系統(tǒng)中 DAG 任務調(diào)度的雙螺旋結(jié)構(gòu)遺傳算法[J].計算機研究與發(fā)展,2014,51(6):1240-1252．

[8] Chen Minrong,Li Xia,Wang Na,et al．An improved shuffled frog-leaping algorithm for job-shop scheduling problem[C]//Proc of the 2nd International Conference on Innovations in Bio-inspired Compu-ting and Applications,2011:203-206．

[9] 劉朝華,張英杰,吳建輝.一種求解TSP問題的改進克隆選擇算法[J].系統(tǒng)仿真學報,2010,22(7):1627-1631．

[10] 周輝仁,唐萬生,牛犇.基于遞階遺傳算法的多旅行商問題優(yōu)化[J].計算機應用研究,2012,26(10):3754 -3757．

[11] 馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究,2012,29(4):1201-1206.

[12] 陳芳園,張東松,王志英.異構(gòu)多核處理器體系架構(gòu)設計研究[J].計算機工程與科學,2011(12):27-36.

[13] 彭曉明,郭浩然,龐建民.多核處理器-技術趨勢和挑戰(zhàn)[J].計算機科學,2012(S3):320-326.

[14] 余伶俐,蔡自興.改進混合離散粒子群的多種優(yōu)化策略算法[J].中南大學學報:自然科學版,2011,40(4):1047-1053.

Task Scheduling for Heterogeneous Multi-core Processors Based on HPSO

Tian Hui

(College of Information Science&Engineering,Guilin University of Technology,Guilin 541006,China)

In order to solve the problem of task scheduling among heterogeneous multi-core processors and better play to the advantage of heterogeneous multi-core processor platform,a replicating idea based on connected and not on the same processor task is proposed,so that each heterogeneous multi-core processor can independently perform the task to reduce the communication overhead among different processors.The hybrid particle swarm optimization algorithm (HPSO) is used to schedule tasks in heterogeneous multi-core processor,avoids the results can not be timely and accurately shown when an arbitrary heterogeneous multi-core processor has too many tasks.The experiment results show that compared with the traditional heuristic allocation scheme and the common genetic algorithm,the solution has better solving ability,and can provide the implementation scheme of less time scheduling and allocation,and has good application value.

multiprocessor;task scheduling;HPSO

TP301.6

A

士然

2017-01-03)