葉常華，左朝樹

(保密通信重點實驗室，成都 610041)

0 引言

近年來，隨著無線和移動設(shè)備的廣泛應用，功耗問題日益突出。功耗問題不是一個單一的問題，其關(guān)系到系統(tǒng)安全性及散熱代價等方面。因此，低功耗作為實時嵌入式系統(tǒng)的一個關(guān)鍵的設(shè)計需求，正在受到越來越多的關(guān)注。

對于多核的節(jié)能任務調(diào)度，張冬松等［1］做了深入討論，指出多核系統(tǒng)中的實時節(jié)能調(diào)度問題可以歸納為分配問題、優(yōu)先級問題和速度調(diào)節(jié)問題三個方面。彭蔓蔓等［2］提出了一種基于異構(gòu)多核處理器的節(jié)能任務分配方法。該方法通過將任務進行兩輪分配，降低了系統(tǒng)總能耗。桑楠等［3］提出了一種針對周期任務的多處理器節(jié)能調(diào)度算法。該算法通過靜態(tài)分析確定了最低處理器調(diào)度要求，在滿足可調(diào)度性的條件下動態(tài)縮放各個處理器電壓，從而降低了整個系統(tǒng)的能耗。Liu等［4］提出了一種針對流媒體應用的多核節(jié)能任務調(diào)度方法。該方法將依賴性任務集轉(zhuǎn)化為獨立任務后，在硬實時條件約束下以能耗最小為原則確定任務映射。王穎鋒等［5，6］提出了一種面向同構(gòu)多核處理器的節(jié)能任務調(diào)度算法。該算法將任務獨立化后，按照調(diào)度長度最短的原則安排任務映射，然后在各個核進行頻率/電壓調(diào)整以降低系統(tǒng)功耗。

這些研究一般都沒有考慮各處理器的任務在不同頻率/電壓模式下的電壓轉(zhuǎn)換能量，而且一些算法求得的解是近似最優(yōu)解，還有優(yōu)化的空間。因此，基于目前的研究現(xiàn)狀，通過深入研究，基于遺傳算法進行節(jié)能任務調(diào)度的方法被設(shè)計出來。該方法首先利用RDAG算法將任務獨立化，然后以能耗最低為原則，采用遺傳算法確定任務映射?；?Intel PXA270功耗模型，采用幾個隨機任務集進行仿真實驗，結(jié)果表明該方法比現(xiàn)有的方法節(jié)省了20%～30%的能耗。

1 任務和功耗

1.1 任務模型

任務集可以抽象為有向無環(huán)圖，表示為G={V，E，p，ET，CT，D}。其中 V 是結(jié)點集，E 是有向邊的集合，p是節(jié)點間所差的迭代次數(shù)的集合，ET表示任務的執(zhí)行周期數(shù)集合，CT表示任務間的通信周期數(shù)集合，D表示任務集的截止時間。例如，vi∈V、vj∈V分別表示任務集的兩個任務。eij表示兩個任務的依賴關(guān)系，即任務vj在vi之后執(zhí)行。p(eij)=k(k為常數(shù))表示任務vj在任務vi后的第k輪執(zhí)行。Eti∈ET表示任務vi執(zhí)行的周期數(shù)，Ctij∈CT表示任務vi和任務vj間的核間通信周期數(shù)。

1.2 功耗模型

對于具有多個核的同構(gòu)處理器，假設(shè)每個處理器核都支持m個離散的頻率/電壓模式。將每個核的頻率/電壓模式表示為Core(F，V)，F(xiàn)代表頻率的集合，V代表電壓的集合。其中，Corei=(fi，Vi)，表示一個頻率/電壓模式。

總能耗為

式中，Etask代表所有任務消耗的總能量;Ecommunication代表核間通信消耗的總能量;Etransition代表各核狀態(tài)變換消耗的總能量;Eidle代表各核空閑時小號的的總能量。

任務vi所消耗的動態(tài)能量為

