劉 科，張龍信，王 蘭，王 苗，滿君豐

(湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 株洲 412007)

1 引 言

近年來(lái)，谷歌、亞馬遜、微軟、IBM等國(guó)際著名云提供商已經(jīng)在云中大力地加入人工智能應(yīng)用.人工智能和云計(jì)算的組合被稱為智能云計(jì)算[1].在現(xiàn)代化的數(shù)據(jù)密集化環(huán)境，霧和云服務(wù)的部署日益增長(zhǎng)，在不同層次需要越來(lái)越多的智能，以提供最佳的任務(wù)調(diào)度決策、虛擬機(jī)遷移等[2].為了適應(yīng)大數(shù)據(jù)時(shí)代的計(jì)算服務(wù)需求，云計(jì)算系統(tǒng)數(shù)據(jù)中心處理器的數(shù)量急劇增加[3].運(yùn)行規(guī)模龐大的數(shù)據(jù)中心，云計(jì)算系統(tǒng)需要消耗大量的電能.據(jù)統(tǒng)計(jì)，2020年美國(guó)所有數(shù)據(jù)中心的電能增長(zhǎng)了14%，達(dá)到730億千瓦時(shí)，我國(guó)數(shù)據(jù)中心消耗的電能已超過(guò)匈牙利和希臘兩國(guó)用電總和[4].云計(jì)算系統(tǒng)數(shù)據(jù)中心的能耗問(wèn)題已經(jīng)引起了國(guó)內(nèi)外研究人員的廣泛關(guān)注.

在云計(jì)算系統(tǒng)中，降低能耗的方法包含改進(jìn)硬件技術(shù)和設(shè)計(jì)能耗感知的調(diào)度算法，其中，硬件的改進(jìn)技術(shù)包括設(shè)計(jì)低功耗的處理器和固態(tài)驅(qū)動(dòng)等；能耗感知算法的設(shè)計(jì)包括操作系統(tǒng)級(jí)別的電源管理和應(yīng)用級(jí)的電源管理等[5].動(dòng)態(tài)電壓和頻率縮放(DVFS)技術(shù)通過(guò)降低處理器的電壓和頻率從而減少能量的消耗，這已成為一種重要的能耗調(diào)節(jié)技術(shù)[6，7].

由于云計(jì)算系統(tǒng)架構(gòu)的復(fù)雜性，其運(yùn)行過(guò)程中發(fā)生錯(cuò)誤難以避免.同時(shí)，減少能量消耗和增強(qiáng)系統(tǒng)可靠性互斥，較低的能量消耗會(huì)導(dǎo)致系統(tǒng)可靠性低.近年來(lái)有諸多研究表明，動(dòng)態(tài)調(diào)節(jié)處理器的電壓可能導(dǎo)致處理器瞬態(tài)故障急劇增加，從而影響系統(tǒng)的可靠性[8-10].異構(gòu)云計(jì)算系統(tǒng)中，除了降低數(shù)據(jù)中心的能耗，如何保證云系統(tǒng)的可靠性也是衡量服務(wù)質(zhì)量的一個(gè)重要課題.

為了解決云計(jì)算系統(tǒng)中的高能量消耗問(wèn)題，科研人員已經(jīng)提出了大量的節(jié)能調(diào)度方法.Chen等[11]針對(duì)云計(jì)算環(huán)境中并行任務(wù)集的低成本和低能耗的需求，提出了可用的成本開(kāi)銷預(yù)分配算法，在滿足任務(wù)集成本約束下，減少了能量消耗.Tang等[12]在滿足基于云計(jì)算性能服務(wù)水平協(xié)議的基礎(chǔ)上，提出了一種新的能源感知調(diào)度算法，在滿足截止期限約束的前提下，有效地減少能源消耗.Li等[13]針對(duì)異構(gòu)分布式計(jì)算系統(tǒng)中的并行應(yīng)用提出了一種增強(qiáng)的調(diào)度算法(EECC)，該算法可以在滿足給定能耗約束的同時(shí)獲得更優(yōu)的調(diào)度長(zhǎng)度.Zhang等[14]提出異構(gòu)云計(jì)算中成本約束下的工作流能量高效調(diào)度算法，算法包括任務(wù)優(yōu)先級(jí)的計(jì)算、任務(wù)預(yù)算成本的分配以及最優(yōu)執(zhí)行虛擬機(jī)和能量高效頻率的確定3個(gè)階段，最大限度地節(jié)省能量.

