并行任務可靠性約束下的資源最小化調度

徐洪智 李仁發(fā) 曾理寧

1(湖南大學信息科學與工程學院 長沙 410082) 2(吉首大學軟件學院 湖南張家界 427000) (xuhongzhi9@163.com)

近年來，嵌入式系統(tǒng)，特別是信息物理融合系統(tǒng)(cyber-physical system, CPS)[1]已在智能交通、智能電網、智能家居、醫(yī)療保健、航空航天、大型建筑狀態(tài)監(jiān)控等眾多領域得到廣泛應用[2-4].這些系統(tǒng)普遍具有異構特征，它們利用高速網絡將不同的處理器單元互聯(lián)執(zhí)行并行應用程序.從系統(tǒng)設計的角度看，并行程序由具有先后約束關系的任務構成，通常被表示成有向無環(huán)圖(directed acyclic graph, DAG)，程序運行時將各任務按一定的邏輯次序分配到相應的處理器執(zhí)行.以往基于異構系統(tǒng)調度DAG的研究基本都是為了縮短調度長度，而對于很多嵌入式系統(tǒng)而言，可靠性是系統(tǒng)的一項重要質量指標，尤其在安全關鍵的實時系統(tǒng)設計中極其重要，可靠性目標必須被滿足.可靠性是系統(tǒng)正確運行的概率，由于系統(tǒng)硬件自身原因、外部電磁干擾等，系統(tǒng)在運行時可能會發(fā)生錯誤，影響系統(tǒng)的可靠性[5-7].為提高系統(tǒng)可靠性，一般通過資源冗余的方式容忍系統(tǒng)運行過程中發(fā)生的錯誤，如將任務復制到不同的處理器上執(zhí)行或當任務發(fā)生錯誤后重新執(zhí)行[8].

對于很多嵌入式系統(tǒng)而言，系統(tǒng)資源往往是有限的，如有許多系統(tǒng)可能工作于能量受限的環(huán)境，能耗過高將會影響電池或系統(tǒng)的壽命[9-10].一般地，當我們應用資源冗余的方式提高系統(tǒng)可靠性時會消耗更多的系統(tǒng)資源，而過多限制資源的使用則會降低系統(tǒng)的可靠性.因此，在系統(tǒng)設計時需要權衡可靠性與資源消耗的問題，在滿足系統(tǒng)可靠性目標的前提下盡量節(jié)省系統(tǒng)資源.基于這些分析，本文主要研究異構系統(tǒng)執(zhí)行并行任務，在給定系統(tǒng)可靠性目標的情況下如何盡量節(jié)省系統(tǒng)資源，主要貢獻包括4方面：

1) 將應用系統(tǒng)的可靠性目標轉換為單個任務的可靠性目標，分別給出了任務非復制和任務復制情況下單個任務可靠性目標的計算方法；

2) 設計了一個任務非復制的可靠性約束下資源最小化算法，當給出的系統(tǒng)可靠性目標不大于系統(tǒng)可達到的最大可靠性時，該算法能將任務分配到合適的處理器并使可靠性達到目標要求；

3) 由于任務非復制算法不能滿足系統(tǒng)更高可靠性要求，設計了2個可靠性目標約束下最小化資源的啟發(fā)式算法；

4) 分別應用隨機任務和實際任務對算法進行模擬仿真，驗證了本文算法的有效性.

1 相關工作

基于異構系統(tǒng)的并行任務調度，經典的算法如異構最早完成時間(heterogeneous earliest finish time, HEFT)算法[11]、關鍵路徑(critical-path-on-a-processor, CPOP)算法[11]等，基于這些算法人們提出了一些新的算法，如雙螺旋結構遺傳算法(double-helix structure genetic algorithm, DHSGA)[12]等，這類算法的目的是盡量縮短調度長度.另有一些學者研究了調度過程中系統(tǒng)資源利用的問題，如Qiu等人[13]研究了異構系統(tǒng)任務分配時在滿足軟/硬時間約束下的資源最小化問題.Huang等人[14]研究了異構系統(tǒng)調度隨機到達的任務時能量資源利用的問題，提出一種基于拉格朗日理論的功率分配和負載均衡策略.Xie等人[15]基于異構系統(tǒng)調度先后約束關系的任務，在滿足任務截止期限的情況下最小化系統(tǒng)能耗.這些研究沒有考慮系統(tǒng)的可靠性問題.

目前，有許多學者研究了系統(tǒng)能量資源消耗與可靠性問題.如針對單處理器系統(tǒng)，Zhu等人[6]基于搶占最早截止期限優(yōu)先(earliest deadline first, EDF)策略分別研究了實時周期性任務靜態(tài)和動態(tài)可靠性感知功耗管理(reliability-aware power management, RA-PM)問題，證明了靜態(tài)RA-PM是NP難問題.同時Zhu還在文獻[7]中假設任務松弛時間不小于任務最壞計算時間的情況下，利用松弛時間調低任務的執(zhí)行電壓實現(xiàn)節(jié)能.為了使長任務能夠利用松弛時間，他們引入了程序檢查點(checkpoint)技術，將長任務分解為小的任務段，然后利用松弛時間節(jié)能并保證任務的可靠性.Lin等人[16]在保證系統(tǒng)可靠性的同時通過調節(jié)處理器的速度和關閉處理器節(jié)省能耗.Li等人[17]基于幀的實時任務集在保證系統(tǒng)可靠性的前提下使能耗最小化.Zhao等人[18]基于單處理器系統(tǒng)調度有約束關系的任務，在給定能量預算的前提下使系統(tǒng)的可靠性最大化.文獻[19]針對有截止期限要求的DAG任務，應用共享恢復(shared recovery)技術保證系統(tǒng)的可靠性并降低能耗.

