面向異構(gòu)處理平臺(tái)任務(wù)調(diào)度的麻雀優(yōu)化算法

沈小龍,馬金全,冀亞瑋,謝宗甫,李宜亭,李宇東

(戰(zhàn)略支援部隊(duì)信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,河南 鄭州 450000)

隨著時(shí)代進(jìn)步和科學(xué)技術(shù)飛速發(fā)展,信號(hào)處理應(yīng)用對處理器性能要求越來越高。由于傳統(tǒng)單一信號(hào)處理平臺(tái)已經(jīng)不能滿足當(dāng)前需求,因此異構(gòu)處理平臺(tái)應(yīng)運(yùn)而生,其內(nèi)部包含豐富的處理器類型[1-2],能夠滿足不同信號(hào)處理應(yīng)用的需求。信號(hào)處理應(yīng)用通過有向無環(huán)圖(Directed Acyclic Graph,DAG)[3-4]抽象為任務(wù)集合,然后通過調(diào)度算法將任務(wù)分配到各處理器執(zhí)行,當(dāng)前調(diào)度算法[5-7]對任務(wù)執(zhí)行的實(shí)時(shí)性關(guān)注較多,均以調(diào)度長度為優(yōu)化目標(biāo),造成處理器負(fù)載失衡,因此異構(gòu)處理平臺(tái)中的負(fù)載均衡調(diào)度算法具有重要研究價(jià)值。

文獻(xiàn)[8]提出麻雀搜索算法(Sparrow Search Algorithm,SSA),通過麻雀捕食與反捕食機(jī)制解決數(shù)學(xué)中求取極值問題。SSA算法因具有較強(qiáng)全局尋優(yōu)能力故在電力系統(tǒng)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域得到廣泛應(yīng)用。文獻(xiàn)[9]對SSA算法中的發(fā)現(xiàn)者位置更新做出改進(jìn),從跳躍式優(yōu)化為移動(dòng)式,所提算法對網(wǎng)絡(luò)的權(quán)值參數(shù)進(jìn)行優(yōu)化,提高了電力負(fù)荷預(yù)測準(zhǔn)確度。文獻(xiàn)[10]在麻雀種群初始化時(shí)采取Logistic混沌映射提高初始種群質(zhì)量,得到較優(yōu)解后采取隨機(jī)游走擾動(dòng)策略提高全局搜索能力,減小了電力負(fù)荷預(yù)測誤差。文獻(xiàn)[11]利用遺傳算法對麻雀位置更新規(guī)則進(jìn)行改進(jìn),利用模擬退火算法避免陷入局部最優(yōu),所提算法在車間調(diào)度問題中取得了較好的調(diào)度結(jié)果。文獻(xiàn)[12～13]利用SSA算法對BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值參數(shù)進(jìn)行優(yōu)化,提高了網(wǎng)絡(luò)穩(wěn)定性和準(zhǔn)確性。

由于SSA算法在異構(gòu)處理平臺(tái)任務(wù)調(diào)度領(lǐng)域研究較少,因此本文提出一種面向異構(gòu)處理平臺(tái)的麻雀優(yōu)化算法(Heterogeneous Processing platform Sparrow Optimization Algorithm,HPSOA),該算法對SSA算法進(jìn)行優(yōu)化,設(shè)計(jì)了離散任務(wù)分配到連續(xù)麻雀位置信息的編解碼規(guī)則,改善了麻雀位置更新計(jì)算式,并制定符合優(yōu)化目標(biāo)的適應(yīng)度函數(shù)。

1 系統(tǒng)模型

異構(gòu)處理平臺(tái)總體分為4層[14-15],如圖1所示。底層為硬件層,包含平臺(tái)所有處理器資源;底層之上為中間層,由操作系統(tǒng)層、板級(jí)支持包和平臺(tái)抽象層等組成;中間層之上為組件層,包含項(xiàng)目組研發(fā)的所有組件;頂層為應(yīng)用層,包含當(dāng)前平臺(tái)部署的信號(hào)處理應(yīng)用程序。當(dāng)異構(gòu)信號(hào)處理平臺(tái)增加新應(yīng)用時(shí),首先進(jìn)行功能分析,從組件庫中挑選組件搭建應(yīng)用程序;之后利用調(diào)度算法為應(yīng)用程序中組件分配處理器;最后通過中間層將組件部署到相應(yīng)處理器,完成新應(yīng)用程序在異構(gòu)處理平臺(tái)的開發(fā)。

圖1 平臺(tái)結(jié)構(gòu)Figure 1. Platform structure

