程小輝 童輝輝 康燕萍*

1(桂林理工大學(xué)信息科學(xué)與工程學(xué)院 廣西 桂林 541006) 2(廣西嵌入式技術(shù)與智能系統(tǒng)重點實驗室 廣西 桂林 541006)

0 引 言

隨著高性能計算的發(fā)展和AI、機(jī)器學(xué)習(xí)、云技術(shù)等技術(shù)的興起,結(jié)構(gòu)單一的處理器系統(tǒng)無法同時滿足應(yīng)用程序的并行計算等多樣化需求[1]。因此異構(gòu)多核處理器應(yīng)運而生,逐步進(jìn)入市場。異構(gòu)多核處理器是由多種類型和不同計算能力的處理核心組成的非對稱多核處理器,如何協(xié)調(diào)這些處理核心間的工作,將任務(wù)合理劃分,分配到處理器上執(zhí)行,是異構(gòu)多核處理器研究的關(guān)鍵。任務(wù)調(diào)度技術(shù)的好壞決定系統(tǒng)執(zhí)行效率的高低,異構(gòu)多核處理器領(lǐng)域中針對任務(wù)調(diào)度策略的研究也是近幾年眾多學(xué)者關(guān)注和研究的熱點。

任務(wù)調(diào)度問題已經(jīng)被證明為NP-hard 問題[2]。目前在異構(gòu)多核處理器間任務(wù)調(diào)度的研究領(lǐng)域中,應(yīng)用較多的有調(diào)度技術(shù)[3-6]、遺傳算法和粒子群算法等啟發(fā)式算法[7-12]。根據(jù)任務(wù)優(yōu)先權(quán)大小策略來構(gòu)造調(diào)度序列,合理分配任務(wù)至處理器上,基于列表調(diào)度算法來迭代尋找最優(yōu)解,在滿足任務(wù)間依賴的條件下取得任務(wù)的最短完成時間。列表調(diào)度技術(shù)具有時間復(fù)雜度和空間復(fù)雜度低的優(yōu)點,但是對于解質(zhì)量的優(yōu)劣無法保證。粒子群算法和遺傳算法等智能優(yōu)化算法通過不斷搜索鄰域來尋找最優(yōu)解,在一定迭代中找得優(yōu)質(zhì)解的能力較強(qiáng),深受異構(gòu)多核處理器任務(wù)調(diào)度研究領(lǐng)域的歡迎。然而,遺傳算法操作復(fù)雜、實時性差,難以保證尋優(yōu)時間;粒子群算法雖然操作簡單、容易實現(xiàn),但易出現(xiàn)粒子陷入“早熟”現(xiàn)象和后期陷入局部最優(yōu)等困境。

麻雀搜索算法[13]是由中國學(xué)者Xue等提出的一種最新的群體智能優(yōu)化算法,其算法思想來自于麻雀的覓食行為和反捕食行為的啟發(fā)。該算法主要具有數(shù)學(xué)模型簡單、調(diào)用參數(shù)少、收斂速度快等特點。目前該算法在函數(shù)優(yōu)化和解決多目標(biāo)問題上有了初步應(yīng)用,但在異構(gòu)多核處理器任務(wù)調(diào)度領(lǐng)域中對于該算法的使用還是空白階段?；谏鲜霰尘?在研究異構(gòu)多核處理器平臺的任務(wù)調(diào)度問題中,本文提出一種新的任務(wù)調(diào)度方法,使用麻雀搜索算法進(jìn)行迭代尋優(yōu),在滿足任務(wù)間約束依賴的條件下,使得調(diào)度任務(wù)完成時間最小,提升系統(tǒng)的執(zhí)行效率。為了驗證該算法的性能和可行性,對該算法與遺傳算法和改進(jìn)的粒子群算法進(jìn)行了實驗對比,結(jié)果表明該算法的調(diào)度能力更加優(yōu)異。

1 異構(gòu)多核處理器任務(wù)調(diào)度研究