近年來，由于多處理器系統(tǒng)在各個領域的廣泛應用，有很多學者研究了異構系統(tǒng)調度DAG任務的可靠性與資源消耗的問題，如MaxRe算法[20]和RR[21]算法分別應用任務復制的方法保證系統(tǒng)的可靠性.Zhang等人[22]基于異構多處理器系統(tǒng)調度DAG，提出能量約束下的可靠性最大化算法，該算法包括任務優(yōu)先級的確定、頻率選擇和處理器分配3個階段，用以權衡系統(tǒng)的可靠性與能耗.Yi等人[23]針對異構多處理器系統(tǒng)可靠性保證與時間約束下的任務調度問題，首先在多項式時間內求解簡單路徑和樹結構(simple-path and tree-structured)任務圖問題，進而應用整數(shù)線性規(guī)劃求解DAG調度問題，然后提出DAG_Heu算法求近似最優(yōu)解.Xie等人[24]基于異構計算系統(tǒng)提出滿足可靠性目標并最小化系統(tǒng)代價的算法，但該文沒有應用任務復制技術進一步提高系統(tǒng)的可靠性.文獻[25]基于能量收集系統(tǒng)(energy harvesting)供電的多核嵌入式系統(tǒng)，綜合考慮任務執(zhí)行時間、瞬時錯誤和永久錯誤，利用調度窗口能量預算對任務進行調度.文獻[26]基于多核平臺調度周期任務，通過調整每個任務復制的數(shù)量和執(zhí)行頻率滿足系統(tǒng)可靠性要求并盡量節(jié)能.本文研究異構系統(tǒng)執(zhí)行DAG任務，考慮處理器資源和網絡資源消耗，在滿足系統(tǒng)可靠性目標的前提下盡量節(jié)省系統(tǒng)資源.

2 系統(tǒng)模型與問題定義

2.1 應用程序模型

本文研究并行應用程序運行于異構多處理器系統(tǒng)，處理器節(jié)點用集合PN={pn1，pn2,…,pnm}表示，其中m為處理器節(jié)點數(shù).假定每個處理器節(jié)點的處理能力不同，這些處理器節(jié)點通過網絡進行連接.將運行于處理器節(jié)點上的應用程序表示為有向無環(huán)圖DAGG=(T,C)[11]，現(xiàn)對T,C描述如下：

T表示G中的任務(DAG中的頂點)，任務ti∈T，其中1≤i≤n.因為任務執(zhí)行過程中具有先后約束關系，用C表示任務間的先后約束關系及通信時間(DAG中的邊)，ci,j∈C表示任務ti與任務tj之間存在先后約束關系，任務tj必須在任務ti執(zhí)行完之后才能執(zhí)行，ci,j的值表示任務tj與任務ti不在同一個處理器上執(zhí)行時的通信時間.若任務tj與任務ti在同一個處理器上執(zhí)行，則ci,j=0.

一個經典的DAG如圖1所示[11,15,24,28]，c1,2∈C表示任務t2必須在任務t1之后執(zhí)行；c1,2=18表示任務t2與任務t1不在同一個處理器上執(zhí)行時，從任務t1所在的處理器傳輸數(shù)據(jù)到任務t2所在的處理器需要的時間為18；如果任務t2與任務t1在同一個處理器上執(zhí)行，則傳輸數(shù)據(jù)的時間為0.定義parent(ti)表示任務ti的直接前驅任務集，child(ti)表示任務ti的直接后繼任務集，將沒有前驅任務的任務稱為tentry，將沒有后繼任務的任務稱為texit.如果G中有多個tentry或texit，我們可以構造不需要實際執(zhí)行的虛擬任務表示tentry或texit.因為處理器異構，任務ti在每個處理器上的最壞執(zhí)行時間(worst-case execution time, WCET)可能不同，定義一個n行m列的矩陣W=(wi,j)表示G中的任務在各個處理器上的執(zhí)行時間，wi,j表示任務ti在處理器pnj上執(zhí)行時的WCET.圖1中的任務在3個處理器上的WCET如表1所示，任務t1在3個處理器上執(zhí)行的最壞時間分別為14，16和9個單位時間.

Fig. 1 Example of a DAG with ten tasks圖1 10個任務的DAG圖

Taskpn1pn2pn3t114169t2131918t3111319t413817t5121310t613169t771511t851114t9181220t1021716

2.2 資源消耗模型

根據(jù)文獻[24,27]，系統(tǒng)資源消耗與任務執(zhí)行時間成比例關系，如果一個任務的執(zhí)行時間為et，則消耗的資源為rcr×et，其中rcr為單位時間的資源消耗率.因為不同處理器的資源消耗率可能不同，因此，定義集合RCRP={rcrp1,rcrp2,…,rcrpm}表示系統(tǒng)中各處理器單位時間的資源消耗率，其中rcrpi表示處理器pni單位時間的資源消耗率.根據(jù)資源消耗關系，如果G中的任務ti在處理器pnj上執(zhí)行，消耗的處理器資源可表示為

Costpro(ti,pnj)=rcrpj×wi,j.

