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

程小輝 童輝輝 康燕萍*

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

0 引 言

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

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

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

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

1.1 異構多核系統任務調度問題描述

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

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

1.2 任務調度模型描述

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

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

圖2 DAG任務圖實例

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

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

(1)

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

2 麻雀搜索算法

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

2.1 麻雀覓食行為描述

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

2.2 麻雀搜索算法數學描述

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

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

(2)

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

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

(3)

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

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

(4)

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

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

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

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

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

3.1 麻雀個體編碼

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

(5)

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

表1 任務分配編碼方案

3.2 解碼方案

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

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

(6)

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

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

(7)

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

表2 任務分配解碼方案

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

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

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

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

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

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

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

(6) 根據式(4)更新發現危險的麻雀的位置。

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

SSA的流程如圖3所示。

圖3 SSA流程

4 實驗仿真與分析

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

本文實驗參數設置如下:麻雀搜索算法,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模擬平臺上執行了上述三種算法。為了減少數據隨機造成的實驗結果偏差,更精確反映出算法的性能,全部任務完成時間取50次重復測試中得到最優解的平均值。

圖4為SSA、GA和IPSO在100個任務和5個處理器條件下適應度值-迭代次數曲線。可以看出相較于GA和IPSO,SSA尋得最優解的迭代次數更少、適應度更低、最優解質量高,從而全部任務執行完成的時間更短,SSA具有快速收斂、高效求解的特點。

圖4 算法適應度值對比

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

圖5 最優調度長度對比

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

圖6 算法執行時間對比

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

5 結 語

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