一種用于異構環境中并行任務調度的彈性節能算法

摘 要：節能調度算法設計是高性能計算領域中的一個研究熱點。本文通過軟件方法設計異構多核計算機的調度算法，實現系統的彈性節能，達到降低能耗并提升系統性能的目的。本文的調度策略建立在基于處理器異構的并行任務調度的環境中，構建了節能模型，提出了EAPS（Energy-aware parallel scheduling）算法模型，該算法在每一任務完成之后重新計算優先級以使優先級符合任務的實時情況，并對復制的前驅任務是否冗余任務進行判斷從而避免資源的浪費，并通過調節節點電壓選擇能耗最少的節點進行調度，在節能與期望完成時間之間取得平衡。

關鍵詞：異構；并行任務；節能；DAG

中圖分類號：TP301.6

隨著計算機體系結構的發展以及人們對于性能需求的提高，大型計算系統在計算能力大幅提高的同時，成本和體積逐漸下降，并在數據密集型領域得到了廣泛應用[1]。其中，異構多核計算系統以應用程序并行化程度高及處理器功耗低等優點比同構計算系統更適合于工作中的常見應用。在計算機系統集群化越來越普遍，并且朝著高性能發展的同時，能量的消耗也逐漸增多，如何實現綠色節能已成為當前計算機系統能耗所關注的方向[2]。

現存的異構多核處理器調度算法大多采用任務復制的方法，以減少任務總體完成時間為研究目標，并沒有考慮到能量消耗的問題[3]。而將同一任務復制到不同的處理器進行調度時，所耗費的時間及所消耗的能量都會因為處理器的不同而有所區別。而現在的處理器具有電壓級別，可采用動態電調整技術根據任務的處理需求在執行時使用不同的電壓級別，產生不同的能耗，在一定程度上可減少設備的能量消耗，縮短任務的總體執行時間，在實際工作中具有廣闊的前景[4]。

1 EAPS（Energy-aware parallel scheduling）算法

本算法的假設條件有以下幾點：（1）所有的資源狀態確定已知，如處理器的數目、每個任務在每個處理器上運行所耗費的時間。（2）處理器之間的鏈路是雙通高速鏈路，處理器可以在運行處理器上任務的同時向別的處理器傳遞數據。（3）任務屬于非搶占式任務，在執行過程當中不可中斷。任務需按事先設定好的順序執行，即任務之間具有先后依賴性。任務在執行過程中分成若干個子任務，這些子任務需按照設定的順序在前驅任務完成后，并且所需資源達到相應處理器后，才可開始執行，執行完畢后，也將相應的資源傳遞給后續子任務。（4）節點的電壓具有相應的運行級別，并且可以動態調整，同一任務運行在同一節點的不同電壓所耗費的能量有所不同。

下表展示的是本文中計算相關的一些變量：

本算法采用任務的最早開始時間est（ni）以及任務與出口任務之間的最長距離nlevel（ni）作為優先級的設置值。在任務的調度過程當中，選擇具有最早開始時間的任務進行調度，如果有多于一個任務的最早開始時間相同，則選nlevel（ni）值較大的任務，因為這是影響調度長度的關鍵任務，nlevel（ni）值最大的任務的是當前所有任務中對于提前完成總任務調度具有最大影響的節點，所以需要優先進行調度。

在按照算法1生成調度列表后，開始進行處理器節點的分配。由于任務的優先值在任務的調度過程當中會有所更新，如果一直采用任務調度前設定好的優先值，會對任務的調度時間有所影響，不能進行最有效的調度，所以這里會在每一個任務調度完后重新計算任務的優先級，以使調度狀態更加符合真實情況，有利于算法性能的提高。

任務確定以后進行處理器的選擇。在進行處理器的選擇時，考慮到節能的需要，通過對處理器電壓所處級別的調整達到節能的目的。首先所有可調度的節點必然是已經處理完任務、所有資源就緒的結點，對于這些空閑結點，電壓已調整至最低級別，在此基礎之上，不斷試探各處理器是否可以在截止期內完成任務，如不能則逐級調高電壓，直至任務可在截止需求時間內完成，最后選擇能耗最少的節點進行調度。如各就緒節點調至最高電壓，也沒有滿足在截止期內完成任務的節點，則選擇最高電壓能耗最少的結點進行調度即可。

當然此時的處理器還沒有進行實質的任務調度，只是選擇了合適的處理器以及合適的電壓級別進行了標記。本算法為了減少數據傳遞開銷，縮短任務的總調度時間，借鑒了一些算法的復制思路，對于任務并行性的提高也起到了一定作用。之前許多算法雖然有復制前驅任務這一思路，但都有不足之處，或是沒有對復制任務進行判斷，導致復制的任務對于縮短任務的總體調度時間沒有任何幫助，反而浪費了資源，或是在所有的任務調度完成以后再對復制的前驅任務進行判斷是否冗余，如果冗余則刪除此前驅任務，必然造成處理器結點在刪除任務后又存在大量空閑時間段，浪費資源的后果，不能進行理想的任務調度、提高調度成功的概率。而本算法則是在任務調度前就先進行判斷前驅任務是否有必要復制，有的話再進行調度，否則放棄復制，達到了提高任務調度率、節省資源的目的。

2 結束語

本節內容通過實驗數據測試EAPS算法的有效性。這里將用異構環境類似的HNDP與HCPFD算法與EAPS算法進行比較分析。在實驗過程中，針對每組實驗只改變一個參數，保持其他參數值不變，這樣可以更加清楚地觀察到什么參數對于任務的調度影響最大，也可以比較各算法在評測指標上的變化。本節將從CCR值、處理器異構兩個參數值來測評算法的性能。由圖1和2可知EAPS的能耗最小，具有最好的效果。

參考文獻：

[1]李新，賈智平，鞠雷等.一種面向同構集群系統的并行任務節能調度優化方法[J].計算機學報，2012（03）.

[2]朱曉敏，賀川，王建江等.異構計算系統中彈性節能調度策略研究[J].計算機學報，2012（06）.

[3]過敏意.綠色計算：內涵及趨勢[J].計算機工程，2010（10）：1-7.

[4]喬穎，鄒冰，方亭，王宏安，戴國忠.一種實時異構系統的集成動態調度算法[J].軟件學報，2002（12）.

[5]林闖，田源，姚敏.綠色網絡和綠色評價：節能機制、模型和評價[J].計算機學報，2011（04）.

[6]蔣韻聯，孫廣中，孫胤龍.并行異構系統中的一種高效任務調度算法[J].計算機工程，2007（06）.

作者簡介：肖瑤星（1985-），女，貴州六盤水人，講師，計算機技術碩士，研究方向：計算機網絡技術。

作者單位：湖南信息學院 電子信息學院，湖南長沙 410000；湖南信息職業技術學院 計算機工程系，湖南長沙 410000

基金項目：湖南省教育廳科學研究項目（項目編號：13C649）。