(1)

考慮到G中具有先后約束關系的任務可能在不同的處理器上執(zhí)行，任務之間存在通信，同樣，設通信過程中消耗的資源與通信時間成比例關系，因此定義處理器之間單位時間的通信消耗率為rcrc.若將任務ti分配給處理器pnj，消耗的通信資源與ti的父任務tx是否在pnj上執(zhí)行有關，可表示為

(2)

根據(jù)式(1)(2)可知，將任務ti分配給處理器pnj，消耗的處理器資源與通信資源之和為

Cost(ti,pnj)=Costpro(ti,pnj)+
Costcom(ti,pnj).

(3)

2.3 錯誤模型

系統(tǒng)運行過程中出現(xiàn)的錯誤一般分為瞬時錯誤和永久錯誤，而瞬時錯誤更加常見[5-7,16,22,24,26]，所以類似于這些研究，本文只考慮瞬時錯誤.系統(tǒng)的可靠性是系統(tǒng)正確運行的概率，如果系統(tǒng)運行時出現(xiàn)的瞬時錯誤服從泊松分布，處理器執(zhí)行任務時的可靠性表示為R(t)=e-λ t，其中λ是處理器執(zhí)行單位時間的平均錯誤率.由于處理器系統(tǒng)異構，不同的處理器的λ值可能不同，因此，定義λj表示處理器pnj執(zhí)行單位時間的平均錯誤率，這時G中的任務ti在處理器pnj上執(zhí)行，其可靠性表示為

R(ti,pnj)=e-λj×wi,j.

(4)

2.4 系統(tǒng)資源消耗與可靠性計算

本文主要研究任務非復制和復制2種情況下滿足系統(tǒng)可靠性目標并最小化資源消耗的問題.現(xiàn)對系統(tǒng)資源消耗與可靠性的計算方法分析如下.

根據(jù)2.2節(jié)和2.3節(jié)所述，如果將任務ti分配到處理器pnj上執(zhí)行，其可靠性為R(ti,pnj)，發(fā)生錯誤的概率為1-R(ti,pnj).如果將任務ti及其復制版本分配到多個處理器上執(zhí)行并將這些處理器組成一個集合Replica(ti)，這時任務ti的可靠性及消耗的資源可分別表示為

(5)

和

(6)

類似于文獻[22,24]，本文假定網絡傳輸是可靠的，即不考慮網絡通信過程中的錯誤.當G中所有的任務分配并執(zhí)行完后，系統(tǒng)的可靠性及消耗的資源總量可分別表示為

(7)

和

(8)

2.5 問題定義

給定一個異構多處理器系統(tǒng)和DAG任務G，本文定義的問題是：如果給出系統(tǒng)的可靠性目標為Rgoal(G)，怎樣將G中的任務分配到合適的處理器使系統(tǒng)可靠性R(G) ≥Rgoal(G)，并且使系統(tǒng)資源Cost(G)盡可能小，該問題形式化描述如下：

其中，n為G中的任務數(shù).

3 調度分析

3.1 任務優(yōu)先級

調度過程中必須保證任務執(zhí)行的先后次序，前驅任務先執(zhí)行，后繼任務后執(zhí)行，為了滿足這個條件，本文使用Rank的概念生成任務的拓撲次序[11,15,22,24,28]，Rank定義如下：

(9)

Table 2 Rank Value of the Tasks in Fig.1表2 圖1各個任務的Rank值

3.2 任務最早完成時間

一個任務的最早完成時間依賴于其開始時間，在DAG調度中，如果將任務ti分配到處理器pnj，則任務ti必須等所有的前驅任務parent(ti)執(zhí)行完并將相關數(shù)據(jù)傳送到所在的處理器才能開始執(zhí)行.因此，任務ti的最早開始時間(earliest start time,EST)和最早完成時間(earliest finish time,EFT)可分別表示為

(10)

和

EFT(tx,pny)=EST(tx,pny)+wx,y.

(11)

3.3 任務可靠性目標的確定

在滿足任務的先后約束關系之后，調度過程中還要保證系統(tǒng)的可靠性目標被滿足.直觀地看，系統(tǒng)的可靠性由G中的n個任務的可靠性決定，所以類似于文獻[20-21,24].當進行任務調度時，先確定單個任務的可靠性目標，然后再將任務分配到滿足可靠性要求的處理器.如果給出的可靠性目標Rgoal(G)小于或等于任務非復制情況下系統(tǒng)可達到的最大可靠性，則不需要進行任務復制，否則需要進行任務復制才能使系統(tǒng)達到可靠性目標要求.以下分任務非復制和復制的情況進行討論.

3.3.1 非復制情況下任務的可靠性目標

我們先分析系統(tǒng)可達到的最高可靠性.如果將任務ti分配到可靠性最高的處理器上執(zhí)行，則其可靠性為

(12)

當G中所有的任務都選擇可靠性最高的處理器執(zhí)行，系統(tǒng)的可靠性將最高，可表示為

(13)

如果不進行任務復制，當給出的系統(tǒng)可靠性目標要求Rgoal(G) ≤Rmax_nonrep(G)時，本文將系統(tǒng)的可靠性目標轉換為單個任務的可靠性目標.

