在異構(gòu)系統(tǒng)上基于權(quán)重和復(fù)制的調(diào)度算法

鄧德康，張振榮

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

降低計(jì)算系統(tǒng)功耗的方法可以從硬件和軟件兩方面進(jìn)行解決[1-4]。一種通用處理技術(shù)是動(dòng)態(tài)電壓和頻率縮放(DVFS)技術(shù)。這項(xiàng)技術(shù)能動(dòng)態(tài)調(diào)整處理器的電壓和頻率以此來節(jié)省能量消耗[5-7]。因此，研究在具有這種特性的處理上進(jìn)行任務(wù)調(diào)度具有重要的價(jià)值，并且在近些年已向云計(jì)算領(lǐng)域拓展[8-12]。

雖然DVFS能實(shí)現(xiàn)能耗的優(yōu)化，但這種對(duì)電壓和頻率的操作可能會(huì)導(dǎo)致處理器故障率短時(shí)間內(nèi)的急劇增加，從而對(duì)系統(tǒng)的可靠性產(chǎn)生嚴(yán)重的威脅[13-15]?？煽啃远x為預(yù)計(jì)成功的概率。對(duì)于那些對(duì)安全性極為敏感的應(yīng)用，可靠性的優(yōu)先級(jí)應(yīng)高于功耗；否則，造成災(zāi)難性后果的概率將大幅提高。一種極為有效的措施是通過復(fù)制任務(wù)以提高可靠性。任務(wù)復(fù)制使得只要有一個(gè)處理器能正常的完成任務(wù)，就認(rèn)為任務(wù)被成功完成。因此，被視為重要的可靠性增強(qiáng)機(jī)制[14]。

可靠性感知任務(wù)調(diào)度是并行和分布式計(jì)算中的一個(gè)重要問題。Quan等[13]提出了一種被稱為ISAECC的算法，其使用了基于任務(wù)權(quán)重的能量預(yù)分配方式，以解決能量分配不公平的問題，從而獲得較好的效果。Xie等[14]提出了ESRG和基于復(fù)制機(jī)制的EFSRG算法，以減少能源消耗，同時(shí)滿足應(yīng)用的可靠性目標(biāo)，但是性能不佳。Xu等[15]提出將應(yīng)用程序的可靠性目標(biāo)轉(zhuǎn)換為DVFS的任務(wù)的DERG算法。Medara等[16]將DVFS運(yùn)用到云計(jì)算環(huán)境下，它在實(shí)現(xiàn)應(yīng)用可靠性目標(biāo)的同時(shí)減少了系統(tǒng)資源的使用。Chen等[17]提出了一種基于鏈表的能量感知算法，用于解決異構(gòu)系統(tǒng)的調(diào)度問題，但盡管有良好的性能，算法的復(fù)雜度高。Ahmad等[18]將能量?jī)?yōu)化運(yùn)用到云計(jì)算環(huán)境下。

本文研究了在異構(gòu)計(jì)算系統(tǒng)上滿足可靠性約束下，并行應(yīng)用程序能量消耗和調(diào)度長度最小化問題，為了降低異構(gòu)計(jì)算系統(tǒng)上并行應(yīng)用程序的資源消耗和成本，提出一種基于任務(wù)權(quán)重和復(fù)制機(jī)制的分配算法，使用浮點(diǎn)減運(yùn)算代替除運(yùn)算，提高了數(shù)值的穩(wěn)定性和性能的優(yōu)化，在滿足可靠性條件下，實(shí)現(xiàn)能量消耗優(yōu)化的解決方案。

1 系統(tǒng)模型

1.1 應(yīng)用模型

與先前的工作一致[9，13，14]，我們使用有向無環(huán)圖(directed acyclic graph，DAG)來表示應(yīng)用模型，記作X，|X|表示其大小。U={u1，u2，…，u|U|} 表示異構(gòu)處理器集合。其中|U|表示其大小。G={N，M，C，W} 用于定義DAG。其具體說明如下：