調(diào)度算法決定各應(yīng)用完成時(shí)間和處理器分配任務(wù)情況,對系統(tǒng)整體實(shí)時(shí)性和各處理器工作效率影響較大,因此調(diào)度算法較為重要。在調(diào)度問題研究中,將應(yīng)用程序抽象成DAG圖,定義為G=(V,C,P,W)。經(jīng)典DAG如圖2所示。vi為任務(wù),與圖中節(jié)點(diǎn)對應(yīng),cij為任務(wù)間平均通信開銷,與圖中有向邊對應(yīng),pi為處理器,wij為任務(wù)在處理器上計(jì)算開銷,與表1對應(yīng)。

表1 典型DAG計(jì)算成本

圖2 典型DAG任務(wù)圖Figure 2. Typical DAG task diagram

2 HPSOA算法

2.1 算法思想

當(dāng)麻雀進(jìn)行覓食時(shí),根據(jù)麻雀適應(yīng)度函數(shù)值將種群內(nèi)部分為發(fā)現(xiàn)者、跟隨者和警戒者。經(jīng)典SSA算法中適應(yīng)度函數(shù)值表示麻雀和食物之間的距離。

發(fā)現(xiàn)者處于種群領(lǐng)導(dǎo)位置,具有較強(qiáng)覓食能力和搜索能力,能夠引導(dǎo)其他個(gè)體在當(dāng)前局部最優(yōu)范圍進(jìn)行搜索。發(fā)現(xiàn)者還具有較高的反捕食能力,當(dāng)報(bào)警值超過安全閾值時(shí),會(huì)向麻雀較多地方移動(dòng),以此來降低自身被捕食的風(fēng)險(xiǎn)。

跟隨者是種群中數(shù)量最多的群體,大部分麻雀會(huì)在發(fā)現(xiàn)者確定的局部區(qū)域進(jìn)行搜索,尋找當(dāng)前區(qū)域內(nèi)的最優(yōu)解。其他個(gè)體因?yàn)榫嚯x當(dāng)前區(qū)域食物源位置較遠(yuǎn),故選擇逃離當(dāng)前區(qū)域,尋找新的覓食區(qū)域。因此,發(fā)現(xiàn)者和跟隨者的劃分并不是一成不變,兩者中的個(gè)體能夠進(jìn)行角色轉(zhuǎn)換。

警戒者是將種群中所有麻雀按照一定數(shù)量比例隨機(jī)選取,所以有發(fā)現(xiàn)者也有跟隨者。當(dāng)警戒者意識(shí)到危險(xiǎn)時(shí),引導(dǎo)種群離開當(dāng)前區(qū)域到更廣泛區(qū)域搜索,有利于跳出局部最優(yōu),尋找全局最優(yōu)解。

2.2 算法建模

將異構(gòu)處理平臺(tái)中應(yīng)用程序抽象為DAG任務(wù)圖后,任務(wù)調(diào)度算法負(fù)責(zé)將各任務(wù)分配到處理器,屬于離散問題。麻雀算法最初是求解極值問題,屬于連續(xù)問題,因此建立合適的模型將麻雀算法應(yīng)用到任務(wù)調(diào)度領(lǐng)域較為重要。

本文將每只麻雀建模為任務(wù)調(diào)度算法的一種分配方案,建模計(jì)算式為

(1)

其中,n表示待分配任務(wù)數(shù);m表示麻雀數(shù)量;pop21表示第2只麻雀為任務(wù)1分配的處理器;若有p個(gè)處理器,則pop中每個(gè)值有p種可能,因此任務(wù)調(diào)度問題被轉(zhuǎn)換為麻雀搜索問題。

2.3 任務(wù)優(yōu)先級(jí)排序

麻雀為每個(gè)任務(wù)分配處理器后,任務(wù)調(diào)度順序較重要,由于優(yōu)先級(jí)排序不同,因此調(diào)度結(jié)果差別較大。當(dāng)前任務(wù)調(diào)度算法中優(yōu)先級(jí)排序策略單一時(shí),不同類型任務(wù)采用相同排序方法,未分析各類型任務(wù)之間的差別,這將導(dǎo)致排序結(jié)果不準(zhǔn)確。針對該問題,本文采用任務(wù)優(yōu)先級(jí)分流排序策略。

根據(jù)任務(wù)圖通信計(jì)算比,將任務(wù)圖分為計(jì)算密集型和通信密集型任務(wù),對于通信密集型任務(wù),其優(yōu)先級(jí)排序計(jì)算式為

(2)

計(jì)算密集型任務(wù)的優(yōu)先級(jí)排序計(jì)算式為

