一個基于魚群算法的多核系統實時節能調度

張建軍 郭偉華

(海軍工程大學基礎部 湖北 武漢 430033)

0 引 言

能耗已經成為現代實時嵌入式系統設計時需考慮的一個重要因素，特別是電池驅動的無人操控裝備、無線移動和便攜式計算設備。在保證實時性的前提下，盡可能地降低任務的執行能耗已成為多核系統實時任務調度研究領域的熱點。

多核系統的實時節能調度問題已經被證明是一個NP-Hard問題[2]。一般來說，該問題可以歸結為以下問題的求解[1]：(1)分配問題，即任務應該在哪一個核上執行；(2)優先級問題，即分配到同一處理器核上的任務的執行順序問題；(3)動態電壓調節(Dynamic Voltage Scaling，DVS)問題，即任務應以何電壓級來執行。

目前針對該問題的算法大都基于局部法[3-6]的思想。例如：Pagani等[3]針對周期任務模型，根據能耗最壞情況下近似因子分析，提出一種單頻近似方法(Single Frequency Approximation，SFA)；Huang等[5]利用EDF算法和片上全局DVS技術，設計了一種簡單的靜態DVS調節啟發式方法。上述調度策略均取得了一定的節能效果，但只考慮了全局DVS，沒有考慮對每個核分別進行DVS。

近年來，智能優化算法也逐漸被應用到實時任務節能調度領域并成為新的研究方向。其中，Kianzad等[6]基于遺傳算法提出了兩種調度策略，一是基于比例分布和并行算法的齊次遺傳列表調度并應用靜態功率管理的策略(Homogeneous Genetic List Scheduling+Static Power Management with Proportional Distribution and Parallelism Algorithm，HGLS+PDP-SPM)；二是綜合考慮任務分配、執行順序和電壓調節，并以單個染色體的形式對它們進行編碼的整體節能調度框架(combined assignment，scheduling，and power management，CASPER)。以上調度策略均是基于遺傳算法研究多核系統的實時節能調度問題，由于遺傳算法本身存在著易于“早熟”等問題，因而盡管它們都能取得一定的節能效果，但仍存在著容易陷入局部最優解的突出問題。

李曉磊等[7]通過研究魚群的行為特點，并應用動物自治體的模型，提出人工魚群算法(Artificial Fish-swarm Algorithm，AFSA)。其模擬魚的聚群、追尾等行為，然后選擇其中食物濃度最大的行為來實際執行。AFSA是一種有效的尋優算法，與GA相比具有并行性、全局尋優能力強、尋優速度快等特點。

由于同構環境下的多核系統實時節能調度問題本質上是典型的并行計算問題，因而與GA相比，基于AFSA研究該問題具有更強的針對性；另一方面，相比GA，AFSA的全局尋優能力強，基于AFSA研究該問題可以有效避免陷入局部最優。

因此，本文基于AFSA設計一種新的調度策略(Combined Assignment and Power-management basing on Artificial Fish-Swarm Algorithm，CAP-AFSA)。其基本思想是：定義高度值并藉此對任務節點進行優先級排序，以確定執行順序；對任務分配及電壓調節進行整合編碼；基于可行性規則處理截止期約束條件，限制尋優方向，以滿足系統的實時性要求；在上述基礎上對問題進行分析轉化，建立相應模型并應用AFSA進行迭代尋優。仿真結果表明，與HGLS+PDP-SPM和CASPER相比，應用CAP-AFSA進行任務調度能得到更好的節能效果。

1 問題模型

1.1 系統模型