式中，PAC是處理器每周期動態(tài)功耗;Eti是任務vi所需執(zhí)行周期數(shù);Ceff是每周期平均開關(guān)電容;Vdd是電源電壓;f是處理器時鐘頻率。電壓從Vddi轉(zhuǎn)換到Vddj所產(chǎn)生的轉(zhuǎn)換能量為

式中，Cr是電源導軌電容。

2 多核節(jié)能任務調(diào)度算法

2.1 算法思想

存在包含依賴關(guān)系的周期性硬實時任務集G={V，E，p，ET，CT，D}及具有 n 個核的同構(gòu)處理器，其中每個核的頻率/電壓模式為Core(F，V)。算法是把該任務集的任務以特定處理器頻率分配到各個核上進行處理，使得總能耗最小。算法思想如圖1所示，首先使用Liu等［4］提出的RDAG算法將任務獨立化，然后使用基于多核節(jié)能任務調(diào)度的遺傳算法確定最佳的任務映射。

圖1 算法思想

其中，基于多核節(jié)能任務調(diào)度的遺傳算法思想如下。

(1)任務調(diào)度種群的初始化

遺傳算法的一個優(yōu)點是它能夠隱式并行地搜索解空間的多個解，當然這需要隨機地生成一個包含多個解的初始種群。設(shè)任務集共有m個任務，種群中的個體 i表示為 Ui={vi1，vi2，…，vim，fi1，fi2，…，fim}。vij代表為任務集中的任務vj分配的處理器核，fij代表該任務在核vij上運行時對應的處理器頻率。種群初始化步驟如下:(a)隨機產(chǎn)生一個個體;(b)將該個體中各核上的任務按fi由大到小的序列執(zhí)行;(c)若某處理器核上的任務執(zhí)行總時間長于限定時間，則淘汰該個體;(d)回到步驟(a)，直到產(chǎn)生給定數(shù)目的個體，形成一個種群。

(2)調(diào)度序列的選擇

選擇的目的是使得較優(yōu)的個體能夠以較大的概率遺傳到下一代。設(shè)個體i適應度函數(shù)為

Egi是個體i消耗的總能量。假設(shè)任務集有m個任務，處理器核共有n個，核i上的任務共S(i)個，按執(zhí)行頻率降序排列。ET表示任務的執(zhí)行周期數(shù)集合，CT表示任務間的通信周期數(shù)集合。任務vi和任務vj間的核間通信周期數(shù)

由式(1)(2)(3)(4)(6)可得

式中，Pk代表執(zhí)行任務k時處理器功率;Pc代表核間通信功率;Vddk代表執(zhí)行核上第k個任務時的處理器電壓;Pidle為空閑時處理器功率;tidle(k)表示第k個處理器的空閑時間。

采用輪盤賭方式進行選擇，使得較優(yōu)的個體被選中的概率較高。方式如下:(a)計算當前種群中所有個體適應度函數(shù)的總和Sum;(b)計算適應度函數(shù)的一個累加值序列:Seq={s1，s2，…，sk}，k代表個體數(shù)隨機生成一個數(shù) x，0≤x ＜Sum;令s0=0，如果，si－1≤x ＜si，則個體 i被選擇。

(3)調(diào)度序列的交叉和變異

交叉和變異的目的是為了增加種群的多樣性，其操作如圖2所示。采用的單點交叉方法如下:(a)通過選擇得到兩個個體;(b)隨機選擇一個交叉點;(c)將兩個個體交叉點以后的部分進行交叉。如圖2(a)所示，Ui={vi1，vi2，…，vim，fi1，fi2，…，fim}和 Uj={vj1，vj2，…，vjm，fj1，fj2，…，fjm}為兩個個體。假設(shè)交叉點為k，則將k以后的序列互換。

圖2 交叉和變異操作

從個體中隨機選擇某一個元素進行變異，分兩種情況:若選擇的元素表示處理器核，則變異后的元素同樣表示處理器核;若該元素表示處理器頻率，變異后的元素同樣表示處理器頻率。如圖2(b)所示，個體Ui的第k個元素表示一個處理器核，該元素發(fā)生了變異，將會變?yōu)楸硎玖硪粋€處理器核的元素。

