一種在線節能實時調度算法

張彬連,徐洪智,2

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

一種在線節能實時調度算法

張彬連1,徐洪智1,2

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

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

多處理器系統;隨機任務;動態電壓/頻率調整;在線;實時;節能調度

1 概述

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

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

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

2 系統功耗模型與問題定義

2.1 處理器功耗

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

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

2.2 問題定義

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

3 OERSA算法

3.1 算法設計思想

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

3.2 算法描述

根據3.1節所述思想,設計OERSA調度如算法1所示。

算法1OERSA調度算法

輸入任務t

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

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

算法2SearchMinEnergy(machineList,Task)

輸入任務t

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

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

算法3Schedule(t,tasklistOnMachine)

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

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

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

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

算法4EstimateSpeed(t);

輸入任務t

輸出處理器的執行速度

3.3 算法分析

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

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

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

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

設:

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

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

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

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

證明:n個任務需要執行,算法1執行n次,因為除cpuNo=SearchMinEnergy(machineList,t)這行外,其他行的時間復雜度為O(1),該行的SearchMinEnergy()函數需要執行n次,即算法2需要執行n次。執行一次算法2時,Schedule()函數需要執行m次,而Schedule()函數執行時要遍歷一個處理器上的任務3次(計算mTime和mTasklLength 1次,for循環調整電壓1次,最后2行語句執行1次),系統中共有m個處理器,將每個處理器上的任務遍歷3次,實際上就是將系統中未執行完的任務遍歷3次,系統中未執行完的任務最多為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]。為了體現各處理器之間的差異,算法隨機生成α,β和MaxSpeed,并分別設定其范圍:1.1＜α＜1.8,0.05＜β＜0.11,0.8 GHz＜MaxSpeed＜1.8 GHz。為方便計算,實驗中的能耗用P(S)乘以時間單位表示。

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

表1 處理器信息

表2 100個任務的調度結果

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

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

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

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

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

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

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

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

5 結束語

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

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

[2] 林 闖,田 源,姚 敏.綠色網絡和綠色評價:節能機制、模型和評價[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] 過敏意.綠色計算:內涵及趨勢[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] 張冬松,吳 飛,陳芳園,等.開銷敏感的多處理器最優節能實時調度算法[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集群中基于自適應閾值的并行任務節能調度算法[J].計算機學報, 2013,36(2):393-407.

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

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

[13] 張冬松.多核多處理器系統的節能實時調度技術研究[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] 張彬連,徐洪智.多處理器系統的在線節能調度算法[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

張彬連,徐洪智.一種在線節能實時調度算法[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-),女,講師、碩士,主研方向:分布式系統,任務調度算法;徐洪智,副教授、博士研究生。

2014-03-07

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