本文的多核系統采用模型P={P1,P2,…,Pn}描述，其中Pi(i=1,2,…,n)為同構的處理器核，n為處理器核的個數。同時，將實時嵌入式任務抽象地用有向無環圖[8](Directed Acyclic Graph，DAG)描述，并用一個四元組G(N,E,W,D)來表示，其中：任務集N={N1,N2,…,Nm}，Ni(i=1,2,…,m)為子任務節點；鄰接矩陣E={eij|ti,tj∈T}表示任務節點之間的依賴關系和通信代價，eij=(ti,tj)>0表示ti是tj的前趨節點，tj是ti的后繼節點，eij的值表示ti和tj之間的通信開銷；W={w1,w2,…,wm}，其中wi表示任務節點Ni的估計執行時間(i=1,2,…,m)，一般取最壞執行時間；D表示任務截止時間，可根據文獻[9]中的方法求得。

1.2 能耗模型

目前大部分嵌入式系統的處理器都采用了COMS集成電路，其功耗主要由靜態功耗和動態功耗兩部分組成。其中，動態功耗約占總功耗的70%左右[10]。

由于靜態功耗占比相對較低，且受所采用的調度策略影響很小，因此本文只考慮動態功耗的影響，采用下述功耗模型[11]：

(1)

式中：Pdyn表示動態功耗；α、k為常數；Cl是電路負載電容；Vdd為電路中處理器核的運行電壓；f為運行頻率；Vt為門限電壓。一般有Vdd>>Vt，即處理器核上的運行頻率和電壓間近似線性相關。

執行任務節點Ni(i=1,2,…,m)的能耗為：

(2)

式中：ti=Tc(i)/f為任務節點Ni的執行時間；Tc(i)為執行Ni所需的時鐘周期數；Vdd(i)為執行Ni的運行電壓；Pdyn(i)為執行Ni的動態功耗。可以看出，降低任務節點的執行電壓可有效降低動態功耗，但會導致任務的執行時間增加。

本文基于DVS研究多核系統實時節能調度問題，其基本思想是在保證實時性的前提下，通過動態調節執行電壓來降低能耗。經電壓調節后，我們可將執行嵌入式任務G的能耗表示為：

(3)

上述能耗模型中總能耗只與各任務節點的執行電壓與執行所需時鐘周期數有關。由于時鐘周期數是任務節點的固有屬性，與調度策略無關，故只需求得各任務節點的執行電壓即可得到總能耗。因而采用本能耗模型便于計算總能耗，進而得到節能效率。

2 策略設計

與GA相比，AFSA的并行性處理及全局尋優能力更強，因而基于AFSA設計調度策略對多核系統的實時節能調度問題這一典型的并行計算問題的針對性更強，且能夠有效避免陷入局部最優。

本文基于AFSA設計的調度策略，具體思路如下：

(1)為避免破壞任務節點之間的依賴關系，基于高度值優先級確定執行順序。

(2)為便于整體化考慮任務分配和電壓調節過程，將運行電壓離散化處理，從而得到整合任務分配和電壓調節過程的新編碼方案。同時在模擬行為中進行了取整與越界處理，以確保人工魚狀態向量的合理性。

(3)在問題分析與模型建立中，定義任務節點的開始執行時刻與終止執行時刻，并結合任務節點的執行順序等限制條件給出計算公式，進而結合分配方案得到任務節點的具體狀態。

(4)由于調度問題中存在截止期約束條件，直接應用AFSA迭代尋優所得解不一定可行。因此，本文基于可行性規則處理截止期約束條件，使得尋優過程始終朝著可行、更優的方向前進。

2.1 任務節點的預處理

任務節點的預處理基于以下定義：

定義1對任務節點Ni，定義其高度值h(Ni)[6]為：

(4)

式中：i∈{1,2,…,m}；pred(Ni)表示Ni的前趨節點。

本文基于高度值優先級，采用以下策略對任務執行順序進行排序：

(1)對任務圖G，由式(4)求出任務節點Ni的高度值h(Ni)(i=1,2,…,m)，再將任務節點按其高度值升序排序，并重新編號，仍記為N1,N2,…,Nm；(2)當兩個任務分配到同一處理器核上時，編號小的任務優先執行。

2.2 基于AFSA的算法設計

2.2.1人工魚行為描述

在本文中，用X表示人工魚的位置向量；用η=f(X)表示人工魚當前所在位置的食物濃度，用以表示節能效率；visual表示人工魚的感知距離；step表示人工魚移動的步長；delta表示擁擠度因子。