(3)

其中,σi為任務(wù)i在3個(gè)處理器上計(jì)算成本標(biāo)準(zhǔn)差。利用計(jì)算成本標(biāo)準(zhǔn)差可得到符合計(jì)算密集型任務(wù)排序方法,并將對任務(wù)序值降序排序后的結(jié)果作為最終調(diào)度順序。

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

針對處理器負(fù)載不均衡問題,本文優(yōu)化目標(biāo)為處理器負(fù)載均衡指數(shù)(processor load,pld),其計(jì)算式為

(4)

makespan(m)=EFT(m,vexit)

(5)

其中,EFT(m,vexit)表示麻雀m分配方案中出口任務(wù)完成時(shí)間,調(diào)度長度值越小越好。

本文將調(diào)度長度和處理器負(fù)載均衡指數(shù)的組合作為最終適應(yīng)度函數(shù),但二者數(shù)值相差較大,因此不能直接相加。為使二者處于相同衡量水平,首先進(jìn)行歸一化處理,pld計(jì)算式為

(6)

其中,max(pld)為本次迭代負(fù)載均衡指數(shù)最大值;normal_pld(m)表示麻雀m歸一化后的負(fù)載均衡指數(shù)。

makespan的計(jì)算式為

(7)

其中,max(makespan)為本次迭代調(diào)度長度最大值,表示麻雀m歸一化后的調(diào)度長度。

適應(yīng)度函數(shù)計(jì)算式為

fitness(m)=normal_pld(m)+normal_makespan(m)

(8)

得到適應(yīng)度函數(shù)值后,按降序排序作為麻雀種群分工依據(jù),將排序靠前的麻雀作為發(fā)現(xiàn)者,其余作為跟隨者,隨機(jī)選取警戒者。

2.5 編碼規(guī)則

麻雀算法在連續(xù)問題求解中運(yùn)用廣泛,而任務(wù)調(diào)度問題是離散化問題,將麻雀的位置更新計(jì)算式運(yùn)用到任務(wù)分配方案中是關(guān)鍵問題。針對該問題,本文提出二進(jìn)制異或編碼規(guī)則,將任務(wù)分配方案映射成連續(xù)位置信息。

以經(jīng)典DAG任務(wù)圖為例,對編碼規(guī)則進(jìn)行介紹。當(dāng)麻雀確定好任務(wù)分配處理器后,按照任務(wù)優(yōu)先級(jí)排序順序計(jì)算其分配方案的適應(yīng)度函數(shù)值,然后進(jìn)行位置編碼,圖3為其編碼過程。

圖3 編碼過程Figure 3. Coding process

其中,麻雀A在本次迭代中適應(yīng)度函數(shù)值最優(yōu),因此將其分配方案作為參考基準(zhǔn),在計(jì)算麻雀B位置信息時(shí),采取異或思想。將麻雀B分配方案同麻雀A逐任務(wù)對比,然后將對比結(jié)果轉(zhuǎn)換為十進(jìn)制數(shù)作為其連續(xù)位置信息,其余麻雀均按照此規(guī)則計(jì)算。

2.6 位置更新規(guī)則

在每次迭代中計(jì)算麻雀適應(yīng)度函數(shù),按其降序?qū)ΨN群分工,然后根據(jù)編碼規(guī)則計(jì)算麻雀位置信息,最后根據(jù)不同更新規(guī)則計(jì)算更新后的位置信息。

發(fā)現(xiàn)者是處于位置較好的麻雀,具有較優(yōu)適應(yīng)度函數(shù)值,其位置更新計(jì)算式為

(9)

其中,Xi(t+1)表示麻雀i迭代后的位置信息;safe為安全閾值,取值范圍是(0.5～1.0);rand是報(bào)警值,取值范圍為(0～1);K為服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù);genmax是最大迭代次數(shù)。

跟隨者是數(shù)量最多的群體,其適應(yīng)度函數(shù)值較差,其中前半部分的位置更新計(jì)算式為

Xi(t+1)=Xbest(t)+|Xi(t)-Xbest(t)|×A

(10)

其中,Xbest(t)表示本次迭代中最優(yōu)位置;A取值為-1或1,后半部分因位置較差,需重新分配處理器。

警戒者位置更新計(jì)算式為

(11)

其中,fit(best)和fit(worse)分別是適應(yīng)度函數(shù)的最優(yōu)值和最差值;rand是服從標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù);B是介于[-1,1]的隨機(jī)數(shù);β是一個(gè)較小的數(shù),用以保證分母不為0,其取值需同適應(yīng)度函數(shù)值的差值保持相同數(shù)量級(jí)。

