沈小龍,馬金全,胡澤明,李宇東

(信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,鄭州 450001)

0 引 言

信號處理應(yīng)用通過有向無環(huán)圖(Directed Acyclic Graph,DAG)建模為有依賴關(guān)系的任務(wù)集合。隨著科技飛速發(fā)展,信號處理應(yīng)用規(guī)模越來越大,功能日趨復(fù)雜,信號處理應(yīng)用通過DAG抽象建模后的任務(wù)規(guī)模急劇上升,各任務(wù)功能不同,對處理器需求有差別,傳統(tǒng)同構(gòu)處理平臺已經(jīng)不能滿足此需求,而異構(gòu)信號處理平臺包含豐富處理器資源,成為首要選擇。任務(wù)在不同處理器上執(zhí)行時(shí)間不同,調(diào)度算法決定任務(wù)分配情況,直接影響信號處理應(yīng)用完成時(shí)間和平臺處理器效率,因此調(diào)度算法研究尤為重要。

目前,根據(jù)搜索過程把任務(wù)調(diào)度算法分為啟發(fā)式和元啟發(fā)式調(diào)度算法。啟發(fā)式調(diào)度算法分為3種:基于列表的調(diào)度算法[1-5]運(yùn)算復(fù)雜度低,易于實(shí)現(xiàn),適用于任務(wù)和處理器數(shù)量較少的情形;基于聚類的調(diào)度算法[6-8]可擴(kuò)展性和魯棒性較強(qiáng),但要求聚類后的類別數(shù)量小于處理器數(shù)量;基于任務(wù)復(fù)制的調(diào)度算法[9-10]可對其他算法進(jìn)行優(yōu)化,擴(kuò)展性較強(qiáng),但會提高額外計(jì)算開銷,增加算法復(fù)雜度。元啟發(fā)式調(diào)度算法分為蟻群優(yōu)化算法[11-12]、遺傳算法[13-14]、粒子群算法[15-16]等,該類算法通過不斷迭代從廣泛解空間中找到符合目標(biāo)性能的最優(yōu)解,適用于任務(wù)較多情形。其中蟻群算法憑借著靈活性高、自適應(yīng)性強(qiáng)且能夠得到較優(yōu)解的特點(diǎn)得到了廣泛應(yīng)用,在旅行商問題(Traveling Salesman Problem,TSP)、二次分配問題(Quadratic Assignment Problem,QAP)和作業(yè)車間調(diào)度(Job Shop Scheduling Problem,JSP)問題中取得了較好實(shí)驗(yàn)結(jié)果。但蟻群算法存在初始信息素不足、收斂速度慢、易陷入局部最優(yōu)解等問題,且以上調(diào)度算法主要優(yōu)化任務(wù)調(diào)度長度,屬于單目標(biāo)調(diào)度,在最終調(diào)度方案中,處理器負(fù)載不均衡,造成資源浪費(fèi)。

基于以上背景,本文提出了一種基于蟻群優(yōu)化算法的負(fù)載均衡調(diào)度算法(Ant Colony Optimization Load Balancing,ACOLB)。該算法針對蟻群算法初始信息素不足、搜索空間廣泛、搜索時(shí)間較長等不足,采用優(yōu)化初始信息素矩陣,指定螞蟻遍歷任務(wù)順序,運(yùn)用輪盤賭選擇方式尋求最優(yōu)解,并結(jié)合優(yōu)化目標(biāo)對啟發(fā)因子和狀態(tài)轉(zhuǎn)移公式進(jìn)行改進(jìn),在調(diào)度長度和負(fù)載均衡方面的性能均有明顯改善。

1 系統(tǒng)模型