2.2 算法描述

基于多核節(jié)能任務調(diào)度的遺傳算法輸入為獨立化后的任務集G、處理器核數(shù)n、任務集截止時間D、各核的頻率/電壓模式 Core(F，V)、各核在不同頻率下的功率、核間的通信功率、算法每代的個體數(shù)N、遺傳的最大代數(shù)Gn、截止條件q、交叉概率P1及變異概率P2，輸出為最終調(diào)度序列S。S=［L0，L1，…，Ln－1］，其中Li表示核 i的調(diào)度序列。算法偽代碼如下。

圖3 算法偽代碼

3 實驗結(jié)果與分析

為了驗證算法的有效性，將上述算法與文獻［6］中的方法進行比較。實驗中各任務執(zhí)行周期數(shù)在10至50間隨機產(chǎn)生，而任務間通信周期數(shù)在1至5之間隨機產(chǎn)生。輸入任務個數(shù)和邊數(shù)，隨機產(chǎn)生一個用有向無環(huán)圖表示的任務集。

處理器采用Intel PXA270［7］的功耗模型，該模型的模式轉(zhuǎn)換時間可以忽略，其頻率/電壓模式及對應的功耗見表1。設(shè)定系統(tǒng)總線頻率固定為208 MHz，電源導軌電容Cr為5 pF。在該模型下，隨機產(chǎn)生6個任務集，其特征見表2。設(shè)置遺傳算法交叉概率和變異概率分別為0.9和0.03。在兩核和四核下分別進行比較，得出功耗比較圖，如圖4所示?？梢钥闯?，文章的方法節(jié)能效果優(yōu)于文獻［6］的方法。主要原因在于文獻［6］的方式在進行任務到核的分配時運用的是一種近似算法，得到的解還有優(yōu)化的空間。

表1 Intel PXA270功耗模型頻率及對應電壓和功耗

表2 任務集特征

4 結(jié)語

隨著多核嵌入式系統(tǒng)的發(fā)展，能耗問題已成為研究的熱點。在當前研究的基礎(chǔ)上，針對多核節(jié)能任務調(diào)度算法的不足，設(shè)計了一種節(jié)能任務調(diào)度方法。該方法分兩個階段:第一階段采用RDAG算法將依賴性任務獨立化，第二階段運用遺傳算法將任務集分配到各處理器核上進行處理。實驗表明，該方法達到了較為良好的節(jié)能效果。

［1］張冬松，陳芳園，等.多核系統(tǒng)中基于動態(tài)電壓頻率調(diào)節(jié)的實時節(jié)能調(diào)度研究［J］.計算機工程與科學，2010，32(9):157-162.

［2］彭蔓蔓，徐立超，等.異構(gòu)多核處理器的任務分配及能好研究［J］.計算機應用研究，2010，27(5):1 729-1 731.

［3］桑楠，李保宇，等.多處理器的節(jié)能調(diào)度算法［J］.電子科技大學學報，2008，37(1):116-119.

［4］LIU H，SHAO Z L，et al.Overhead-Aware System-Level Joint Energy and Performance Optimization for Streaming Applications one Multiprocessor Systems-on-Chip［C］//Proceedings of the 2008 Euromicro Conference on Real-Time Systems，Washington DC，2008:92-101.

［5］王穎鋒，劉志鏡.一種變電壓多核處理器上的有效節(jié)能方法［J］.計算機科學，2010，37(9):294-296.

［6］王穎鋒，劉志鏡.面向同構(gòu)多核處理器的節(jié)能任務調(diào)度方法［J］.計算機科學，2011，38(9):294-297.

［7］YANG C C，WANG K C，et al.Energy Efficient Intra-Task Dynamic Voltage Scaling for Realistic Cpus of Mobile Devices［J］.Journal of Information Science and Engineering，2009，25(1):251-272.