以上方法雖然都采用DVFS技術(shù)減少云計(jì)算系統(tǒng)運(yùn)行過(guò)程中的能量消耗，但并未考慮使用DVFS技術(shù)在減少能耗的同時(shí)會(huì)降低系統(tǒng)可靠性.Zhao等[15]為單處理器實(shí)時(shí)系統(tǒng)建立了能耗和可靠性之間的關(guān)系模型，后來(lái)的多處理器系統(tǒng)也使用的此模型解決能耗和可靠性相關(guān)的任務(wù)調(diào)度問(wèn)題，為本文的研究提供了理論基礎(chǔ).Zhang等[16]針對(duì)DVFS技術(shù)減少能量消耗會(huì)帶來(lái)可靠性降低的問(wèn)題，提出了可靠性最大化能量節(jié)省策略，有效地提高了異構(gòu)多處理器的可靠性.Zhang等[17]提出了一種能量和截止時(shí)間雙重約束下并行應(yīng)用任務(wù)集的可靠性感知算法，進(jìn)一步提高了系統(tǒng)的可靠性.Xiao等人采用DVFS技術(shù)解決異構(gòu)分布式系統(tǒng)上有能耗約束的并行應(yīng)用可靠性最大化問(wèn)題，并提出了MREC算法，該算法主要包含兩個(gè)階段，確定任務(wù)優(yōu)先級(jí)和選擇合適的處理器與頻率組合[18].本文針對(duì)異構(gòu)云計(jì)算系統(tǒng)中能耗約束下可靠性加強(qiáng)問(wèn)題，提出了能耗約束下最大化可靠性算法(ERMEC).ERMEC算法主要包含以下3個(gè)階段：1)確保任務(wù)的調(diào)度順序不違反任務(wù)集的拓?fù)浣Y(jié)構(gòu)，建立任務(wù)的優(yōu)先排序隊(duì)列；2)計(jì)算任務(wù)集的最大能耗，最小能耗以及任務(wù)的能耗約束；3)根據(jù)任務(wù)的能耗約束，確定最優(yōu)的處理器與頻率組合，確保在滿足能耗約束的前提下可靠性值最大.異構(gòu)云計(jì)算系統(tǒng)中并行應(yīng)用任務(wù)集調(diào)度是NP難問(wèn)題，屬于組合優(yōu)化的范疇[19].

2 系統(tǒng)模型

本文使用集合U={u1，u2，…，uk}表示一組異構(gòu)的處理器集合，其中k為云計(jì)算系統(tǒng)數(shù)據(jù)中心處理器的數(shù)量，每個(gè)處理器都支持DVFS技術(shù).處理器的電壓和頻率滿足隨機(jī)的均勻分布.任意兩個(gè)處理器之間可以直接通信，處理器之間的數(shù)據(jù)通信速率一致.相對(duì)于任務(wù)的處理時(shí)間而言，處理器上頻率切換的開(kāi)銷通常很小，在設(shè)計(jì)調(diào)度算法的過(guò)程中忽略不計(jì).

2.1 任務(wù)模型

異構(gòu)云計(jì)算系統(tǒng)中存在優(yōu)先約束的任務(wù)集通常采用有向無(wú)環(huán)圖(DAG)描述[20]，并使用四元組G={N，E，C，W}表示，其中，N為所有任務(wù)的集合，節(jié)點(diǎn)ni∈N表示并行應(yīng)用任務(wù)集中第i個(gè)任務(wù)；E為任務(wù)間所有通信鏈路的集合，邊ei，j∈E表示任務(wù)ni-nj之間存在的依賴關(guān)系，ni是nj的直接前驅(qū)節(jié)點(diǎn)；C為任務(wù)間通信時(shí)間的集合，對(duì)于ci，j∈C，ci，j表示當(dāng)任務(wù)ni和nj被分配至不同處理器時(shí)的通信時(shí)間，若兩個(gè)任務(wù)被分配至同一個(gè)處理器，則ci，j=0；W是一個(gè)|N|×|U|的矩陣，矩陣中的元素wi，j表示任務(wù)ni在處理器uj上以最大頻率運(yùn)行時(shí)的計(jì)算開(kāi)銷.另外，本文使用pred(ni)表示任務(wù)ni的直接前驅(qū)任務(wù)的集合，succ(ni)表示任務(wù)ni的直接后繼任務(wù)的集合，沒(méi)有直接前驅(qū)的任務(wù)稱為入口任務(wù)，沒(méi)有直接后繼的任務(wù)稱為出口任務(wù).