得到新位置信息后,將該數(shù)據(jù)轉(zhuǎn)換為二進(jìn)制數(shù),找到值為1的任務(wù),對其處理器進(jìn)行隨機(jī)選擇,作為更新后分配方案。HPSOA算法的運(yùn)行流程如圖4所示。

圖4 HPSOA運(yùn)行流程Figure 4. HPSOA operation flow

3 仿真實(shí)驗(yàn)及性能分析

設(shè)計(jì)仿真實(shí)驗(yàn)將HPSOA算法同ICPA[4]進(jìn)行對比,驗(yàn)證算法有效性和可靠性。

表2為仿真實(shí)驗(yàn)平臺(tái)信息,表3為算法參數(shù)設(shè)置,其中m為麻雀種群數(shù)量,genmax為迭代次數(shù),safe為安全閾值,N_discover為發(fā)現(xiàn)者比例,N_vigilant為預(yù)警者比例。

表2 仿真平臺(tái)信息

表3 HPSOA算法參數(shù)設(shè)置

3.1 算法有效性分析

為驗(yàn)證本文算法有效性,設(shè)置兩組實(shí)驗(yàn)進(jìn)行對比,實(shí)驗(yàn)1是經(jīng)典任務(wù)圖,實(shí)驗(yàn)2是隨機(jī)任務(wù)圖。

實(shí)驗(yàn)1將經(jīng)典任務(wù)圖用ICPA和HPSOA算法分別進(jìn)行調(diào)度,得到HPSOA適應(yīng)度函數(shù)變化如圖5所示,HPSOA調(diào)度長度如圖6所示,ICPA負(fù)載情況如圖7所示,HPSOA負(fù)載情況如圖8所示。

圖5 HPSOA適應(yīng)度值變化(實(shí)驗(yàn)1)Figure 5. Change of HPSOA fitness value(experiment 1)

圖6 HPSOA調(diào)度長度變化(實(shí)驗(yàn)1)Figure 6. Change of HPSOA scheduling length(experiment 1)

圖7 ICPA負(fù)載情況(實(shí)驗(yàn)1)Figure 7. Load of ICPA(experiment 1)

圖8 HPSOA負(fù)載情況(實(shí)驗(yàn)1)Figure 8. Load of HPSOA(experiment 1)

仿真得到ICPA調(diào)度長度為67,HPSOA為76, HPSOA調(diào)度長度小于ICPA是因?yàn)槠鋬?yōu)化目標(biāo)為負(fù)載均衡,調(diào)度長度性能有所犧牲。

仿真得到ICPA負(fù)載均衡指數(shù)為0,HPSOA負(fù)載均衡指數(shù)為0.471 4。其中ICPA總?cè)蝿?wù)數(shù)為12,是因?yàn)樵趦蓚€(gè)非關(guān)鍵處理器上進(jìn)行了任務(wù)復(fù)制。該實(shí)驗(yàn)中任務(wù)數(shù)較小,未發(fā)揮出算法的性能優(yōu)勢,HPSOA的負(fù)載均衡劣于ICPA。

實(shí)驗(yàn)2應(yīng)用DAG隨機(jī)生成程序生成一個(gè)任務(wù)數(shù)為20、處理器數(shù)為4的DAG任務(wù)圖,仿真得到HPSOA適應(yīng)度函數(shù)變化如圖9所示,調(diào)度長度如圖10所示,ICPA負(fù)載情況如圖11所示,HPSOA負(fù)載情況如圖12所示。

圖9 HPSOA適應(yīng)度值變化(實(shí)驗(yàn)2)Figure 9. Change of HPSOA fitness value(experiment 2)

圖10 HPSOA 調(diào)度長度變化(實(shí)驗(yàn)2)Figure 10. Change of HPSOA scheduling length(experiment 2)

圖11 ICPA 負(fù)載情況(實(shí)驗(yàn)2)Figure 11. Load of ICPA(experiment 2)

圖12 HPSOA 負(fù)載情況(實(shí)驗(yàn)2)Figure 12. Load of HPSOA(experiment 2)

仿真得到ICPA調(diào)度長度為136,HPSOA調(diào)度長度為150,ICPA負(fù)載均衡指數(shù)為3.344 8,HPSOA負(fù)載均衡指數(shù)為1.581 1,該實(shí)驗(yàn)中ICPA算法的3個(gè)非關(guān)鍵處理器進(jìn)行了任務(wù)復(fù)制。從仿真實(shí)驗(yàn)結(jié)果可以看出,HPSOA算法相比于ICPA算法,在犧牲一定調(diào)度長度性能后,處理器負(fù)載均衡性明顯提升。

