嵌入式多核多任務實時DVFS調度方法仿真

王曉瑩,張仲雯,何海生

(桂林電子科技大學計算機工程學院,廣西 北海 536000)

1 引言

近年來,嵌入式設備在其它技術的扶持下取得了突飛猛進的發(fā)展,多核處理器系統(tǒng)也因低成本、高速率等優(yōu)勢在嵌入式設備中被廣泛應用。在對多核處理器研究過程中,任務調度是一個十分重要的內容,一個優(yōu)秀的任務調度方法可以最大限度的發(fā)揮嵌入式設備性能,同時保證最低的能耗。人們對多媒體應用程序的需求越來越高,傳統(tǒng)單核單任務調度的方式已經很難滿足復雜的編解碼處理程序。因此,多核多任務調度方式應時而生,將數(shù)字信號處理器引入到傳統(tǒng)微處理器中協(xié)同操作,在提高調度效率的同時有效降低計算量。但是,由于處理器數(shù)量的增多,系統(tǒng)的能耗也隨之增大,對于嵌入式設備來說,在調度過程中要格外關注能耗變化情況。

針對該問題,梁秋玲等人[1]利用并行感知調度算法實現(xiàn)對多核系統(tǒng)的任務調度。計算任務點到終點的最大路徑,并按遞減的順序排序,從而決定任務的調度順序;在多核系統(tǒng)中,充分考慮了任務的相關性和最早可執(zhí)行時間,憑借構造的優(yōu)化匹配評估函數(shù),完成多核任務的調度。陳瑩等人[2]提出基于可靠性的多核系統(tǒng)任務調度方法。對所有應用程序任務有向無環(huán)圖建模分析,獲得了任務執(zhí)行效率、任務依賴性和任務通信量。采用聚類多數(shù)投票的方法,研究投票并行性和純再執(zhí)行序列化之間的關系。采用硬實時應用任務映射方法,以最小化通信代價和任務圖副本實例最小化為目標,獲得可靠度閾值,實現(xiàn)對多核系統(tǒng)的任務調度。由于上述兩種方法實現(xiàn)過程較為繁雜,導致最終的調度效率低。

基于此,引入實時DVFS算法,通過分析處理器的實時負載情況,動態(tài)調節(jié)電壓、頻率,達到降低能耗、提高嵌入式設備工作效率的目的。結果驗證所提方法可在花費最少時間的前提下完成高效率地調度。

2 DVFS算法描述

DVFS[3]是一種動態(tài)的、先進的設備能耗分析管理算法,通過分析處理器當前負載是否處于理想范圍內,來調整電壓和頻率,達到降低設備功耗的目的。一般情況下,互補金屬氧化物半導體(CMOS)具有相當大規(guī)模的數(shù)據(jù)群體,分布在集成電路中。計算集成電路上的總能耗為:

E=CeffV2fclkT

(1)

式中,Ceff表示有效切換電容,V表示設備當前電壓,fclk表示時鐘頻率,T表示總的運行時間。

(2)

(3)

通過上述分析可以看出,在理想狀態(tài)下CPU的功耗可以節(jié)省75%左右,并且對執(zhí)行任務效率不產生任何影響。

3 嵌入式多核多任務能耗模型

嵌入式多核多任務能耗模型主要通過以下定義分析:

定義1:假設嵌入式設備的處理器只存在運行和休眠兩種狀態(tài),當片上多核處理器存在n個同構核[5],計算處理器核corei在頻率為p時的運行功耗Ei(p)為:

Ei(p)=Es+λ(Eind+Ed)=Es+λ(Eind+Cefpm)

(4)

式中,Es表示休眠狀態(tài)處理器所產生的能耗值;Eind、Ed分別表示頻率無關功率、頻率相關功率;Cef表示開關電容處于有效狀態(tài)下;m表示處理器功率指數(shù),是一個常數(shù)項,且m≥2;λ表示多核處理器當前狀態(tài)。當λ=0時,處理器為休眠狀態(tài);當λ=1時,處理器處于運行狀態(tài)。

