姚英彪，王 璇

（杭州電子科技大學(xué)通信工程學(xué)院，浙江杭州310018）

面向多核任務(wù)調(diào)度的混合遺傳算法

姚英彪，王 璇

（杭州電子科技大學(xué)通信工程學(xué)院，浙江杭州310018）

多核處理器的并行任務(wù)調(diào)度一直是研究的熱點(diǎn)話題，屬于NP-hard問(wèn)題。針對(duì)此問(wèn)題，本文提出了一種集啟發(fā)式算法、禁忌搜索算法、模擬退火算法于一體的改進(jìn)混合遺傳算法（modified hybrid genetic algorithm，MHGA）。MHGA改進(jìn)如下：首先，采用啟發(fā)式的分層調(diào)度來(lái)初始化種群，提高初始種群質(zhì)量；其次，提出基于禁忌搜索（tabu search，TS）的隨機(jī)編號(hào)交叉算子，提高種群的多樣性；最后，采用基于模擬退火（simulated annealing，SA）的變異，提高個(gè)體質(zhì)量。實(shí)驗(yàn)結(jié)果表明，與其他遺傳算法（genetic algorithm，GA）相比，MHGA可以得到更小的任務(wù)調(diào)度時(shí)間和更快的最優(yōu)解搜索能力。

遺傳算法；禁忌搜索；模擬退火；并行調(diào)度；多核處理器

0 引 言

在多核系統(tǒng)芯片（multi-processor system-on-chip，MPSoC）設(shè)計(jì)中，如何進(jìn)行任務(wù)分配和調(diào)度是一個(gè)非常關(guān)鍵的問(wèn)題，這個(gè)問(wèn)題可以簡(jiǎn)單描述為：N個(gè)有前后依賴關(guān)系的任務(wù)如何分配到P個(gè)處理器上執(zhí)行，在保證任務(wù)依賴關(guān)系的條件下使得任務(wù)總完工時(shí)間最小。任務(wù)分配解決在哪個(gè)處理器核上執(zhí)行任務(wù)，即匹配任務(wù)到處理器核上；任務(wù)調(diào)度解決何時(shí)執(zhí)行任務(wù)，即給出任務(wù)在具體處理器核上的起止時(shí)間。影響任務(wù)分配和調(diào)度的因素主要有：任務(wù)計(jì)算時(shí)間、任務(wù)之間的依賴關(guān)系和處理器核之間的數(shù)據(jù)傳輸延遲等。國(guó)內(nèi)外學(xué)者對(duì)這個(gè)問(wèn)題進(jìn)行了深入的研究，研究結(jié)果表明多核任務(wù)分配和調(diào)度問(wèn)題是一種組合優(yōu)化問(wèn)題，不能在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)找到最優(yōu)解，已被證明是NP-hard問(wèn)題［1－4］。

目前解決這個(gè)問(wèn)題的方法大致可以劃分為啟發(fā)式算法和智能搜索算法兩類(lèi)。啟發(fā)式算法一般采用某種啟發(fā)規(guī)則進(jìn)行任務(wù)的分配和調(diào)度，它一般只能找到問(wèn)題的次優(yōu)解，且在求解大規(guī)模任務(wù)分配和調(diào)度問(wèn)題時(shí)，得到的解往往與最優(yōu)解相差甚遠(yuǎn)。它的優(yōu)點(diǎn)在于復(fù)雜度低，可以快速給出某種次優(yōu)結(jié)果。啟發(fā)式算法的代表有修改關(guān)鍵路徑算法［5］（modified critical path，MCP）、異構(gòu)最早完成時(shí)間算法［6］（heterogeneous earliest finish time，HEFT）等。智能搜索算法是一種利用自然現(xiàn)象與優(yōu)化過(guò)程的某些相似性而逐步發(fā)展起來(lái)的搜索方法，其算法思想簡(jiǎn)單，同時(shí)還具備搜索全局最優(yōu)解的能力。遺傳算法（genetic algorithm，GA）［7－9］、模擬退火（simulated annealing，SA）［10］、粒子群算法（particle swarm optimization，PSO）［11］、禁忌搜索（tabu search，TS）［12］等都屬于智能搜索算法。

本文計(jì)劃采用遺傳算法框架解決MPSoC的任務(wù)分配和調(diào)度問(wèn)題。文獻(xiàn)［13］率先將GA應(yīng)用到并行任務(wù)調(diào)度中，奠定了用GA解決此類(lèi)問(wèn)題的基礎(chǔ)。但是，傳統(tǒng)GA也碰到了下面3個(gè)主要難題：①問(wèn)題描述困難，②初始化種群質(zhì)量難以保證，③容易早熟，造成進(jìn)化后期搜索效率較低。因此，GA的改進(jìn)可以從優(yōu)化初始種群［14］、改進(jìn)編碼機(jī)制［15］、改進(jìn)遺傳算子［16］、防止種群早熟［17］等方面進(jìn)行。