N表示為G的一系列節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)表示為一個(gè)任務(wù)。succ(ni) 表示ni節(jié)點(diǎn)的立即后續(xù)任務(wù)的集合，類似的pred(ni) 表示ni的前置任務(wù)的集合，任務(wù)ni必須等到其所有前置任務(wù)完成后，才能被執(zhí)行。succ(ni) 為0的節(jié)點(diǎn)稱為nexit節(jié)點(diǎn)，相似的pred(ni) 為0節(jié)點(diǎn)稱為nentry節(jié)點(diǎn)，對(duì)于存在多個(gè)nexit或nentry的任務(wù)可以通過添加執(zhí)行時(shí)間和通信時(shí)間為0的虛擬節(jié)點(diǎn)，使其變成標(biāo)準(zhǔn)任務(wù)工作流。

M表示為任務(wù)通信的關(guān)系，m(i，j) 表示存在任務(wù)ni到nj的通信，C表示任務(wù)間通信的時(shí)間，c(i，j) 表示兩個(gè)任務(wù)通信所需花費(fèi)的時(shí)間。W是一個(gè)大小為 |N|×|U| 的矩陣，任意一個(gè)w(i，j) 值表示任務(wù)ni以最大頻率運(yùn)行在處理器uj上，在最壞的情況下所花費(fèi)的時(shí)間。圖1展示了一個(gè)基于DAG的并行程序的例子[15]。

圖1 基于DAG的并行程序例子

為了更好理解DAG，對(duì)其進(jìn)行一些簡(jiǎn)單的說明，其中任務(wù)n1到n2的通信時(shí)間花費(fèi)c(1，2) 為18，n2在任務(wù)n1執(zhí)行完成后執(zhí)行，如果n1和n2在同一處理器可立即執(zhí)行，否則需要等待c(1，2) 的時(shí)間后才能執(zhí)行。

1.2 功耗模型

本研究討論的功耗為處理器的功耗，功耗是一個(gè)關(guān)于處理器頻率的函數(shù)，其具體定義為

P(f)=Ps+h(Pind+Pd)=
Ps+g(Pind+Cef+fm)

(1)

其中，Ps表示靜態(tài)功率，Pind和Pd分別表示頻率無關(guān)和頻率相關(guān)的動(dòng)態(tài)功率，h為激活函數(shù)(1表示系統(tǒng)活躍狀態(tài)，0為處于非活躍狀態(tài))，Cef表示有效電容，m表示動(dòng)態(tài)功率指數(shù)，Ps是不可調(diào)控的為處理器的內(nèi)在屬性，所以與先前的工作一致，本文關(guān)注于動(dòng)態(tài)功率[13-15]。處理器的最低能效頻率用fee表示，定義為

(2)

顯然，如果處理器的頻率范圍從最小值fmin到最大值fmax，那么實(shí)際最低工作頻率flow為：flow=max(fmin，fee)。 處理器的能量消耗可以通過以下公式進(jìn)行計(jì)算

(3)

其中

P(k，h)=P(k，ind)+C(k，ef)×f(k，h)mk

(4)

1.3 可靠性模型

在真實(shí)的系統(tǒng)環(huán)境下，在任務(wù)執(zhí)行階段時(shí)，故障是不可預(yù)測(cè)，并且不可避免的，遵循泊松概率分布[13-15]。設(shè)λk表示處理器uk單位時(shí)間的故障率。任務(wù)ni在處理器uk上以最大頻率執(zhí)行的可靠性可以用通過以下公式計(jì)算

R(ni，uk)=e-λkw(i，k)

(5)

對(duì)于支持DVFS的系統(tǒng)，考慮到動(dòng)態(tài)頻率縮放對(duì)瞬態(tài)故障的影響，因而故障率取決于實(shí)際處理器的頻率，不同的頻率具有不同的故障率。

不同頻率點(diǎn)下的可靠性計(jì)算可以使用如下公式進(jìn)行計(jì)算

(6)

