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

田 輝

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

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

田 輝

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

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

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

引 言

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

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

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

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

圖1 具有14個(gè)任務(wù)的DAG例圖

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

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

圖2 存在不同任務(wù)之間通信的DAG圖

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

圖3 經(jīng)過(guò)任務(wù)復(fù)制后的DAG圖

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

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

2 任務(wù)的調(diào)度

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

算法的實(shí)現(xiàn)過(guò)程如下：

(1) 任務(wù)個(gè)體的編碼

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

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

(2) 適應(yīng)度值

任務(wù)適應(yīng)度值為執(zhí)行完全部任務(wù)時(shí)間的長(zhǎng)短，表示為：

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

(3) 交叉操作

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

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

(4) 變異操作

采用任務(wù)內(nèi)部?jī)蓛晌恢没Q原則，首先隨機(jī)確定兩個(gè)任務(wù)位置，例如位置8和2進(jìn)行互換，變異過(guò)程為：[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)秀個(gè)體策略，只有當(dāng)新執(zhí)行路徑比舊執(zhí)行路徑短才選擇更新。

3 任務(wù)調(diào)度性能測(cè)試以及對(duì)比分析

3.1.1 任務(wù)調(diào)度算法在VisualStudio2010平臺(tái)上的測(cè)試實(shí)驗(yàn)

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

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

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

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

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

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

3.1.2 實(shí)驗(yàn)總結(jié)

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

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

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

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

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

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

3.2 任務(wù)調(diào)度算法在Matlab上仿真實(shí)驗(yàn)

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

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

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

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

圖7 當(dāng)任務(wù)N=14時(shí)的任務(wù)分布圖

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

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

當(dāng)任務(wù)N=14時(shí),HPSO和GA算法的仿真對(duì)比圖如圖8所示。

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

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

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

圖9 當(dāng)任務(wù)N=50時(shí)的任務(wù)分布圖

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

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

當(dāng)任務(wù)N=50時(shí),HPSO和GA算法的仿真對(duì)比圖如圖10所示。

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

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

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

N=130時(shí)的任務(wù)分布圖如圖11所示。

圖11 當(dāng)任務(wù)N=130時(shí)的任務(wù)分布圖

當(dāng)任務(wù)N=130時(shí)仿真對(duì)比圖如圖12所示。

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

3.2.2 實(shí)驗(yàn)總結(jié)

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

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

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

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

結(jié) 語(yǔ)

為優(yōu)化異構(gòu)多核處理器環(huán)境下任務(wù)調(diào)度性能，本文提出一種基于將有關(guān)聯(lián)的且不在同一處理器上的任務(wù)進(jìn)行復(fù)制思想，從而使每個(gè)異構(gòu)多核的處理器能獨(dú)立地執(zhí)行任務(wù)，來(lái)減少不同處理器之間的通信開(kāi)銷，并且通過(guò)混合粒子群算法(HPSO)來(lái)調(diào)度異構(gòu)多核處理器中的任務(wù)，避免由于當(dāng)任意一個(gè)異構(gòu)多核處理器由于任務(wù)分配過(guò)多而導(dǎo)致處理器不能及時(shí)且準(zhǔn)確地處理出結(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)多處理器任務(wù)調(diào)度[J].計(jì)算機(jī)工程與設(shè)計(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ìn)蟻群算法的周期多幀任務(wù)分配[J].計(jì)算機(jī)應(yīng)用研究,2012,29(9):3251-3254．

[5] 楊輝華,張曉鳳.基于布谷鳥(niǎo)搜索的多處理器任務(wù)調(diào)度算法[J].計(jì)算機(jī)科學(xué),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] 徐雨明,朱寧波,歐陽(yáng)艾嘉,等．異構(gòu)系統(tǒng)中 DAG 任務(wù)調(diào)度的雙螺旋結(jié)構(gòu)遺傳算法[J].計(jì)算機(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問(wèn)題的改進(jìn)克隆選擇算法[J].系統(tǒng)仿真學(xué)報(bào),2010,22(7):1627-1631．

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

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

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

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

[14] 余伶俐,蔡自興.改進(jìn)混合離散粒子群的多種優(yōu)化策略算法[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版,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)