針對(duì)傳統(tǒng)GA碰到的問(wèn)題，本文提出一種集啟發(fā)式調(diào)度、TS、SA于一體的改進(jìn)混合遺傳調(diào)度算法（modified hybrid genetic algorithm，MHGA）：①采用啟發(fā)式的分層調(diào)度來(lái)初始化種群，提高初始種群質(zhì)量；②提出基于TS的隨機(jī)編號(hào)交叉算子，使用禁忌表來(lái)封鎖剛搜索過(guò)的區(qū)域從而避免迂回搜索，同時(shí)赦免禁忌區(qū)域中的一些優(yōu)良狀態(tài)，保證搜索的多樣性，從而提高種群的多樣性；③在對(duì)個(gè)體進(jìn)行變異時(shí)，采用SA對(duì)個(gè)體進(jìn)行變異，提高種群中每個(gè)個(gè)體的質(zhì)量。本文實(shí)驗(yàn)結(jié)果表明，與其他GA相比，MHGA可以得到更小的任務(wù)調(diào)度時(shí)間和更快的最優(yōu)解搜索能力。

1 任務(wù)模型及算法框架

1.1 任務(wù)模型

任務(wù)模型用有向無(wú)環(huán)圖（directed acyclic graph，DAG）來(lái)表示，即G＝〈T，E〉。其中，T為任務(wù)節(jié)點(diǎn)的集合，T＝｛i｜1≤i≤N｝表示N個(gè)任務(wù)的集合；E＝｛eij｝為任務(wù)之間有向邊的集合，邊eij表示任務(wù)i執(zhí)行后才可以執(zhí)行j。同時(shí)假設(shè)t＝｛t1，t2，…，tN｝表示任務(wù)的執(zhí)行時(shí)間；c＝｛cij｝為任務(wù)之間有向邊eij的權(quán)重，cij表示任務(wù)i和j分配到不同處理器時(shí)的通信時(shí)間；當(dāng)任務(wù)i和j分配到同一處理器時(shí)，通信時(shí)間為0。一個(gè)簡(jiǎn)單的11個(gè)任務(wù)的DAG圖如圖1所示（圖1中，每個(gè)任務(wù)的執(zhí)行時(shí)間為2，任務(wù)間的通信時(shí)間為1）。

圖1 任務(wù)DAG圖

1.2 算法框架

對(duì)于已知的DAG圖，可以根據(jù)任務(wù)之間的依賴關(guān)系定義任務(wù)層級(jí)值h，表示任務(wù)節(jié)點(diǎn)的層數(shù)，定義如下：

本文提出的MHGA算法由節(jié)點(diǎn)層級(jí)值計(jì)算、初始種群生成、輪盤(pán)賭選擇、禁忌搜索交叉、模擬退火變異組成。算法的框架圖如圖2所示。

圖2 算法框架圖

2 MHGA算法設(shè)計(jì)

2.1 初始種群生成

為提高初始種群質(zhì)量，本文采用基于層級(jí)值h的分層調(diào)度啟發(fā)式算法來(lái)生成初始種群，替代傳統(tǒng)的完全隨機(jī)的初始種群。

2.1.1 任務(wù)的初始處理器分配

對(duì)于一個(gè)特定的DAG圖，根據(jù)式（1）可以算出每個(gè)任務(wù)的層級(jí)值h。圖1中，任務(wù)的層級(jí)值依次為｛1；2，2；3，3；4，4，4；5，5；6｝，不同層級(jí)值的任務(wù)用分號(hào)隔開(kāi)。將所有任務(wù)按照層級(jí)值進(jìn)行分層，層級(jí)值相同的任務(wù)放在同一層，第j層的任務(wù)集合為T(mén)j＝T｛h＝j(luò)｝。因此，圖1可以分為6層，分別為T(mén)1＝｛1｝，T2＝｛2，3｝，T3＝｛4，5｝，T4＝｛6，7，8｝，T5＝｛9，10｝，T6＝｛11｝。

從圖1可以看出，具有相同層級(jí)值的任務(wù)可以并行執(zhí)行。因此，為降低任務(wù)的完工時(shí)間，應(yīng)該盡量將每層的任務(wù)均衡地分配到處理器上。假設(shè)處理器總數(shù)為P，每層的任務(wù)總數(shù)為n，則n／P＝a…b（其中b為余數(shù)）。在總?cè)蝿?wù)中隨機(jī)選取b個(gè)任務(wù)（b＜P）隨機(jī)分配到不同的處理器；對(duì)于剩下的a×P個(gè)任務(wù)，每個(gè)處理器從中隨機(jī)選擇a個(gè)任務(wù)。這樣可以確保將每層任務(wù)均衡的分配到處理器上，避免同一層任務(wù)過(guò)多集中在一個(gè)處理器上造成完工時(shí)間的延遲。