圖1展示了一個(gè)包含10個(gè)任務(wù)的并行應(yīng)用任務(wù)集.根據(jù)前文的定義：圖1中的節(jié)點(diǎn)n1-n10代表并行應(yīng)用的任務(wù)，其中n1為入口任務(wù)，n10為出口任務(wù)；邊e1，2(e1，2∈E)為兩個(gè)任務(wù)間的通信鏈路，邊上的數(shù)值表示相連兩個(gè)任務(wù)被分配至不同處理器執(zhí)行時(shí)的平均通信開(kāi)銷.當(dāng)n2唯一的直接前驅(qū)任務(wù)n1執(zhí)行完成并將數(shù)據(jù)傳輸至執(zhí)行n2的處理器時(shí)，n2進(jìn)入準(zhǔn)備就緒狀態(tài)，等待處理器空閑時(shí)執(zhí)行.本文約定，并行應(yīng)用任務(wù)集僅包含一個(gè)入口任務(wù)和一個(gè)出口任務(wù)，如果給定的并行應(yīng)用任務(wù)集不符合此約定，可以通過(guò)增加零計(jì)算的虛擬節(jié)點(diǎn)作為入口任務(wù)或出口任務(wù)，同時(shí)增加零通信開(kāi)銷的虛擬通信鏈路以滿足此約定.

圖1 一個(gè)簡(jiǎn)單的工作流圖

由于處理器的異構(gòu)性，任務(wù)在不同的處理器上的計(jì)算時(shí)間不同.表1展示了圖1中各任務(wù)在3個(gè)處理器{u1，u2，u3}上對(duì)應(yīng)的計(jì)算時(shí)間.任務(wù)的平均計(jì)算時(shí)間表達(dá)式如式(1)所示：

表1 圖1中任務(wù)在各處理器上的計(jì)算開(kāi)銷

(1)

其中，wi，k為任務(wù)ni在處理器uk上以最大頻率執(zhí)行時(shí)所需要的時(shí)間，|U|為異構(gòu)云計(jì)算系統(tǒng)中處理器的數(shù)量.

2.2 能耗模型

異構(gòu)云計(jì)算系統(tǒng)中處理器的功耗分為動(dòng)態(tài)功耗和靜態(tài)功耗兩部分[21].動(dòng)態(tài)功耗指處理器處于激活狀態(tài)所產(chǎn)生的功耗，它是系統(tǒng)功耗的主要來(lái)源，靜態(tài)功耗指無(wú)論系統(tǒng)處于活動(dòng)狀態(tài)還是睡眠狀態(tài)都會(huì)持續(xù)產(chǎn)生的功耗.基于DVFS技術(shù)降低異構(gòu)分布式系統(tǒng)能耗的設(shè)計(jì)已經(jīng)得到了廣泛的研究，DVFS技術(shù)通過(guò)降低電壓和頻率以減少能量消耗[21].

本文采用喬治梅森大學(xué)的Aydin教授等人提出的系統(tǒng)級(jí)功率模型[8]為異構(gòu)云計(jì)算系統(tǒng)的功率模型，該模型被廣泛用于網(wǎng)格計(jì)算、云計(jì)算、異構(gòu)分布式計(jì)算[5，6，9，10，15-18].當(dāng)處理器運(yùn)行的頻率為f時(shí)，系統(tǒng)功率定義為：

P(f)=Ps+h(Pind+Pd)=Ps+h(Pind+Ceffm)

(2)

其中，Ps表示靜態(tài)功率，只有關(guān)閉整個(gè)系統(tǒng)的電源Ps才能消除，它所引起的能耗很小，在能耗的統(tǒng)計(jì)過(guò)程中忽略不計(jì)；h表示系統(tǒng)的狀態(tài)，當(dāng)系統(tǒng)處于活動(dòng)狀態(tài)時(shí)，h=1；當(dāng)系統(tǒng)處于關(guān)閉狀態(tài)時(shí)，h=0；Pind表示與頻率無(wú)關(guān)的功率，是一個(gè)常量；Pd表示與頻率相關(guān)的動(dòng)態(tài)功率；Cef表示有效開(kāi)關(guān)電容；m表示動(dòng)態(tài)功率指數(shù)，通常不小于2.

