多處理器系統(tǒng)可靠性約束下的節(jié)能調(diào)度算法

1、多處理器系統(tǒng)可靠性約束下的節(jié)能調(diào)度算法摘要：針對(duì)多處理器系統(tǒng)中隨機(jī)到達(dá)的任務(wù)，設(shè)計(jì)了可靠性約束下的節(jié)能調(diào)度算法ESACR。該算法在滿足任務(wù)截止期限的前提下選擇一個(gè)預(yù)計(jì)產(chǎn)生能耗最小的處理器以節(jié)能，在單個(gè)處理器上運(yùn)用最早截止期限優(yōu)先策略進(jìn)展調(diào)度并盡量使各個(gè)任務(wù)的執(zhí)行電壓/頻率平衡，當(dāng)新到任務(wù)在處理器上不能滿足截止期限要求時(shí)那么逐個(gè)調(diào)高前面未執(zhí)行任務(wù)的電壓/頻率。同時(shí)，為保證系統(tǒng)的可靠性，ESACR給正在執(zhí)行的任務(wù)預(yù)留錯(cuò)誤恢復(fù)時(shí)間以保證當(dāng)發(fā)生瞬時(shí)錯(cuò)誤時(shí)該任務(wù)能被恢復(fù)。實(shí)驗(yàn)結(jié)果說(shuō)明，與最高電壓節(jié)能調(diào)度HVEA、最小能耗最小完成時(shí)間調(diào)度MEMC、最早完成時(shí)間優(yōu)先調(diào)度EFF相比，ESACR在保證系統(tǒng)可靠性

2、的前提下節(jié)能效果最好。關(guān)鍵詞：多處理器系統(tǒng)；隨機(jī)任務(wù)；可靠性約束；節(jié)能；調(diào)度中圖分類號(hào)： TP393 文獻(xiàn)標(biāo)志碼：A英文摘要Abstract：A kind of Energyefficient Scheduling Algorithm under the Constraint of Reliability ESACR for the random tasks in multiprocessor system was proposed. It would choose the processor which might consume the least energy when the task

3、s deadline could be guaranteed. For the signal processor， Earliest Deadline First EDF strategy was used to schedule the tasks and all the tasks were made execute in the same voltage/frequency. When the new task could not match the deadline， the nonexecution voltage/frequency of former tasks would be

4、 raised. At the same time， the recovery time was reserved for the executing task in order to promise that the task could be rescheduled when errors happened. The simulation shows that the ESACR can provide the better energy efficiency with the guarantee of system reliability ， compared to Highest Vo

5、ltage EnergyAware HVEA， Minimum Energy Minimum Completion time MEMC and Earliest Finish First EFF.英文關(guān)鍵詞Key words：multiprocessor system； random task； reliability constraint； energyefficient； scheduling0 引言因?yàn)樗矔r(shí)錯(cuò)誤更加常見(jiàn)，所以本文只考慮瞬時(shí)錯(cuò)誤，假設(shè)系統(tǒng)的瞬時(shí)錯(cuò)誤服從泊松分布8，11，14，處理器以頻率f對(duì)應(yīng)的電壓為V執(zhí)行任務(wù)時(shí)瞬時(shí)錯(cuò)誤率8，11為：f=0gf=0 10d1-f1-fmin

6、31.4 問(wèn)題定義給定一個(gè)隨機(jī)到達(dá)的任務(wù)集T和一個(gè)具有m個(gè)處理器的計(jì)算系統(tǒng)，系統(tǒng)中的每一個(gè)處理器都DVFS可調(diào)，任務(wù)集中的每一個(gè)任務(wù)可在任何一個(gè)處理器上執(zhí)行。為使系統(tǒng)滿足可靠性，要求執(zhí)行任務(wù)的錯(cuò)誤率保持在0的程度并盡量節(jié)能。2 ESACR算法設(shè)計(jì)2.1 算法思想考慮有m個(gè)處理器的系統(tǒng)，每個(gè)處理器上的任務(wù)隊(duì)列都按EDF縮略語(yǔ)算法進(jìn)展調(diào)度。為保證每個(gè)處理器上任務(wù)執(zhí)行時(shí)的可靠性，當(dāng)處理器以非最高電壓/頻率執(zhí)行時(shí)，因?yàn)榭赡軙?huì)產(chǎn)生瞬時(shí)錯(cuò)誤使系統(tǒng)的可靠性達(dá)不到要求，需要在任務(wù)的截止期限內(nèi)預(yù)留錯(cuò)誤恢復(fù)時(shí)間，并設(shè)定任務(wù)恢復(fù)時(shí)都以最高電壓/頻率執(zhí)行，假設(shè)無(wú)錯(cuò)誤發(fā)生那么下一個(gè)任務(wù)可緊接著執(zhí)行。當(dāng)處理器以最高電壓/

7、頻率執(zhí)行時(shí)那么不預(yù)留錯(cuò)誤恢復(fù)時(shí)間。在考慮了預(yù)留錯(cuò)誤恢復(fù)時(shí)間之后，處理器上的松弛時(shí)間那么可回收用于節(jié)能。當(dāng)一個(gè)任務(wù)到達(dá)時(shí)，立即獲取任務(wù)三元組Ai， Ci， Di信息，假設(shè)將該任務(wù)分配到某個(gè)處理器后，處理器將按一個(gè)相對(duì)平衡的電壓/頻率執(zhí)行任務(wù)，在滿足截止期限的情況下，算法選擇一個(gè)預(yù)計(jì)能耗最小的處理器執(zhí)行該任務(wù)。2.2 算法描繪為保證任務(wù)執(zhí)行時(shí)的可靠性，Scheduling算法為即將執(zhí)行的任務(wù)構(gòu)造一個(gè)錯(cuò)誤恢復(fù)時(shí)間recoveryTime，然后試圖將任務(wù)按一個(gè)統(tǒng)一的電壓/頻率執(zhí)行。當(dāng)任務(wù)不能滿足截止期限要求時(shí)，那么逐個(gè)將前面未執(zhí)行任務(wù)的電壓/頻率調(diào)至最高并去掉recoveryTime。通過(guò)調(diào)用Sche