對于G中的任務，雖然處理器異構，但任務本身的計算量也存在差異，計算量大的任務在各個處理器上的執(zhí)行時間會相對較長，計算量小的任務在各個處理器上的執(zhí)行時間會短一些.從式(4)可知，單個任務的可靠性與執(zhí)行時間有關，執(zhí)行時間越長可靠性將越低.所以本文用任務的平均最壞執(zhí)行時間為參考預確定任務的可靠性目標.因此，定義總參考時間(total reference time,TRT)為

(14)

由于不進行任務復制，給任務ti預確定的可靠性目標不能大于Rmax_nonrep(ti)，否則將找不到合適的處理器執(zhí)行任務ti.所以，我們先算出系統(tǒng)可靠性目標與系統(tǒng)最大可靠性的比值GRM，用GRM做參考計算任務ti預確定的可靠性目標.GRM表示為

(15)

因為給出的可靠性目標Rgoal(G)≤Rmax_nonrep(G)，所以GRM(G)≤1.現(xiàn)在任務ti的可靠性目標可預確定為

(16)

因為GRM(G)≤1，所以RG RM(ti)≤Rmax_nonrep(ti).如果任務被分配之前已按Rank值拓撲排序，任務執(zhí)行的序號為1,2,…,n，設在調度過程中已經分配完的任務為{t1,t2,…,ti-1}，沒有被分配的任務為{ti+1,ti+2,…,tn}，當前準備分配的任務為ti，這時給任務ti預確定的可靠性目標為

(17)

當把G中的任意一個任務ti分配到處理器時，只要ti的可靠性大于等于式(17)中的Rpgoal(ti)，即可使系統(tǒng)的可靠性達到目標要求.

定理1. 在非復制的情況下，當給出的可靠性目標Rgoal(G)≤Rmax_nonrep(G)時，應用式(16)(17)對任務的可靠性目標進行預確定，在調度時每個任務總能分配到合適的處理器并且使系統(tǒng)滿足可靠性目標要求.

證明. 應用數(shù)學歸納法進行證明.

1) 當分配第1個任務，即i=1時，根據(jù)式(17)，第1個任務的可靠性目標為

(18)

所以能找到合適的處理分配第1個任務，當將第1個任務分配到處理器后，其實際可靠性為

(19)

余下的任務按式(16)預確定可靠性，則系統(tǒng)的可靠性為

(20)

所以當i=1時，定理1成立.

2) 假設分配完第k個任務后，定理1仍然成立，即

(21)

3) 如果第k+1個任務時按式(17)分配，則第k+1個任務預確定的可靠性目標為

(22)

根據(jù)式(21)可知

(23)

將式(23)帶入式(22)，得

(24)

所以能找到合適的處理器分配第k+1個任務，當?shù)趉+1個任務分配到處理器后，第k+1個任務的實際可靠性為

(25)

這時系統(tǒng)的可靠性為

(26)

根據(jù)以上步驟，可知定理1成立.

證畢.

3.3.2 復制情況下任務的可靠性目標

如果給出的系統(tǒng)可靠性目標大于Rmax_nonrep(G)，則需要應用任務復制技術才能達到系統(tǒng)可靠性目標要求.進行任務復制可提高單個任務的可靠性從而提高整個系統(tǒng)的可靠性，但在調度過程中仍然需要確定每個任務的可靠性目標才能確定復制哪些任務.因為式(17)中的單個任務的可靠性目標是基于式(15)的GRM(G)≤1設計的，如果給出的Rgoal(G)>Rmax_nonrep(G)，式(17)計算任務可靠性目標的方法將不再適應.因此，對于任務復制的情況，需要重新給每個任務分配可靠性目標，受式(4)結果的影響，平均執(zhí)行時間長的任務預確定的可靠性目標應該相對低一些.所以本文直接根據(jù)任務ti的平均最壞執(zhí)行時間在TRT(G)中所占的份額確定任務ti的可靠性目標，因此，給任務ti預確定的可靠性目標Rreplica(ti)計算為

(27)

在進行任務調度時，當前任務ti的可靠性目標為

(28)

4 資源最小化算法

4.1 資源最小化非復制算法

根據(jù)3.1節(jié)中任務Rank值的計算方法，首先可以算出G中各任務的優(yōu)先級，然后根據(jù)優(yōu)先級次序將任務分配到合適的處理器上執(zhí)行.對于任意一個任務ti，先根據(jù)3.3節(jié)中介紹的方法算出該任務的可靠性目標，然后將它分配到滿足可靠性目標要求并且資源消耗最小的處理器上執(zhí)行.因此，設計一個可靠性約束下的資源最小化算法(minimizing resource consumption with reliability goal, MRC).

算法1. MRC算法.

輸入：PN={pn1，pn2,…,pnm}，G，Rgoal(G)；

輸出：R(G)，Cost(G).

① 遍歷G，計算Rank；

② 將任務根據(jù)Rank非增排列至隊列ReadyQ；

③ whileReadyQ≠?

④ti=ReadyQ.out()；

⑤ 根據(jù)式(17)計算Rpgoal(ti)；

⑥cost=∞；*cost為臨時變量*

⑦ for each processorpnj∈PNdo

⑧ ifR(ti,pnj)≥Rpgoal(ti) then

⑨res=Cost(ti,pnj)；*式(3)*

⑩ ifcost>resthen