1.1 異構(gòu)多核系統(tǒng)任務(wù)調(diào)度問題描述

異構(gòu)多核處理器由核架構(gòu)模型、任務(wù)調(diào)度模型和任務(wù)調(diào)度算法三個部分組成,三者關(guān)系如圖1所示。系統(tǒng)模型是根據(jù)系統(tǒng)的硬件環(huán)境搭建的數(shù)學(xué)模型,反映了處理核心的處理指令、執(zhí)行操作、時間控制和數(shù)據(jù)處理能力的相關(guān)信息;任務(wù)調(diào)度模型是指根據(jù)子任務(wù)之間的約束關(guān)系和任務(wù)本身的調(diào)度屬性建立的數(shù)據(jù)模型,它反映了任務(wù)的自身信息和任務(wù)間執(zhí)行的順序;任務(wù)調(diào)度算法指在系統(tǒng)模型和任務(wù)模型間建立起映射關(guān)系的約束規(guī)則。圖1中,TM(Task scheduling model)表示任務(wù)調(diào)度模型,PM(Processor model)表示核架構(gòu)模型,TPA(Task scheduling algorithm)表示任務(wù)調(diào)度算法。

圖1 異構(gòu)多核處理器任務(wù)調(diào)度模型

1.2 任務(wù)調(diào)度模型描述

異構(gòu)多核環(huán)境下,不同處理核心的計算能力存在差異,任務(wù)在各處理器中的執(zhí)行時間以及任務(wù)間產(chǎn)生的通信銷量不同,因此,在研究任務(wù)調(diào)度問題上,一般采用有向無環(huán)圖(DAG)[14]來表述任務(wù)之間的依賴關(guān)系。為了更清晰描述問題,定義異構(gòu)多核處理器環(huán)境下有m個處理器和n個任務(wù)。其中P={P1,P2,…,Pm}為m個處理核心,節(jié)點集合T={T1,T2,…,Tn}表示有n個任務(wù),Ti(1≤i≤n)表示第i個任務(wù)。節(jié)點間的帶權(quán)有向邊代表任務(wù)間存在依賴關(guān)系,用C={…Ci,j…}表示。C表示任務(wù)間的通信數(shù)據(jù)集合,Ci,j是任務(wù)間的有向邊權(quán)值,代表著兩任務(wù)間的通信開銷。W={…WTi,pj…},表示任務(wù)在每個計算核心上處理時間的集合,WTi,pj表示任務(wù)Ti在處理核pj上的計算開銷。對相關(guān)的調(diào)度屬性做出如下定義:Tentry代表DAG圖中的入口任務(wù)節(jié)點;Texit代表DAG圖的出口任務(wù)節(jié)點;Pred(Ti) 代表任務(wù)Ti的前驅(qū)任務(wù)節(jié)點集合,若Pred(Ti)=?,則該任務(wù)為入口任務(wù)節(jié)點;Succ(Ti)表示任務(wù)Ti的后繼任務(wù)節(jié)點,若Succ(Ti)=?意味著該任務(wù)為出口任務(wù)。

如圖2所示,舉例一個DAG圖,任務(wù)數(shù)為9。T1到T9表示任務(wù),有向邊上的值用來表示通信開銷,編號旁邊數(shù)字代表任務(wù)處理需要的時間。同一處理器中的任務(wù)之間沒有通信開銷;不同處理器間任務(wù)具有依賴約束條件,通信開銷不可忽略。例如,T1是T4的前驅(qū)任務(wù),它們的處理時間分別為2和4,若它們在同一處理器上,通信銷量為0,否則為1。

圖2 DAG任務(wù)圖實例

在考慮到任務(wù)間互聯(lián),具有約束關(guān)系的前提下,將n個任務(wù)分配到m個處理器上執(zhí)行完成最短時間作為本文研究目標(biāo), 并且要滿足以下約束條件:(1) 每個處理器都可執(zhí)行任務(wù);(2) 同一時刻,任務(wù)無法被多個處理器執(zhí)行;(3) 任務(wù)間滿足依賴約束條件。任務(wù)間有先序后繼關(guān)系。任務(wù)調(diào)度的目標(biāo)函數(shù)描述如下:

makespan(f)=min{makespan(s)}

(1)

式中:s表示為調(diào)度的任意一種方案,makespan(s)指在s調(diào)度方案中所有任務(wù)的最晚完成時間,也稱作調(diào)度長度;makespan(f)表示求得一個最佳調(diào)度方案f,在滿足任務(wù)間互聯(lián)和通信的前提下,任務(wù)被合理分配到各處理器上處理,使所有任務(wù)執(zhí)行的時間最短,即調(diào)度長度最短。

2 麻雀搜索算法

眾所周知,群智能優(yōu)化算法因其不受目標(biāo)函數(shù)可微、可導(dǎo)、連續(xù)性等特性的限制,具有較好的穩(wěn)定性、高效性和收斂速度快等優(yōu)點。正是如此,群智能優(yōu)化算法在求解實際工程設(shè)計優(yōu)化問題中越來越受歡迎。

2.1 麻雀覓食行為描述

麻雀搜索算法主要模擬麻雀群覓食的過程,麻雀是群居類鳥類動物,根據(jù)其覓食特點,可分為探索者(發(fā)現(xiàn)者)和加入者(追隨者),定義為發(fā)現(xiàn)者-加入者行為策略,同時疊加了麻雀偵查預(yù)警機(jī)制。所有麻雀都只有一個屬性——位置,代表麻雀找到食物的位置,每只麻雀有三種可能行為:(1) 作為發(fā)現(xiàn)者:負(fù)責(zé)尋找食物和引導(dǎo)整個群體的移動;(2) 作為加入者:通過追隨發(fā)現(xiàn)者來獲取食物;(3) 警戒偵查:發(fā)現(xiàn)危險,告知同伴,并且放棄食物,轉(zhuǎn)移到新的覓食區(qū)域。除此以外,有研究表明,麻雀深諳行為策略,可在發(fā)現(xiàn)者和加入者兩種角色中任意轉(zhuǎn)換。

2.2 麻雀搜索算法數(shù)學(xué)描述

麻雀搜索算法的流程首先初始化種群并且定義相關(guān)參數(shù),輸出當(dāng)前麻雀的全局最優(yōu)位置和全局最優(yōu)適應(yīng)度值,并根據(jù)當(dāng)前迭代次數(shù)小于最大迭代次數(shù)時,對適應(yīng)度值排列次序,找出當(dāng)前最好和最差的個體。根據(jù)覓食規(guī)則,發(fā)現(xiàn)者進(jìn)行位置的更新。加入者則通過圍繞在發(fā)現(xiàn)者周圍獲取食物或者從發(fā)現(xiàn)者的食物中獲取食物,也可以通過爭奪獲取食物,并更新其位置。當(dāng)群體的一些麻雀感知到危險后,也會進(jìn)行相應(yīng)位置的更新。

假設(shè)在d維解空間里有n只麻雀,X代表麻雀的位置。發(fā)現(xiàn)者職責(zé);(1) 為種群尋找食物;(2) 為加入者指引覓食方向。根據(jù)這一規(guī)則,發(fā)現(xiàn)者的位置更新如下:

(2)

式中:itermax表示最大迭代次數(shù),t為當(dāng)前迭代數(shù);Xij表示第i個麻雀在j維中的位置信息;R2和ST分別代表預(yù)警值和安全值,取值范圍分別為R2∈[0,1],ST∈[0.5,1.0];Q和α∈(0,1]代表隨機(jī)數(shù),Q服從正態(tài)分布;L表示所有元素為1的1×d矩陣。由式(2):R2

加入者(追隨者)的位置更新描述如下:

(3)