由于存在與頻率無(wú)關(guān)的動(dòng)態(tài)功率，隨著處理器頻率的降低，系統(tǒng)的功率隨之減低.式(2)為一個(gè)關(guān)于頻率的凸函數(shù)，而能耗等于功率乘以時(shí)間，因此能耗亦為關(guān)于頻率的凸函數(shù).每個(gè)處理器必然存在一個(gè)最優(yōu)節(jié)能頻率fme，當(dāng)處理器的運(yùn)行頻率低于fme后，降低頻率將會(huì)消耗更多的能量，fme可由式(3)計(jì)算得出[16]：

(3)

假設(shè)處理器的頻率的變化范圍為最低頻率fmin到最高頻率fmax，為了保證能量效率，處理器的最小可用頻率flow定義為：

flow=max(fmin，fme)

(4)

因此，可以得到處理器的實(shí)際有效頻率f的取值范圍[flow，fmax].

在包含k個(gè)處理器的異構(gòu)云計(jì)算系統(tǒng)中，每個(gè)處理器都對(duì)應(yīng)各自的功率，以下為處理器功率參數(shù)集合：

·Pind集合：{P1，ind，P2，ind，…，Pk，ind}

·Pd集合：{P1，d，P2，d，…，Pk，d}

·Cef集合：{C1，ef，C2，ef，…，Ck，ef}

·m集合：{m1，ef，m2，ef，…，mk，ef}

·flow集合：{f1，low，f2，low，…，fk，low}

·fmax集合：{f1，max，f2，max，…，fk，max}

任務(wù)ni在處理器uk上運(yùn)行，當(dāng)處理器的運(yùn)行頻率為fk，h時(shí)，完成此任務(wù)消耗能量的計(jì)算表達(dá)式如式(5)所示：

(5)

并行應(yīng)用任務(wù)集的能耗為完成所有任務(wù)消耗能量的總和，計(jì)算表達(dá)式如式(6)所示：

(6)

其中，uord(i)為分配給任務(wù)ni的處理器，ford(i)，fz(i)為處理器uord(i)的運(yùn)行頻率.

2.3 可靠性模型

當(dāng)云計(jì)算系統(tǒng)運(yùn)行時(shí)，幾乎不可能避免由于軟件錯(cuò)誤、硬件錯(cuò)誤等導(dǎo)致的故障[18].并行應(yīng)用任務(wù)集的可靠性被定義為該任務(wù)集在云計(jì)算系統(tǒng)上成功完成的概率.瞬態(tài)故障滿足平均到達(dá)率為λ的泊松分布，并且任務(wù)運(yùn)行時(shí)發(fā)生故障的概率是獨(dú)立的[16].若λk表示處理器uk單位時(shí)間的故障率，則任務(wù)ni在處理器uk上以最大頻率fk，max運(yùn)行時(shí)的可靠性如式(7)所示[16]：

R(ni，uk)=e-λk×wi，k

(7)

對(duì)于支持DVFS技術(shù)的處理器而言，以不同的頻率運(yùn)行時(shí)系統(tǒng)的故障到達(dá)率不同.定義λk，max為處理器uk在最大頻率運(yùn)行狀態(tài)下的故障到達(dá)率，則處理器uk以頻率為fk，h運(yùn)行時(shí)的故障到達(dá)率λk，h可由式(8)計(jì)算[16].

(8)

其中，d為處理器靈敏度因子，用以衡量歸一化后處理器的頻率改變時(shí)系統(tǒng)故障率改變的速率，其取值為常數(shù)1.

根據(jù)式(7)與式(8)，可以計(jì)算出任務(wù)ni在處理器uk上以頻率為fk，h運(yùn)行時(shí)的可靠性，其計(jì)算表達(dá)式如式(9)所示[18]：

(9)

由式(9)可得，在同一處理器上，可靠性和頻率是單調(diào)遞增的關(guān)系.為了節(jié)約能量，動(dòng)態(tài)降低處理器的頻率，可能導(dǎo)致可靠性低.DVFS系統(tǒng)中并行應(yīng)用任務(wù)集可靠性的計(jì)算表達(dá)式如式(10)所示：

(10)

3 能耗約束下最大化可靠性