圖1的DAG圖，設(shè)其處理器總數(shù)P＝2。對(duì)于T4＝｛6，7，8｝，n／P＝3／2＝1…1，先任選1個(gè)任務(wù)分配給任一個(gè)處理器，例如把任務(wù)8分配給處理器P1；剩下的任務(wù)均衡分配給P1和P2；這樣T4可能的一個(gè)處理器分配為｛p1，p2，p1｝。根據(jù)以上處理器分配原則，圖1所示的11個(gè)任務(wù)的一個(gè)可能的處理器初始分配p＝｛p1；p1，p2；p1，p2；p1，p2，p1；p2，p1；p1｝。

2.1.2 任務(wù)的編碼

本文采用符號(hào)編碼方案，符號(hào)由任務(wù)的基因值組成，所有任務(wù)的基因序列構(gòu)成一個(gè)染色體（或個(gè)體）。任務(wù)基因值產(chǎn)生包括兩個(gè)階段：

步驟1 基因值初始化階段，即由初始處理器分配序列得到初始基因值序列。這一階段采用固定映射方式，映射規(guī)則如下：

式中，vi為任務(wù)i的基因值；pi為任務(wù)i初始分配處理器號(hào)；P為處理器總數(shù)。上述規(guī)則能夠保證個(gè)體中的每個(gè)基因值都唯一，即每個(gè)任務(wù)的基因值都不相同。這樣可以保證后面（2.1.3節(jié)）根據(jù)基因值進(jìn)行任務(wù)調(diào)度時(shí)，能夠得到唯一的調(diào)度方案。

步驟2 基因值隨機(jī)交換階段，即對(duì)每個(gè)處理器上的任務(wù)的基因值進(jìn)行隨機(jī)交換。交換規(guī)則如下：假設(shè)某個(gè)處理器上共分配m個(gè)任務(wù)，隨機(jī)選取該處理器上兩個(gè)任務(wù)，將其基因值進(jìn)行交換，重復(fù)進(jìn)行 m／2 次交換；對(duì)每個(gè)處理器都執(zhí)行上述操作，最終得到新的染色體。

進(jìn)行此階段的原因在于，依據(jù)式（2）得到的任務(wù)的基因值跟任務(wù)序號(hào)成正比，是逐漸遞增的，不具有隨機(jī)性，減小了初始種群的空間的大小。隨機(jī)交換后，任務(wù)的基因值與其序號(hào)不在具有對(duì)應(yīng)關(guān)系，具有更好的隨機(jī)性。

上節(jié)所示的處理器初始分配序列p＝｛p1；p1，p2；p1，p2；p1，p2，p1；p2，p1；p1｝，根據(jù)式（2）初始化后得到的個(gè)體為V＝｛3；5，8；9，12；13，16，17；20，21；23｝；隨機(jī)交換后，可能的一個(gè)個(gè)體為V＝｛23；5，20；13，16；9，12，21；8，3；17｝。此時(shí)，任務(wù)1到11對(duì)應(yīng)的基因值分別為23，5，20，13，16，9，12，21，8，3，17。

2.1.3 任務(wù)調(diào)度與分配

得到個(gè)體V后，采用基于任務(wù)的層級(jí)值和基因值的任務(wù)調(diào)度、基于任務(wù)基因值的處理器分配。

任務(wù)調(diào)度規(guī)則：首先，對(duì)于不同層級(jí)值的任務(wù)，按照任務(wù)的層級(jí)值從小到大進(jìn)行調(diào)度，也就是說(shuō)，層級(jí)值較小的所有任務(wù)都調(diào)度完成才能調(diào)度層級(jí)值較大的任務(wù)；其次，對(duì)于相同層級(jí)值的任務(wù)，按照任務(wù)的基因值從大到小進(jìn)行調(diào)度。

根據(jù)以上規(guī)則，個(gè)體V＝｛23；5，20；13，16；9，12，21；8，3；17｝的調(diào)度順序TS為：1→3→2→5→4→8→7→6→9→10→11。

處理器分配規(guī)則：任務(wù)的基因值和處理器總數(shù)取余即為任務(wù)分配的處理器，如式（3）所示，其中mod代表取余。

上述個(gè)體進(jìn)行處理器分配后，可得到任務(wù)1，2，4，6，8，10和11在p1上執(zhí)行，任務(wù)3，5，7和9在p2上執(zhí)行?？梢园l(fā)現(xiàn)，由式（3）得到的處理器分配序列和該個(gè)體對(duì)應(yīng)的初始處理器分配序列p＝｛p1；p1，p2；p1，p2；p1，p2，p1；p2，p1；p1｝仍然一致，這是因?yàn)椋菏剑?）是式（2）的反變換，同時(shí)，上一節(jié)基因值隨機(jī)交換只針對(duì)同一個(gè)處理器上的任務(wù)進(jìn)行，它不改變?nèi)蝿?wù)分配的處理器結(jié)果。

對(duì)該個(gè)體，在兩個(gè)處理器上的任務(wù)調(diào)度順序可以表示成：

2.1.4 任務(wù)開(kāi)始時(shí)間和完工時(shí)間

