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

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

2、的前提下節(jié)能效果最好。關(guān)鍵詞：多處理器系統(tǒng)；隨機任務(wù)；可靠性約束；節(jié)能；調(diào)度中圖分類號： TP393 文獻標(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 引言因為瞬時錯誤更加常見，所以本文只考慮瞬時錯誤，假設(shè)系統(tǒng)的瞬時錯誤服從泊松分布8，11，14，處理器以頻率f對應(yīng)的電壓為V執(zhí)行任務(wù)時瞬時錯誤率8，11為：f=0gf=0 10d1-f1-fmin

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

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

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

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

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

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

12、壓/頻率以節(jié)能，實驗結(jié)果說明本文算法在保證系統(tǒng)可靠性的前提下具有較好的節(jié)能效果。后續(xù)研究可以考慮任務(wù)調(diào)度過程中的通信能耗、存儲器訪問能耗等。參考文獻：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