一種用于異構(gòu)環(huán)境中并行任務(wù)調(diào)度的彈性節(jié)能算法

摘 要：節(jié)能調(diào)度算法設(shè)計(jì)是高性能計(jì)算領(lǐng)域中的一個(gè)研究熱點(diǎn)。本文通過軟件方法設(shè)計(jì)異構(gòu)多核計(jì)算機(jī)的調(diào)度算法，實(shí)現(xiàn)系統(tǒng)的彈性節(jié)能，達(dá)到降低能耗并提升系統(tǒng)性能的目的。本文的調(diào)度策略建立在基于處理器異構(gòu)的并行任務(wù)調(diào)度的環(huán)境中，構(gòu)建了節(jié)能模型，提出了EAPS（Energy-aware parallel scheduling）算法模型，該算法在每一任務(wù)完成之后重新計(jì)算優(yōu)先級(jí)以使優(yōu)先級(jí)符合任務(wù)的實(shí)時(shí)情況，并對(duì)復(fù)制的前驅(qū)任務(wù)是否冗余任務(wù)進(jìn)行判斷從而避免資源的浪費(fèi)，并通過調(diào)節(jié)節(jié)點(diǎn)電壓選擇能耗最少的節(jié)點(diǎn)進(jìn)行調(diào)度，在節(jié)能與期望完成時(shí)間之間取得平衡。

關(guān)鍵詞：異構(gòu)；并行任務(wù)；節(jié)能；DAG

中圖分類號(hào)：TP301.6

隨著計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展以及人們對(duì)于性能需求的提高，大型計(jì)算系統(tǒng)在計(jì)算能力大幅提高的同時(shí)，成本和體積逐漸下降，并在數(shù)據(jù)密集型領(lǐng)域得到了廣泛應(yīng)用[1]。其中，異構(gòu)多核計(jì)算系統(tǒng)以應(yīng)用程序并行化程度高及處理器功耗低等優(yōu)點(diǎn)比同構(gòu)計(jì)算系統(tǒng)更適合于工作中的常見應(yīng)用。在計(jì)算機(jī)系統(tǒng)集群化越來越普遍，并且朝著高性能發(fā)展的同時(shí)，能量的消耗也逐漸增多，如何實(shí)現(xiàn)綠色節(jié)能已成為當(dāng)前計(jì)算機(jī)系統(tǒng)能耗所關(guān)注的方向[2]。

現(xiàn)存的異構(gòu)多核處理器調(diào)度算法大多采用任務(wù)復(fù)制的方法，以減少任務(wù)總體完成時(shí)間為研究目標(biāo)，并沒有考慮到能量消耗的問題[3]。而將同一任務(wù)復(fù)制到不同的處理器進(jìn)行調(diào)度時(shí)，所耗費(fèi)的時(shí)間及所消耗的能量都會(huì)因?yàn)樘幚砥鞯牟煌兴鶇^(qū)別。而現(xiàn)在的處理器具有電壓級(jí)別，可采用動(dòng)態(tài)電調(diào)整技術(shù)根據(jù)任務(wù)的處理需求在執(zhí)行時(shí)使用不同的電壓級(jí)別，產(chǎn)生不同的能耗，在一定程度上可減少設(shè)備的能量消耗，縮短任務(wù)的總體執(zhí)行時(shí)間，在實(shí)際工作中具有廣闊的前景[4]。

1 EAPS（Energy-aware parallel scheduling）算法

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

下表展示的是本文中計(jì)算相關(guān)的一些變量：

本算法采用任務(wù)的最早開始時(shí)間est（ni）以及任務(wù)與出口任務(wù)之間的最長距離nlevel（ni）作為優(yōu)先級(jí)的設(shè)置值。在任務(wù)的調(diào)度過程當(dāng)中，選擇具有最早開始時(shí)間的任務(wù)進(jìn)行調(diào)度，如果有多于一個(gè)任務(wù)的最早開始時(shí)間相同，則選nlevel（ni）值較大的任務(wù)，因?yàn)檫@是影響調(diào)度長度的關(guān)鍵任務(wù)，nlevel（ni）值最大的任務(wù)的是當(dāng)前所有任務(wù)中對(duì)于提前完成總?cè)蝿?wù)調(diào)度具有最大影響的節(jié)點(diǎn)，所以需要優(yōu)先進(jìn)行調(diào)度。