異構(gòu)信號處理平臺總體分為4層,如圖1所示:底層為硬件層包含平臺所有處理器資源,如中央處理器(Central Processing Unit,CPU)、圖形處理器(Graphics Processing Unit,GPU)、數(shù)字信號處理器(Digital Signal Processor,DSP)、現(xiàn)場可編程門陣列(Field Programmable Gate Array,FPGA)等;底層之上為中間層,由操作系統(tǒng)層、板級支持包、平臺抽象層等組成,通過對操作系統(tǒng)、驅(qū)動等建模,實(shí)現(xiàn)不同處理器間數(shù)據(jù)傳輸;中間層之上為組件層,包含項(xiàng)目組研發(fā)的所有組件,并根據(jù)組件特點(diǎn)分類管理;頂層為應(yīng)用層,包含當(dāng)前平臺部署的信號處理應(yīng)用程序。異構(gòu)信號處理平臺增加新信號處理應(yīng)用時(shí),首先進(jìn)行功能分析從組件庫中挑選組件搭建應(yīng)用程序,然后利用調(diào)度算法為應(yīng)用程序中組件分配處理器,最后通過中間層將組件部署到相應(yīng)處理器,完成新應(yīng)用程序在異構(gòu)信號處理平臺上的開發(fā)運(yùn)行。

圖1 異構(gòu)信號處理平臺架構(gòu)

信號處理應(yīng)用在異構(gòu)信號處理平臺運(yùn)行時(shí),調(diào)度算法決定了其執(zhí)行時(shí)間和各處理器的負(fù)載情況,對系統(tǒng)整體實(shí)時(shí)性和各處理器工作效率影響較大,因此調(diào)度算法尤為重要。調(diào)度問題研究中,將應(yīng)用程序抽象成DAG圖,定義為G=(V,C,P,W)。經(jīng)典DAG如圖2所示。其中,V={vi}為任務(wù)集合與圖中節(jié)點(diǎn)對應(yīng);C={Cij}為任務(wù)間平均通信開銷與圖中有向邊對應(yīng),有向邊表示任務(wù)間依賴關(guān)系和數(shù)據(jù)傳遞方向;P={Pi}為處理器集合;W={Wij}為任務(wù)在處理器上的計(jì)算開銷,與表1相對應(yīng)。針對某通信信號處理應(yīng)用,假設(shè)所有處理器是連接通暢的,每個(gè)任務(wù)不可再拆分必須分配到處理器執(zhí)行,且任務(wù)執(zhí)行期間其所在處理器不可以再執(zhí)行其他任務(wù),若兩個(gè)任務(wù)分配到同一處理器,則任務(wù)間通信開銷為零。

表1 典型任務(wù)圖計(jì)算成本表

圖2 典型DAG任務(wù)圖

2 ACOLB算法

2.1 算法思想

蟻群算法靈感來自于真實(shí)世界中螞蟻的覓食過程。蟻群會根據(jù)環(huán)境變換表現(xiàn)出不同行為特性。螞蟻從A到B有3條路徑可供選擇,其長度關(guān)系是 2<1<3。螞蟻在行走過程中釋放信息素標(biāo)記路徑,信息素隨著時(shí)間推移而蒸發(fā),假設(shè)每條路徑信息素蒸發(fā)系數(shù)和行進(jìn)速度相同。對于最初螞蟻,3條路徑初始信息素相同,隨機(jī)選擇路線,選擇路線2耗時(shí)較短,殘留信息素濃度較大;對于后面的螞蟻,3條線路信息素濃度有差異,選擇2的概率明顯提高,在動態(tài)正反饋機(jī)制作用下引導(dǎo)整個(gè)蟻群選擇最佳路線,找到問題最優(yōu)解。

在蟻群算法思想上構(gòu)建異構(gòu)信號處理平臺中信號處理應(yīng)用的調(diào)度模型,應(yīng)用通過有向無環(huán)圖抽象成n個(gè)任務(wù)、m個(gè)處理器,螞蟻需從任務(wù)列表中選擇一個(gè)任務(wù),通過處理器選擇規(guī)則確定該任務(wù)運(yùn)行的處理器,直到遍歷完列表中所有任務(wù)。針對經(jīng)典蟻群算法存在的不足,從任務(wù)優(yōu)先級排序、信息素設(shè)置和更新、處理器選擇三方面進(jìn)行改進(jìn)。

2.2 優(yōu)先級排序

任務(wù)調(diào)度順序?qū)τ谧罱K調(diào)度結(jié)果十分關(guān)鍵,若有n個(gè)任務(wù)則調(diào)度順序有n!種,造成搜索空間廣泛,收斂速度慢。本文采用異構(gòu)最早完成時(shí)間(Heterogeneous Earliest Finish Time,HEFT)算法任務(wù)優(yōu)先級排序規(guī)則,計(jì)算公式如下:

(1)

2.3 信息素設(shè)置和更新

本文研究的通信密集型任務(wù),任務(wù)間通信開銷大于計(jì)算開銷,降低通信開銷有助于提升調(diào)度結(jié)果,而關(guān)鍵路徑(Critical Path on a Processor,CPOP)算法采用關(guān)鍵路徑任務(wù)分配到關(guān)鍵處理器思想,能極大減少通信開銷,降低調(diào)度長度。因此,本文將CPOP調(diào)度結(jié)果作為初始信息素矩陣,解決初始信息素不足問題。以圖2為例,CPOP得到的任務(wù)分配情況如表2所示。根據(jù)該表對信息素矩陣phe(pheromone)初始化設(shè)置,結(jié)果如公式(2)所示。

表2 經(jīng)典DAG圖任務(wù)分配情況

(2)

式中:phe(j,i)為任務(wù)j分配到處理器i的信息素濃度。受初始信息素矩陣引導(dǎo),蟻群將向著降低通信開銷方向不斷迭代優(yōu)化。每次迭代中螞蟻為所有任務(wù)分配處理器,每只螞蟻完成調(diào)度后的信息素增量Δphe計(jì)算公式如下:

(3)

式中:Δphe(j,i)為螞蟻i為任務(wù)j分配處理器后引起信息素增量;Q為信息素增加系數(shù);L(i)為螞蟻在本次迭代中取得的調(diào)度長度。為獲得更加全面的信息素矩陣,充分利用蟻群群體行為優(yōu)勢,將每只螞蟻的Δphe累加后對信息素phe進(jìn)行更新,更新公式如下:

phe=(1-ρ)×phe+Δphe(j,i)。

(4)

式中:ρ為信息素蒸發(fā)系數(shù);phe按照蟻群迭代頻次進(jìn)行更新。

2.4 處理器選擇

ACOLB算法通過對傳統(tǒng)蟻群算法狀態(tài)轉(zhuǎn)移公式和啟發(fā)因子改進(jìn),在調(diào)度長度基礎(chǔ)上增加負(fù)載均衡優(yōu)化目標(biāo)。啟發(fā)因子由eta和etb兩部分組成。eta計(jì)算公式如下:

(5)

式中:EFT為螞蟻完成時(shí)間矩陣。etb計(jì)算公式如下:

(6)

式中:num_process為處理器實(shí)時(shí)負(fù)載矩陣。ACOLB狀態(tài)轉(zhuǎn)移公式如下:

(7)

式中:p(i,k),phe(i,k)和eta(i,k)分別為任務(wù)i分配到處理器k上的概率、信息素濃度和完成時(shí)間倒數(shù);etb(k)為處理器k累計(jì)任務(wù)量倒數(shù);α,β,χ分別是phe,eta和etb的重要程度因子。

得到任務(wù)選擇處理器概率后,運(yùn)用輪盤賭方法確定任務(wù)運(yùn)行處理器。首先計(jì)算任務(wù)i分配到處理器1～k的概率之和p(i,k)′,公式如下:

(8)

之后,從(0,1)內(nèi)生成一個(gè)隨機(jī)數(shù)rand,確定處理器集合find_process,公式如下:

find_process=p(i,k)′≥rand 。

(9)

選取find_process中編號最小處理器,作為任務(wù)i最終分配處理器。

2.5 算法步驟

ACOLB算法流程如圖3所示,具體步驟如下:

圖3 ACOLB算法流程

輸入:DAG

輸出:最優(yōu)解

1 計(jì)算優(yōu)先級列表和CPOP調(diào)度結(jié)果;

2 設(shè)置蟻群規(guī)模,迭代次數(shù),phe,α,β,χ,ρ和Q;

3 迭代次數(shù)加1;

4 將上一次迭代中:EST,EFT,num_process,eta和etb進(jìn)行重置;

5 任務(wù)數(shù)加1;

6 螞蟻數(shù)加1;

7 分配處理器;

8 更新eta和etb;