d是一個(gè)常數(shù)，表示頻率對(duì)故障率影響水平。通過式(5)和式(6)可以得到可靠性的最終表達(dá)式為

(7)

從式(7)中，我們可以看到，可靠性與頻率之間的關(guān)系為線性關(guān)系。將每個(gè)任務(wù)的可靠性進(jìn)行計(jì)算，就可以得到整個(gè)應(yīng)用G的可靠性數(shù)值，具體的計(jì)算公式如下所示

(8)

其中，f(pr(i)，hz(i))∈[f(pr(i)，low)，f(pr(i)，max)]，upr(i)∈U為處理器集合，upr(i)和f((pr(i)，hz(i)) 分別表示任務(wù)i使用的處理器和對(duì)應(yīng)處理器的頻率?？傮w的能量通過對(duì)每個(gè)任務(wù)相加可得，具體如下公式計(jì)算

(9)

每個(gè)任務(wù)都有最小的可靠性和最大的可靠性，分別使用如下公式進(jìn)行計(jì)算

(10)

和

(11)

類似的，將每個(gè)任務(wù)的最小可靠性和最大可靠性應(yīng)用于整個(gè)應(yīng)用G，應(yīng)用G就存在有最小的可靠性和最大的可靠性，計(jì)算公式如下

(12)

和

(13)

通過上述公式可以得到，一個(gè)實(shí)際應(yīng)用G的可靠性范圍為：Rmin(G)≤Rgoal(G)≤Rmax(G)。

1.4 問題描述

在整個(gè)任務(wù)調(diào)度過程中需要解決的問題為：給定一個(gè)特定的可靠性目標(biāo)，在整個(gè)任務(wù)調(diào)度能達(dá)到既定的可靠性目標(biāo)的情況下，盡可能優(yōu)化其能量的消耗，對(duì)應(yīng)得數(shù)學(xué)描述可以歸納為如下

(14)

這個(gè)優(yōu)化問題以被證明為是一個(gè)NP困難問題[13-15]，因此更為普遍的方法是通過使用啟發(fā)式算法來解決這個(gè)問題。算法在求解整個(gè)問題的過程中，通常是將調(diào)度任務(wù)被劃分為兩部分：首先進(jìn)行預(yù)分配操作，根據(jù)任務(wù)自身的屬性為每個(gè)任務(wù)劃分特點(diǎn)的可靠性目標(biāo)，然后根據(jù)任務(wù)的優(yōu)先級(jí)依次求解，確定每個(gè)任務(wù)的最終調(diào)度情況。較之先前的工作，我們對(duì)分配的過程，和依次求解的過程進(jìn)行了相應(yīng)的改進(jìn)，以實(shí)現(xiàn)更好的性能。

2 分配算法

2.1 任務(wù)優(yōu)先級(jí)劃分

任務(wù)優(yōu)先級(jí)排序是基于鏈表調(diào)度方法中的一個(gè)必要的步驟，它為每個(gè)任務(wù)分配合理的優(yōu)先級(jí)，并根據(jù)任務(wù)優(yōu)先級(jí)排序來生成調(diào)度鏈表。任務(wù)的優(yōu)先級(jí)rank(u)可以通過以下公式計(jì)算

(15)

其中

(16)

這是一個(gè)遞歸定義式，nexit節(jié)點(diǎn)的rank(u)值，max部分0。除此之外，另外兩個(gè)重要的概念為最早開始時(shí)間(earliest start time，EST)和實(shí)際完成時(shí)間(actual finish time，AFT)，這兩種時(shí)間的計(jì)算公式分別如下

(17)

和

(18)

其中，avail[k] 表示處理器uk可以執(zhí)行一項(xiàng)任務(wù)時(shí)，可以獲得的最早時(shí)間。如果ni和nj被分配在同一處理器中，則c(i，j)=0。 整個(gè)應(yīng)用G的調(diào)度長度(scheduling length，SL)為：SL(G)=AFT(nexit)。

2.2 ESRG分配算法

本小節(jié)將對(duì)先前工作中提出ESRG算法進(jìn)行一個(gè)簡(jiǎn)單的回顧。為了達(dá)到預(yù)定的可靠性目標(biāo)值Rgoal，ESRG分配算法使用了如下的分配公式

(19)

先將所有的任務(wù)賦予相同的可靠性目標(biāo)數(shù)值，然后依次將剩余任務(wù)的可靠性值，通過依次傳遞的方式疊加到下個(gè)任務(wù)中，最終所有任務(wù)得到處理，公式如下

(20)

然后對(duì)于任意的任務(wù)ny而言，其可靠性值為

(21)

最后整個(gè)應(yīng)用的可靠性能夠滿足預(yù)定的目標(biāo)。從上面的公式可以看出：

(1)ESRG不考慮任務(wù)的大小分配可靠性，計(jì)算量大的任務(wù)要實(shí)現(xiàn)高可靠性，將消耗更多的能量，與此相對(duì)，計(jì)算量小的任務(wù)即使實(shí)現(xiàn)高可靠性，也不會(huì)造成較大能量的開銷。

(2)ESRG使用除法實(shí)現(xiàn)可靠性分配，在大量浮點(diǎn)數(shù)除法下，會(huì)造成結(jié)果不準(zhǔn)確，為了解決這個(gè)問題，我們將浮點(diǎn)數(shù)除法轉(zhuǎn)化成浮點(diǎn)數(shù)加減操作，這能使得計(jì)算結(jié)果更加的準(zhǔn)確。

(3)ESRG更為關(guān)鍵的問題是當(dāng)任務(wù)數(shù)較大時(shí)，將無法完成任務(wù)調(diào)度。一個(gè)簡(jiǎn)單的例子是，當(dāng)我們要調(diào)度一個(gè)有40個(gè)任務(wù)的可靠性為0.9的應(yīng)用G時(shí)，第一個(gè)任務(wù)需要滿足的可靠性為0.9973，這個(gè)是一個(gè)非常大的值，ESRG將無法完成這個(gè)調(diào)度任務(wù)，而我們的方法可以解決這個(gè)問題。

基于上述的問題，我們對(duì)其進(jìn)行了改進(jìn)，通過加入權(quán)重機(jī)制，使可靠性預(yù)分配變得更為合理。

2.3 基于權(quán)重的分配策略

首先，我們需要對(duì)可靠性的表達(dá)進(jìn)行變形

(22)

然后，設(shè)新的可靠性函數(shù)為

R′(ni)=log2(R(ni))

(23)

為了后文能更好進(jìn)行闡述，進(jìn)行以下定義：

定義1 給定R′max(G) 和R′goal(G)， 可降低的可靠性值R′rr(G)， 可以通過如下公式計(jì)算

R′rr(G)=R′max(G)-R′goal(G)

(24)

定義2 給定任務(wù)ni，其預(yù)先分配的可靠性R′pre(ni) 為

(25)

因?yàn)槲覀兎峙涑瞿繕?biāo)可靠性的值，任務(wù)計(jì)算量越大所需要的可靠性越低，反之，則需要越高的可靠性，這能更好的降低整個(gè)應(yīng)用的能量消耗，然后將所有任務(wù)按照rank值排序，進(jìn)行順序優(yōu)化，因此在滿足可靠性目標(biāo)的前提下，可以實(shí)現(xiàn)更小的能量消耗。