對(duì)于一個(gè)給定的并行應(yīng)用任務(wù)集G，在滿足指定能耗約束Egoal(G)的前提下，為G中的每個(gè)任務(wù)選擇合適的處理器與執(zhí)行頻率，確保并行應(yīng)用任務(wù)集消耗的能量不會(huì)超過(guò)能耗約束，同時(shí)最大程度地增加并行應(yīng)用任務(wù)集執(zhí)行可靠性.上述問(wèn)題的形式化描述如式(11)和式(12)所示：

(11)

Subjectto：Eresult(G)≤Egoal(G)

(12)

其中，Rresult(G)為并行應(yīng)用任務(wù)集執(zhí)行可靠性，Egoal(G)和Eresult(G)分別為并行應(yīng)用任務(wù)集的能耗約束和實(shí)際能量消耗.

3.1 任務(wù)優(yōu)先級(jí)排序

定義1.(向上優(yōu)先等級(jí)(ranku))：并行應(yīng)用任務(wù)集中任務(wù)的ranku值是基于任務(wù)的平均計(jì)算成本和平均通信成本計(jì)算得出.ranku的計(jì)算表達(dá)式如式(13)所示：

(13)

3.2 滿足能耗約束

為了方便表述，本文定義任務(wù)ni的最小能耗Emin(ni)和最大能耗Emax(ni)，由式(5)可知，任務(wù)運(yùn)行的能量消耗與運(yùn)行頻率成正比，即任務(wù)運(yùn)行時(shí)消耗的能量隨著頻率的升高而增加.因此Emin(ni)和Emax(ni)的計(jì)算表達(dá)式分別如式(14)和式(15)所示：

(14)

(15)

并行應(yīng)用任務(wù)集的總能量消耗為所有任務(wù)的能耗之和，因此并行應(yīng)用任務(wù)集的最小能耗Emin(G)和最大能耗Emax(G)表達(dá)式定義如下：

(16)

(17)

在并行應(yīng)用任務(wù)集G開(kāi)始調(diào)度之前，它的能耗約束Egoal(G)由用戶給定.為保證能耗約束有意義，能耗約束應(yīng)滿足Emin(G)≤Egoal(G)≤Emax(G).本文提出的任務(wù)能耗預(yù)分配方案由式(18)表示：

(18)

假設(shè)等待調(diào)度的并行應(yīng)用任務(wù)集按ranku值排序后的任務(wù)調(diào)度列表為{ns(1)，ns(2)，…，ns(|N|)}.若當(dāng)前準(zhǔn)備就緒的候選任務(wù)為ns(i)，則{ns(1)，ns(2)，…，ns(i-1)}表示已經(jīng)完成調(diào)度的任務(wù)集合；{ns(i+1)，ns(i+2)，…，ns(|N|)}表示尚未調(diào)度的任務(wù)集合，此時(shí)并行應(yīng)用的能耗應(yīng)為：

(19)

根據(jù)式(19)將并行應(yīng)用任務(wù)集的能耗約束轉(zhuǎn)移至每個(gè)任務(wù)，得到任務(wù)的能耗約束.任務(wù)的能耗約束計(jì)算表達(dá)式如式(20)所示.在任務(wù)的調(diào)度過(guò)程中，只需為每個(gè)任務(wù)找到滿足能耗約束的處理器與頻率的組合即可.

(20)

證明：本文使用數(shù)學(xué)歸納法來(lái)證明通過(guò)上述策略對(duì)等待調(diào)度的任務(wù)進(jìn)行能耗預(yù)分配[5]，并行應(yīng)用中每個(gè)任務(wù)ns(i)都能被分配一個(gè)處理器和頻率組合，使并行應(yīng)用的總能耗滿足式(12).

首先，考慮調(diào)度列表中第一個(gè)任務(wù)ns(1).ns(1)是當(dāng)前被調(diào)度的任務(wù)，剩下|N|-1個(gè)任務(wù)還未被調(diào)度.根據(jù)式(19)和式(20)，可以得到此時(shí)應(yīng)用的總能耗為：

(21)

由式(18)可知：Epre(ns(1))≥Emin(ns(1)).因此，當(dāng)E(ns(1)，uk，fk，h)=Emin(ns(1))時(shí)，式(21)可表示為：

Es(1)(G)=Emin(ns(1))+Egoal(G)-Epre(ns(1))≤Egoal(G)

(22)

對(duì)任務(wù)ns(1)而言，使用該能耗預(yù)分配策略產(chǎn)生的能量滿足能耗約束.

不失一般性，調(diào)度第i個(gè)任務(wù)的總能耗為：

(23)

