張彬連,徐洪智,2

(1.吉首大學軟件服務外包學院,湖南張家界427000;2.湖南大學嵌入式系統(tǒng)及網(wǎng)絡實驗室,長沙410082)

一種在線節(jié)能實時調度算法

張彬連1,徐洪智1,2

(1.吉首大學軟件服務外包學院,湖南張家界427000;2.湖南大學嵌入式系統(tǒng)及網(wǎng)絡實驗室,長沙410082)

隨著多處理器系統(tǒng)規(guī)模的不斷擴大,如何節(jié)能成為一個亟待解決的重要問題。為此,基于多處理器系統(tǒng)提出一種針對隨機任務的在線節(jié)能實時調度算法。使用統(tǒng)計方法,根據(jù)已有任務的到達時間和計算量估計新任務在空閑處理器上執(zhí)行的電壓/頻率,使還未到達的任務能夠滿足截止期限并有效節(jié)能。在考慮單個處理器上執(zhí)行的任務時,計算執(zhí)行這些任務所需的平均電壓/頻率,使所有任務的執(zhí)行速度盡量均衡,當某些任務不能滿足截止期限要求時,則調高未執(zhí)行任務的電壓/頻率。實驗結果表明,與EDF,HVEA,MEG和ME-MC算法相比,該算法在滿足截止期限和節(jié)能方面具有明顯的優(yōu)勢。

多處理器系統(tǒng);隨機任務;動態(tài)電壓/頻率調整;在線;實時;節(jié)能調度

1 概述

隨著電子技術和計算機硬件技術的飛速發(fā)展,多處理器計算系統(tǒng)在成本和體積迅速下降的同時計算能力大幅提升,已被廣泛用于計算密集型和數(shù)據(jù)密集型應用[1]。同時,高性能經(jīng)常會產(chǎn)生高能耗,大規(guī)模多處理器計算系統(tǒng)消耗的能量巨大。據(jù)統(tǒng)計,目前計算中心服務器消耗的能量大約占全球電力總消耗的0.5%,如果照此速度發(fā)展,預計到2020年,其能量消耗將翻番[2]。在全球70%的計算中心中,能耗開銷已成為第二大運營開銷[3],高性能計算系統(tǒng)生命周期內(nèi)維持正常運行所需的電力成本已經(jīng)超出了系統(tǒng)的硬件成本[4]。為了降低系統(tǒng)的能耗,有許多處理器能在不同電壓模式下工作,系統(tǒng)運行時,可動態(tài)調整電壓以改變執(zhí)行頻率從而降低能耗。一般情況下,處理器產(chǎn)生的能耗包括動態(tài)能耗、靜態(tài)能耗和狀態(tài)轉換能耗,其中動態(tài)能耗和靜態(tài)能耗是CMOS處理器能耗的主要來源[5]。

近年來,有許多學者研究了節(jié)能調度問題。文獻[6]基于同構集群系統(tǒng)采用任務復制算法減少調度長度和通信能耗,利用任務依賴之間的松弛時間,調低處理器電壓以節(jié)能。文獻[7]討論了開銷敏感的多處理器最優(yōu)節(jié)能實時調度,根據(jù)關鍵速度判斷系統(tǒng)負載情況,確定具有最低能耗值的活躍處理器個數(shù),然后根據(jù)狀態(tài)切換開銷來確定最優(yōu)調度序列。文獻[8]針對周期性任務模型提出一種最優(yōu)節(jié)能調度算法。文獻[9]研究了周期性實時任務的節(jié)能調度,通過調低電壓或關閉很少使用的處理器以節(jié)能,證明了在任務截止期限內(nèi)使耗能最小的調度屬于NP-hard問題。文獻[10]提出一種同構動態(tài)電壓調整(Dynamic Voltage Scaling,DVS)集群中基于自適應閾值的并行任務節(jié)能調度算法,利用任務之間的空閑時間降低處理器電壓以節(jié)省能耗。以上方法在一定的條件下具有很好的節(jié)能效果,但都屬于靜態(tài)調度,不適合處理動態(tài)到達的任務。也有一些學者研究了動態(tài)節(jié)能調度,如文獻[11]針對異構計算系統(tǒng)中非周期、獨立任務提出一種彈性節(jié)能調度策略(EEAS),根據(jù)系統(tǒng)負載情況在系統(tǒng)節(jié)能與用戶期望之間進行權衡。文獻[12-13]提出了一種多核系統(tǒng)中基于Global EDF在線節(jié)能硬實時任務調度算法,通過引入調速因子,利用任務之間的松弛時間,結合動態(tài)電壓頻率調整技術,降低多核系統(tǒng)中任務執(zhí)行速度,達到滿足任務約束與節(jié)能能耗的合理折衷。文獻[14]基于異構系統(tǒng)提出了多種動態(tài)節(jié)能調度算法:ME-MC,MEG等。文獻[15]提出一種在線節(jié)能調度算法,盡量將任務調度到產(chǎn)生能耗最少的處理器。這些算法大都事先獲取了任務的到達時間、截止期限、周期等相關屬性,而現(xiàn)實中有些應用任務是隨機到達的,很難事先獲取任務的相關屬性,導致現(xiàn)有的一些算法不太適合處理這類問題,文獻[12]雖然是基于隨機到達的任務,但沒有考慮處理器負載較重的情況。文獻[15]則沒有考慮如何使更多的任務滿足截止期限要求。