上述的分配策略相比于ESRG分配算法，不但考慮了任務(wù)的權(quán)重，對(duì)可靠性進(jìn)行分配，并且將多重浮點(diǎn)除法轉(zhuǎn)化為浮點(diǎn)加法，從而將計(jì)算誤差降低，提高計(jì)算的精度，對(duì)于任務(wù)數(shù)量眾多的情況，表現(xiàn)的越為明顯。

2.4 基于權(quán)重和復(fù)制的分配算法

前面所述的基于權(quán)重的分配策略對(duì)于較低的可靠性目標(biāo)，能夠起到不錯(cuò)的效果，但是，當(dāng)可靠性目標(biāo)增大到一個(gè)比較大的數(shù)值時(shí)，調(diào)度任務(wù)失敗的可能性依舊偏高，為了解決這個(gè)問題，通過引入復(fù)制機(jī)制，來提高整體應(yīng)用程序的可靠性。復(fù)制機(jī)制是將一個(gè)任務(wù)復(fù)制到多個(gè)處理器上運(yùn)行，只要有一個(gè)處理器成功運(yùn)行了任務(wù)，此任務(wù)就被認(rèn)為沒有出現(xiàn)錯(cuò)誤，剩下的任務(wù)依然能夠正常進(jìn)行調(diào)度。將權(quán)重與復(fù)制機(jī)制相結(jié)合，不僅能夠使可靠性大幅提升，同時(shí)能量的消耗也會(huì)得到相應(yīng)的降低。

