張彬連,徐洪智,2

(1.吉首大學(xué)軟件服務(wù)外包學(xué)院,湖南張家界427000;2.湖南大學(xué)嵌入式系統(tǒng)及網(wǎng)絡(luò)實(shí)驗(yàn)室,長(zhǎng)沙410082)

一種在線節(jié)能實(shí)時(shí)調(diào)度算法

張彬連1,徐洪智1,2

(1.吉首大學(xué)軟件服務(wù)外包學(xué)院,湖南張家界427000;2.湖南大學(xué)嵌入式系統(tǒng)及網(wǎng)絡(luò)實(shí)驗(yàn)室,長(zhǎng)沙410082)

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

多處理器系統(tǒng);隨機(jī)任務(wù);動(dòng)態(tài)電壓/頻率調(diào)整;在線;實(shí)時(shí);節(jié)能調(diào)度

1 概述

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

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

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

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

2.1 處理器功耗

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

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

2.2 問(wèn)題定義

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

3 OERSA算法

3.1 算法設(shè)計(jì)思想

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

3.2 算法描述

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

算法1OERSA調(diào)度算法

輸入任務(wù)t

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

當(dāng)一個(gè)新的任務(wù)t到達(dá)后,記錄前面所有已到達(dá)任務(wù)的總計(jì)算長(zhǎng)度和總可用時(shí)間,按算法2尋找一個(gè)預(yù)計(jì)系統(tǒng)總能耗最小的處理器分配該任務(wù)。

算法2SearchMinEnergy(machineList,Task)

輸入任務(wù)t

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

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

算法3Schedule(t,tasklistOnMachine)

輸入任務(wù)t以及某個(gè)處理器上的任務(wù)列表tasklistOnMachine

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

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

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

算法4EstimateSpeed(t);

輸入任務(wù)t

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

3.3 算法分析

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

證明:先證明2個(gè)任務(wù)的情況,設(shè)任務(wù)task1以速度S1執(zhí)行的時(shí)間為T(mén)1,任務(wù)task2以速度S2執(zhí)行的時(shí)間為T(mén)2,S1≠S2,按這種方式執(zhí)行的總能耗為:

將速度設(shè)置為總運(yùn)算量/總運(yùn)算時(shí)間:

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

設(shè):

則只要證明E＞0即可,因?yàn)棣粒?,本文只要考慮大括號(hào)內(nèi)的項(xiàng):

因?yàn)镾1＞0,S2＞0且S1≠S2,所以(S2-S1)2＞0且(S1-S2)2＞0,故E1-E2＞0,2個(gè)任務(wù)的情況成立。

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

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

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

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

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

實(shí)驗(yàn)1輕量負(fù)載情形。使用3個(gè)處理器,隨機(jī)產(chǎn)生100個(gè)任務(wù),前后2個(gè)任務(wù)到達(dá)的時(shí)間差為1～ 10之間的隨機(jī)數(shù),任務(wù)長(zhǎng)度為1～10之間的隨機(jī)數(shù),截止期限為任務(wù)到達(dá)時(shí)間加2倍任務(wù)長(zhǎng)度,各處理器信息及其調(diào)度結(jié)果如表1和表2所示。

表1 處理器信息

表2 100個(gè)任務(wù)的調(diào)度結(jié)果

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

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

圖1 任務(wù)長(zhǎng)度變化時(shí)各算法的性能比較

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

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

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

圖3 任務(wù)到達(dá)時(shí)間間隔變化時(shí)各算法的性能比較

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

5 結(jié)束語(yǔ)

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

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

[2] 林 闖,田 源,姚 敏.綠色網(wǎng)絡(luò)和綠色評(píng)價(jià):節(jié)能機(jī)制、模型和評(píng)價(jià)[J].計(jì)算機(jī)學(xué)報(bào),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] 過(guò)敏意.綠色計(jì)算:內(nèi)涵及趨勢(shì)[J].計(jì)算機(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] 張冬松,吳 飛,陳芳園,等.開(kāi)銷敏感的多處理器最優(yōu)節(jié)能實(shí)時(shí)調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào),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] 劉 偉,尹 行,段玉光,等.同構(gòu)DVS集群中基于自適應(yīng)閾值的并行任務(wù)節(jié)能調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào), 2013,36(2):393-407.

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

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

[13] 張冬松.多核多處理器系統(tǒng)的節(jié)能實(shí)時(shí)調(diào)度技術(shù)研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),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é)能調(diào)度算法[J].計(jì)算機(jī)應(yīng)用,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é)能實(shí)時(shí)調(diào)度算法[J].計(jì)算機(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

湖南省科技計(jì)劃基金資助項(xiàng)目(2012GK2006)。

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

2014-03-07

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