然后，當(dāng)調(diào)度第i+1個(gè)任務(wù)時(shí)，應(yīng)用的總能耗為：

(24)

結(jié)合式(23)和式(24)可得：

(25)

又因Emin(ns(i+1))≤E(ns(i+1)，uk，fk，h)≤Epre(ns(i+1))，由式(25)可得：

Es(i+1)(G)≤Egoal(G)

(26)

通過(guò)上述證明可知，本文提出的能耗預(yù)分配策略理論上可以滿足式(12).

3.3 能耗約束下最大化可靠性算法

算法1.The ERMEC algorithm

輸入：G={N，E，C，W}，Egoal(G).

輸出：任務(wù)集的能耗Eresult(G)和可靠性Rresult(G).

1.計(jì)算G中所有節(jié)點(diǎn)的ranku值，降序排列，得到任務(wù)優(yōu)先隊(duì)列task_list

2.計(jì)算任務(wù)節(jié)點(diǎn)的Emin(ni)和Emax(ni)

3.計(jì)算任務(wù)節(jié)點(diǎn)的預(yù)分配能耗Epre(ni)

4.while隊(duì)列task_list非空

5.ni=task_list.out

6.計(jì)算任務(wù)的能耗約束Egoal(ni)

7.foreachuk∈Udo

8.foreachfk，h∈[fk，max，fk，low]do

9. 計(jì)算E(ni，uk，fk，h)

10.ifE(ni，uk，fk，h)>Egoal(ni)then

11. continue;

12.endif

13. 計(jì)算R(ni，uk，fk，h)

14.ifR(ni，uk，fk，h)>R(ni，uord(i)，ford(i)，hz(i))

15.upr(i)←ukandfpr(i)，hz(i)←fk，h

16.E(ni，uk，fk，h)←E(ni，uord(i)，ford(i)，hz(i))

17.R(ni，uk，fk，h)←R(ni，uord(i)，ford(i)，hz(i))

18.break;

19.endif

20.endfor

21.endfor

22.endwhile

23.計(jì)算任務(wù)集的能耗Eresult(G)

24.計(jì)算任務(wù)集的可靠性Rresult(G)

異構(gòu)云計(jì)算系統(tǒng)中具有能耗約束的并行應(yīng)用任務(wù)集的可靠性最大化算法(ERMEC)的偽代碼如算法1所示.步驟1計(jì)算并行應(yīng)用任務(wù)集中所有任務(wù)的ranku值，并按ranku值非遞增方式排序得到任務(wù)的調(diào)度列表task_list.步驟2計(jì)算任務(wù)ni的最小能耗Emin(ni)和最大能耗Emax(ni).步驟3計(jì)算任務(wù)ni的預(yù)分配能耗Epre(ni).步驟4-步驟22從任務(wù)調(diào)度列表中依次取出等待調(diào)度的任務(wù)，計(jì)算其對(duì)應(yīng)的能耗約束，并為其選擇該能耗約束下最優(yōu)的執(zhí)行處理器及使可靠性值最大的執(zhí)行頻率.其中，步驟5取出task_list中的任務(wù)；步驟6根據(jù)式(20)計(jì)算該任務(wù)的能耗約束；步驟7-步驟21為等待調(diào)度的任務(wù)選擇合適的處理器與頻率；步驟8從最大頻率開(kāi)始以遞減順序遍歷選擇的頻率，由于較小的頻率會(huì)導(dǎo)致可靠性值偏低，一旦找到滿足任務(wù)能耗約束的處理器與頻率組合時(shí)，則停止遍歷該處理器剩下的頻率.步驟23統(tǒng)計(jì)并行應(yīng)用任務(wù)集的總能量消耗，步驟24計(jì)算任務(wù)集的可靠性.

不難得出，ERMEC算法的時(shí)間復(fù)雜度為O(|N|×|U|×|F|)，其中|F|表示所有處理器中從fk，low到fk，max的最大離散頻率級(jí)別數(shù)量.調(diào)度過(guò)程將遍歷調(diào)度列表中所有的任務(wù)，需要的時(shí)間為O(|N|)，為每個(gè)任務(wù)選擇合適的處理器與頻率組合消耗的時(shí)間為O(|U|×|F|).

3.4 ERMEC算法實(shí)例