由于引入了復(fù)制機(jī)制，一些相關(guān)的參數(shù)計(jì)算會(huì)發(fā)生相應(yīng)的變化，整個(gè)應(yīng)用程序的最大可靠性值，使用如下公式計(jì)算

(26)

相應(yīng)的，整個(gè)應(yīng)用G的最大可靠性，計(jì)算公式為

(27)

目標(biāo)可靠性仍需滿足約束：Rgoal(G)≤Rmax(G)， 否則解是不存在的。相應(yīng)的，兩個(gè)重要的參數(shù)AST和AFT也需要修改，它們的計(jì)算方式如下

(28)

和

(29)

(30)

Fse=αEd(ni，uk)+(1-α)SL(ni，uk)

(31)

其中，α是權(quán)重系數(shù)，用于衡量能量消耗和調(diào)度長度對(duì)處理選擇的影響。具體的算法流程描述如下：

算法1：基于分配和權(quán)重的分配算法

輸入：應(yīng)用G；處理器集U；目標(biāo)可靠性R′goal(G)

輸出：能量消耗E(G)；調(diào)度長度SL(G)

(1)Sort tasks in a listdlby descending order ofranku;

(2)computeR′max(G),R′pre(ni);

(3)R′left←0;

(4)fortindldo

(5)r_list←Null

(6)foreachukinUdo

(7)foreachf(k,h) in [f(k,max),f(k,low)]do

(8) ComputeE,R,SL;

(9) Add item tor_list;

(10) Sort ther_listby descending order ofFse;

(11)assign_list←Null;

(12)tmp_list←Null;

(13)energy_used←∞;

(14)R′goal(ni)←R′goal(ni)+Rleft;

(15) Get current node info;

(16)foreacheleminr_listdo

(17)ifprocess ofelemintmp_listthen

(18) Remove item that has the same process aselemfrom tmp_list;

(19) Add elem to tmp_list;

(20) ComputeR′(ni);

(21)ifR′(ni)≥R′goal(ni)then

(22) ComputeE(ni);

(23)ifE(ni)

(24)assign_list=tmp_list;

(25)energy_used=E(ni);

(26) Update task AFT;

(27)R′left←R′goal(ni)-R′(ni);

(28)returnE(G),R′(G),SL(G);

算法第(1)行對(duì)應(yīng)用G按照rank值按降序進(jìn)行排序，第(2)行進(jìn)行預(yù)分配可靠性計(jì)算，第(4)～(26)行對(duì)排序后的所有任務(wù)進(jìn)行調(diào)度，第(5)～(9)行計(jì)算每一個(gè)處理的每一個(gè)頻率點(diǎn)所產(chǎn)生能量、可靠性和調(diào)度長度，并將其添加入列表。第(10)～(15)對(duì)變量進(jìn)行初始化操作，第(16)～(26)行，遍歷先前步驟產(chǎn)生的列表，為了避免同一處理器被分配兩次，第(17)行進(jìn)行判斷，然后從中選擇出滿足可靠性目標(biāo)的處理器集，并進(jìn)行能量消耗優(yōu)化和臨時(shí)數(shù)值結(jié)果的參數(shù)更新。第(27)行對(duì)中間可靠性數(shù)值進(jìn)行更新。