從以上兩個(gè)實(shí)驗(yàn)得出,HPSOA算法適應(yīng)度函數(shù)值曲線均趨于收斂,說明算法中對于編碼規(guī)則和位置更新規(guī)則的改進(jìn)有效。對隨機(jī)生成的任務(wù)圖,處理器負(fù)載均衡性能改進(jìn)明顯,證明了算法的有效性。

3.2 算法可靠性分析

為驗(yàn)證算法可靠性,本文設(shè)置兩組實(shí)驗(yàn)進(jìn)行對比,與實(shí)驗(yàn)1中任務(wù)圖處理器數(shù)相同,與實(shí)驗(yàn)2中任務(wù)圖任務(wù)數(shù)相同。

實(shí)驗(yàn)3利用隨機(jī)DAG程序生成一組處理器數(shù)為5、任務(wù)數(shù)為40、60、80、100任務(wù)圖,進(jìn)行仿真實(shí)驗(yàn),得到ICPA和HPSOA的調(diào)度長度對比如圖13所示,負(fù)載均衡指數(shù)對比如圖14所示。

圖13 調(diào)度長度對比(實(shí)驗(yàn)3)Figure 13. Comparison of scheduling length(experiment 3)

圖14 處理器負(fù)載均衡指數(shù)對比(實(shí)驗(yàn)3)Figure 14. Comparison of processor load balancing coefficients(experiment 3)

從圖13～圖14可以看出,HPSOA算法在犧牲調(diào)度長度性能后,其負(fù)載均衡指數(shù)均優(yōu)于ICPA。

對隨機(jī)任務(wù)圖的調(diào)度結(jié)果進(jìn)行計(jì)算可知,該實(shí)驗(yàn)中調(diào)度長度平均犧牲率為46.90%,負(fù)載均衡指數(shù)平均優(yōu)化率為66.09%。

實(shí)驗(yàn)4利用隨機(jī)DAG程序生成一組任務(wù)數(shù)為20、處理器數(shù)為4、5、6的任務(wù)圖,進(jìn)行仿真實(shí)驗(yàn),得到ICPA和HPSOA的調(diào)度長度對比如圖15所示,負(fù)載均衡指數(shù)對比情況如圖16所示。

圖15 調(diào)度長度對比(實(shí)驗(yàn)4)Figure 15. Comparison of scheduling length(experiment 4)

圖16 處理器負(fù)載均衡指數(shù)對比(實(shí)驗(yàn)4)Figure 16. Comparison of processor load balancing coefficients(experiment 4)

從圖15～圖16可以看出,HPSOA算法在犧牲調(diào)度長度性能后,其負(fù)載均衡指數(shù)均優(yōu)于ICPA。對調(diào)度結(jié)果進(jìn)行計(jì)算得到,該實(shí)驗(yàn)中調(diào)度長度平均犧牲率為56.13%,負(fù)載均衡指數(shù)平均優(yōu)化率為69.57%。

實(shí)驗(yàn)3中任務(wù)平均數(shù)為70,處理器數(shù)為5;實(shí)驗(yàn)4中任務(wù)數(shù)為20,處理器平均數(shù)為5。從以上兩組實(shí)驗(yàn)結(jié)果中看出,隨著任務(wù)數(shù)目增多,相比于ICPA算法,HPSOA調(diào)度長度犧牲率從56.13%降到46.90%,負(fù)載均衡指數(shù)優(yōu)化率穩(wěn)定在60%左右。隨著任務(wù)數(shù)目增多,HPSOA調(diào)度長度犧牲率越來越小,負(fù)載均衡優(yōu)化率依舊穩(wěn)定,證明了該算法的可靠性。

4 結(jié)束語

針對異構(gòu)信號(hào)處理平臺(tái)中各處理器負(fù)載差異較大問題,本文提出了一種面向異構(gòu)處理平臺(tái)的麻雀優(yōu)化算法。該算法在SSA算法基礎(chǔ)上提出了適合任務(wù)調(diào)度分配的編碼規(guī)則,制定了求取最優(yōu)化的適應(yīng)度函數(shù),并對位置更新規(guī)則進(jìn)行改進(jìn)。通過仿真實(shí)驗(yàn)可知,相比于ICPA算法,HPSOA算法的負(fù)載均衡指數(shù)優(yōu)化效果明顯,能更好地發(fā)揮每個(gè)處理器效能,提升平臺(tái)整體工作效率。