按照任務(wù)在調(diào)度序列TS的順序，依次計(jì)算每個(gè)任務(wù)開(kāi)始執(zhí)行時(shí)間和完工時(shí)間，可得到每個(gè)處理器的完工時(shí)間和任務(wù)的總完工時(shí)間。假設(shè)TS序列中第q個(gè)執(zhí)行的任務(wù)為i，其分配到的處理器為pi，任務(wù)i能夠開(kāi)始執(zhí)行的先決條件是其資源約束和依賴約束同時(shí)被滿足，具體如下：

（1）資源約束規(guī)則。由于每個(gè)處理器一個(gè)時(shí)刻只能執(zhí)行一個(gè)任務(wù)，即分配到pi上的任務(wù)調(diào)度序列必須順序執(zhí)行，因此i在pi上的開(kāi)始時(shí)間必須不小于i前一個(gè)任務(wù)k的完工時(shí)間。假設(shè)k的開(kāi)始時(shí)間為sk，執(zhí)行時(shí)間為tk，則該約束確定的i的開(kāi)始時(shí)間應(yīng)該滿足：

（2）依賴約束規(guī)則。任務(wù)i能在pi開(kāi)始執(zhí)行的另一個(gè)約束為其前繼任務(wù)集合pre（i）中的每一個(gè)任務(wù)j都完成，且當(dāng)i與j不在同一個(gè)處理器時(shí)，i與j之間的通信任務(wù)也必須完成，即要滿足任務(wù)之間的前后依賴關(guān)系。根據(jù)該約束確定的i的開(kāi)始時(shí)間應(yīng)該滿足：

最后，根據(jù)上述兩個(gè)規(guī)則確定的任務(wù)i的最早開(kāi)始執(zhí)行時(shí)間為

在得到每個(gè)任務(wù)的開(kāi)始執(zhí)行時(shí)間和完工時(shí)間后，就可以給出任務(wù)的分配和調(diào)度圖。圖3給出圖1所示11個(gè)任務(wù)的一個(gè)可能分配和調(diào)度圖。

圖3 任務(wù)分配和調(diào)度圖

2.1.5 初始種群優(yōu)化

為更好地生成高質(zhì)量的初始種群，本文還進(jìn)行了初始種群優(yōu)化，其思想是在完工時(shí)間最長(zhǎng)的處理器plong上選取一個(gè)任務(wù)分配到完工時(shí)間最短的處理器pshort上，重復(fù)進(jìn)行若干次。具體步驟如下：

步驟1 若plong上存在一個(gè)任務(wù)i，使得i與在i后執(zhí)行且分配到plong的所有任務(wù)都沒(méi)有前后繼依賴關(guān)系，那么將i分配到pshort上，這樣明顯可以縮短完工時(shí)間；若不存在這樣的i，則在plong上隨機(jī)選取一個(gè)任務(wù)分配到pshort上。

需要注意的是，由于任務(wù)i的處理器分配發(fā)生了改變，必須修改任務(wù)i的基因值。假設(shè)任務(wù)i原基因值為vi，原分配的處理器號(hào)為pi，新分配的處理器號(hào)為p′i，則新基因值v′i如式（7）所示。

這樣，不僅任務(wù)的新基因值和分配到的處理器符合式（3），同時(shí)保證了新基因值不會(huì)與其他任務(wù)的基因值重復(fù)，確保了基因值的唯一性。同時(shí)可以證明，該層的任務(wù)調(diào)度序列不會(huì)發(fā)生改變，因此總的任務(wù)調(diào)度序列不變。

步驟2 計(jì)算新個(gè)體的任務(wù)完工時(shí)間并與原來(lái)的完工時(shí)間進(jìn)行對(duì)比，如果新完工時(shí)間更短，則用新個(gè)體代替原個(gè)體；反之，保持原個(gè)體不變。

圖3所示調(diào)度中，p1上不存在任務(wù)i，使得i與在i后執(zhí)行且分配到p1的所有任務(wù)都沒(méi)有前后繼依賴關(guān)系。所以只能在p1上隨機(jī)選取一個(gè)任務(wù)（假設(shè)選擇了任務(wù)6），重新分配到p2上。任務(wù)6的原基因值為9，因此新基因值為9＋2－1＝10。同h值有6，7，8三個(gè)任務(wù)，該層的基因序列由｛9，12，21｝變?yōu)椋?0，12，21｝，依據(jù)第2.1.3節(jié)得到該層的調(diào)度順序仍為：8→7→6，沒(méi)有發(fā)生改變，因此總的任務(wù)調(diào)度序列TS保持不變。由此可以得到新的調(diào)度圖，如圖4所示，任務(wù)的完工時(shí)間由18變?yōu)?6，得到了優(yōu)化，因此用該新個(gè)體代替原個(gè)體。

圖4 重新調(diào)度的任務(wù)圖

步驟3 重復(fù)前兩步，進(jìn)行足夠多次后（本文取10次）就可以得到較優(yōu)個(gè)體。

以上3步，可以有效地減少個(gè)體的總完工時(shí)間，提高個(gè)體質(zhì)量。對(duì)種群中所有個(gè)體進(jìn)行相同的操作，這樣就可以得到高質(zhì)量的初始種群。圖5為初始種群的流程圖。

