在異構系統上基于權重和復制的調度算法

鄧德康，張振榮

(廣西大學 計算機與電子信息學院，廣西 南寧 530004)

0 引 言

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

雖然DVFS能實現能耗的優化，但這種對電壓和頻率的操作可能會導致處理器故障率短時間內的急劇增加，從而對系統的可靠性產生嚴重的威脅[13-15]。可靠性定義為預計成功的概率。對于那些對安全性極為敏感的應用，可靠性的優先級應高于功耗；否則，造成災難性后果的概率將大幅提高。一種極為有效的措施是通過復制任務以提高可靠性。任務復制使得只要有一個處理器能正常的完成任務，就認為任務被成功完成。因此，被視為重要的可靠性增強機制[14]。

可靠性感知任務調度是并行和分布式計算中的一個重要問題。Quan等[13]提出了一種被稱為ISAECC的算法，其使用了基于任務權重的能量預分配方式，以解決能量分配不公平的問題，從而獲得較好的效果。Xie等[14]提出了ESRG和基于復制機制的EFSRG算法，以減少能源消耗，同時滿足應用的可靠性目標，但是性能不佳。Xu等[15]提出將應用程序的可靠性目標轉換為DVFS的任務的DERG算法。Medara等[16]將DVFS運用到云計算環境下，它在實現應用可靠性目標的同時減少了系統資源的使用。Chen等[17]提出了一種基于鏈表的能量感知算法，用于解決異構系統的調度問題，但盡管有良好的性能，算法的復雜度高。Ahmad等[18]將能量優化運用到云計算環境下。

本文研究了在異構計算系統上滿足可靠性約束下，并行應用程序能量消耗和調度長度最小化問題，為了降低異構計算系統上并行應用程序的資源消耗和成本，提出一種基于任務權重和復制機制的分配算法，使用浮點減運算代替除運算，提高了數值的穩定性和性能的優化，在滿足可靠性條件下，實現能量消耗優化的解決方案。

1 系統模型

1.1 應用模型

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

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

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

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

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

1.2 功耗模型

本研究討論的功耗為處理器的功耗，功耗是一個關于處理器頻率的函數，其具體定義為

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

(1)

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

(2)

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

(3)

其中

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

(4)

1.3 可靠性模型

在真實的系統環境下，在任務執行階段時，故障是不可預測，并且不可避免的，遵循泊松概率分布[13-15]。設λk表示處理器uk單位時間的故障率。任務ni在處理器uk上以最大頻率執行的可靠性可以用通過以下公式計算

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

(5)

對于支持DVFS的系統，考慮到動態頻率縮放對瞬態故障的影響，因而故障率取決于實際處理器的頻率，不同的頻率具有不同的故障率。

不同頻率點下的可靠性計算可以使用如下公式進行計算

(6)

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

(7)

從式(7)中，我們可以看到，可靠性與頻率之間的關系為線性關系。將每個任務的可靠性進行計算，就可以得到整個應用G的可靠性數值，具體的計算公式如下所示

(8)