式中:Xp是當(dāng)前發(fā)現(xiàn)者占據(jù)的最優(yōu)位置,Xworst則表示當(dāng)前全局最差的位置;A表示一個1×d矩陣,矩陣內(nèi)元素隨機(jī)賦值為1或-1,并且A+=AT(AAT)-1。若i>n/2,則代表第i個加入者未得到食物,適應(yīng)度低,處于饑餓狀態(tài),此時需要飛往其他地方覓食來獲得能量。

當(dāng)意識到危險時,麻雀種群會做出反捕食行為,其數(shù)學(xué)表達(dá)式如下:

(4)

式中:fi代表當(dāng)前麻雀個體的適應(yīng)度值;fg和fw分別是當(dāng)前全局最佳和最差的適應(yīng)度值;Xbest代表當(dāng)前的全局最優(yōu)位置;作為波長控制參數(shù)的β是一個標(biāo)準(zhǔn)的0和方差分布的隨機(jī)數(shù);K∈[-1,1]是一個隨機(jī)數(shù),代表麻雀捕食方向;ε是最小的常數(shù),以避免分母出現(xiàn)零。

fi>fg時,代表此時的麻雀位于種群邊緣,極易被捕食者攻擊。

fi=fg時,表明位于種群中間的麻雀意識到危險,需向其他麻雀靠攏以避免自己被捕食的風(fēng)險。

SSA之所以擁有良好的優(yōu)化性能與麻雀種群內(nèi)部靈活的覓食機(jī)制聯(lián)系密不可分。首先,發(fā)現(xiàn)者能夠為整個種群的覓食提供正確的引導(dǎo),即探索階段;其次,麻雀察覺到危險后采取的反捕食行為增強(qiáng)了種群的局部搜索能力,即開發(fā)階段;再者,加入者或者追隨發(fā)現(xiàn)者進(jìn)行局部搜索,或者改變自身的覓食行為轉(zhuǎn)變?yōu)榘l(fā)現(xiàn)者進(jìn)而對全局進(jìn)行搜索。由此可見,該算法具有平衡局部開發(fā)和全局搜索的能力,以及收斂速度快、穩(wěn)定性強(qiáng)等特點,為解決復(fù)雜的優(yōu)化問題提供一種全新的方法。

3 基于麻雀搜索算法的異構(gòu)多核任務(wù)調(diào)度

3.1 麻雀個體編碼

異構(gòu)多處理器任務(wù)調(diào)度問題是一種屬于離散范疇的優(yōu)化問題,而SSA是一種連續(xù)算法,主要用來解決尋解連續(xù)化的問題。在異構(gòu)多核環(huán)境下,任務(wù)調(diào)度算法在考慮如何提高系統(tǒng)效率的同時,如何最大限度地減少任務(wù)執(zhí)行時間、降低通信負(fù)載、提高資源利用率也是眾多學(xué)者關(guān)注的熱點。所以,使用SSA解決異構(gòu)多核處理器任務(wù)調(diào)度問題,為清晰表述任務(wù)調(diào)度的潛在解決方案,必須設(shè)計合理的編碼方案?？紤]到任務(wù)調(diào)度問題的性質(zhì),本文根據(jù)任務(wù)的優(yōu)先次序[15]設(shè)計編碼表,由隨機(jī)函數(shù)隨機(jī)產(chǎn)生小于任務(wù)總數(shù)的正整數(shù)序列,將每一只麻雀覓食位置的矢量信息轉(zhuǎn)換成滿足一定互聯(lián)結(jié)構(gòu)的任務(wù)調(diào)度序列表。麻雀覓食位置矢量定義為一個矩陣X。

(5)

對于任務(wù)i賦予的1～d的隨機(jī)數(shù),表示任務(wù)i的優(yōu)先權(quán)Pi,從而將群體中麻雀覓食的一個連續(xù)位置向量Xi=Xi,1,Xi,2,…,Xi,d]轉(zhuǎn)化為一個任務(wù)優(yōu)先級序列π=(p1,p2,…,pd)。每一個潛在解都是有效的,麻雀搜索算法在搜索進(jìn)程中不會被修改信息。表1是P1、P2兩個處理器上任務(wù)分配(見圖2)時的編碼方案。

