張建軍 郭偉華

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

0 引 言

能耗已經(jīng)成為現(xiàn)代實(shí)時(shí)嵌入式系統(tǒng)設(shè)計(jì)時(shí)需考慮的一個(gè)重要因素，特別是電池驅(qū)動(dòng)的無人操控裝備、無線移動(dòng)和便攜式計(jì)算設(shè)備。在保證實(shí)時(shí)性的前提下，盡可能地降低任務(wù)的執(zhí)行能耗已成為多核系統(tǒng)實(shí)時(shí)任務(wù)調(diào)度研究領(lǐng)域的熱點(diǎn)。

多核系統(tǒng)的實(shí)時(shí)節(jié)能調(diào)度問題已經(jīng)被證明是一個(gè)NP-Hard問題[2]。一般來說，該問題可以歸結(jié)為以下問題的求解[1]：(1)分配問題，即任務(wù)應(yīng)該在哪一個(gè)核上執(zhí)行；(2)優(yōu)先級(jí)問題，即分配到同一處理器核上的任務(wù)的執(zhí)行順序問題；(3)動(dòng)態(tài)電壓調(diào)節(jié)(Dynamic Voltage Scaling，DVS)問題，即任務(wù)應(yīng)以何電壓級(jí)來執(zhí)行。

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

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

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

由于同構(gòu)環(huán)境下的多核系統(tǒng)實(shí)時(shí)節(jié)能調(diào)度問題本質(zhì)上是典型的并行計(jì)算問題，因而與GA相比，基于AFSA研究該問題具有更強(qiáng)的針對(duì)性；另一方面，相比GA，AFSA的全局尋優(yōu)能力強(qiáng)，基于AFSA研究該問題可以有效避免陷入局部最優(yōu)。

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

1 問題模型

1.1 系統(tǒng)模型

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

1.2 能耗模型

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

由于靜態(tài)功耗占比相對(duì)較低，且受所采用的調(diào)度策略影響很小，因此本文只考慮動(dòng)態(tài)功耗的影響，采用下述功耗模型[11]：

(1)

式中：Pdyn表示動(dòng)態(tài)功耗；α、k為常數(shù)；Cl是電路負(fù)載電容；Vdd為電路中處理器核的運(yùn)行電壓；f為運(yùn)行頻率；Vt為門限電壓。一般有Vdd>>Vt，即處理器核上的運(yùn)行頻率和電壓間近似線性相關(guān)。

執(zhí)行任務(wù)節(jié)點(diǎn)Ni(i=1,2,…,m)的能耗為：

(2)

式中：ti=Tc(i)/f為任務(wù)節(jié)點(diǎn)Ni的執(zhí)行時(shí)間；Tc(i)為執(zhí)行Ni所需的時(shí)鐘周期數(shù)；Vdd(i)為執(zhí)行Ni的運(yùn)行電壓；Pdyn(i)為執(zhí)行Ni的動(dòng)態(tài)功耗?？梢钥闯觯档腿蝿?wù)節(jié)點(diǎn)的執(zhí)行電壓可有效降低動(dòng)態(tài)功耗，但會(huì)導(dǎo)致任務(wù)的執(zhí)行時(shí)間增加。

本文基于DVS研究多核系統(tǒng)實(shí)時(shí)節(jié)能調(diào)度問題，其基本思想是在保證實(shí)時(shí)性的前提下，通過動(dòng)態(tài)調(diào)節(jié)執(zhí)行電壓來降低能耗。經(jīng)電壓調(diào)節(jié)后，我們可將執(zhí)行嵌入式任務(wù)G的能耗表示為：

(3)

上述能耗模型中總能耗只與各任務(wù)節(jié)點(diǎn)的執(zhí)行電壓與執(zhí)行所需時(shí)鐘周期數(shù)有關(guān)。由于時(shí)鐘周期數(shù)是任務(wù)節(jié)點(diǎn)的固有屬性，與調(diào)度策略無關(guān)，故只需求得各任務(wù)節(jié)點(diǎn)的執(zhí)行電壓即可得到總能耗。因而采用本能耗模型便于計(jì)算總能耗，進(jìn)而得到節(jié)能效率。

2 策略設(shè)計(jì)

與GA相比，AFSA的并行性處理及全局尋優(yōu)能力更強(qiáng)，因而基于AFSA設(shè)計(jì)調(diào)度策略對(duì)多核系統(tǒng)的實(shí)時(shí)節(jié)能調(diào)度問題這一典型的并行計(jì)算問題的針對(duì)性更強(qiáng)，且能夠有效避免陷入局部最優(yōu)。