算法1首先遍歷G計算Rank，并將任務按Rank非增排列至隊列ReadyQ.行③～while循環(huán)為任務調度過程，將每個任務分配到合適的處理器.對于任意一個任務ti，首先計算可靠性目標(行⑤)，然后遍歷處理器(行⑦～)，尋找滿足可靠性要求且資源消耗最小的處理器pnj，然后將ti分配給pnj(行).行～分別計算系統(tǒng)的實際可靠性和消耗的資源總量.

算法1的時間復雜度主要由行③⑦⑨決定.其中，行③遍歷G中所有任務，時間復雜度為O(n)；行⑦遍歷所有處理器，時間復雜度為O(m)；行⑨需要訪問任務ti和所有前驅任務之間的通信邊，時間復雜度為O(ei)，其中ei為任務ti的前驅任務數(shù).所以算法1在調度過程中的時間復雜度為O(n×m×ei)=O(m×e)，其中e為DAG中的邊數(shù).如果DAG為稠密圖，一個任務的前驅任務數(shù)接近于任務總數(shù)，則算法1的時間復雜度為O(n2×m).所以，算法1的時間復雜度與經典算法HEFT[11]的時間復雜度相同.

4.2 MRC算法(算法1)示例

應用文獻[24]中的參數(shù)，將圖1中3個處理器的參數(shù)設置如表3，單位時間通信資源消耗率rcrc=1，可算出系統(tǒng)最大可靠性為0.974 335，如果將可靠性目標設為0.95，應用MRC進行調度，結果如表4所示.

Table 3 Parameters of Three Processors表3 3個處理器參數(shù)表

Table 4 Processor Assignments for Tasks Using MRC表4 MRC調度結果

從表4可知，算法1的調度長度為96，系統(tǒng)可靠性為0.958 773 9，超過可靠性目標要求，消耗的資源為791，優(yōu)于文獻 [24]中的結果.因為算法1只能將單個任務調度到一個處理器上執(zhí)行，如果給出的系統(tǒng)可靠性目標超過Rmax_nonrep(G)，即使將每個任務都分配到可靠性最高的處理器仍然不能使系統(tǒng)達到可靠性目標要求.因此，4.3節(jié)我們應用任務復制技術提高系統(tǒng)的可靠性.

4.3 基于復制的調度算法

因為本文主要關注系統(tǒng)設計階段，所以運用嚴格的調度技術[29]，即一個任務只有等它的前驅任務及其所有復制都執(zhí)行完后才可以開始執(zhí)行，所以先將任務ti的前驅任務的最早完成時間(earliest finish time of predecessors,EFTP)表示為

(29)

式(29)表示任務ti的所有前驅任務的所有復制的最遲完成時間，這時任務ti的一個復制在處理器pnj上的最早開始時間可表示為

(30)

在調度過程中，首先根據(jù)式(27)(28)算出任務ti的可靠性目標，然后應用基于復制的調度技術從處理器集合中選擇多個處理器執(zhí)行任務ti并且使資源消耗最小化，設計一個可靠性約束下資源最小化的復制調度算法(minimizing resource consump-tion with reliability goal using replication technique, MRCR).

算法2. MRCR算法.

輸入：PN={pn1，pn2,…,pnm}，G，Rgoal(G)；

輸出：R(G)，Cost(G).

① 遍歷G，計算Rank；

② 將任務根據(jù)Rank非增排列至隊列ReadyQ；

③ whileReadyQ≠?

④ti=ReadyQ.out()；

⑤ 根據(jù)式(28)計算Rpgoal(ti)；

⑥ 調用算法SelectProc計算Replica(ti)；

⑦ 將任務ti分配到Replica(ti)中的所有處理器；

⑧ end while

⑨ 根據(jù)式(7)計算R(G)；

⑩ 根據(jù)式(8)計算Cost(G).

算法2首先計算各任務的Rank值，然后將任務按Rank非增排列至隊列ReadyQ.在進行調度時，先計算任務ti的可靠性目標，然后調用算法SelectProc計算任務ti分配的處理器集合并將任務ti及其副本分配到這些處理器.

算法SelectProc從處理器集合中選擇多個處理器執(zhí)行任務ti，在滿足可靠性目標的前提下使資源消耗最小化，該問題類似于0-1背包問題，描述如下：

其中xj∈{0,1}.

該問題可應用回溯法尋找最優(yōu)解，在此不再詳述.當處理器器的數(shù)目較多時，時間復雜度很大，設計2個啟發(fā)式算法確定任務ti分配的處理器集合，這2個算法分別如算法3和算法4所示.

算法3. SelectProc1算法.

輸入：PN={pn1，pn2,…,pnm}，Rpgoal(ti)；

輸出：Replica(ti).

①k=1；

② 將處理器按執(zhí)行任務ti的可靠性降序排列至RelDown；

③pof=1-R(ti,RelDownk)；

④ whilepof>1-Rpgoal(ti) do

⑤ 將RelDownk加入Replica(ti)；

⑥ if (k++)>mthen

⑦ return；

⑧ end if

⑨pof=pof×(1-R(ti,RelDownk))；

⑩ end while

Rpgoal(ti)且資源消耗最小的處理器

RelDownj；

算法3加入一個處理器到Replica(ti)的基本思想是：如果余下的任何一個處理器加入Replica(ti)都不能滿足可靠性要求，則優(yōu)先選擇可靠性高的處理器加入Replica(ti).如果有一些處理器能夠達到可靠性要求，則優(yōu)先選擇資源消耗小的處理器加入Replica(ti).算法3中行①初始化變量k;行②將各處理器按執(zhí)行任務ti的可靠性進行降序排列至RelDown序列;行④～⑩while循環(huán)表示如果將任務ti復制到當前處理器RelDownk仍不能滿足可靠性要求，則將處理器RelDownk加入Replica(ti);行⑥～⑧表示如果將任務ti復制到所有的處理器仍不能滿足可靠性要求，則返回;行～表示將滿足可靠性要求且資源消耗最小的處理加入Replica(ti).