9 如果有螞蟻未對該任務(wù)進(jìn)行調(diào)度,轉(zhuǎn)到步驟6;

10 如果有任務(wù)未分配處理器,轉(zhuǎn)到步驟5;

11 記錄此次迭代中最佳調(diào)度結(jié)果;

12 更新信息素矩陣;

13 如果迭代次數(shù)不大于最大迭代值,轉(zhuǎn)到步驟3。

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

實(shí)驗(yàn)平臺是CPU 為Intel(R) Core(TM) i5-1135G7 @ 2.40 GHz 、內(nèi)存為16 GB的64位操作系統(tǒng)。隨機(jī)DAG生成程序參數(shù)設(shè)置為任務(wù)數(shù)V={10,20,40,60,80},處理器數(shù)P={3,4,5,6},通信計(jì)算比CCR={0.1,0.25,0.5,0.75,1,2.5,5,7.5,10};并行因子Parallel={0.1,0.5,1,5,10}。CPOP算法對于通信密集型任務(wù)調(diào)度效果較好,因此將其作為對比算法,通過圖1所示的典型DAG和隨機(jī)DAG,驗(yàn)證ACOLB的有效性和可靠性。

3.1 優(yōu)化目標(biāo)

本文所提算法優(yōu)化目標(biāo)有兩個(gè),即調(diào)度長度makespan和負(fù)載均衡系數(shù)pld。makespan表示算法整體執(zhí)行時(shí)間,越小越好,計(jì)算公式如下:

makespan=EFT(vexit)。

(10)

式中:vexit為出口任務(wù)。

pld表示系統(tǒng)內(nèi)所有處理器負(fù)載均衡程度,越小越好,其計(jì)算公式如下:

(11)

3.2 參數(shù)設(shè)置

設(shè)置50只螞蟻,進(jìn)行1 000次迭代,信息素增加系數(shù)為1,信息素蒸發(fā)系數(shù)為0.25,phe重要程度因子α為1,eta重要程度因子β取值范圍為0～2,etb重要程度χ為0～1,其中α,β,χ取值范圍是通過大量實(shí)驗(yàn)確定的。

3.3 ACOLB有效性分析

為驗(yàn)證算法有效性,采用經(jīng)典DAG和隨機(jī)DAG進(jìn)行實(shí)驗(yàn),從調(diào)度長度和負(fù)載均衡兩方面進(jìn)行對比。

實(shí)驗(yàn)1：經(jīng)典DAG如圖1所示,其計(jì)算成本如表1所示。ACOLB調(diào)度長度如圖4所示,CPOP負(fù)載情況如圖5所示,ACOLB如圖6所示。

圖4 ACOLB的調(diào)度長度

圖5 CPOP處理器負(fù)載情況

圖6 ACOLB處理器負(fù)載情況

仿真得到CPOP調(diào)度長度為86,負(fù)載均衡系數(shù)為1.247 2;ACOLB調(diào)度長度為76,負(fù)載均衡系數(shù)為0.471 4,ACOLB調(diào)度長度和負(fù)載均衡均優(yōu)于CPOP。ACOLB前期調(diào)度結(jié)果下降到某個(gè)值時(shí),陷入局部最優(yōu)出現(xiàn)振蕩,后通過輪盤賭策略跳出,繼續(xù)尋找全局最優(yōu)解。ACOLB負(fù)載情況遵循CPOP調(diào)度結(jié)果引導(dǎo),2號處理器仍是關(guān)鍵處理器,但較CPOP處理器負(fù)載分配情況,能更加均衡最大發(fā)揮各處理器性能,提高效率。

實(shí)驗(yàn)2：隨機(jī)生成一個(gè)任務(wù)數(shù)為20,處理器數(shù)為5的DAG,應(yīng)用兩種算法得到的調(diào)度結(jié)果如表3所示。

表3 調(diào)度結(jié)果

從隨機(jī)DAG結(jié)果可以看出,ACOLB調(diào)度長度和負(fù)載均衡系數(shù)均優(yōu)于CPOP。對處理器負(fù)載均衡之后,關(guān)鍵處理器同CPOP保持一致,能夠極大減少任務(wù)間通信開銷。