本文基于AFSA設(shè)計(jì)的調(diào)度策略，具體思路如下：

(1)為避免破壞任務(wù)節(jié)點(diǎn)之間的依賴關(guān)系，基于高度值優(yōu)先級(jí)確定執(zhí)行順序。

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

(3)在問題分析與模型建立中，定義任務(wù)節(jié)點(diǎn)的開始執(zhí)行時(shí)刻與終止執(zhí)行時(shí)刻，并結(jié)合任務(wù)節(jié)點(diǎn)的執(zhí)行順序等限制條件給出計(jì)算公式，進(jìn)而結(jié)合分配方案得到任務(wù)節(jié)點(diǎn)的具體狀態(tài)。

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

2.1 任務(wù)節(jié)點(diǎn)的預(yù)處理

任務(wù)節(jié)點(diǎn)的預(yù)處理基于以下定義：

定義1對(duì)任務(wù)節(jié)點(diǎn)Ni，定義其高度值h(Ni)[6]為：

(4)

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

本文基于高度值優(yōu)先級(jí)，采用以下策略對(duì)任務(wù)執(zhí)行順序進(jìn)行排序：

(1)對(duì)任務(wù)圖G，由式(4)求出任務(wù)節(jié)點(diǎn)Ni的高度值h(Ni)(i=1,2,…,m)，再將任務(wù)節(jié)點(diǎn)按其高度值升序排序，并重新編號(hào)，仍記為N1,N2,…,Nm；(2)當(dāng)兩個(gè)任務(wù)分配到同一處理器核上時(shí)，編號(hào)小的任務(wù)優(yōu)先執(zhí)行。

2.2 基于AFSA的算法設(shè)計(jì)

2.2.1人工魚行為描述

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

用以下方式描述覓食行為：設(shè)人工魚當(dāng)前狀態(tài)為Xi，在其感知范圍內(nèi)隨機(jī)選擇一新狀態(tài)Xj：

Xj=Xi+visual·rand

(5)

如果ηi<ηj，則向Xj前進(jìn)一步：

(6)

式中：Xnext表示人工魚移動(dòng)后的位置向量。

否則，重新選擇新狀態(tài)Xj進(jìn)行嘗試。反復(fù)嘗試try_number次后，若仍無法前進(jìn)，則隨機(jī)移動(dòng)一步。

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

(7)

否則執(zhí)行覓食行為。

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

(8)

否則執(zhí)行覓食行為。

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