本文基于多處理器系統(tǒng),針對隨機到達的任務提出一種在線節(jié)能實時調度算法(On-line Energyefficient Real-time Scheduling Algorithm,OERSA),在滿足任務截止期限的條件下實現(xiàn)節(jié)能。

2 系統(tǒng)功耗模型與問題定義

2.1 處理器功耗

根據(jù)文獻[7,16]可知,處理器以速度S運行的功耗函數(shù)可表示為P(S)=αS3+β,其中,α＞0,β≥0。設處理器的速度可連續(xù)調節(jié)[17],其速度范圍為[Smin,Smax],令k(k≤1)為調速因子,在t時刻處理器的頻率記為kSmax,若在一段時間[t1,t2]內(nèi)k保持不變,則處理器在這段時間內(nèi)的功耗為:

根據(jù)功耗函數(shù)P(S)=αS3+β,某處理器以速度S執(zhí)行一個單位時間的能耗為P(S)/S=αS2+β/ S[13],對P(S)/S求一階導數(shù)得2αS-β/S2,令2αS-β/S2=0,可求出該處理器耗能最小的運行速度。所以,某一處理器處在一段時間內(nèi)運行的功耗函數(shù)可表示為:

2.2 問題定義

考慮相互獨立且隨機到達的任務集T={t1,t2,…,tn},任務ti用三元組{ai,li,di}表示,其中,ai,li,di分別表示ti的到達時間、計算長度和截止期限。當ti到達后,即能獲取該三元組的信息。如果任務ti的實際完成時間fi≤di,則稱ti滿足截止期限要求。調度問題的定義是給出一個由m個處理器構成的計算系統(tǒng)和任務集T,將任務調度到這些處理器上執(zhí)行,使?jié)M足截至期限的任務數(shù)最大化并使能耗最小化。

3 OERSA算法

3.1 算法設計思想

針對隨機到達的實時任務集,當一個任務到達后,立即獲取它的大小和截止期限,在任務滿足截止期限的條件下,查找所有可用處理器,將任務分配到預計系統(tǒng)總能耗最小的處理器上。由于系統(tǒng)中處理器的數(shù)目可能比較多,當把某個任務分配到空閑的處理器時,由于后面的任務在什么時候到達,計算量有多大是未知的,這個任務如果用最大速度執(zhí)行,則可能會增加不必要的能耗,如果用一個較小的速度執(zhí)行則可能會占用過多處理器的時間導致后面到達的任務不能滿足截止期限要求,本文采用統(tǒng)計的方法根據(jù)已到達任務的大小和單位時間內(nèi)的到達率估計該處理器運行的電壓/頻率。算法在考慮單個處理器上執(zhí)行的任務時,先計算執(zhí)行這些任務所需的平均電壓/頻率,使所有任務的執(zhí)行速度盡量均衡,當某些任務不能滿足截止期限要求時,則調高前面未執(zhí)行任務的電壓/頻率。

3.2 算法描述

根據(jù)3.1節(jié)所述思想,設計OERSA調度如算法1所示。

算法1OERSA調度算法

輸入任務t

輸出將任務t調度到系統(tǒng)總能耗最小的處理器

當一個新的任務t到達后,記錄前面所有已到達任務的總計算長度和總可用時間,按算法2尋找一個預計系統(tǒng)總能耗最小的處理器分配該任務。

算法2SearchMinEnergy(machineList,Task)

輸入任務t

輸出在滿足任務t截止期限的要求下,將t調度到預計系統(tǒng)總能耗最小的處理器,并設置處理器的電壓/頻率,返回處理器的編號,如果任務在任何一個處理器上執(zhí)行都不能滿足截止期限要求,則返回0

算法2搜尋預計系統(tǒng)總能耗最小的cpuNo,本算法中將任務t調度到某個處理器上產(chǎn)生的能耗見算法3。