其中，f(pr(i)，hz(i))∈[f(pr(i)，low)，f(pr(i)，max)]，upr(i)∈U為處理器集合，upr(i)和f((pr(i)，hz(i)) 分別表示任務i使用的處理器和對應處理器的頻率。總體的能量通過對每個任務相加可得，具體如下公式計算

(9)

每個任務都有最小的可靠性和最大的可靠性，分別使用如下公式進行計算

(10)

和

(11)

類似的，將每個任務的最小可靠性和最大可靠性應用于整個應用G，應用G就存在有最小的可靠性和最大的可靠性，計算公式如下

(12)

和

(13)

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

1.4 問題描述

在整個任務調度過程中需要解決的問題為：給定一個特定的可靠性目標，在整個任務調度能達到既定的可靠性目標的情況下，盡可能優化其能量的消耗，對應得數學描述可以歸納為如下

(14)

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

2 分配算法

2.1 任務優先級劃分

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

(15)

其中

(16)

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

(17)

和

(18)

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

2.2 ESRG分配算法

本小節將對先前工作中提出ESRG算法進行一個簡單的回顧。為了達到預定的可靠性目標值Rgoal，ESRG分配算法使用了如下的分配公式

(19)

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

(20)

然后對于任意的任務ny而言，其可靠性值為

(21)

最后整個應用的可靠性能夠滿足預定的目標。從上面的公式可以看出：

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

(2)ESRG使用除法實現可靠性分配，在大量浮點數除法下，會造成結果不準確，為了解決這個問題，我們將浮點數除法轉化成浮點數加減操作，這能使得計算結果更加的準確。

(3)ESRG更為關鍵的問題是當任務數較大時，將無法完成任務調度。一個簡單的例子是，當我們要調度一個有40個任務的可靠性為0.9的應用G時，第一個任務需要滿足的可靠性為0.9973，這個是一個非常大的值，ESRG將無法完成這個調度任務，而我們的方法可以解決這個問題。

基于上述的問題，我們對其進行了改進，通過加入權重機制，使可靠性預分配變得更為合理。

2.3 基于權重的分配策略

首先，我們需要對可靠性的表達進行變形

(22)

然后，設新的可靠性函數為

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

(23)

為了后文能更好進行闡述，進行以下定義：

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

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

(24)

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

(25)

因為我們分配超出目標可靠性的值，任務計算量越大所需要的可靠性越低，反之，則需要越高的可靠性，這能更好的降低整個應用的能量消耗，然后將所有任務按照rank值排序，進行順序優化，因此在滿足可靠性目標的前提下，可以實現更小的能量消耗。

上述的分配策略相比于ESRG分配算法，不但考慮了任務的權重，對可靠性進行分配，并且將多重浮點除法轉化為浮點加法，從而將計算誤差降低，提高計算的精度，對于任務數量眾多的情況，表現的越為明顯。

2.4 基于權重和復制的分配算法

前面所述的基于權重的分配策略對于較低的可靠性目標，能夠起到不錯的效果，但是，當可靠性目標增大到一個比較大的數值時，調度任務失敗的可能性依舊偏高，為了解決這個問題，通過引入復制機制，來提高整體應用程序的可靠性。復制機制是將一個任務復制到多個處理器上運行，只要有一個處理器成功運行了任務，此任務就被認為沒有出現錯誤，剩下的任務依然能夠正常進行調度。將權重與復制機制相結合，不僅能夠使可靠性大幅提升，同時能量的消耗也會得到相應的降低。

由于引入了復制機制，一些相關的參數計算會發生相應的變化，整個應用程序的最大可靠性值，使用如下公式計算

(26)

相應的，整個應用G的最大可靠性，計算公式為

(27)

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

(28)

和

(29)

(30)

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

(31)

其中，α是權重系數，用于衡量能量消耗和調度長度對處理選擇的影響。具體的算法流程描述如下：

算法1：基于分配和權重的分配算法

輸入：應用G；處理器集U；目標可靠性R′goal(G)

輸出：能量消耗E(G)；調度長度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)行對應用G按照rank值按降序進行排序，第(2)行進行預分配可靠性計算，第(4)～(26)行對排序后的所有任務進行調度，第(5)～(9)行計算每一個處理的每一個頻率點所產生能量、可靠性和調度長度，并將其添加入列表。第(10)～(15)對變量進行初始化操作，第(16)～(26)行，遍歷先前步驟產生的列表，為了避免同一處理器被分配兩次，第(17)行進行判斷，然后從中選擇出滿足可靠性目標的處理器集，并進行能量消耗優化和臨時數值結果的參數更新。第(27)行對中間可靠性數值進行更新。

算法復雜度分析：①第(4)～(26)行遍歷所有任務，算法復雜度為O(|N|)。 ②第(6)～(9)行遍歷所有處理器和其對應的頻率點為O(|U|2×|F|2)， 第(10)行對其進行排序為：O(|U|2×|F|2log2(|U|2×|F|2))。 ③第(15)行會尋找最晚開始的父節點的AFT，復雜度為O(|N|)。 ④第(16)～(26)行遍歷容量為 |U|2×|F|2的列表，并且訪問當前處理節點的父節點任務的AFT，算法復雜度為：O(|U|2×|F|2)。 ②、③、④為并列結構，①嵌套了②、③和④，并且②的復雜度高于④，因此整個算法的復雜度為：O(T)， 其中T=max(|N|×|U|2×|F|2log2(|U|2×|F|2)，|N|2)。

3 性能評估

3.1 測試環境

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

3.2 仿真參數設置

仿真參數的設置對結果至關重要，因此我們所使用的仿真參數參考了先前工作所使用的參數[15]，具體的系統參數如下：

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

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

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

(4)將權重因子α設為0.5。

3.3 評價指標

對算法的評價指標有：能量消耗和調度長度，能量消耗越小代表算法越節能，調度長度反應了任務完成的時間，越短處理器所需時間越少，算法的性能越好，兩個指標都能對算法性能進行直接反應。

分布式系統和嵌入式系統中一些常用的基于DAG的并行應用程序，如高斯消元和傅立葉變換，這兩種并行應用程序將用于此次的仿真驗證中，其具體細節介紹如下：

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

圖2 傅里葉變換ρ=4

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

圖3 高斯消除ρ=5

3.4 仿真結果

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

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

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

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

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

圖7 各算法調度長度在可靠性為0.98的高斯消除

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

圖8 不同的α對能量消耗的影響

從圖8中可以看出，α值會導致最終的能量消耗結果發生震蕩，綜合兩種應用的結果來看，α在取0.5的附近時，所取得的結果較為合適，對于這種情況的出現，一個比較合理的解釋是，α值將影響能量消耗較少的還是調度長度較短的處理器的優先選擇，為一種啟發示的貪心算法，從而進入局部最優解而無法得到全局最優解，因而造成所得到的結果出現震蕩情況。

4 結束語

在本文中，我們提出了SAWR分配算法，用于提高異構系統上基于DAG的并行應用程序的可靠性并降低能量消耗。這種方法首先將調度任務分為兩個子任務來處理：任務的可靠性劃分和減少任務的能量消耗。SAWR在使用復制機制使得高可靠性目標的調度能夠完成，并加入了權重機制使得能量分配更為平均，從而降低能量的消耗。仿真結果表明，與現有方法相比，我們提出的方法能有效降低能耗。未來將進一步探索在云計算環境中進行拓展，并對提出的猜想進行探索和驗證。