算法3先要計算任務ti在各處理器上執(zhí)行的可靠性，對處理器進行排序，時間復雜度為O(mlbm)；然后while循環(huán)(行④～⑩)和for循環(huán)(行～)總共要遍歷所有處理器一次，而for循環(huán)要選擇資源消耗最少的處理器，因此，行④～的時間復雜度為O(m×ei)，其中ei為任務ti的直接前驅數(shù).可知，算法3的時間復雜度為O(m×ei+mlbm).

如果算法2調用算法3，因為每個任務都要選擇處理器，所以算法2的時間復雜度為O(n×(m×ei+mlbm))，即O(m×e+n×mlbm)，其中e為DAG中的邊數(shù).

算法4. SelectProc2算法.

輸入：PN={pn1，pn2,…,pn|PN|}，Rpgoal(ti)；

輸出：Replica(ti).

①k=1；

② 將各處理器按執(zhí)行任務ti消耗的資源升序排列至CostUp；

③ 將CostUpk加入Replica(ti),調用式(5)計算R(ti)；

④ whileR(ti)

⑤ if (k++)>mthen

⑥ return；

⑦ end if

⑧ 將CostUpk加入Replica(ti),調用式(5)計算R(ti)；

⑨ end while

算法4的基本思想是依次將資源消耗最小的處理器加入Replica(ti)集合，直到滿足可靠性要求為止.算法4中行①初始化變量;行②將各處理器按執(zhí)行任務ti消耗的資源按升序排列至CostUp序列;行④～⑨while循環(huán)依次選擇資源消耗最小的處理器CostUpk加入Replica(ti);行⑤～⑦表示如果將任務ti復制到所有的處理器仍不能滿足可靠性要求，則返回.

算法4首先計算任務ti在各個處理器上消耗的資源，時間復雜度為O(m×ei)，其中ei為任務ti的直接前驅數(shù)；然后對處理器進行排序，時間復雜度為O(mlbm)；最后遍歷所有的處理器直到可靠性滿足要求，時間復雜度為O(m).基于這些分析，算法4的時間復雜度為O(m×ei+mlbm)，該復雜度與算法3的時間復雜度相同.因此，如果MRCR調用算法4，時間復雜度也為O(m×e+n×mlbm).

4.4 MRCR算法(算法2)示例

本節(jié)給出算法2示例，以下將MRCR調用算法3稱為MRCR-1，調用算法4稱為MRCR-2，調用回溯法尋找最優(yōu)處理器稱為MRCR-3.沿用4.2節(jié)中的參數(shù)調度圖1中的任務，可靠性目標設為0.98.應用MRCR-1進行調度的結果如表5所示(另外2個算法略).最后，MRCR-1消耗的資源為1 251，系統(tǒng)的可靠性為0.982 575 05；MRCR-2消耗的資源為856，系統(tǒng)的可靠性為0.987 954 83；MRCR-3消耗的資源為805，系統(tǒng)的可靠性為0.982 008 67.

Table 5 Processor Assignments for Tasks Using MRCR-1表5 MRCR-1算法的調度結果

3個算法都能滿足系統(tǒng)可靠性要求，MRCR-1算法消耗的資源最多，MRCR-3算法消耗的資源最少.從觀察3個算法選擇的處理器可知，MRCR-1算法偏向于將任務分配到處理器2和處理器3，即先選擇可靠性高的處理器，然后選擇資源消耗少的處理器；MRCR-2算法偏向于將任務復制到處理器3和處理器1，即優(yōu)先選擇資源消耗率低的處理器；MRCR-3算法選擇滿足可靠性目標的處理器組合，在3個處理器選擇中沒有明顯的傾向.

5 實 驗

5.1 實驗環(huán)境及參數(shù)

通過仿真實驗對本文提出的算法進行測評.基于Windows平臺應用C++語言編寫一個調度模擬器.將處理器和任務表示為對象并設置標識，根據(jù)實驗描述生成相應的DAG任務圖.初始化時將任務圖、處理器參數(shù)、每個任務在各處理器上的WCET分別存放至文件，保證各算法使用完全相同的數(shù)據(jù)，最后分別調用各算法將任務分配至處理器.

因為MaxRe算法[20]、RR算法[21]和MRCRG算法[24]的目標和本文類似，所以將本文算法和這些算法進行比較.現(xiàn)將這3個算法計算單個任務可靠性目標的方法簡單介紹如下：

MaxRe算法中任務ti的可靠性目標為

(31)

RR算法中任務ti的可靠性目標為

(32)

MRCRG算法中任務ti的可靠性目標為

(33)

根據(jù)文獻[5-7,24]中相關參數(shù)的取值，本文中任務參數(shù)為10≤wi,j≤100,10≤ci,j≤100；處理器資源消耗率為0.1≤rcrpi≤0.9；單位時間通信資源消耗率rcrc=0.2；錯誤參數(shù)0.000 001≤λj≤0.000 009.為了測試不同情況下各個算法的性能，我們運用一些分布式系統(tǒng)中常用的有先后約束關系的任務圖，如高斯消元應用、快速傅里葉變換[15,22,24]及隨機生成的DAG任務圖對算法進行模擬.根據(jù)文獻[24]中描述ISO 26262中損傷發(fā)生的概率級別E3(中等概率)和E2(低概率)確定系統(tǒng)的可靠性目標取值范圍為0.9～0.99.