表1 任務(wù)分配編碼方案

3.2 解碼方案

在得到麻雀覓食位置的信息之后,根據(jù)其適應(yīng)度的好壞將麻雀分類成發(fā)現(xiàn)者和跟隨者。以確定發(fā)現(xiàn)者未來新的覓食方向。本文將調(diào)度長度makespan,即任務(wù)調(diào)度的全部完成時間作為目標(biāo)函數(shù)。makespan越小,全部任務(wù)的最晚完成時間越短,調(diào)度方案可行性越高。目標(biāo)函數(shù)公式如下:

f(x)=max{eft(Ti)}i=1,2,…,n

(6)

式中:eft(Ti)表示任務(wù)Ti的最早執(zhí)行完成時間。在計算調(diào)度長度時需要對編碼方案進(jìn)行解碼,參照任務(wù)優(yōu)先級規(guī)則排列任務(wù)的調(diào)度序列,要求前驅(qū)任務(wù)被執(zhí)行完之后下一個任務(wù)才能調(diào)度;并且在滿足任務(wù)間約束依賴的條件下,高優(yōu)先任務(wù)被執(zhí)行完后,下一級任務(wù)才會被執(zhí)行,由此可以確定一個任務(wù)調(diào)度列表。

經(jīng)過以上分析可知,最后一個任務(wù)執(zhí)行完成的時間就是全部任務(wù)完成的時間,用eft(Ti)表示。ci,j表示任務(wù)在處理器上的通信開銷。若任務(wù)為入口任務(wù)節(jié)點,則任務(wù)的全部完成時間為cTi,Pj。若任務(wù)存在先序任務(wù)節(jié)點,則任務(wù)完成的全部時間為任務(wù)Ti的直接前驅(qū)任務(wù)Tj的計算產(chǎn)生的開銷與任務(wù)間通信開銷和的最大值。計算公式如下:

(7)

任務(wù)優(yōu)先級值和處理器數(shù)目被取余操作以獲得對處理器的任務(wù)分配。任務(wù)分配解碼方案如表2所示。

表2 任務(wù)分配解碼方案

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

基于麻雀搜索的任務(wù)調(diào)度算法流程如下:

(1) 讀入應(yīng)用程序的DAG圖,根據(jù)優(yōu)先級規(guī)則確定調(diào)度序列。

(2) 初始化種群及初始位置,設(shè)置SSA相關(guān)參數(shù)和迭代次數(shù)。

(3) 計算麻雀的適應(yīng)度fitness(),將種群分為發(fā)現(xiàn)者和追隨者,設(shè)置麻雀的Xbest。

(4) 計算預(yù)警值,根據(jù)預(yù)警更新發(fā)現(xiàn)者的位置。

(5) 根據(jù)式(3)更新跟隨者的位置。

(6) 根據(jù)式(4)更新發(fā)現(xiàn)危險的麻雀的位置。

(7) 判斷是否達(dá)到itermax,若達(dá)到,輸出最優(yōu)位置最優(yōu)解,算法結(jié)束;否則轉(zhuǎn)步驟(3)進(jìn)行下一輪搜索。

SSA的流程如圖3所示。

圖3 SSA流程

4 實驗仿真與分析

本文在MATLAB 2017a仿真環(huán)境下對SSA、GA和改進(jìn)的IPSO[11]的性能進(jìn)行了比較驗證,對比標(biāo)準(zhǔn)選擇任務(wù)完成時間的平均值和算法適應(yīng)度和最優(yōu)調(diào)度長度。

