[發明專利]一種基于DVFS技術的大規模并行任務節能調度方法

有效

• 申請號: 201310006427.8
• 申請日: 2013-01-08
• 公開（公告）號: CN103235640A
• 公開（公告）日: 2013-08-07
• 發明（設計）人: 王玉龍;蘇森;黃慶佳;雙鍇;徐鵬
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F1/32
• 分類號: G06F1/32;G06F9/50
• 代理公司: 北京思創畢升專利事務所 11218
• 代理人: 郭韞

1.一種基于DVFS技術的大規模并行任務節能調度方法，其特征在于：所述方法包括以下步驟：

(1)任務映射階段：將所有處理器的初始狀態均設為運行在其最高電壓和最高頻率狀態，然后通過計算獲得任務映射階段的有向無環圖調度結果的整體執行時間M_HEFT；

(2)任務拉伸階段：將任務的執行電壓和頻率進行拉伸優化，在不影響整體性能的情況下降低能耗開銷。

2.根據權利要求1所述的基于DVFS技術的大規模并行任務節能調度方法，其特征在于：所述步驟(1)包括以下步驟：

(A1)：計算所有任務的平均執行開銷；

設任務n_i在處理器p_k上的執行開銷記為w_i，k，則該任務在q個處理器上的平均執行開銷是該任務在所有處理器上的執行時間的均值，如下式所示：

wi‾=Σj=1qwi,j/q;]]>

(A2)：計算所有任務的b-level值，然后按b-level值的降序順序將任務壓入隊列Q；

b-level值是指：通過廣度優先算法逆序計算從有向無環圖退出節點到當前節點所有路徑中最大的路徑開銷值；

(A3)：選擇所述隊列Q中的第一個任務，設該任務為n_i，即未被調度的b-level值最高的任務；

(A4)：循環查找所有的處理器獲得該任務在各個處理器上最早結束時間EFT(n_i，p_k)，選擇最早結束時間最小的處理器p_k，將任務n_i調度到該處理器上執行；

所述最早結束時間EFT(n_i，p_k)是通過下式得到的：任務n_i在處理器p_k的最早結束時間EFT(n_i，p_k)＝EST(n_i，p_k)+w_i，k，其中，EST(n_i，p_k)是任務n_i在處理器p_k的最早開始時間，EST(ni,pk)=maxnj∈pred(ni)(AFT(nj)+cj,i),]]>其中，AFT(n_i)為任務n_i的實際結束時間，n_j為另外一個任務，c_i，j為兩個任務的通信開銷，即每兩個存在依賴關系的可執行任務之間的傳輸時間；pred(n_i)為該任務的直接前驅任務集合，n_j為該任務的直接前驅任務集合中的一個任務，

pred(ni)={∀nj|∃(nj→ni),ni∈DAG,nj∈DAG};]]>

(A5)：將已調度的任務n_i移出隊列Q，然后判斷隊列Q是否為空，如果是，則轉入步驟(A6)，如果否，則返回步驟(A3)；

(A6)：計算出任務映射階段的有向無環圖調度結果的整體執行時間M_HEFT：

MHEFT=max{AFT(ni)|∀ni∈DAG}.]]>

3.根據權利要求2所述的基于DVFS技術的大規模并行任務節能調度方法，其特征在于：所述步驟(2)包括以下步驟：

(B1)：如果M_HEFT≤T_deadline，轉入步驟(B2)，T_deadline為用戶設定的并行任務最長執行時間；如果M_HEFT＞T_deadline則調度無法滿足用戶設定，轉入步驟(B14)；

(B2)：計算任務拉伸系數μ＝T_deadline/M_HEFT；

(B3)：令S為所有任務的集合，當S不為空時，從S中取出AFT(n_i)值最大的任務n_i；

(B4)：對任務映射階段的原調度進行拉伸，在處理器p_k不變的情況下重新計算任務n_i的實際結束時間AFT′(n_i)和實際開始時間AST′(n_i)，計算方式如下：

將實際開始時間更新為：AST′(n_i)＝μ·AST(n_i)，其中AST(n_i)為任務n_i的實際開始時間；

將實際結束時間更新為：AFT′(n_i)＝AST′(n_i)+w_i，k，其中，w_i，k為任務n_i在處理器p_k上的執行開銷；

更新后的實際開始時間和更新后的實際結束時間構成新調度結果；

(B5)將已經拉伸的任務n_i從任務集合S中刪除，如果S不為空，返回步驟(B4)，如果S為空，則轉入步驟(B6)；

(B6)：計算所述新調度結果下的所有計算任務的最早開始時間EST(n_i)和最晚結束時間LFT(n_i)：

EST(ni)=maxnj∈pred(ni)(AFT(nj)+cj,i);]]>

LFT(ni)=minnj∈succ(ni)(AST(nj)-ci,j),]]>其中，c_i，j為兩個任務的通信開銷；

(B7)：令N為所有任務的集合；

(B8)如果N不為空，則取出LFT(n_i)值最大的任務n_i，放入臨時調度隊列Q_temp；

(B9)：任務n_i在處理器p_k上的執行序號表示為l，則任務n_i也可表示為并設置變量x＝l；

(B10)：如果則將放入Q_temp，繼續執行步驟(B11)；否則跳到步驟(B12)；

(B11)：設置變量x′＝x-1，如果x′＞0，則返回步驟(B10)，否則跳到步驟(B12)；

(B12)：計算任務n_i的全局最優執行頻率值f_global：

計算隊列Q_temp中所有任務的執行時間：Texec(Qtemp)={Σwi,pk|∀ni∈Qtemp}]]>

計算隊列Q_temp中任務集的整體可用時間：

Ttotal(Qtemp)=LFT(npk,biggest)-EST(npk,smallest)]]>

計算任務n_i的全局最優執行頻率值f_global：

fglobal(ni,pk)=fmax(pk)·max(wiwi+Slack(ni),Texec(Qtemp)Ttotal(Qtemp))]]>

(B13)：將任務n_i的執行電壓從f_max(p_k)到f_global(n_i，p_k)，其實際執行開銷調整為Texec′(ni)=nifglobal(ni,pk),]]>

實際結束時間調整為AFT(n_i)＝LFT(n_i)，

實際開始時間調整為AST(ni)=AFT(ni)-Texec′(ni);]]>

(B14)：將任務n_i移出任務集合N，更新任務n_i的前驅任務集合的最晚結束時間LFT，清空臨時隊列Q_temp；

(B15)：如果任務集合N不為空，則返回步驟(B7)；否則調度結束，轉入步驟(B16)；

(B16)：退出程序。