因為MRCRG算法主要針對非復制的情況，所以我們先比較非復制的情況，用本文提出的MRC算法和MaxRe算法、RR算法及MRCRG算法進行比較，然后再比較復制的情況，用本文提出的MRCR系列算法和MaxRe算法、RR算法進行比較.

5.2 非復制情況下各算法的性能比較

Fig. 2 Gaussian elimination application with ρ=5圖2 ρ=5的高斯消元DAG

Fig. 3 Resource consumption and actual reliability of algorithms for different number of tasks圖3 任務數(shù)不同時各算法的資源消耗及可靠性

從圖3(b)可知，4個算法都能滿足可靠性要求，從消耗的資源來看MaxRe算法消耗的資源最多，RR算法次之，MRC算法消耗的資源最少.從4個算法消耗的資源總量來看，MRC算法消耗的資源是MaxRe算法的59.0%，是RR算法的63.4%，是MRCRG算法的87.9%.從圖3(a)可知，當ρ<24時，MRCRG算法與MRC算法消耗的資源沒有明顯差異，這是因為，任務數(shù)較少時系統(tǒng)能達到的最大可靠性Rmax_nonrep(G)相對更高一些，MRCRG算法與MRC算法給任務ti分配的可靠性目標相對于Rmax_nonrep(ti)更低一些，這樣2個算法可能會選擇相同的處理器執(zhí)行任務ti；當ρ>24時，任務數(shù)變多，系統(tǒng)能達到的最大可靠性相對低一些，MRCRG算法假設后面的任務的可靠性為Rmax_nonrep(ti)，而給前面的任務分配較低的可靠性，所以實際調度時后面的任務必須分配到可靠性較高的處理器，導致選擇處理器的機會相對較少，從而資源消耗較多.MRC算法根據(jù)任務平均最壞執(zhí)行時間確定任務的可靠性目標，各任務選擇處理器的機會更加均衡.而MaxRe算法給每個任務確定的可靠性目標都相同，RR算法在此基礎上有些改進，但由于系統(tǒng)異構的原因，所以效果不如MRCRG算法與MRC算法.

實驗2. 基于高斯消元應用比較可靠性目標變化時各算法的性能.本次實驗應用8個處理器，ρ=16，即任務數(shù)為135，可靠性目標從0.95增加到0.98時，4個算法消耗的資源和實際可靠性如圖4所示.

Fig. 4 Resource consumption and actual reliability of algorithms for different reliability goals圖4 可靠性目標不同時各算法的資源消耗及可靠性

從圖4可知，4個算法都能滿足可靠性目標要求，隨著可靠性目標的提高，4個算法消耗的資源都增加，相對來說，MaxRe算法消耗的資源最多，RR算法次之，MRC算法消耗的資源最少.從4個算法消耗的資源總量來看，MRC算法消耗的資源是MaxRe算法的69.7%，是RR算法的72.9%，是MRCRG算法的95.0%.該結果和實驗1的結果有一些差別，導致這種現(xiàn)象的原因是：隨著系統(tǒng)的可靠性目標的提高，當一個任務被分配時，可被選擇的處理變得越來越少，所以這些算法消耗的資源總量差異變小.

實驗3. 基于快速傅里葉變換比較應用規(guī)模變化時各算法的性能.快速傅里葉變換經常被用于分布式系統(tǒng)，為了描述任務節(jié)點總數(shù)，引入?yún)?shù)ρ，任務總數(shù)n=(2×ρ-1)+ρ×lbρ，其中ρ=2y，y為正整數(shù).圖5為一個ρ=4的具有15個任務節(jié)點的快速傅里葉變換DAG(在調度時構造一個不需要實際執(zhí)行虛擬任務表示texit).本次實驗應用8個處理器，可靠性目標設為0.95，ρ分別為8，16，32，64，即DAG中任務數(shù)分別為39，95，223，511時，4個算法的資源消耗和實際可靠性如圖6所示.

Fig. 5 D AG of fast Fourier transform application with ρ=4圖5 ρ=4的快速傅里葉變換DAG

Fig. 6 Resource consumption and actual reliability of algorithms for different number of tasks圖6 任務數(shù)不同時各算法的資源消耗及可靠性

實驗3的結果類似于實驗1和實驗2，在ρ=64之前所有算法都能滿足可靠性要求，且隨著ρ的增加各算法消耗的資源都變多，綜合來看，MRC算法消耗的資源仍然最少.

從實驗1～3可知，本文提出的算法優(yōu)于已有的3個算法，特別地，當給出的系統(tǒng)可靠性目標Rgoal(G)相對于系統(tǒng)能達到的最大可靠性Rmax_nonrep(G)更低一些的時候，本文算法在節(jié)省系統(tǒng)資源方面將具有非常明顯的優(yōu)勢.

5.3 任務復制情況下各算法的性能比較

本節(jié)比較本文提出的MRCR系列算法和MaxRe算法、RR算法的性能.

Fig. 7 Resource consumption and actual reliability of algorithms for different number of tasks圖7 任務數(shù)不同時各算法的資源消耗及可靠性