為整合任務(wù)分配過程和電壓調(diào)節(jié)過程，并將它們編碼進(jìn)同一條人工魚的位置向量中，本文選擇將核上的運(yùn)行電壓Vdd離散化處理為k個(gè)電壓級(jí)別{V1

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

(9)

式中：X的前m個(gè)分量表示任務(wù)分配策略：xi=j表示將第i個(gè)任務(wù)節(jié)點(diǎn)分配到第j個(gè)處理器核上；X的后m個(gè)分量表示任務(wù)執(zhí)行電壓選擇策略：xm+i=j表示以電壓Vj執(zhí)行第i個(gè)任務(wù)節(jié)點(diǎn)，即有：

(10)

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

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

(11)

再進(jìn)行越界處理：

(12)

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

2.2.3問題分析與模型建立

基于DVS的多核系統(tǒng)實(shí)時(shí)節(jié)能調(diào)度問題的本質(zhì)是在保證任務(wù)實(shí)時(shí)性的基礎(chǔ)上進(jìn)行任務(wù)分配、執(zhí)行順序和執(zhí)行電壓的選擇以最小化能耗，是一個(gè)有約束優(yōu)化問題。

由于任務(wù)節(jié)點(diǎn)Ni的估計(jì)執(zhí)行時(shí)間wi與執(zhí)行任務(wù)節(jié)點(diǎn)所需的時(shí)鐘周期數(shù)Tc(i)成正比，由式(3)可得：

(13)

式中：a為常數(shù)。

不妨假設(shè)未經(jīng)電壓調(diào)節(jié)前任務(wù)均以最大執(zhí)行電壓執(zhí)行，即未經(jīng)電壓調(diào)節(jié)前的任務(wù)執(zhí)行能耗為：

(14)

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

從式(13)-式(14)可見，對(duì)給定的任務(wù)圖，調(diào)度策略對(duì)能耗的影響由各任務(wù)節(jié)點(diǎn)的執(zhí)行電壓選擇唯一確定，進(jìn)而節(jié)能效率可由各任務(wù)節(jié)點(diǎn)的執(zhí)行電壓表示。

命題1節(jié)能效率可表示為：

(15)

定義2對(duì)于任意人工魚的狀態(tài)向量X，定義任務(wù)分配的關(guān)聯(lián)矩陣A為：

(16)

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

關(guān)于任務(wù)節(jié)點(diǎn)的開始執(zhí)行時(shí)刻與終止執(zhí)行時(shí)刻，有以下結(jié)論：

命題2記任務(wù)節(jié)點(diǎn)Ni(i=1,2,…,m)的開始執(zhí)行時(shí)刻為Tb(i)，終止執(zhí)行時(shí)刻為Tf(i)。則：

(17)

(18)

式中：

(19)

若Qji=1，說明任務(wù)節(jié)點(diǎn)Ni、Nj分配到不同的處理器核上；若Qji=0，說明任務(wù)節(jié)點(diǎn)Ni、Nj分配到同一個(gè)處理器核上。

證明：由任務(wù)調(diào)度需滿足以下規(guī)則：

(1)任務(wù)節(jié)點(diǎn)的執(zhí)行順序要滿足DAG上的依賴關(guān)系，即任意任務(wù)節(jié)點(diǎn)必須在其前趨節(jié)點(diǎn)全部執(zhí)行完畢后執(zhí)行；

(2)任意處理器核的利用率不超過1，即一個(gè)處理器核上不可同時(shí)執(zhí)行多個(gè)任務(wù)節(jié)點(diǎn)。

由上述規(guī)則即可推得結(jié)論。

命題3多核系統(tǒng)的實(shí)時(shí)任務(wù)節(jié)能調(diào)度問題可歸結(jié)為具有實(shí)時(shí)性約束條件的節(jié)能效率最大值問題，可表示為：

(20)

式中：D為截止時(shí)限。

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

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

記人工魚i當(dāng)前狀態(tài)為Xi，節(jié)能效率為ηi，完成時(shí)間為Ti；模擬行為所得狀態(tài)為Xnext，節(jié)能效率為ηnext，完成時(shí)間為Tnext?；诳尚行砸?guī)則，當(dāng)以下三種行為中任意一種發(fā)生時(shí)，均說明Xnext狀態(tài)優(yōu)于Xi狀態(tài)，執(zhí)行模擬行為：

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

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

(3)Ti>Tnext>D：Xi和Xnext均不可行，但Xnext完成時(shí)間相對(duì)較小，表示執(zhí)行時(shí)間相對(duì)較短的不可行解狀態(tài)更優(yōu)。

2.3 CAP-AFSA描述

首先，計(jì)算給定任務(wù)圖G上所有任務(wù)節(jié)點(diǎn)Ni的高度值h(Ni)(i=1,2,…,m)，基于高度值升序排序并重新編號(hào)，仍依次記為N1，N2，…，Nm。其次，根據(jù)編碼方案生成初始魚群，并計(jì)算各人工魚相應(yīng)的節(jié)能效率η和完成時(shí)間T，將其中狀態(tài)最優(yōu)的個(gè)體賦給公告板?；诳尚行砸?guī)則進(jìn)行迭代尋優(yōu)，得到最優(yōu)狀態(tài)X0、相應(yīng)的節(jié)能效率η0、完成時(shí)間T0并生成迭代曲線。最后,計(jì)算任務(wù)節(jié)點(diǎn)Ni(i=1,2,…,m)開始執(zhí)行時(shí)刻Tb(i)與終止執(zhí)行時(shí)刻Tf(i)，對(duì)最優(yōu)狀態(tài)X0進(jìn)行解碼，得到執(zhí)行結(jié)果圖。

算法1CAP-AFSA調(diào)度策略

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

輸出：公告版狀態(tài)X0，節(jié)能效率η0，完成時(shí)間T0。

Step1對(duì)任務(wù)節(jié)點(diǎn)進(jìn)行預(yù)處理，計(jì)算任務(wù)節(jié)點(diǎn)的高度值，并按其高度值升序排序，并重新編號(hào)，仍記為N1,N2,…,Nm。

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

fori=1:Nfish

forj=1:m

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

%任務(wù)分配

end

forj=m+1:2m

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

%任務(wù)執(zhí)行電壓級(jí)選擇

end

end

并記迭代次數(shù)gen=1。

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

Step4檢查gen是否小于最大迭代次數(shù)，如果gen小于最大迭代次數(shù)，轉(zhuǎn)至Step 5；否則轉(zhuǎn)至輸出，算法結(jié)束。