用以下方式描述覓食行為：設人工魚當前狀態為Xi，在其感知范圍內隨機選擇一新狀態Xj：

Xj=Xi+visual·rand

(5)

如果ηi<ηj，則向Xj前進一步：

(6)

式中：Xnext表示人工魚移動后的位置向量。

否則，重新選擇新狀態Xj進行嘗試。反復嘗試try_number次后，若仍無法前進，則隨機移動一步。

聚群行為則描述如下：設人工魚當前狀態為Xi，探索其感知范圍內的人工魚個體數nf及中心位置Xc。若ηc/nf>delta·ηi，表明該中心位置食物充足且不擁擠，則朝該中心方向前進一步：

(7)

否則執行覓食行為。

追尾行為可表示為：設人工魚當前狀態為Xi，探索其感知范圍內的食物濃度最高的人工魚個體狀態Xj。若ηj/nf>delta·ηi，表明Xj位置食物充足且不擁擠，則朝Xj的方向前進一步:

(8)

否則執行覓食行為。

2.2.2編碼策略及其取整與越界處理

為整合任務分配過程和電壓調節過程，并將它們編碼進同一條人工魚的位置向量中，本文選擇將核上的運行電壓Vdd離散化處理為k個電壓級別{V1

X=(x1,x2,…,xm,xm+1,xm+2,…,x2m)

(9)

式中：X的前m個分量表示任務分配策略：xi=j表示將第i個任務節點分配到第j個處理器核上；X的后m個分量表示任務執行電壓選擇策略：xm+i=j表示以電壓Vj執行第i個任務節點，即有：

(10)

由于X的分量分別表示任務分配策略和執行電壓級選擇策略，均為有界的正整數，因而在執行聚群、追尾等行為時，所得到的新狀態必須進行取整和越界處理，以保證模擬行為的可行性。

以聚群行為為例，式(7)中的Xnext首先需取整為：

(11)

再進行越界處理：

(12)

式中：j∈{1,2,…,m}。

2.2.3問題分析與模型建立

基于DVS的多核系統實時節能調度問題的本質是在保證任務實時性的基礎上進行任務分配、執行順序和執行電壓的選擇以最小化能耗，是一個有約束優化問題。

由于任務節點Ni的估計執行時間wi與執行任務節點所需的時鐘周期數Tc(i)成正比，由式(3)可得：

(13)

式中：a為常數。

不妨假設未經電壓調節前任務均以最大執行電壓執行，即未經電壓調節前的任務執行能耗為：

(14)

式中：(Vdd)max為處理器核上最大執行電壓。

從式(13)-式(14)可見，對給定的任務圖，調度策略對能耗的影響由各任務節點的執行電壓選擇唯一確定，進而節能效率可由各任務節點的執行電壓表示。

命題1節能效率可表示為：

(15)

定義2對于任意人工魚的狀態向量X，定義任務分配的關聯矩陣A為：

(16)

式中：i∈{1,2,…,m}；k∈{1,2,…,n}。

關于任務節點的開始執行時刻與終止執行時刻，有以下結論：

命題2記任務節點Ni(i=1,2,…,m)的開始執行時刻為Tb(i)，終止執行時刻為Tf(i)。則：

(17)

(18)

式中：

(19)

若Qji=1，說明任務節點Ni、Nj分配到不同的處理器核上；若Qji=0，說明任務節點Ni、Nj分配到同一個處理器核上。

證明：由任務調度需滿足以下規則：

(1)任務節點的執行順序要滿足DAG上的依賴關系，即任意任務節點必須在其前趨節點全部執行完畢后執行；

(2)任意處理器核的利用率不超過1，即一個處理器核上不可同時執行多個任務節點。

由上述規則即可推得結論。

命題3多核系統的實時任務節能調度問題可歸結為具有實時性約束條件的節能效率最大值問題，可表示為：

(20)

式中：D為截止時限。

2.2.4基于可行性規則的截止期處理方案

針對相應的有約束最大值問題如式(20)，為確保所設計的調度策略滿足約束條件，本節基于可行性規則，即可行解始終優于不可行解這一原則處理截止期約束條件，對迭代尋優過程限制如下：

記人工魚i當前狀態為Xi，節能效率為ηi，完成時間為Ti；模擬行為所得狀態為Xnext，節能效率為ηnext，完成時間為Tnext。基于可行性規則，當以下三種行為中任意一種發生時，均說明Xnext狀態優于Xi狀態，執行模擬行為：

(1)Ti>D且Tnext≤D：Xi不可行，Xnext可行，表示可行解始終優于不可行解；

(2)Ti≤D，Tnext≤D且ηi<ηnext：Xi和Xnext均可行，且Xnext節能效果更好，表示節能效率高的可行解狀態更優；

(3)Ti>Tnext>D：Xi和Xnext均不可行，但Xnext完成時間相對較小，表示執行時間相對較短的不可行解狀態更優。

2.3 CAP-AFSA描述

首先，計算給定任務圖G上所有任務節點Ni的高度值h(Ni)(i=1,2,…,m)，基于高度值升序排序并重新編號，仍依次記為N1，N2，…，Nm。其次，根據編碼方案生成初始魚群，并計算各人工魚相應的節能效率η和完成時間T，將其中狀態最優的個體賦給公告板。基于可行性規則進行迭代尋優，得到最優狀態X0、相應的節能效率η0、完成時間T0并生成迭代曲線。最后,計算任務節點Ni(i=1,2,…,m)開始執行時刻Tb(i)與終止執行時刻Tf(i)，對最優狀態X0進行解碼，得到執行結果圖。

算法1CAP-AFSA調度策略

輸入：任務圖G(N,E,W,D)，處理器核的個數n，k個電壓級別Vdd={V1

輸出：公告版狀態X0，節能效率η0，完成時間T0。

Step1對任務節點進行預處理，計算任務節點的高度值，并按其高度值升序排序，并重新編號，仍記為N1,N2,…,Nm。

Step2生成初始魚群,代碼如下：

fori=1:Nfish

forj=1:m

X(i,j)=round(rand(1,1)*(n-1))+1;

%任務分配

end

forj=m+1:2m

X(i,j)=round(rand(1,1)*(k-1))+1;

%任務執行電壓級選擇

end

end

并記迭代次數gen=1。

Step3公告板賦初值：計算初始魚群中各人工魚的節能效率η和完成時間T。如果?T≤D，比較所有滿足T≤D的狀態X的節能效率η大小，取η最大的魚賦值給公告板；否則取T最小的魚賦值給公告板。

Step4檢查gen是否小于最大迭代次數，如果gen小于最大迭代次數，轉至Step 5；否則轉至輸出，算法結束。

Step5行為選擇：各人工魚模擬追尾、聚群等行為，基于可行性規則選擇狀態更優的行為實際執行。

Step6公告板更新：各人工魚基于可行性規則比較自身新狀態與公告板狀態，如果自身新狀態更優，則將自身新狀態賦給公告板。記gen←gen+1，轉至Step 4。

3 仿真實例與結果分析

本文在Windows 8.1系統環境中用MATLAB 2018b編程實現了提出的CAP-AFSA調度策略，并采用上述系統模型及經典實例[6]進行仿真實驗以驗證算法的有效性。

仿真實驗采用的處理器模型包含6個同構的處理器核，其中每個處理器核都能獨立地調整執行電壓，且有4種離散電壓模式，分別為(1.75 V，1 000 MHz)、(1.40 V，800 MHz)、(1.20 V，600 MHz)和(1.00 V，466 MHz)；并采用以下5個經典的測試任務圖(它們分別表示相關類別的應用問題)，其中：RG1[12]是一個具有通信成本的優先圖；RG2[13]是使用模型G(Γ,→,μ,η)的一個任務圖例；RG3[14]是基于高斯消元法求解含4個變量的四個方程的實現過程；RG4[14]是適應PDG(程序依賴圖)的一個物理算法；RG5[15]是拉普拉斯變換的一種實現。

CAP-AFSA的參數設置為魚群規模Nfish=500；最大迭代次數為200；最多試探次數try_number=100；感知距離visual=5；擁擠度因子delta=0.618；步長step=1。

3.1 實例求解

以RG5為例，介紹CAP-AFSA迭代尋優的過程。

(1)基于高度值優先級對任務節點進行預處理，得到各任務節點的高度值和新編號，結果如圖1所示。

圖1 RG5中任務節點的預處理

(2)應用CAP-AFSA進行迭代尋優，經迭代200次后，所得公告板狀態為：

X0=[6,1,6,2,3,4,6,6,2,3,4,2,2,3,4,3,3,4,1,

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

(21)

節能效率η0=67.35%，完成時間T0=480。

節點開始執行時刻Tb與終止執行時刻Tf分別為:

Tb=[0,140,80,140,140,140,120,180,240,240,240,270,310,370,370,390,410,470]

Tf=[80,180,120,180,180,180,180,210,270,270,270,310,330,390,390,410,420,480]

(22)

(3)結合任務節點的開始執行時刻Tb和終止執行時刻Tf對所得公告板狀態X0進行解碼，得到執行方案如圖2所示，迭代曲線如圖3所示。

圖2 CAP-AFSA調度RG5所得執行方案

3.2 仿真結果及其分析

將HGLS+PDP-SPM、CASPER與本文調度策略所得結果進行比較，結果見表1。可以看出，CAP-AFSA執行每個任務圖的節能效率均優于HGLS+PDP-SPM與CASPER，且相對HGLS+PDP-SPM平均節能效率提高了約10.9%，相對CASPER平均節能效率提高了約4.2%，說明CAP-AFSA調度策略節能效果較好。

表1 CAP-AFSA與相關調度策略節能效率比較

應用CAP-AFSA調度RG1～RG4的迭代尋優曲線分別如圖4至圖7所示。

圖4 CAP-AFSA調度RG1的迭代尋優曲線

圖5 CAP-AFSA調度RG2的迭代尋優曲線

圖6 CAP-AFSA調度RG3的迭代尋優曲線

圖7 CAP-AFSA調度RG4的迭代尋優曲線

可以看出，應用CAP-AFSA調度RG1、RG2、RG4的迭代曲線分別在節能效率達到60.7%、54.3%、62.2%的附近時尋優過程暫時停滯，而后均跳出該點并進一步迭代尋優。因此，可以認為執行RG1、RG2、RG4的節能效率局部最優值分別位于60.7%、54.3%、62.2%附近，這恰好是應用CAPSER執行RG1、RG2、RG4所得的節能效率。可見，應用CAP-AFSA尋優時有效地跳出了局部最優，而應用CAPSER尋優時陷入了局部最優。上述仿真結果表明，與GA相比，AFSA的全局尋優能力更強，從而應用CAP-AFSA能較好地跳出局部最優。

4 結 語

本文針對基于GA的調度策略HGLS+PDP-SPM、CASPER存在的易陷入局部最優等突出問題，基于有約束的AFSA，研究多核系統的實時節能調度問題。通過定義并基于任務節點的高度值確定任務的執行順序；對任務分配和電壓調節進行有機的整合編碼；對人工魚位置向量進行取整和越界處理；基于可行性規則處理截止期約束以保證模擬行為的可行性，進而限制尋優過程等一系列過程，建立有效的問題模型，并應用AFSA進行迭代尋優。仿真結果表明，與HGLS+PDP-SPM、CASPER相比，應用CAP-AFSA執行任務圖可以獲得更好的節能效果，其總體性能有較顯著的改善，因而不失為一種有效的、更具應用性的實時節能調度策略。下一步工作將集中于對更為復雜的多核系統的實時節能調度問題模型進行研究。