基于麻雀搜索算法的異構多核處理器任務調度

程小輝 童輝輝 康燕萍*

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

0 引 言

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

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

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

1 異構多核處理器任務調度研究

1.1 異構多核系統(tǒng)任務調度問題描述

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

圖1 異構多核處理器任務調度模型

1.2 任務調度模型描述

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

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

圖2 DAG任務圖實例

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

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

(1)

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

2 麻雀搜索算法

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

2.1 麻雀覓食行為描述

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

2.2 麻雀搜索算法數學描述

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

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

(2)

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

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

(3)

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

當意識到危險時,麻雀種群會做出反捕食行為,其數學表達式如下:

(4)

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

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

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

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

3 基于麻雀搜索算法的異構多核任務調度

3.1 麻雀個體編碼

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

(5)

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

表1 任務分配編碼方案

3.2 解碼方案

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

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

(6)

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

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

(7)

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

表2 任務分配解碼方案

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

基于麻雀搜索的任務調度算法流程如下:

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

(2) 初始化種群及初始位置,設置SSA相關參數和迭代次數。

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

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

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

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

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

SSA的流程如圖3所示。

圖3 SSA流程

4 實驗仿真與分析

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

本文實驗參數設置如下:麻雀搜索算法,PopSize為100,MaxGen為600,ST=0.8;文獻[11]中改進的粒子群算法,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個任務調度結果,并在MATLAB 2017a模擬平臺上執(zhí)行了上述三種算法。為了減少數據隨機造成的實驗結果偏差,更精確反映出算法的性能,全部任務完成時間取50次重復測試中得到最優(yōu)解的平均值。

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

圖4 算法適應度值對比

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

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

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

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

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

5 結 語

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