在按照算法1生成調(diào)度列表后，開始進(jìn)行處理器節(jié)點(diǎn)的分配。由于任務(wù)的優(yōu)先值在任務(wù)的調(diào)度過程當(dāng)中會(huì)有所更新，如果一直采用任務(wù)調(diào)度前設(shè)定好的優(yōu)先值，會(huì)對(duì)任務(wù)的調(diào)度時(shí)間有所影響，不能進(jìn)行最有效的調(diào)度，所以這里會(huì)在每一個(gè)任務(wù)調(diào)度完后重新計(jì)算任務(wù)的優(yōu)先級(jí)，以使調(diào)度狀態(tài)更加符合真實(shí)情況，有利于算法性能的提高。

任務(wù)確定以后進(jìn)行處理器的選擇。在進(jìn)行處理器的選擇時(shí)，考慮到節(jié)能的需要，通過對(duì)處理器電壓所處級(jí)別的調(diào)整達(dá)到節(jié)能的目的。首先所有可調(diào)度的節(jié)點(diǎn)必然是已經(jīng)處理完任務(wù)、所有資源就緒的結(jié)點(diǎn)，對(duì)于這些空閑結(jié)點(diǎn)，電壓已調(diào)整至最低級(jí)別，在此基礎(chǔ)之上，不斷試探各處理器是否可以在截止期內(nèi)完成任務(wù)，如不能則逐級(jí)調(diào)高電壓，直至任務(wù)可在截止需求時(shí)間內(nèi)完成，最后選擇能耗最少的節(jié)點(diǎn)進(jìn)行調(diào)度。如各就緒節(jié)點(diǎn)調(diào)至最高電壓，也沒有滿足在截止期內(nèi)完成任務(wù)的節(jié)點(diǎn)，則選擇最高電壓能耗最少的結(jié)點(diǎn)進(jìn)行調(diào)度即可。

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

2 結(jié)束語

本節(jié)內(nèi)容通過實(shí)驗(yàn)數(shù)據(jù)測(cè)試EAPS算法的有效性。這里將用異構(gòu)環(huán)境類似的HNDP與HCPFD算法與EAPS算法進(jìn)行比較分析。在實(shí)驗(yàn)過程中，針對(duì)每組實(shí)驗(yàn)只改變一個(gè)參數(shù)，保持其他參數(shù)值不變，這樣可以更加清楚地觀察到什么參數(shù)對(duì)于任務(wù)的調(diào)度影響最大，也可以比較各算法在評(píng)測(cè)指標(biāo)上的變化。本節(jié)將從CCR值、處理器異構(gòu)兩個(gè)參數(shù)值來測(cè)評(píng)算法的性能。由圖1和2可知EAPS的能耗最小，具有最好的效果。

參考文獻(xiàn)：

[1]李新，賈智平，鞠雷等.一種面向同構(gòu)集群系統(tǒng)的并行任務(wù)節(jié)能調(diào)度優(yōu)化方法[J].計(jì)算機(jī)學(xué)報(bào)，2012（03）.

[2]朱曉敏，賀川，王建江等.異構(gòu)計(jì)算系統(tǒng)中彈性節(jié)能調(diào)度策略研究[J].計(jì)算機(jī)學(xué)報(bào)，2012（06）.

[3]過敏意.綠色計(jì)算：內(nèi)涵及趨勢(shì)[J].計(jì)算機(jī)工程，2010（10）：1-7.

[4]喬穎，鄒冰，方亭，王宏安，戴國忠.一種實(shí)時(shí)異構(gòu)系統(tǒng)的集成動(dòng)態(tài)調(diào)度算法[J].軟件學(xué)報(bào)，2002（12）.

[5]林闖，田源，姚敏.綠色網(wǎng)絡(luò)和綠色評(píng)價(jià)：節(jié)能機(jī)制、模型和評(píng)價(jià)[J].計(jì)算機(jī)學(xué)報(bào)，2011（04）.

[6]蔣韻聯(lián)，孫廣中，孫胤龍.并行異構(gòu)系統(tǒng)中的一種高效任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程，2007（06）.

作者簡(jiǎn)介：肖瑤星（1985-），女，貴州六盤水人，講師，計(jì)算機(jī)技術(shù)碩士，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)。

作者單位：湖南信息學(xué)院 電子信息學(xué)院，湖南長沙 410000；湖南信息職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程系，湖南長沙 410000

基金項(xiàng)目：湖南省教育廳科學(xué)研究項(xiàng)目（項(xiàng)目編號(hào)：13C649）。