算法3Schedule(t,tasklistOnMachine)

輸入任務t以及某個處理器上的任務列表tasklistOnMachine

輸出如果任務t滿足截止期限,則返回調度該任務后系統(tǒng)預計增加的能耗,否則返回+∞

重新計算tasklistOnMachine中所有任務執(zhí)行的能耗和時間,return任務t加入tasklistOnMachine后增加的能耗。

如果處理器空閑,算法3根據(jù)當前任務和先前已到達的任務以及系統(tǒng)處理器數(shù)確定當前處理器的執(zhí)行電壓/頻率(見算法4),否則盡量將單個處理器上的任務按平均電壓/頻率執(zhí)行。

算法4EstimateSpeed(t);

輸入任務t

輸出處理器的執(zhí)行速度

3.3 算法分析

定理1在同一個處理器上以不同速度s執(zhí)行不同的任務,將其速度設置為總運算量/總運算時間后能節(jié)省能耗。

證明:先證明2個任務的情況,設任務task1以速度S1執(zhí)行的時間為T1,任務task2以速度S2執(zhí)行的時間為T2,S1≠S2,按這種方式執(zhí)行的總能耗為:

將速度設置為總運算量/總運算時間:

以此速度執(zhí)行在T1+T2時間段內(nèi)仍然能完成原任務的計算,此時的能耗為:

設:

則只要證明E＞0即可,因為α＞0,本文只要考慮大括號內(nèi)的項:

因為S1＞0,S2＞0且S1≠S2,所以(S2-S1)2＞0且(S1-S2)2＞0,故E1-E2＞0,2個任務的情況成立。

因為這2個任務的執(zhí)行速度相同,所以本文將這2個任務看成一個任務,然后再與第3個任務按平均速度執(zhí)行,以此類推,能證明定理1成立。

定理2OERSA算法的時間復雜度為O(n2)。

證明:n個任務需要執(zhí)行,算法1執(zhí)行n次,因為除cpuNo=SearchMinEnergy(machineList,t)這行外,其他行的時間復雜度為O(1),該行的SearchMinEnergy()函數(shù)需要執(zhí)行n次,即算法2需要執(zhí)行n次。執(zhí)行一次算法2時,Schedule()函數(shù)需要執(zhí)行m次,而Schedule()函數(shù)執(zhí)行時要遍歷一個處理器上的任務3次(計算mTime和mTasklLength 1次,for循環(huán)調整電壓1次,最后2行語句執(zhí)行1次),系統(tǒng)中共有m個處理器,將每個處理器上的任務遍歷3次,實際上就是將系統(tǒng)中未執(zhí)行完的任務遍歷3次,系統(tǒng)中未執(zhí)行完的任務最多為n個。所以OERSA算法的時間復雜度為O(n2)。

4 實驗與結果分析

為了驗證本文算法的有效性,將OERSA算法與EDF(Earliest Deadline First),HVEA(Highest Voltage Energy-aware)[11],ME-MC(MinimumEnergy Minimum Completion Time)[14],MEG(Minimum Energy Greedy)[14]算法進行比較。實驗時,以Intel Xscale處理器為參考,其功耗近似為P(S)= 1.52S3+0.08W[7,16]。為了體現(xiàn)各處理器之間的差異,算法隨機生成α,β和MaxSpeed,并分別設定其范圍:1.1＜α＜1.8,0.05＜β＜0.11,0.8 GHz＜MaxSpeed＜1.8 GHz。為方便計算,實驗中的能耗用P(S)乘以時間單位表示。

實驗1輕量負載情形。使用3個處理器,隨機產(chǎn)生100個任務,前后2個任務到達的時間差為1～ 10之間的隨機數(shù),任務長度為1～10之間的隨機數(shù),截止期限為任務到達時間加2倍任務長度,各處理器信息及其調度結果如表1和表2所示。

表1 處理器信息

表2 100個任務的調度結果

從表1可以看出,處理器1最快,處理器2最慢,而處理器2的β相對較小,處理器1的α相對較小。從表2中的處理器上任務數(shù)和能耗可以看出,在任務滿足截至期限的條件下,OERSA算法的能耗最小。MEG和ME-MC算法總是試圖將當前任務的電壓/頻率降至最低以節(jié)省能耗,導致有些任務的執(zhí)行時間過長,使后面的任務不能滿足截止期限的要求。