圖5 初始種群流程圖

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)表示個(gè)體對(duì)生存環(huán)境的適應(yīng)能力，個(gè)體的適應(yīng)度越大，則該個(gè)體被遺傳到下一代的概率就越大。對(duì)于多核處理器的任務(wù)調(diào)度，可以用總?cè)蝿?wù)的完工時(shí)間（也就是最后一個(gè)執(zhí)行的任務(wù)的完成時(shí)間）來(lái)評(píng)價(jià)其適應(yīng)能力，個(gè)體Vi適應(yīng)度函數(shù)如下：

式中，span（Vi）表示個(gè)體Vi的完工時(shí)間，圖4中任務(wù)的完工時(shí)間為16。

2.3 遺傳搜索過(guò)程

2.3.1 輪盤(pán)賭選擇

選擇是從當(dāng)前種群中選取適應(yīng)值高的個(gè)體進(jìn)行交叉、變異，將優(yōu)良基因遺傳給后代。本文用輪盤(pán)賭旋轉(zhuǎn)法進(jìn)行選擇，如圖6所示，方法如下：

（1）在［0，1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r；（2）若r≤q（1），則個(gè)體V1被選中；

（3）若q（k－1）＜r≤q（k）（2≤k≤SN，SN為種群規(guī)模），則個(gè)體Vk被選中。

其中，q（i）為染色體的累計(jì)概率，計(jì)算公式為

P（Vi）為個(gè)體Vi被挑選的概率，其公式為

圖6 輪盤(pán)賭選擇

2.3.2 基于TS的隨機(jī)編號(hào)交叉

交叉可以增加種群多樣性，提高種群搜索能力。鑒于GA的廣域搜索能力較強(qiáng)，TS的局部搜索能力較強(qiáng)，可以將兩者混合對(duì)交叉操作進(jìn)行改進(jìn)，也就是把TS的“禁忌”和“特赦”思想引入到GA的交叉步驟中。

基于TS的隨機(jī)編號(hào)交叉步驟如下：

步驟1 初始化。規(guī)定種群中所有個(gè)體的最大適應(yīng)度值為初始渴望水平；個(gè)體的適應(yīng)度值為禁忌表中的元素；禁忌表長(zhǎng)度為l。

步驟2 根據(jù)交叉率選擇相鄰兩個(gè)父代進(jìn)行基于隨機(jī)編號(hào)交叉操作，產(chǎn)生兩個(gè)子代。對(duì)于進(jìn)行交叉的兩個(gè)個(gè)體V1，V2，在V1中隨機(jī)選擇一個(gè)初始交叉點(diǎn)和截止交叉點(diǎn)，交叉總?cè)蝿?wù)數(shù)為l，該初始交叉點(diǎn)和截止交叉點(diǎn)也是V2的初始交叉點(diǎn)和截止交叉點(diǎn)。將V1截取的一小段個(gè)體的l個(gè)任務(wù)隨機(jī)編號(hào)1～l；V2同理。然后，將這兩小段編號(hào)一樣的任務(wù)的基因值進(jìn)行交換，最后再將這兩小段整體互換，這樣就可以得到新的個(gè)體S1，S2，如圖7所示。

圖7 基于隨機(jī)編號(hào)的交叉

步驟3 如果子代個(gè)體適應(yīng)度值大于渴望水平，則破禁，該個(gè)體進(jìn)入下一代；同時(shí)，更新禁忌表和渴望水平，將該個(gè)體的適應(yīng)度值設(shè)為新的渴望水平。

步驟4 如果沒(méi)有破禁，檢測(cè)子代個(gè)體適應(yīng)度值是否在禁忌表中。如果不在，該個(gè)體進(jìn)入下一代，同時(shí)更新禁忌表；反之，舍棄該個(gè)體，選擇相應(yīng)的父本進(jìn)入下一代。

步驟5 返回步驟2，直至種群中所有個(gè)體完成交叉。

2.3.3 基于SA的變異

變異提供給種群新的基因，提高了種群的多樣性。GA的局部搜索能力差，變異后個(gè)體的質(zhì)量不高；將SA算法添加到遺傳算法中，利用SA算法局部搜索能力強(qiáng)的優(yōu)點(diǎn)，優(yōu)化每個(gè)個(gè)體的質(zhì)量。

基于SA的變異步驟如下：

步驟1 初始化。在種群中隨機(jī)選取個(gè)體Vi為初始解。給定初始溫度T0，終止溫度Tf，降溫值ΔT，內(nèi)循環(huán)次數(shù)n（Tk）。令Tk＝T0，最優(yōu)解Vbest初始化為Vbest＝Vi。

步驟2 對(duì)個(gè)體Vi進(jìn)行變異，變異后的個(gè)體為Vj，則完工時(shí)間增量Δf＝span（Vj）－span（Vi）。