使用ERMEC算法調(diào)度圖1所示并行應(yīng)用任務(wù)集，處理器的功率參數(shù)如表2所示，每個(gè)處理器歸一化后的最大頻率fk，max為1.0，頻率的精度設(shè)置為0.01.根據(jù)式(16)和式(17)可以計(jì)算出并行應(yīng)用的最小能耗和最大能耗.給定并行應(yīng)用任務(wù)集的能耗約束為Egoal(G)=3×Emin(G)=72.8073.

表2 處理器參數(shù)

表3展示了使用ERMEC算法調(diào)度并行應(yīng)用任務(wù)集實(shí)例的結(jié)果，第1列根據(jù)ranku值排序得到的任務(wù)調(diào)度列表.表3中每行的元素分別為任務(wù)的編號(hào)、任務(wù)的能耗約束、任務(wù)分配的處理器及其工作頻率組合、產(chǎn)生的能耗值和可靠性值.從表3可以看出，每個(gè)任務(wù)的實(shí)際能耗值都小于任務(wù)的能耗約束值.并行應(yīng)用的實(shí)際總能耗為72.7985，小于給定的并行應(yīng)用的能耗約束Egoal(G).使用MREC算法在相同環(huán)境下調(diào)度同一并行應(yīng)用任務(wù)集得到的可靠性為0.8197.與MREC算法相比，在滿足并行應(yīng)用任務(wù)集能耗約束的同時(shí)，ERMEC算法使得系統(tǒng)的可靠性提升了19.14%.

表3 使用ERMEC算法調(diào)度圖1并行應(yīng)用的分配過(guò)程

使用ERMEC算法調(diào)度圖1所示并行應(yīng)用任務(wù)集的結(jié)果如圖2所示，調(diào)度長(zhǎng)度為SL(G)=85.55.

圖2 ERMEC算法調(diào)度應(yīng)用結(jié)果

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

本文使用64個(gè)不同計(jì)算能力、存儲(chǔ)空間和帶寬的虛擬節(jié)點(diǎn)，來(lái)模擬異構(gòu)云計(jì)算環(huán)境中的64個(gè)處理器.實(shí)驗(yàn)中任務(wù)的計(jì)算開(kāi)銷為10h≤wi，k≤100h，處理器的通信開(kāi)銷為10h≤ci，j≤100h，與功率相關(guān)的處理器其他重要參數(shù)的取值范圍：0.03≤Pind≤0.07、0.8≤Cef≤1.2、2.5≤m≤3.0、fmax=1.0G Hz.處理器的工作頻率為區(qū)間[flow，fmax]內(nèi)的離散值，其精度為0.01G Hz，處理器在最大頻率下運(yùn)行的故障到達(dá)率0.0000001≤λmax≤0.0000128[18].實(shí)驗(yàn)中使用Intel Core(TM)i7-9750H CPU @2.60GHz六核處理器，16GB內(nèi)存，JDK版本為1.8，系統(tǒng)運(yùn)行環(huán)境為Windows 10.

本文選擇的對(duì)比算法為MREC和EECC*.MREC算法解決基于DVFS的異構(gòu)分布式系統(tǒng)上能量受限并行應(yīng)用的可靠性最大問(wèn)題.EECC*為文獻(xiàn)[13]中能耗約束下最小化調(diào)度長(zhǎng)度EECC算法的擴(kuò)展，旨在提高并行應(yīng)用的可靠性.本文采用的算法性能標(biāo)準(zhǔn)指標(biāo)為并行應(yīng)用任務(wù)集的實(shí)際能量消耗和可靠性.

實(shí)驗(yàn)中采用兩個(gè)廣泛使用的并行應(yīng)用任務(wù)集，分別為高斯消元(GE)并行應(yīng)用和快速傅里葉變換(FFT)并行應(yīng)用.

4.2 GE并行應(yīng)用任務(wù)集

圖3 GE并行應(yīng)用

由圖4(a)可得，固定GE并行應(yīng)用的規(guī)模大小，隨著能耗約束的增大，并行應(yīng)用的可靠性不斷提高.當(dāng)能耗約束較小時(shí)，即α=7，本文提出的ERMEC算法比MREC、EECC*算法得到的可靠性分別提高了16.25%、11.37%；當(dāng)能耗約束較大時(shí)，即α=4，ERMEC算法比MREC和EECC*算法得到的可靠性平均可提高35.04%、16.65%.

圖4 GE并行應(yīng)用的結(jié)果