實驗2任務長度變化的情形。使用16個處理器,隨機產(chǎn)生1000個任務,任務長度分別為1～10, 1～15,1～20,1～25,1～30,1～35之間的隨機數(shù),前后2個任務到達的時間差為1～10之間的隨機數(shù),截止期限為任務到達時間加2倍任務長度。為便于觀察實驗結果,各算法產(chǎn)生的能耗以EDF算法為參考進行歸一化處理,結果如圖1所示?？梢钥闯? EDF,HVEA和OERSA 3個算法在滿足任務截止期限的性能方面基本相同,當任務長度都小于30時,它們能使所有任務都滿足截止期限要求,但OERSA算法的能耗最小,該算法相對于EDF平均可節(jié)省超過40%的能耗。MEG和ME-MC算法的能耗雖然小于OERSA算法,但滿足任務截止期限的性能明顯不如OERSA算法。

圖1 任務長度變化時各算法的性能比較

實驗3處理器數(shù)目變化的情形。隨機產(chǎn)生1000個任務,任務長度為1～100之間的隨機數(shù),前后兩個任務到達的時間差為1～5之間的隨機數(shù),截止期限為任務到達時間加2倍任務長度,處理器數(shù)目分別為8,12,16,20,24,28,各算法的結果如圖2所示。從圖2可知,當處理器數(shù)目大于20時,EDF、HVEA和OERSA 3個算法基本能使所有任務滿足截止期限要求,但OERSA算法的能耗最小,且隨著處理器數(shù)目的增多,OERSA算法的相對能耗越來越小。當處理器數(shù)目達到28時,MEG和ME-MC算法仍有約10%的任務不能滿足截止期限要求。

圖2 處理器數(shù)目變化時各算法的性能比較

實驗4任務到達時間間隔變化的情形。使用16個處理器,隨機產(chǎn)生1000個任務,任務長度為1～500之間的隨機數(shù),前后2個任務到達的時間間隔分別為1～8,9～16,17～24,25～32,33～40,41～48的隨機數(shù),截止期限為任務到達時間加2倍任務長度,各算法的結果如圖3所示。從圖3可知,當前后2個任務到達的時間間隔達到17～24區(qū)間時, EDF,HVEA和OERSA 3個算法完成了所有的任務,但OERSA算法的能耗最小。當時間間隔達到33～40區(qū)間時,5個算法都完成了任務,且隨著任務到達時間間隔的放寬,OERSA算法的能耗趨向于MEG算法,說明OERSA算法基本上將所有任務的執(zhí)行電壓/頻率都調至最低,這時OERSA算法實際上已退化為MEG算法。

圖3 任務到達時間間隔變化時各算法的性能比較

從上述實驗可以看出,OERSA算法在滿足任務截止期限方面的性能和EDF,HVEA算法基本相同,明顯優(yōu)于MEG和ME-MC算法,而OERSA算法的能耗始終低于EDF和HVEA算法。

5 結束語

為降低多處理器系統(tǒng)的能耗,本文針對隨機到達的任務提出一種在線節(jié)能實時調度算法,使用統(tǒng)計的方法估算新任務在空閑處理器上執(zhí)行的電壓/頻率,使還未到達的任務能夠滿足截止期限并有效節(jié)能,同時該算法使單個處理器上任務的執(zhí)行電壓/頻率盡量均衡以實現(xiàn)節(jié)能。實驗對比結果表明,與傳統(tǒng)算法相比,本文算法在滿足任務截止期限和節(jié)省能耗方面具有明顯的優(yōu)勢。下一步將研究多處理器系統(tǒng)中隨機任務的可靠性約束與節(jié)能調度。

[1] Goller A,LeberlF.RadarImageProcessingwith Clusters of Computers[J].IEEE Aerospace and Electronics Systems Magazine,2009,24(1):18-22.

[2] 林 闖,田 源,姚 敏.綠色網(wǎng)絡和綠色評價:節(jié)能機制、模型和評價[J].計算機學報,2011,34(4): 593-612.

[3] Li Yu,Liu Yi,Qian Depei.An Energy-aware Heuristic Scheduling Algorithm for Heterogeneous Clusters[C]// Proceedings of the15th International Conference on Parallel and Distributed Systems.[S.l.]:IEEE Press, 2009:407-413.

[4] 過敏意.綠色計算:內(nèi)涵及趨勢[J].計算機工程, 2010,36(10):1-7.

[5] Jejurikar R,PereiraC,GuptaR.LeakageAware Dynamic VoltageScalingforReal-timeEmbedded Systems[C]//Proceedings of the 41st Annual Design Automation Conference.San Diego,USA:ACM Press, 2004:275-280.