變異步驟：在個(gè)體V中，隨機(jī)選擇兩個(gè)不同的變異點(diǎn)，然后交換其基因值，就可以得到一個(gè)新的個(gè)體S，如圖8所示。

圖8 變異

步驟3 如果Vj的完工時(shí)間小于Vbest的完工時(shí)間，更新Vbest＝Vj。

步驟4 若Δf＜0，則無(wú)條件轉(zhuǎn)移：Vi＝Vj；若Δf＞0，則進(jìn)行有條件轉(zhuǎn)移：隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)ξ＝U（0，1），如果則Vi＝Vj，反之Vi保持不變。

步驟5 若達(dá)到熱平衡狀態(tài)（內(nèi)循環(huán)次數(shù)大于n（Tk）），進(jìn)行步驟6，否則轉(zhuǎn)步驟2。

步驟6 降低Tk，降溫函數(shù)為：Tk＝Tk－ΔT。若Tk＜Tf，則算法停止，輸出Vbest；否則轉(zhuǎn)步驟2。

對(duì)交叉后的種群中的每個(gè)個(gè)體都進(jìn)行上述操作，最終可以得到變異后新的種群。通過(guò)SA，新種群中每個(gè)個(gè)體的適應(yīng)度值均得到有效的提高，避免了常規(guī)變異造成個(gè)體變差的可能性，提高了GA的性能。

2.3.4 變異后調(diào)度圖

需要注意的是，變異使得某些任務(wù)的基因值發(fā)生了改變，這些任務(wù)分配到的處理器也就相應(yīng)地發(fā)生變化，由式（3）可得到這些任務(wù)分配到的新處理器。根據(jù)第2.1.3節(jié)，可得到任務(wù)調(diào)度序列TS；根據(jù)第2.1.4節(jié)可得到新一代種群中所有個(gè)體的任務(wù)調(diào)度圖，也就知道了其最優(yōu)個(gè)體完工時(shí)間。

2.3.5 算法結(jié)束

重復(fù)進(jìn)行上述步驟到規(guī)定的代數(shù)，就可以得到最優(yōu)任務(wù)調(diào)度圖及最短完工時(shí)間。圖1的DAG圖，根據(jù)上述算法，得到的最優(yōu)調(diào)度圖如圖9所示，其完工時(shí)間為14。

圖9 最優(yōu)調(diào)度圖

本文所述的遺傳算法流程圖如圖10所示。

圖10 遺傳算法流程圖

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

3.1 實(shí)驗(yàn)參數(shù)

在進(jìn)行仿真實(shí)驗(yàn)時(shí)，可以隨機(jī)生成DAG圖，規(guī)定所有任務(wù)的計(jì)算時(shí)間總和與通信開(kāi)銷(xiāo)的總和的比值為0.5，且每個(gè)任務(wù)的計(jì)算時(shí)間和任務(wù)間通信時(shí)間的取值范圍為［2，20］，其他仿真實(shí)驗(yàn)參數(shù)如表1所示。用MATLAB 2012b進(jìn)行仿真，并將本文的MHGA算法和標(biāo)準(zhǔn)HGA算法［13］、Hwang的PGA算法［15］進(jìn)行比較。為了消除數(shù)據(jù)隨機(jī)性對(duì)結(jié)果的影響，將實(shí)驗(yàn)數(shù)據(jù)取30次平均，可以得到最終的對(duì)比結(jié)果。

表1 實(shí)驗(yàn)參數(shù)設(shè)定

3.2 仿真結(jié)果

本文提出的MHGA算法使用了初始化種群和混合遺傳算法兩部分操作，為了更好地研究MHGA的性能，這里將該算法拆分成兩部分。MHGA-1只進(jìn)行初始化種群，沒(méi)有采用改進(jìn)混合遺傳算法；MHGA-2只進(jìn)行改進(jìn)混合遺傳算法，沒(méi)有初始化種群。

圖11是不同任務(wù)數(shù)完工時(shí)間的比較。從圖11中可以看到，本文提出的MHGA算法得到的完工時(shí)間是最優(yōu)的，即MHGA尋找最優(yōu)解的能力最強(qiáng)。PGA次之，HGA搜索最優(yōu)解的能力最差。MHGA相比于MHGA-1，性能得到較大提高；相比于MHGA-2相差不多，但也得到了改善。

圖11 不同任務(wù)數(shù)的完工時(shí)間比較

圖12為3種算法在100代的完工時(shí)間收斂過(guò)程。從圖12可以看出，在收斂值方面，本文提出的MHGA算法的收斂值明顯優(yōu)于HGA和PGA；在收斂速度方面，HGA最快，MHGA次之，PGA最慢。HGA算法因?yàn)槠溥^(guò)早收斂，造成其收斂值最大，即搜索最優(yōu)解能力最差。PGA算法不僅收斂較慢，其收斂值也高于MHGA算法。由于MHGA優(yōu)化了初始種群，使用了混合遺傳算法，導(dǎo)致此算法整體上每代結(jié)果均優(yōu)于其他兩種算法。

圖12 最小完工時(shí)間的收斂過(guò)程