算法復(fù)雜度分析：①第(4)～(26)行遍歷所有任務(wù)，算法復(fù)雜度為O(|N|)。 ②第(6)～(9)行遍歷所有處理器和其對(duì)應(yīng)的頻率點(diǎn)為O(|U|2×|F|2)， 第(10)行對(duì)其進(jìn)行排序?yàn)椋篛(|U|2×|F|2log2(|U|2×|F|2))。 ③第(15)行會(huì)尋找最晚開始的父節(jié)點(diǎn)的AFT，復(fù)雜度為O(|N|)。 ④第(16)～(26)行遍歷容量為 |U|2×|F|2的列表，并且訪問當(dāng)前處理節(jié)點(diǎn)的父節(jié)點(diǎn)任務(wù)的AFT，算法復(fù)雜度為：O(|U|2×|F|2)。 ②、③、④為并列結(jié)構(gòu)，①嵌套了②、③和④，并且②的復(fù)雜度高于④，因此整個(gè)算法的復(fù)雜度為：O(T)， 其中T=max(|N|×|U|2×|F|2log2(|U|2×|F|2)，|N|2)。

3 性能評(píng)估

3.1 測(cè)試環(huán)境

為確保測(cè)試環(huán)境的公平性，所有算法均運(yùn)行于同一測(cè)試環(huán)境下，本次測(cè)試使用的環(huán)境為：操作系統(tǒng)為ubuntu20 LTS，處理器10th Gen Intel(R)Core(TM)i9-10900，內(nèi)存64 GB，使用C++編程語言用于仿真。為了使結(jié)果更加穩(wěn)定和可靠，測(cè)得多次(20次)結(jié)果，去掉最大和最小值，取平均值作為最終結(jié)果。

3.2 仿真參數(shù)設(shè)置

仿真參數(shù)的設(shè)置對(duì)結(jié)果至關(guān)重要，因此我們所使用的仿真參數(shù)參考了先前工作所使用的參數(shù)[15]，具體的系統(tǒng)參數(shù)如下：

(1)任務(wù)參數(shù)：設(shè)置任務(wù)ni的w值為 10≤w≤100，任務(wù)ni到任務(wù)nj的通信時(shí)間為c(i，j)為10 ms≤c(i，j)≤100 ms。

(2)處理器參數(shù)：0.03≤Pind≤0.07，0.8≤Cef≤1.2，2.5≤mk≤3，0.3≤f≤1.0， 頻率的精度為0.01 GHz。

(3)可靠性參數(shù)：處理器處于最大頻率時(shí)的瞬時(shí)故障率為0.00001≤λ≤0.00009。

(4)將權(quán)重因子α設(shè)為0.5。

3.3 評(píng)價(jià)指標(biāo)

對(duì)算法的評(píng)價(jià)指標(biāo)有：能量消耗和調(diào)度長度，能量消耗越小代表算法越節(jié)能，調(diào)度長度反應(yīng)了任務(wù)完成的時(shí)間，越短處理器所需時(shí)間越少，算法的性能越好，兩個(gè)指標(biāo)都能對(duì)算法性能進(jìn)行直接反應(yīng)。

分布式系統(tǒng)和嵌入式系統(tǒng)中一些常用的基于DAG的并行應(yīng)用程序，如高斯消元和傅立葉變換，這兩種并行應(yīng)用程序?qū)⒂糜诖舜蔚姆抡骝?yàn)證中，其具體細(xì)節(jié)介紹如下：

傅里葉變換應(yīng)用：參數(shù)ρ用于描述傅里葉變換應(yīng)用的大小，任務(wù)總數(shù)為N=2×ρ-1+ρ×log2ρ， 其中ρ=2y，y為正整數(shù)，圖2所展示的是ρ=4時(shí)的傅里葉變換。

圖2 傅里葉變換ρ=4

