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

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

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

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

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

1 系統(tǒng)模型

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

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

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

表1 典型DAG計算成本

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

2 HPSOA算法

2.1 算法思想

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

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

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

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

2.2 算法建模

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

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

(1)

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

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

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

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

(2)

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

(3)

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

2.4 適應度函數(shù)

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

(4)

makespan(m)=EFT(m,vexit)

(5)

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

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

(6)

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

makespan的計算式為

(7)

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

適應度函數(shù)計算式為

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

(8)

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

2.5 編碼規(guī)則

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

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

圖3 編碼過程Figure 3. Coding process

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

2.6 位置更新規(guī)則

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

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

(9)

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

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

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

(10)

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

警戒者位置更新計算式為

(11)

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

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

圖4 HPSOA運行流程Figure 4. HPSOA operation flow

3 仿真實驗及性能分析

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

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

表2 仿真平臺信息

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

3.1 算法有效性分析

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

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

圖5 HPSOA適應度值變化(實驗1)Figure 5. Change of HPSOA fitness value(experiment 1)

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

圖7 ICPA負載情況(實驗1)Figure 7. Load of ICPA(experiment 1)

圖8 HPSOA負載情況(實驗1)Figure 8. Load of HPSOA(experiment 1)

仿真得到ICPA調(diào)度長度為67,HPSOA為76, HPSOA調(diào)度長度小于ICPA是因為其優(yōu)化目標為負載均衡,調(diào)度長度性能有所犧牲。

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

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

圖9 HPSOA適應度值變化(實驗2)Figure 9. Change of HPSOA fitness value(experiment 2)

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

圖11 ICPA 負載情況(實驗2)Figure 11. Load of ICPA(experiment 2)

圖12 HPSOA 負載情況(實驗2)Figure 12. Load of HPSOA(experiment 2)

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

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

3.2 算法可靠性分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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