Step5行為選擇：各人工魚模擬追尾、聚群等行為，基于可行性規(guī)則選擇狀態(tài)更優(yōu)的行為實(shí)際執(zhí)行。

Step6公告板更新：各人工魚基于可行性規(guī)則比較自身新狀態(tài)與公告板狀態(tài)，如果自身新狀態(tài)更優(yōu)，則將自身新狀態(tài)賦給公告板。記gen←gen+1，轉(zhuǎn)至Step 4。

3 仿真實(shí)例與結(jié)果分析

本文在Windows 8.1系統(tǒng)環(huán)境中用MATLAB 2018b編程實(shí)現(xiàn)了提出的CAP-AFSA調(diào)度策略，并采用上述系統(tǒng)模型及經(jīng)典實(shí)例[6]進(jìn)行仿真實(shí)驗(yàn)以驗(yàn)證算法的有效性。

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

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

3.1 實(shí)例求解

以RG5為例，介紹CAP-AFSA迭代尋優(yōu)的過程。

(1)基于高度值優(yōu)先級(jí)對(duì)任務(wù)節(jié)點(diǎn)進(jìn)行預(yù)處理，得到各任務(wù)節(jié)點(diǎn)的高度值和新編號(hào)，結(jié)果如圖1所示。

圖1 RG5中任務(wù)節(jié)點(diǎn)的預(yù)處理

(2)應(yīng)用CAP-AFSA進(jìn)行迭代尋優(yōu)，經(jīng)迭代200次后，所得公告板狀態(tài)為：

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)

節(jié)能效率η0=67.35%，完成時(shí)間T0=480。

節(jié)點(diǎn)開始執(zhí)行時(shí)刻Tb與終止執(zhí)行時(shí)刻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)結(jié)合任務(wù)節(jié)點(diǎn)的開始執(zhí)行時(shí)刻Tb和終止執(zhí)行時(shí)刻Tf對(duì)所得公告板狀態(tài)X0進(jìn)行解碼，得到執(zhí)行方案如圖2所示，迭代曲線如圖3所示。

圖2 CAP-AFSA調(diào)度RG5所得執(zhí)行方案

3.2 仿真結(jié)果及其分析

將HGLS+PDP-SPM、CASPER與本文調(diào)度策略所得結(jié)果進(jìn)行比較，結(jié)果見表1?？梢钥闯觯珻AP-AFSA執(zhí)行每個(gè)任務(wù)圖的節(jié)能效率均優(yōu)于HGLS+PDP-SPM與CASPER，且相對(duì)HGLS+PDP-SPM平均節(jié)能效率提高了約10.9%，相對(duì)CASPER平均節(jié)能效率提高了約4.2%，說明CAP-AFSA調(diào)度策略節(jié)能效果較好。

表1 CAP-AFSA與相關(guān)調(diào)度策略節(jié)能效率比較

應(yīng)用CAP-AFSA調(diào)度RG1～RG4的迭代尋優(yōu)曲線分別如圖4至圖7所示。

圖4 CAP-AFSA調(diào)度RG1的迭代尋優(yōu)曲線

圖5 CAP-AFSA調(diào)度RG2的迭代尋優(yōu)曲線

圖6 CAP-AFSA調(diào)度RG3的迭代尋優(yōu)曲線

圖7 CAP-AFSA調(diào)度RG4的迭代尋優(yōu)曲線

可以看出，應(yīng)用CAP-AFSA調(diào)度RG1、RG2、RG4的迭代曲線分別在節(jié)能效率達(dá)到60.7%、54.3%、62.2%的附近時(shí)尋優(yōu)過程暫時(shí)停滯，而后均跳出該點(diǎn)并進(jìn)一步迭代尋優(yōu)。因此，可以認(rèn)為執(zhí)行RG1、RG2、RG4的節(jié)能效率局部最優(yōu)值分別位于60.7%、54.3%、62.2%附近，這恰好是應(yīng)用CAPSER執(zhí)行RG1、RG2、RG4所得的節(jié)能效率?？梢?，應(yīng)用CAP-AFSA尋優(yōu)時(shí)有效地跳出了局部最優(yōu)，而應(yīng)用CAPSER尋優(yōu)時(shí)陷入了局部最優(yōu)。上述仿真結(jié)果表明，與GA相比，AFSA的全局尋優(yōu)能力更強(qiáng)，從而應(yīng)用CAP-AFSA能較好地跳出局部最優(yōu)。

4 結(jié) 語

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