高斯消除應(yīng)用：是帶有優(yōu)先級(jí)限制的并行程序應(yīng)用，應(yīng)用程序中的任務(wù)量為：N=(ρ2+ρ-2)/2， 使用參數(shù)ρ來表示高斯消除應(yīng)用程序的大小，圖3所展示的是ρ=5時(shí)的高斯消除應(yīng)用例子。

圖3 高斯消除ρ=5

3.4 仿真結(jié)果

仿真中所使用的應(yīng)用G，是按照先前的參數(shù)設(shè)置，隨機(jī)產(chǎn)生，每一次隨機(jī)產(chǎn)生的G，都作為一個(gè)樣本，將其輸入到算法中，運(yùn)行算法得到相應(yīng)的仿真結(jié)果。在以下仿真中，將可靠性目標(biāo)設(shè)置為0.98，比較各算法在不同規(guī)模下，每種算法所消耗的能量和調(diào)度的長度。在對(duì)傅里葉變換應(yīng)用仿真時(shí)，ρ的取值分別為：16，32，64，128時(shí)，任務(wù)數(shù)量為：95，223，511，1151，在此條件下：圖4為能量的消耗，圖5為調(diào)度長度。從圖4中可以看出，各算法隨著任務(wù)數(shù)量的上升，能量也隨之增大，增長趨勢(shì)為呈線性增長趨勢(shì)，在任務(wù)數(shù)量達(dá)到1151時(shí)，兩種沒有使用復(fù)制機(jī)制的算法：ESRG和DERG算法，以無法完成調(diào)度任務(wù)，與之不同的是，EFSRG和SAWR則成功完成調(diào)度任務(wù)。從能量消耗的數(shù)值來看，使用復(fù)制機(jī)制的算法，在任務(wù)規(guī)模較小時(shí)，能量消耗較高，但隨著規(guī)模不斷加大，能量消耗會(huì)比不使用復(fù)制機(jī)制的算法低，SAWR算法在任務(wù)數(shù)量大于223時(shí)，消耗的能量最少。對(duì)于上述現(xiàn)象的一個(gè)解釋是：在任務(wù)規(guī)模較小時(shí)，每個(gè)任務(wù)要取得的可靠性目標(biāo)較小，復(fù)制機(jī)制在這種情況下，傾向與將任務(wù)進(jìn)行復(fù)制，為此將耗費(fèi)更多的能量，但是，當(dāng)任務(wù)規(guī)模較大時(shí)，任務(wù)雖然依舊被復(fù)制，但運(yùn)行與較低的頻率，與任務(wù)運(yùn)行在單個(gè)高頻率的處理器上相比，能量消耗較少。另一個(gè)需要說明的問題是，同樣基于復(fù)制機(jī)制，為什么SAWR的能量消耗會(huì)小于EFSRG，對(duì)此一個(gè)可靠的解釋為：在復(fù)制機(jī)制的基礎(chǔ)上，添加了權(quán)重信息，這個(gè)應(yīng)用的能量更趨于平均，很好避免了需要大量計(jì)算量的任務(wù)使用多能量，小型任務(wù)使用少能量，對(duì)能量進(jìn)行均衡，可靠性分配也更為合理，除此以外，添加的平衡系數(shù)也為尋找更小的能量消耗提供信息，綜合兩方面，最終的結(jié)果好于EFSRG算法。圖5為算法的調(diào)度長度，從圖中可以看到調(diào)度長度隨著規(guī)模不斷加大，調(diào)度長度也隨著增大，使用了復(fù)制機(jī)制的算法，其調(diào)度長度相較于不使用的較長，長度多了10%～30%之間。這個(gè)問題是一個(gè)比較好的解釋是：復(fù)制機(jī)制會(huì)使得頻率降低，從而使得任務(wù)處理較慢，每一次復(fù)制，任務(wù)的完成時(shí)間取決于最慢的那個(gè)處理器，因此，相較于使用單個(gè)高頻處理器的情形，調(diào)度長度會(huì)加大。相較與ESFRG算法，SAWR在規(guī)模較小時(shí)，調(diào)度長度高于 EFSRG，隨著規(guī)模增大，調(diào)度長度比EFSRG的短，這個(gè)現(xiàn)象的解釋可以從前面的解釋中獲得啟發(fā)，相較與EFSRG而言，SAWR會(huì)更為平均，而調(diào)度任務(wù)的約束則取決于最慢的那一個(gè)，更為平均相較于一個(gè)快和一個(gè)慢而言，將取得更為短的調(diào)度長度。