由圖4(b)可得，隨著GE并行任務(wù)集的規(guī)模不斷增大，任務(wù)集的可靠性都有所下降，這是由于任務(wù)的可靠性值小于1，根據(jù)式(10)可知，任務(wù)集的可靠性為所有任務(wù)可靠性的乘積.當(dāng)GE并行應(yīng)用的規(guī)模較小時(shí)，即σ=8，ERMEC算法比MREC、EECC*算法得到的可靠性分別提高了6.38%、5.74%.并且，當(dāng)GE并行應(yīng)用的規(guī)模較大時(shí)，即σ=50，ERMEC算法比MREC、EECC*算法得到的可靠性分別提高了85.24%、45.53%.這表明ERMEC算法對(duì)于提高大規(guī)模GE并行應(yīng)用的可靠性更加有效.

4.3 FFT并行應(yīng)用任務(wù)集

FFT由輸入向量和進(jìn)行迭代的蝶形運(yùn)算組成.若用σ表示FFT并行應(yīng)用任務(wù)集的規(guī)模參數(shù)，則節(jié)點(diǎn)總數(shù)滿足|N|=(2×σ-1)+σ×log2σ，σ=2y，y為正整數(shù).規(guī)模為σ的FFT并行應(yīng)用包含σ個(gè)底層節(jié)點(diǎn).圖5為一個(gè)σ=4的FFT并行應(yīng)用任務(wù)集.為了保證并行應(yīng)用出口節(jié)點(diǎn)唯一，實(shí)驗(yàn)過(guò)程中將為FFT任務(wù)集添加零計(jì)算開(kāi)銷的出口節(jié)點(diǎn)nexit，并為所有底層節(jié)點(diǎn)和nexit之間添加零通信開(kāi)銷的邊.

圖5 FFT并行應(yīng)用

由圖6(a)可得，當(dāng)FFT并行應(yīng)用的節(jié)點(diǎn)數(shù)相同時(shí)，隨著能耗約束的增大，并行應(yīng)用的可靠性不斷提高.當(dāng)能耗約束較小時(shí)，即α=7，ERMEC算法比MREC、EECC*算法得到的可靠性分別提高了14.64%、8.79%.當(dāng)能耗約束較大時(shí)，即α=3，ERMEC算法比MREC、EECC*算法得到的可靠性分別提高了30.55%、13.47%.

圖6 FFT并行應(yīng)用的結(jié)果

由圖6(b)不難得出，隨著FFT并行應(yīng)用的規(guī)模不斷增大，應(yīng)用的可靠性都有所下降，其趨勢(shì)與GE并行應(yīng)用的結(jié)果相似.當(dāng)FFT應(yīng)用的規(guī)模較小時(shí)，即σ=8，采用ERMEC算法得到的可靠性最大；當(dāng)FFT并行應(yīng)用的規(guī)模較大時(shí)，即σ=128，ERMEC算法比MREC、EECC*算法得到的可靠性分別提高了82.17%、33.46%.這表明ERMEC算法對(duì)于提高大規(guī)模的FFT并行應(yīng)用的可靠性更有效.

5 總 結(jié)

本文研究異構(gòu)云計(jì)算系統(tǒng)中能耗約束并行應(yīng)用任務(wù)集可靠性加強(qiáng)問(wèn)題，基于動(dòng)態(tài)電壓和頻率縮放技術(shù)，提出了低時(shí)間復(fù)雜度的能耗約束下可靠性最大化(ERMEC)算法.ERMEC算法首先使用ranku值對(duì)并行應(yīng)用中所有的任務(wù)排序得到優(yōu)先級(jí)列表、計(jì)算每個(gè)任務(wù)的預(yù)分配能耗值；再將并行應(yīng)用任務(wù)集的能耗約束轉(zhuǎn)移到每個(gè)任務(wù)上，得到任務(wù)的能耗約束；最后遍歷處理器選擇該能耗約束下最優(yōu)的執(zhí)行處理器及使可靠性值最大的執(zhí)行頻率.實(shí)驗(yàn)采用現(xiàn)實(shí)世界的大規(guī)模GE和FFT并行應(yīng)用任務(wù)集對(duì)算法進(jìn)行性能測(cè)試，與現(xiàn)有的MREC算法和改進(jìn)的EECC*算法相比，本文提出的ERMEC算法比MREC和EECC*算法能獲得更高的可靠性值.并且，當(dāng)并行應(yīng)用任務(wù)集的規(guī)模較大時(shí)，ERMEC算法對(duì)于提高其可靠性更加有效.