基于多核處理器的節(jié)能任務(wù)調(diào)度方法

葉常華，左朝樹

(保密通信重點(diǎn)實(shí)驗(yàn)室，成都 610041)

0 引言

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

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

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

1 任務(wù)和功耗

1.1 任務(wù)模型

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

1.2 功耗模型

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

總能耗為

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

任務(wù)vi所消耗的動(dòng)態(tài)能量為

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

式中，Cr是電源導(dǎo)軌電容。

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

2.1 算法思想

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

圖1 算法思想

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

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

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

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

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

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

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

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

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

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

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

圖2 交叉和變異操作

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

2.2 算法描述

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

圖3 算法偽代碼

3 實(shí)驗(yàn)結(jié)果與分析

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

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

表1 Intel PXA270功耗模型頻率及對(duì)應(yīng)電壓和功耗

表2 任務(wù)集特征

4 結(jié)語(yǔ)

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

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

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

［3］桑楠，李保宇，等.多處理器的節(jié)能調(diào)度算法［J］.電子科技大學(xué)學(xué)報(bào)，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］.計(jì)算機(jī)科學(xué)，2010，37(9):294-296.

［6］王穎鋒，劉志鏡.面向同構(gòu)多核處理器的節(jié)能任務(wù)調(diào)度方法［J］.計(jì)算機(jī)科學(xué)，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.