從圖7(b)可知，5個算法的實際可靠性都大于0.96，滿足系統(tǒng)可靠性要求.從圖7(a)可知，5個算法消耗的資源會隨著任務數(shù)的增加而增加.從5個算法消耗的資源總量來看，MRCR-1算法消耗的資源總量是MaxRe算法的72.6%，是RR算法的82.4%；MRCR-2算法消耗的資源總量是MaxRe算法的58.5%，是RR算法的66.4%；MRCR-3算法消耗的資源總量是MaxRe算法的57.2%，是RR算法的64.9%.5個算法中，MaxRe算法消耗的資源最多，RR算法消耗的資源次之，MRCR-3算法消耗的資源最少，這是因為MaxRe算法中單個任務的可靠性目標被設定得較高，可被選擇的處理器偏少，所以消耗了更多的資源；RR算法每次選擇可靠性大的處理器進行任務復制，所以也消耗了較多的資源；MRCR系列算法用任務的平均最壞執(zhí)行時間為參考確定任務的可靠性目標，從而單個任務的可靠性目標不會過低或過高，可被選擇的處理器數(shù)更加均衡，所以MRCR系列算法消耗的資源更少.其中，MRCR-3算法選擇滿足可靠性要求并且資源消耗最小的處理器組合，所以資源消耗最小.MRCR-1算法和MRCR-2算法消耗的資源小于MaxRe算法和RR算法，其中MRCR-2算法消耗的資源和MRCR-3算法比較接近，說明每次將任務復制到資源消耗較小的處理器能有效地節(jié)省資源.

實驗5. 主要測試DAG的并行度對算法的影響.隨機生成具有600個任務的DAG任務，應用16個處理器，a分別為0.25，0.5，1.0，2.0，4.0，每個任務的出度outdegree在[1,4]范圍內均勻分布，系統(tǒng)可靠性目標設為0.96.5個算法的資源消耗和實際可靠性如圖8所示：

Fig. 8 Resource consumption and actual reliability of algorithms for different a values圖8 任務數(shù)的并行度不同時各算法的資源消耗及可靠性

當a從0.25增加到4時，任務的并行度約從6增加到98.從圖8(b)可知，5個算法都能使系統(tǒng)滿足可靠性目標要求.從圖8(a)各算法消耗的資源看，無論任務的并行度如何變化，5個算法消耗的資源從大到小依次為MaxRe，RR，MRCR-1，MRCR-2，MRCR-3，且MRCR-2和MRCR-3消耗的資源明顯少于其他算法.

實驗6. 基于快速傅里葉變換DAG測試應用程序的規(guī)模較大時各算法的性能.設ρ=256，即DAG中任務數(shù)為2 559，應用32個處理器，可靠性目標從0.95增加到0.99，每次增加0.01.5個算法的資源消耗和實際可靠性如圖9所示：

Fig. 9 Resource consumption and actual reliability of algorithms for different reliability goals圖9 可靠性目標不同時各算法的資源消耗及可靠性

從圖9(b)可知，5個算法都能適用可靠性目標要求，除MaxRe算法之外，其余4個算法的實際可靠性更敏感地隨著可靠性目標的改變而改變，其主要原因是這4個算法對單個任務的可靠性要求相對于MaxRe算法更低一些.從圖9(a)可知，MaxRe算法和RR算法的資源消耗更多一些，MRCR系列算法消耗的資源相對少一些，MRCR-2算法消耗的資源非常接近MRCR-3算法.

由實驗1～6可知，無論是DAG的規(guī)模、并行度的變化，還是系統(tǒng)可靠性目標的變化，當不進行任務復制時，MRC算法的性能優(yōu)于其他幾個算法.當應用任務復制技術提高系統(tǒng)的可靠性時，MRCR系列算法的性能優(yōu)于已有的算法，其中MRCR-2算法消耗的資源非常接近MRCR-3算法.另外，在這6組實驗中，MRCR-2算法產生的實際可靠性略高于MRCR-3算法，說明當系統(tǒng)中處理器的數(shù)目非常多時，應用MRCR-2算法進行調度既能保證系統(tǒng)的可靠性又能有效地節(jié)省系統(tǒng)資源.

6 結 論

隨著嵌入式系統(tǒng)應用范圍的不斷擴大，出現(xiàn)了越來越多的并行應用運行于異構系統(tǒng).一方面，對于很多安全關鍵的系統(tǒng)而言，可靠性目標必須被滿足；另一方面，資源對于很多系統(tǒng)來說是昂貴的，節(jié)省資源對這些系統(tǒng)而言也十分重要.為了保證系統(tǒng)的可靠性要求并節(jié)省系統(tǒng)資源，本文設計了3個可靠性目標約束下的最小化資源算法并應用實際DAG任務和隨機生成的DAG任務對算法進行了驗證.因為本文提出的算法基于異構多處理器系統(tǒng)，所以這些算法可擴展至大多數(shù)分布式異構系統(tǒng)中可靠性目標約束下的資源(或代價、能量)最小化的應用.然而，對于系統(tǒng)能耗而言，如果運用電壓/頻率調整技術降低處理器的執(zhí)行頻率實現(xiàn)節(jié)能，任務的可靠性將會降低，在今后的工作中，我們將進一步研究如何保證系統(tǒng)的可靠性目標被滿足并且最小化系統(tǒng)能耗的問題.