MHGA-1只初始化了種群，盡管在第一代的結(jié)果較優(yōu)，但隨著代數(shù)的增加，其搜索能力變差且收斂速度較慢。MHGA-2采用了混合遺傳算法，使得種群多樣性增加，個(gè)體的適應(yīng)度值也得到提高。隨著代數(shù)的增加，其最優(yōu)解的搜索能力逐漸變好。由于沒(méi)有初始化種群，使得收斂值大于MHGA，且收斂速度較慢，搜索時(shí)間更長(zhǎng)。而本文的MHGA綜合了MHGA-1和MHGA-2兩者優(yōu)點(diǎn)，不僅收斂值更優(yōu)，其收斂速度也得到了提高，提升了遺傳算法的性能。

以上是取30次實(shí)驗(yàn)求平均得到的結(jié)果，為了更好地分析每次遺傳的情況，隨機(jī)選取1次實(shí)驗(yàn)來(lái)進(jìn)行分析（N＝35），由此可以得到每代的任務(wù)完工時(shí)間，如圖13所示（圖13中，MHGA算法輸出的每代完工時(shí)間是圖10中種群S3的最優(yōu)個(gè)體的完工時(shí)間）。

圖13 每代的完工時(shí)間（N＝35）

由圖13可以看出，HGA算法每代結(jié)果的動(dòng)態(tài)范圍最小，其算法達(dá)到較優(yōu)結(jié)果后，很難再跳出去，從而使得算法早熟，其結(jié)果易于陷入局部最優(yōu)。PGA算法采用了基于優(yōu)先級(jí)的編碼（priority-based multi-chromosome，PMC）、權(quán)重交叉（weight mapping crossover，WMX）等操作，使得算法每代結(jié)果的動(dòng)態(tài)范圍最大，可以避免算法早熟，但其收斂速度較慢，且得到的最優(yōu)解較差。MHGA-1初始化了種群，盡管第一代的結(jié)果較優(yōu)，但最優(yōu)解的搜索能力較差。MHGA-2采用混合遺傳算法，但由于沒(méi)有初始化種群，其搜索時(shí)間更長(zhǎng)，收斂速度較慢，最優(yōu)解也差于MHGA。MHGA綜合了MHGA-1和MHGA-2的優(yōu)點(diǎn)，不僅收斂值更優(yōu)，其收斂速度也得到了提高。

4 結(jié)束語(yǔ)

本文提出的MHGA在解決并行多核任務(wù)的分配和調(diào)度時(shí)，其性能優(yōu)于其他算法的原因在于：首先利用啟發(fā)式方法對(duì)初始種群進(jìn)行分層分配和調(diào)度，產(chǎn)生質(zhì)量較高的初始種群；其次，使用基于TS的隨機(jī)編號(hào)交叉，提高了種群的多樣性；最后，采用基于SA的變異，提高個(gè)體的質(zhì)量，所有個(gè)體的適應(yīng)度值得到了提高。仿真結(jié)果表明，MHGA能夠得到更短的任務(wù)完工時(shí)間，具有較強(qiáng)的最優(yōu)解搜索能力，可用于實(shí)際應(yīng)用。當(dāng)然，MHGA也有不足，主要表現(xiàn)在：①僅適用于同構(gòu)MPSoC系統(tǒng)；②算法參數(shù)不能夠自適應(yīng)調(diào)整。因此，未來(lái)希望將本文算法擴(kuò)展到異構(gòu)多核系統(tǒng)中，同時(shí)一些關(guān)鍵參數(shù)能夠自適應(yīng)調(diào)整，從而增強(qiáng)MHGA的適用范圍和性能。

［1］Lee J，Chung M K，Cho Y G，et al.Mapping and scheduling of tasks and communica-tions on many-core soc under local memory constraint［J］.IEEE Trans.on Computer-aided Design of integrated circuits and System，2013，32（11）：1748－1761.

［2］Venugopalan S，Sinnen O.ILP formulations for optimal task scheduling with communi-cation delays on parallel systems［J］.IEEE Trans.on Parallel and Distributed Systems，2014，（99）：1－10.

［3］Topcuoglu H，Hariri S，Wu M Y.Performance-effective and low-complexity task scheduling for heterogeneous compu-ting［J］.IEEE Trans.on Parallel and Distributed Systems，2002，13（3）：260－274.

［4］Fan M，Quan G.Harmonic-aware multi-core scheduling for fixedpriority real-time systems［J］.IEEE Trans.on Parallel and Distributed Systems，2014，25（6）：1476－1488.

［5］Lan Z，Sun S X.Task scheduling genetic algorithm based on the knowledge of critical path［J］.Computer Applications，2008，28（2）：272－274.（蘭舟，孫世新.基于關(guān)鍵路徑知識(shí)的任務(wù)調(diào)度遺傳算法［J］.計(jì)算機(jī)應(yīng)用，2008，28（2）：272－274.）