8、duling算法返回任務(wù)ti分配到處理器m增加的能耗之后，即可應(yīng)用選擇法找出執(zhí)行ti增加能耗最小實(shí)際上是使系統(tǒng)總能耗最小的處理器。另外當(dāng)一個(gè)任務(wù)執(zhí)行完后，應(yīng)該更新預(yù)分配的錯(cuò)誤恢復(fù)時(shí)間recoveryTime。根據(jù)這一思想，設(shè)計(jì)頂層算法如下：2.3 ESACR算法分析2.3.1 錯(cuò)誤恢復(fù)時(shí)間設(shè)定的討論性質(zhì) 錯(cuò)誤恢復(fù)時(shí)間的設(shè)定方法不會(huì)導(dǎo)致處理器上已有的任務(wù)隊(duì)列變得不可調(diào)度。2.3.2 時(shí)間復(fù)雜度分析為驗(yàn)證算法的性能，在考慮系統(tǒng)可靠性的前提下，將ESACR算法與最高電壓節(jié)能 Highest Voltage EnergyAware，HVEA調(diào)度5、最小能耗最小完成時(shí)間 Minimum Energy M

9、inimum Completion time，MEMC調(diào)度6 和最早完成時(shí)間優(yōu)先Earliest Finish First，EFF調(diào)度進(jìn)展比較。3.1 實(shí)驗(yàn)參數(shù)設(shè)定3.2 實(shí)驗(yàn)分析任務(wù)到達(dá)時(shí)間間隔不同時(shí)，不同算法的可靠性與相對(duì)能耗相對(duì)能耗指什么？需明確說(shuō)明，是否是指與EFF的比值？，假設(shè)是，圖中縱坐標(biāo)改為“相對(duì)EFF能耗因?yàn)镋FF算法的能耗相對(duì)其他算法的能耗大一些，這里的歸一化是用各個(gè)算法產(chǎn)生的能耗都單獨(dú)除以EFF算法產(chǎn)生的能耗，那么EFF算法的能耗變?yōu)?，其他算法的能耗那么變?yōu)?-1之間的數(shù)值。從圖3a可知，當(dāng)任務(wù)的計(jì)算量C418，48之前時(shí)，EFF、HVEA及ESACR算法的可靠性均到達(dá)1

10、00%；當(dāng)計(jì)算量變大時(shí)，四個(gè)算法的可靠性均小于100%。從圖3b可知，可靠性能到達(dá)100%的三個(gè)算法中，ESACR算法的能耗最小，約為EFF的70%左右。從圖4a可知，當(dāng)截止期限小于到達(dá)時(shí)間加6C？6C時(shí)，四個(gè)算法的可靠性均小于100%；當(dāng)截止期限為到達(dá)時(shí)間加6C時(shí)，EFF、HVEA及ESACR算法的可靠性到達(dá)100%，MEMC的可靠性那么一直小于60%。從圖4b可知，三個(gè)可靠性到達(dá)100%的算法中，ESACR算法的相對(duì)能耗最小，約為EFF的75%左右，且隨著截止期限的放寬，ESACR算法的相對(duì)能耗有下降趨勢(shì)。從圖5a可知，當(dāng)處理器數(shù)小于10時(shí)，四個(gè)算法的可靠性均小于100%；當(dāng)處理器數(shù)到達(dá)1

11、0時(shí)，EFF、HVEA及ESACR算法的可靠性到達(dá)100%，MEMC的可靠性那么一直小于80%。從圖5b可知，三個(gè)可靠性到達(dá)100%的算法中，ESACR算法的相對(duì)能耗最小，平均約為EFF的70%左右，且隨著處理器的增加有下降趨勢(shì)。通過(guò)以上4個(gè)實(shí)驗(yàn)可知，EFF、HVEA及ESACR算法的可靠性根本一樣，但ESACR算法的相對(duì)能耗明顯低于另外兩個(gè)算法，MEMC算法雖然節(jié)能效果明顯，但多數(shù)時(shí)候不能滿足系統(tǒng)可靠性要求。4 結(jié)語(yǔ)可靠性與節(jié)能在很多系統(tǒng)中非常重要，針對(duì)多處理器系統(tǒng)中隨機(jī)到達(dá)的任務(wù)，設(shè)計(jì)了可靠性約束下的節(jié)能調(diào)度算法，算法通過(guò)構(gòu)造錯(cuò)誤恢復(fù)時(shí)間以保證系統(tǒng)的可靠性，通過(guò)平衡單個(gè)處理器上任務(wù)的執(zhí)行電

12、壓/頻率以節(jié)能，實(shí)驗(yàn)結(jié)果說(shuō)明本文算法在保證系統(tǒng)可靠性的前提下具有較好的節(jié)能效果。后續(xù)研究可以考慮任務(wù)調(diào)度過(guò)程中的通信能耗、存儲(chǔ)器訪問(wèn)能耗等。參考文獻(xiàn)：6KIM J K， SIEGEL H J， MACIEJEWSKI A A， et al. Dynamic resource management in energy constrained heterogeneous computing systems using voltage scaling J. IEEE Transactions on Parallel and Distributed Systems， 2021，1911：1445-1457.9ZHU D， MELHEM R， MOSSE D. The effects of energy management on reliab