(5)

定義2:基于實時DVFS算法的嵌入式設備多核處理器,可以通過調節(jié)每個核的運行頻率達到降低功率的目的,運行頻率的調節(jié)要遵循設備相關標準,保證在[pmin,pmax]區(qū)間內,將θi定義為corei在t時刻下的頻率調節(jié)系數(shù),pi=θipmax。那么,具有n個核的多核處理器的運行總功耗為:

(6)

定義3:在單位時鐘頻率下,將n個核的多核處理器的功耗定義為En,最小功耗為Enmin。

(7)

(8)

定義4:當T=t2-t1時,具有n個核的多核處理器功耗為E(T),該值與時間和頻率調節(jié)系數(shù)有著直接關系,且滿足式(9)條件:

λCef(θipmax)m-1]}dt

(9)

4 嵌入式多核多任務調度實現(xiàn)

4.1 多核多任務調度數(shù)學模型

在嵌入式多核處理器中,每個計算節(jié)點都是同構的,給出了數(shù)學模型構建條件為:

條件1:將一個調度任務分割成k個子任務G={g1,g2,…,gk},任務與任務之間存在一定的約束條件。

條件3:預估執(zhí)行子任務所需的時間用一維向量RG={RG1,RG2,…,RGk}來表示,其中,RGk表示執(zhí)行子任務Gk的預估時間。

條件4:處理器核、通信延遲[8-9]、多任務調度時延以及調度任務量Comuab之間成正比,所有子任務之間的調度任務量可構成一個二維數(shù)組Comum×n。

條件5:給出一個二維數(shù)組Sche={σabd∈{1,0}|d∈[1,n]},σabd=1表示調度任務Gk在處理器核Lab上的執(zhí)行集合,PreGk集合表示任務Gk的所有前驅任務[10-12]。

條件6:任務Gk的初始時間設定為begin[k],完成時間為finish[k],那么可得:

(1-σabd)Comuab}finish[k]=RGk+begin[k]

(10)

多核CPU多任務調度的目的就是在策略集合SI中找到合適的調度策略SI′,使T的值始終保持在最小值。綜上所述,嵌入式多核多任務調度數(shù)據(jù)模型為:

(11)

4.2 多核多任務調度實現(xiàn)

嵌入式多核CPU的利用率,會隨著CPU負載的變化而發(fā)生改變。CPU一般情況下不會滿負載運行,所以需要計算其實際負載情況,為了降低能耗,把任務分配到一個低負荷的處理器中,讓其它相對高負荷的處理器處于睡眠狀態(tài)。為了更加具體地描述算法,給出以下幾點假設:

假設1:由上文分析可知,能耗是嵌入式設備在一段時間內產生的能耗,主要影響因素為時間和功耗。

假設2:功耗代表了一段時間內的能量消耗情況,描述的是CPU的能量消耗速率。在時間段Δt內,平均功耗為:

Eavg=ΔE/Δt

(12)

瞬時功耗表示Δt接近0時的平均功耗,計算公式為:

(13)

假設3:E集合了處理器各部分能耗之和,計算公式整理后為:

E=Ecpu+Ememory+Eio+Eother

(14)

其中各部分能耗計算公式為:

Ecpu=?1Etotal,0.46?10.50

Ememory=?2Etotal,0.08?20.10

Eio=?3Etotal,0.32?30.41

Eother=?4Etotal,0.08?40.10

(15)

其中,?1、?2、?3、?4分別表示處理器各部分的能耗系數(shù)。

假設4:處理核負載(Loadsystem)指的是在一段時間內,處理核執(zhí)行調度任務時工作流指令數(shù)[13]與嵌入式設備執(zhí)行指令數(shù)之間的比率,計算公式為:

(16)

式中,Instructionsload表示執(zhí)行調度任務時的指令數(shù),Instructionsidle表示運行空閑指令數(shù)。

假設5:處理核潛在處理能力(Loadpotential)在正常狀態(tài)下為1,在休眠狀態(tài)下為0。