［6］Chopra N，Singh S.HEFT based workflow scheduling algorithm for cost optimization within deadline in hybrid clouds［C］∥Proc.of the 4th International Conference on Computing，Communications and Networking Technologies，2013：1－6.

［7］TabakE K，Cambazoglu B B，Aykanat C.Improving the performance of independent task assignment heuristics minmin，maxmin and sufferage［J］.IEEE Trans.on Parallel and Distributed Systems，2014，25（5）：1244－1256.

［8］Omara F A，Arafa M M.Genetic algorithms for task scheduling problem［J］.Journal of Parallel and Distributed Computing，2010，70（1）：13－22.

［9］Wen Y，Xu H，Yang J D.A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks［J］.Journal of Parallel and Distributed Computing，2011，71（11）：1518－1531.

［10］Zhou S E，Lei H.Based on the improved genetic-simulated annealing algorithm for task scheduling orderly［J］.Micro-electronics and Computer，2006，23（10）：62－64.（周雙娥，雷輝.基于改進(jìn)的遺傳－模擬退火的有序任務(wù)調(diào)度算法［J］.微電子學(xué)與計(jì)算機(jī)，2006，23（10）：62－64.）

［11］Li J M，Zhang B，Wang X.Heterogeneous multiprocessor task scheduling based on particle swarm optimization algorithm［J］.Application Research of Computers，2012，29（10）：3621－3624.（李靜梅，張博，王雪.基于粒子群優(yōu)化的異構(gòu)多處理器任務(wù)調(diào)度算法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（10）：3621－3624.）

［12］Faragardi H R，Shojaee R，Yazdani N.Reliability-aware task allocation in distributed computing systems using hybrid simu-lated annealing and tabu search［C］∥Proc.of the 14th IEEE International Conference on High Performance Computing and Communication ＆IEEE9th International Conference on Embedded Software and Systems，2012：1088－1095.

［13］Hou E，Ansari N，Ren H.A genetic algorithm for multiprocessor scheduling［J］.IEEE Trans.on Parallel and Distributed Systems，1994，5（2）：113－120.

［14］Peng M M，Huang L.Task scheduling and load balancing for multi-processors［J］.Microelectronics and Computer，2011，28（11）：35－39.（彭蔓蔓，黃亮.多核處理器中任務(wù)調(diào)度與負(fù)載均衡的研究［J］.微電子學(xué)與計(jì)算機(jī)，2011，28（11）：35－39.）

［15］Hwang R，Gen M，Katayama H.A comparison of multiprocessor task schedu-ling algorithms with communication costs［J］.Computers and Operations Research，2008，35（3）：976－993.

［16］Zhong Q X，Xie T，Chen H W.Task matching and scheduling by genetic algorithm［J］.Journal of Computer Rese-arch and Development，2000，37（10）：1197－1203.（鐘求喜，謝濤，陳火旺.基于遺傳算法的任務(wù)分配與調(diào)度［J］.計(jì)算機(jī)研究與發(fā)展，2000，37（10）：1197－1203.）

［17］Yuan X L，Zhong M Y.Improved genetic algorithms for parallel task scheduling［J］.Computer Engineering and Applications，2011，47（10）：56－59.（袁雪莉，鐘明洋.改進(jìn)遺傳算法的并行任務(wù)調(diào)度［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（10）：56－59.）

Modified hybrid genetic algorithm for parallel task scheduling of multiprocessors

YAO Ying-biao，WANG Xuan
（College of Communication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

Parallel task scheduling of multiprocessors is a hot research topic，and also is a well known NP-hard problem.Focusing on this problem，a modified hybrid genetic algorithm（MHGA）is proposed，in which the heuristic algorithm，tabu search（TS）algorithm and simulated annealing（SA）algorithm are integrated.The modifications of the MHGA include：using the hierarchical scheduling based heuristic method to initialize the population so as to improve the quality of initial population；employing the TS based random number crossover to enhance the diversity of the population；adopting the SA based mutation to improve the quality of the individual.Experimental results show that the MHGA can obtain smaller task scheduling time and have ability to fast search better solution in comparison with other GAs.

genetic algorithm（GA）；tabu search（TS）；simulated annealing（SA）；parallel scheduling；multiprocessor

TP 332

A

10.3969／j.issn.1001-506X.2015.08.32

姚英彪（1976－），男，副教授，博士，主要研究方向?yàn)橛?jì)算機(jī)體系結(jié)構(gòu)、嵌入式系統(tǒng)設(shè)計(jì)。

E-mail：yaoyb＠hdu.edu.cn

王 璇（1991－），女，碩士研究生，主要研究方向?yàn)槎嗪颂幚砥魅蝿?wù)調(diào)度。

E-mail：15158116166＠163.com

1001－506X201508－1928－08

網(wǎng)址：www.sys－ele.com

2014－09－11；

2014－10－30；網(wǎng)絡(luò)優(yōu)先出版日期：2015－01－20。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150120.1050.006.html

國(guó)家自然科學(xué)基金（61100044），中國(guó)浙江省科技廳科技計(jì)劃項(xiàng)目（2013C31100）資助課題