從以上兩個(gè)實(shí)驗(yàn)可以得出,ACOLB不僅對于經(jīng)典DAG有改進(jìn)效果,對于隨機(jī)DAG同樣可以起到優(yōu)化調(diào)度長度和負(fù)載均衡的作用,證明了ACOLB算法的有效性。

3.4 ACOLB可靠性分析

為驗(yàn)證算法可靠性,對處理器和任務(wù)數(shù)量采用控制變量原則,從調(diào)度長度和負(fù)載均衡兩方面進(jìn)行對比。

實(shí)驗(yàn)3：隨機(jī)生成一組任務(wù)數(shù)為20,處理器數(shù)分別為3,4,5,6的DAG。兩種算法調(diào)度長度結(jié)果對比如圖7所示,處理器負(fù)載均衡系數(shù)對比如圖8所示,對結(jié)果進(jìn)行計(jì)算得到調(diào)度長度優(yōu)化率和負(fù)載均衡優(yōu)化率。

圖7 任務(wù)調(diào)度長度對比(實(shí)驗(yàn)3)

圖8 處理器負(fù)載均衡系數(shù)對比(實(shí)驗(yàn)3)

從實(shí)驗(yàn)結(jié)果可看出,任務(wù)數(shù)目相同處理器數(shù)目不同時(shí)ACOLB算法依然可靠,相比于CPOP算法,其在調(diào)度長度和負(fù)載均衡方面均有改進(jìn),本組實(shí)驗(yàn)中調(diào)度長度優(yōu)化率最小值是15.3%,負(fù)載均衡優(yōu)化率最小值是44.5%。

實(shí)驗(yàn)4：隨機(jī)生成一組處理器數(shù)為6,任務(wù)數(shù)分別為20,40,60隨機(jī)任務(wù)圖。兩種算法調(diào)度長度結(jié)果對比如圖9所示,處理器負(fù)載均衡系數(shù)對比如圖10所示,對結(jié)果進(jìn)行計(jì)算得到調(diào)度長度優(yōu)化率和負(fù)載均衡優(yōu)化率。

圖9 任務(wù)調(diào)度長度對比(實(shí)驗(yàn)4)

圖10 處理器負(fù)載均衡系數(shù)對比(實(shí)驗(yàn)4)

從實(shí)驗(yàn)結(jié)果看出,處理器數(shù)相同任務(wù)數(shù)不同時(shí),ACOLB算法依然可靠,本組實(shí)驗(yàn)中調(diào)度長度優(yōu)化率最小值是13%,負(fù)載均衡優(yōu)化率最小值25%。

從實(shí)驗(yàn)3和實(shí)驗(yàn)4調(diào)度結(jié)果可看出,對于隨機(jī)DAG,ACOLB算法仍然可以達(dá)到優(yōu)化效果,其中調(diào)度長度優(yōu)化率在13%以上;負(fù)載均衡改善效果明顯,優(yōu)化率在25%以上,實(shí)現(xiàn)了處理器負(fù)載均衡,提高了系統(tǒng)整體效能。

4 結(jié)束語

本文針對當(dāng)前異構(gòu)信號處理平臺信號處理應(yīng)用的調(diào)度算法中處理器負(fù)載不均衡造成系統(tǒng)資源利用不合理的問題,提出了ACOLB算法。該算法在蟻群優(yōu)化算法基礎(chǔ)上,利用CPOP調(diào)度結(jié)果解決初始信息素不足問題;利用HEFT調(diào)度列表縮小搜索空間,提升搜索速度;利用輪盤賭策略跳出局部最優(yōu)解;增加負(fù)載均衡啟發(fā)因子均衡調(diào)度結(jié)果。通過仿真得出,ACOLB算法在任務(wù)調(diào)度長度和負(fù)載均衡方面均有改進(jìn),證明了算法的有效性和可靠性。其中調(diào)度長度優(yōu)化率為13%,優(yōu)化效果一般,是下一步研究方向;負(fù)載均衡優(yōu)化率為25%,優(yōu)化效果明顯。運(yùn)用該算法可解決處理器負(fù)載不均衡問題,使異構(gòu)信號處理平臺負(fù)載更加均衡,發(fā)揮最大效能。