假設6:嵌入式設備預期負載[14]Loadexp ect指的是在參考了處理核平均負載Loadavg和單位時間內運行負載Loadcurrent情況,對未來一段時間內可能產生的負載預估的結果:

Loadexp ect=π×Loadavg+?×Loadcurrent

(17)

式中,π、?分別表示Loadavg和Loadcurrent對Loadexp ect的影響權值[15],π+?=1。

嵌入式設備會根據(jù)式(16)計算每個處理核的潛在負載處理能力,并且利用式(17)預測將來一段時間內可能產生的負載。在新的調度工作準備好后,設備確定是否有處于睡眠狀態(tài)下的處理核,若有,則遍歷所有的處理核;若無,則表示目前的設備負荷很大,應該根據(jù)公平調度的原則合理安排。根據(jù)各處理器的潛在負載處理能力,尋找最接近于期望負荷的處理器核,并將其分配給處理核。當沒有一個處理核具備適當?shù)呢撦d處理能力時,它就會喚醒睡眠中的處理器,并把任務分配到處理器上。當調度任務完成后,如果該處理核沒有其它任務,則直接進入休眠狀態(tài);如果有,找到與其負載情況接近的處理核,并將任務調度到該處理核中,從而完成嵌入式設備多核多任務調度。

5 實驗分析

5.1 實驗環(huán)境

所提算法的主要目的是在嵌入式多核處理器中,保證最低能耗的前提下實現(xiàn)多任務調度。為了凸顯實驗結果的真實性,將所提方法與并行感知調度算法、可靠性任務調度算法對比驗證。

為了模擬不同多核處理器下算法的有效性,選擇三種不同的多核CPU,分別是雙核4物理線程的Inter core i5 3230M2.6GH、4核8物理線程的Inter core i7 Q740 1.73GH以及6核物理線程的Inter Xeon E5-2620 2.00GH。由于每個CPU功耗與頻率不同,能耗與離散頻率之間的對應關系也有所不同,具體如表1所示。將θi的值分別設定為0.2、0.4、0.6、0.8、1.0,引入θi可降低CPU即時理論功率計算難度。

表1 三種多核處理器功耗與離散頻率對應關系

5.2 實驗結果及分析

在不同類型的嵌入式多核處理器下,對比三種算法執(zhí)行多任務調度時的功耗情況,實驗結果如圖1所示。

圖1 三種算法不同多核CPU下功耗對比

通過觀察圖1可以看出,在不同類型的多核處理器下,所提方法執(zhí)行多任務調度消耗的功率始終低于3.5mW,可靠性任務調度算法與并行感知調度算法均高于所提方法。這是由于所提方法通過構建嵌入式多核多任務能耗模型,綜合分析算法在執(zhí)行多核多任務調度時的能耗,并結合實時DVFS技術降低各項能耗。

在不同的調度任務數(shù)量下,對比三種算法完成任務調度所需的最大完成時間,實驗結果如圖2所示。

圖2 三種算法多核多任務調度時間對比結果

從圖2中可以很清楚地看出,隨著調度任務數(shù)量的不斷增加,三種算法的最大完成時間也出現(xiàn)了不同幅度的上升趨勢。其中,所提方法的時間增長幅度最小,所需的最大完成時間為10ms,而其它兩種方法所需要的時間均高于所提方法。這是由于所提方法憑借實時DVFS技術,在降低嵌入式多核處理器能耗的同時,不會影響調度任務的效率,從而可實現(xiàn)花費最少的時間完成高效率的多任務調度。

6 結論

針對當前多核多任務調度算法存在的諸多缺點,在綜合考慮多核多任務調度的特點后,將實時DVFS技術引入其中,提出一種全新的調度方法。分析執(zhí)行多核多任務調度所消耗的能量,構建多核多任務調度模型;計算嵌入式設備中每個處理核的潛在負載處理能力,以及將來可能產生的負載,選取合適的處理核完成調度。實驗結果表明,在處理相同的調度任務時,所提方法產生的能耗最低,所花費的時間最短。