[6] Liu Wei,Yin Hang,Du Wei.Dynamic Threshold-based Energy Efficient SchedulingAlgorithmfor Parallel Tasks on Homogeneous DVS-enabled Clusters[C]// Proceedings of 2011International Conference on CyberenabledDistributedComputingandKnowledge Discovery.Washington D.C.,USA:IEEE Press,2011: 321-328.

[7] 張冬松,吳 飛,陳芳園,等.開銷敏感的多處理器最優(yōu)節(jié)能實時調度算法[J].計算機學報,2012,35(6): 1297-1312.

[8] Funaoka K,Kato S,Yamasaki N.Energy-efficient Optimal Real-time Scheduling on Multiprocessors[C]//Proceedings of the11th IEEE Symposium on Object Oriented Realtime Distributed Computing.Washington D.C.,USA: IEEE Press,2008:23-30.

[9] Lee W Y.Energy-efficient Scheduling of Periodic RealtimeTasksonLightlyLoadedMulticoreProcessors[J].IEEETransactionsonParalleland Distributed Systems,2012,23(3):530-537.

[10] 劉 偉,尹 行,段玉光,等.同構DVS集群中基于自適應閾值的并行任務節(jié)能調度算法[J].計算機學報, 2013,36(2):393-407.

[11] 朱曉敏,賀 川,王建江,等.異構計算系統(tǒng)中彈性節(jié)能調度策略研究[J].計算機學報,2012,35(6): 1313-1326.

[12] 張冬松,吳 彤,陳芳園,等.多核系統(tǒng)中基于Global EDF的在線節(jié)能實時調度算法[J].軟件學報,2012, 23(4):996-1009.

[13] 張冬松.多核多處理器系統(tǒng)的節(jié)能實時調度技術研究[D].長沙:國防科學技術大學,2012.

[14] Kim J K,Siegel H J,Maciejewski A A,et al.Dynamic ResourceManagementinEnergyConstrained HeterogeneousComputingSystemsUsingVoltage Scaling[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(11):1445-1457.

[15] 張彬連,徐洪智.多處理器系統(tǒng)的在線節(jié)能調度算法[J].計算機應用,2013,33(10):2787-2791.

[16] Zhu Dakai.Reliability-aware Dynamic Energy Management inDependableEmbeddedReal-timeSystems[C]// ProceedingsofIEEEReal-timeandEmbedded Technology and Applications Symposium.San Jose, USA:IEEE Press,2006:397-407.

[17] Li Jianjun,Shu L,Chen Jianjia,et al.Energy-efficient Scheduling in Nonpreemptive Systems with Real-time Constraints[J].IEEE Transactions on Systems,2013, 43(2):332-344.

編輯 金胡考

An On-line Energy-efficient Real-time Scheduling Algorithm

ZHANG Binlian1,XU Hongzhi1,2
(1.School of Software and Service Outsourcing,Jishou University,Zhangjiajie 427000,China; 2.Laboratory of Embedded Systems&Networking,Hunan University,Changsha 410082,China)

With the continuous expansion of the scale of the multi processor system,the issue of energy consumption becomes more and more important.How to save energy becomes an important problem to be solved.Based on the multiprocessor system,On-line Energy-efficient Real-time Scheduling Algorithm(OERSA)aiming at a random task is proposed.According to the arrival time and calculated amount of the existing task,the algorithm estimates the executive voltage/frequency of the new task in the idle processor by using statistical methods,which can meet the deadline and save the energy effectively for not yet arrived tasks.At the same time,considering the task executed on a single processor,the algorithm first calculates the average voltage/frequency required to perform these tasks,thus making all the task execution speed equal as much as possible.When some tasks can not meet the deadline requirements,voltage/frequency for previous not executed tasks will be adjusted high.Experimental results show that OERSA has obvious advantages in the aspect of meeting deadlines and energy consumption saving compared with EDF,HVEA,MEG and ME-MC algorithm.

multiprocessor system;random task;dynamic voltage/frequency scaling;on-line;real-time;energy-efficient scheduling

張彬連,徐洪智.一種在線節(jié)能實時調度算法[J].計算機工程,2015,41(2):41-46.

英文引用格式:Zhang Binlian,Xu Hongzhi.An On-line Energy-efficient Real-time Scheduling Algorithm[J].Computer Engineering,2015,41(2):41-46.

1000-3428(2015)02-0041-06

:A

:TP316.4

10.3969/j.issn.1000-3428.2015.02.009

湖南省科技計劃基金資助項目(2012GK2006)。

張彬連(1978-),女,講師、碩士,主研方向:分布式系統(tǒng),任務調度算法;徐洪智,副教授、博士研究生。

2014-03-07

:2014-05-06E-mail:zhangbinlian@163.com