圖4 各算法能量消耗在可靠性為0.98的傅里葉變換

圖5 各算法調(diào)度長度在可靠性為0.98的傅里葉變換

圖6和圖7分別為可靠性為0.98時(shí)，在高斯消除應(yīng)用下，各算法的能量消耗和調(diào)度長度，規(guī)模參數(shù)ρ的設(shè)置為：24、32、40、48，對(duì)應(yīng)的任務(wù)數(shù)量為：299、527、819、1175。從圖6中可以看出，在任務(wù)數(shù)量為819時(shí)，不使用復(fù)制機(jī)制的調(diào)度算法以不能完成調(diào)度任務(wù)，對(duì)比圖4，當(dāng)兩種不同類型的應(yīng)用程序，在任務(wù)數(shù)量接近時(shí)，所消耗的能量接近，可以得到一個(gè)猜想及：能量的消耗與并行程序的類型無關(guān)，與任務(wù)數(shù)量規(guī)模有關(guān)，按照這個(gè)猜想，可以猜測(cè)當(dāng)任務(wù)數(shù)量大于511，小于等于819時(shí)，不使用復(fù)制機(jī)制的算法就存在不能完成調(diào)度任務(wù)情況。圖7展示的調(diào)度長度情況，所展現(xiàn)的情況與圖5所展示的現(xiàn)象基本一致，這里將不再贅述其原因。

圖6 各算法能量消耗在可靠性為0.98的高斯消除

圖7 各算法調(diào)度長度在可靠性為0.98的高斯消除

在仿真參數(shù)的設(shè)置中，一個(gè)重要的參數(shù)α還沒有進(jìn)行研究，為此將探究α對(duì)能量消耗的影響。將參數(shù)α設(shè)置為從0到1，每次增加0.2，在ρ為128的傅里葉變換和在ρ為48的高斯消除下，將可靠性目標(biāo)設(shè)置為0.98，進(jìn)行仿真驗(yàn)證，所得的結(jié)果如圖8所示。

圖8 不同的α對(duì)能量消耗的影響

從圖8中可以看出，α值會(huì)導(dǎo)致最終的能量消耗結(jié)果發(fā)生震蕩，綜合兩種應(yīng)用的結(jié)果來看，α在取0.5的附近時(shí)，所取得的結(jié)果較為合適，對(duì)于這種情況的出現(xiàn)，一個(gè)比較合理的解釋是，α值將影響能量消耗較少的還是調(diào)度長度較短的處理器的優(yōu)先選擇，為一種啟發(fā)示的貪心算法，從而進(jìn)入局部最優(yōu)解而無法得到全局最優(yōu)解，因而造成所得到的結(jié)果出現(xiàn)震蕩情況。

4 結(jié)束語

在本文中，我們提出了SAWR分配算法，用于提高異構(gòu)系統(tǒng)上基于DAG的并行應(yīng)用程序的可靠性并降低能量消耗。這種方法首先將調(diào)度任務(wù)分為兩個(gè)子任務(wù)來處理：任務(wù)的可靠性劃分和減少任務(wù)的能量消耗。SAWR在使用復(fù)制機(jī)制使得高可靠性目標(biāo)的調(diào)度能夠完成，并加入了權(quán)重機(jī)制使得能量分配更為平均，從而降低能量的消耗。仿真結(jié)果表明，與現(xiàn)有方法相比，我們提出的方法能有效降低能耗。未來將進(jìn)一步探索在云計(jì)算環(huán)境中進(jìn)行拓展，并對(duì)提出的猜想進(jìn)行探索和驗(yàn)證。