本文實驗參數(shù)設(shè)置如下:麻雀搜索算法,PopSize為100,MaxGen為600,ST=0.8;文獻(xiàn)[11]中改進(jìn)的粒子群算法,PopSize為100,MaxGen為600,c1=c2=2,wmax=0.9,wmin=0.4;遺傳算法: PopSize為100,MaxGen為600,pc=0.8,pm=0.3,該實驗測試了分布在5個處理器上的100、200、300、400和500個任務(wù)調(diào)度結(jié)果,并在MATLAB 2017a模擬平臺上執(zhí)行了上述三種算法。為了減少數(shù)據(jù)隨機(jī)造成的實驗結(jié)果偏差,更精確反映出算法的性能,全部任務(wù)完成時間取50次重復(fù)測試中得到最優(yōu)解的平均值。

圖4為SSA、GA和IPSO在100個任務(wù)和5個處理器條件下適應(yīng)度值-迭代次數(shù)曲線?？梢钥闯鱿噍^于GA和IPSO,SSA尋得最優(yōu)解的迭代次數(shù)更少、適應(yīng)度更低、最優(yōu)解質(zhì)量高,從而全部任務(wù)執(zhí)行完成的時間更短,SSA具有快速收斂、高效求解的特點。

圖4 算法適應(yīng)度值對比

圖5為使用以上三種算法在5個處理器和5個不同任務(wù)規(guī)模下的最優(yōu)調(diào)度長度結(jié)果,可以看出對于調(diào)度長度,SSA的調(diào)度長度最短、最優(yōu)解質(zhì)量最高,IPSO次之,GA調(diào)度長度最長、最優(yōu)解質(zhì)量最差,隨著任務(wù)數(shù)的數(shù)量增加,這種效果越明顯。GA和 IPSO易出現(xiàn)“早熟”現(xiàn)象,陷入局部最優(yōu),而SSA穩(wěn)定性更好、收斂速率高。

圖5 最優(yōu)調(diào)度長度對比

圖6為在不同任務(wù)數(shù)情況下三種算法的平均調(diào)度長度對比,即算法的平均執(zhí)行時間。由圖6可知,相較于GA和IPSO,SSA的平均執(zhí)行時間更短,尤其是任務(wù)數(shù)量增多時,這種差異越發(fā)明顯,SSA的性能明顯優(yōu)于GA和IPSO。

圖6 算法執(zhí)行時間對比

通過實驗結(jié)果與分析,在異構(gòu)多核任務(wù)調(diào)度問題上,SSA執(zhí)行的完成時間(平均解)比GA執(zhí)行時間縮短21.48%,比IPSO執(zhí)行時間縮短17.52%。由此可知,相較于其他兩種算法,SSA的收斂速度更快、尋優(yōu)能力更強(qiáng)、穩(wěn)定性更強(qiáng)、算法性能優(yōu)良,適合異構(gòu)多核處理器環(huán)境下的大規(guī)模任務(wù)調(diào)度應(yīng)用工程。

5 結(jié) 語

為了提升異構(gòu)多核處理器任務(wù)調(diào)度的效率,本文根據(jù)麻雀搜索算法提出一種新的異構(gòu)多核處理器任務(wù)調(diào)度算法,充分利用其收斂速度快的特點來獲得高精度解特性。在本文異構(gòu)環(huán)境下的任務(wù)調(diào)度中,以全部任務(wù)的執(zhí)行時間最短作為目標(biāo),根據(jù)任務(wù)優(yōu)先權(quán),設(shè)計任務(wù)分配編碼方案,將麻雀搜索空間映射到離散空間,使麻雀搜索算法適用于離散的異構(gòu)多核任務(wù)調(diào)度問題研究上。通過與任務(wù)調(diào)度研究中應(yīng)用較多的遺傳算法和改進(jìn)的粒子群算法進(jìn)行性能測試比較,SSA簡單有效、求解的質(zhì)量更高、收斂速度更快,有效縮短任務(wù)執(zhí)行時間,在異構(gòu)多核處理器任務(wù)調(diào)度領(lǐng)域中研究價值高,應(yīng)用前景廣闊。