李薛劍， 雷 政

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601;2.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230026)

0 引 言

隨著高性能計(jì)算技術(shù)的發(fā)展，集群系統(tǒng)在高性能計(jì)算領(lǐng)域占據(jù)了越來(lái)越大的比重[1]。作業(yè)調(diào)度策略作為集群作業(yè)管理系統(tǒng)的核心，其優(yōu)劣直接影響著高性能集群的性能[2]。以提升集群計(jì)算資源利用率為目的的回填算法被證明是性能最好的調(diào)度算法之一[3]。

一些基于回填算法的改進(jìn)策略對(duì)回填算法進(jìn)行了完善，如LT-backfilling[4]算法能有效的保證計(jì)算節(jié)點(diǎn)的負(fù)載均衡；RB-FIFT[5]算法能大大減少資源碎片，提高系統(tǒng)的吞吐率和資源利用率；基于任務(wù)類型的集群調(diào)度策略[6]在進(jìn)一步提升資源利用率的同時(shí)維護(hù)了用戶共享資源的公平性等。但這些回填算法都是基于作業(yè)的預(yù)估運(yùn)行時(shí)間來(lái)選取填充作業(yè)，由于作業(yè)運(yùn)行時(shí)間無(wú)法精確的預(yù)估，所以一定程度上影響了調(diào)度算法的效率[7]。

之前的回填算法通常會(huì)出現(xiàn)以下兩個(gè)問(wèn)題：①回填作業(yè)的預(yù)估運(yùn)行時(shí)間過(guò)長(zhǎng)，集群會(huì)產(chǎn)生新的資源碎片；②回填作業(yè)的預(yù)估運(yùn)行時(shí)間過(guò)短時(shí)，如果出現(xiàn)預(yù)約時(shí)間到達(dá)而回填作業(yè)沒(méi)有完成的情況。為不影響預(yù)約作業(yè)運(yùn)行，一般采取的方式是殺死回填作業(yè)，釋放計(jì)算資源給預(yù)約作業(yè)使用。產(chǎn)生資源碎片和回填作業(yè)未完成被殺死都會(huì)導(dǎo)致算法的執(zhí)行效率下降。

本文提出的RB_HAR策略在不影響預(yù)約作業(yè)運(yùn)行和集群調(diào)度整體效率的前提下，適當(dāng)延長(zhǎng)回填作業(yè)使用資源的時(shí)間來(lái)提升回填作業(yè)的完成率。設(shè)計(jì)實(shí)驗(yàn)將結(jié)合了RB_HAR的改進(jìn)回填策略應(yīng)用于高性能集群的作業(yè)調(diào)度中，對(duì)比其他調(diào)度策略，RB_HAR不但繼承了回填算法高響應(yīng)比、高利用率等優(yōu)點(diǎn)，而且相于較一般的回填算法，回填作業(yè)的完成率得到了極大的提升。

1 一般回填算法分析

HAR策略主要應(yīng)用于高性能計(jì)算集群的作業(yè)調(diào)度中，用以提升一般回填作業(yè)調(diào)度算法時(shí)回填作業(yè)完成率。本節(jié)通過(guò)分析一般回填算法執(zhí)行過(guò)程，指出在作業(yè)預(yù)約時(shí)間到達(dá)時(shí)，一般回填算法在傳統(tǒng)方式處理回填作業(yè)的不足，從理論上驗(yàn)證了RB_HAR策略的可行性。

1.1 高性能計(jì)算集群模型

為了方便描述使用一般回填算法時(shí)的作業(yè)調(diào)度過(guò)程，這里給出了高性能計(jì)算集群。

高性能計(jì)算集群主要思想是利用高速網(wǎng)絡(luò)將PC機(jī)、SMP服務(wù)器甚至是超級(jí)計(jì)算機(jī)連接起來(lái)，使用單一系統(tǒng)統(tǒng)一管理，以達(dá)到更高的計(jì)算性能，主要用于大規(guī)模數(shù)據(jù)計(jì)算[8]。常見(jiàn)的高性能計(jì)算集群節(jié)點(diǎn)由刀片式計(jì)算機(jī)或PC機(jī)構(gòu)成，這類集群的特點(diǎn)是廉價(jià)易構(gòu)建、便于擴(kuò)充、各節(jié)點(diǎn)運(yùn)算能力差異不明顯。

在高性能計(jì)算集群系統(tǒng)中，用戶提交的作業(yè)可以從兩個(gè)方面描述：申請(qǐng)CPU核數(shù)和預(yù)估運(yùn)行時(shí)間[9]。借鑒文獻(xiàn)[9]中的研究方法，將提交的作業(yè)抽象成以占用CPU核數(shù)為長(zhǎng)、運(yùn)行時(shí)間為寬的矩形；將集群抽象成以集群的總CPU核數(shù)為X軸、集群開啟時(shí)間為Y軸的二維集群坐標(biāo)系。如圖1所示是一個(gè)抽象的CPU核數(shù)為16的高性能計(jì)算集群，其中矩形①、②、③表示正在運(yùn)行的作業(yè)，預(yù)估作業(yè)①將t1時(shí)刻完成計(jì)算；矩形④表示已經(jīng)計(jì)算結(jié)束的作業(yè)；矩形⑤表示該作業(yè)預(yù)約了一塊計(jì)算資源，將在t4時(shí)刻占用CPU核N10～N16；矩形⑥、⑦是因作業(yè)⑤預(yù)約而填充運(yùn)行的作業(yè)。

圖1 高性能計(jì)算集群模型圖

1.2 一般回填算法流程

采用Backfilling算法進(jìn)行作業(yè)調(diào)度流程如圖2所示。

圖2 Backfilling算法流程圖

對(duì)圖1所示集群的當(dāng)前狀態(tài)，按照 圖2的流程圖可知：

(1) 直接運(yùn)行階段。當(dāng)前集群資源滿足①、②、③號(hào)作業(yè)需求，直接投入運(yùn)行。

(2) 作業(yè)預(yù)約階段。當(dāng)前5個(gè)空閑CPU核(圖1中的N12～N16)不能滿足作業(yè)⑤的需求，根據(jù)節(jié)點(diǎn)負(fù)載均衡和盡量減小作業(yè)響應(yīng)比的原則，作業(yè)⑤預(yù)約了7個(gè)CPU核(圖1中的N10～N16),將在作業(yè)③結(jié)束后(t4時(shí)刻)開始計(jì)算。

(3) 填充操作階段。等待隊(duì)列中選取了⑥、⑦作為回填作業(yè)投入到資源碎片中運(yùn)行。

(4) 處理預(yù)約階段。根據(jù)回填算法，在t4時(shí)刻系統(tǒng)會(huì)殺死未完成的作業(yè)⑦，釋放節(jié)點(diǎn)N15、N16給作業(yè)⑤使用。

1.3 一般回填算法分析

上述執(zhí)行過(guò)程的結(jié)果是作業(yè)⑤開始運(yùn)行，CPU核N8、N9空閑。若此時(shí)等待隊(duì)列中找不到一個(gè)作業(yè)申請(qǐng)的CPU核數(shù)小于等于2，節(jié)點(diǎn)N8、N9會(huì)一直處于空閑狀態(tài)，直到t2時(shí)刻，空閑CPU核數(shù)增至5才有可能滿足新作業(yè)的需求?；厮萆鲜鲞^(guò)程，若在t4時(shí)刻讓作業(yè)⑤使用CPU核N8～N14，允許作業(yè)⑦最遲運(yùn)行到t2時(shí)刻，這樣既能保證集群作業(yè)調(diào)度性能不變也能避免作業(yè)⑦未完成被殺死。

2 RB_HAR策略及實(shí)現(xiàn)

2.1 RB_HAR策略思想

從一般回填算法分析可看出，當(dāng)回填作業(yè)因?yàn)轭A(yù)估運(yùn)行時(shí)間短于實(shí)際運(yùn)行時(shí)間而在未完成時(shí)將要被系統(tǒng)殺死時(shí)，如果繼續(xù)讓預(yù)約作業(yè)運(yùn)行，那么既可以不影響集群調(diào)度性能，也能保證預(yù)約作業(yè)在預(yù)約時(shí)間投入計(jì)算。因此，可以適當(dāng)?shù)难娱L(zhǎng)回填作業(yè)運(yùn)行時(shí)間，以提高回填作業(yè)的完成率。

由于多數(shù)改進(jìn)的回填算法僅在第(3)步回填操作階段通過(guò)使用不同的策略選取回填作業(yè)來(lái)對(duì)回填算法進(jìn)行改進(jìn)，而RB_HAR策略主要是在第(4)步處理預(yù)約階段對(duì)回填算法進(jìn)行改進(jìn)，所以理論上RB_HAR策略也適用于多數(shù)改進(jìn)的回填算法。

2.2 RB_HAR策略描述

為方便描述RB_HAR策略，表1和表2給出了集群中單個(gè)CPU核的屬性和單個(gè)作業(yè)的屬性及說(shuō)明。

表1 CPU核心相關(guān)屬性及說(shuō)明

結(jié)合了RB_HAR策略的回填算法流程圖如圖3所示，其中回填算法部分既可以是一般的回填算法也可以是一些改進(jìn)的回填算法。

作業(yè)調(diào)度和預(yù)約處理根據(jù)一般回填算法或其他改進(jìn)的回填算法進(jìn)行。當(dāng)某一預(yù)約作業(yè)AJ的預(yù)約運(yùn)行時(shí)間到達(dá)，因AJ預(yù)約而回填運(yùn)行的作業(yè)FJ沒(méi)有結(jié)束運(yùn)行，即(1)成立時(shí)，考慮如何處理FJ：

表2 作業(yè)相關(guān)屬性及說(shuō)明

圖3 結(jié)合了RB_HAR的回填算法流程圖

FJ=AJ.FJ_V[i](AJ.FJ_V[i].jState==RUN)

(1)

當(dāng)集群系統(tǒng)同時(shí)滿足條件I和II時(shí)，允許FJ繼續(xù)運(yùn)行一段時(shí)間：

條件1 下式成立：

(2)

式中，F(xiàn)J表示繼續(xù)運(yùn)行一段時(shí)間不會(huì)影響AJ在預(yù)約時(shí)間運(yùn)行。其中節(jié)點(diǎn)N[i]如果空閑，枚舉類型N[i].nState==FREE，值為1，求和運(yùn)算后可表示由N個(gè)CPU核心構(gòu)成的集群中空閑節(jié)點(diǎn)的總數(shù)。

條件2

Job[0].aNode

(3)

X.aNode

(4)

minTime>X.aNode

(5)

式(3)成立且式(4)式(5)不同時(shí)成立。式(3)表示當(dāng)前空閑節(jié)點(diǎn)小于等待隊(duì)列隊(duì)首作業(yè)申請(qǐng)節(jié)點(diǎn)數(shù)。式(4)、(5)同時(shí)成立表示能在等待隊(duì)列中找到一個(gè)作業(yè)X填充到因等待隊(duì)列隊(duì)首作業(yè)預(yù)約而形成的資源碎片中。minTime表示當(dāng)前集群運(yùn)行作業(yè)的最短剩余時(shí)間，可用下式說(shuō)明：

minTime=MIN(N[1].ocTime,N[2].ocTime,……,

N[n].ocTime)

(6)

式中,N[n].ocTime表示集群CPU核n上有作業(yè)運(yùn)行(不包括回填作業(yè))，該作業(yè)的剩余運(yùn)行時(shí)間為ocTime。

如果條件1和條件2同時(shí)滿足，則應(yīng)允許填充作業(yè)FJ延長(zhǎng)運(yùn)行，增加的運(yùn)行時(shí)間為minTime，即允許FJ延長(zhǎng)運(yùn)行的時(shí)間等于當(dāng)前集群正在運(yùn)行作業(yè)的最短剩余運(yùn)行時(shí)間。如果FJ繼續(xù)運(yùn)行minTime后仍沒(méi)有完成，則殺死該作業(yè)，反饋給用戶，檢查作業(yè)并重新預(yù)估運(yùn)行時(shí)間后再重新放入等待隊(duì)列中接受調(diào)度。

3 實(shí)驗(yàn)設(shè)計(jì)

本文將HAR策略應(yīng)用于Backfilling算法中提出一種改進(jìn)的回填算法RB_HAR。為驗(yàn)證RB_HAR策略的有效性，本節(jié)設(shè)計(jì)了幾組比較實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)數(shù)據(jù)分析RB_HAR在提升集群利用率、作業(yè)公平性及回填作業(yè)完成率上的表現(xiàn)。

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)使用8臺(tái)PC機(jī)搭建了一個(gè)小型集群用于RB_HAR算法和其他調(diào)度算法的比較測(cè)試，PC機(jī)配置為雙核CPU：Pentium(R)Dual-Core，主頻3.20GHz；2GB內(nèi)存。節(jié)點(diǎn)間使用千兆以太網(wǎng)交換機(jī)相連，裝有Ubuntu15.04操作系統(tǒng)。管理節(jié)點(diǎn)和登錄節(jié)點(diǎn)共用一臺(tái)主機(jī)，使用開源TORQUE[10]作為作業(yè)調(diào)度軟件，自定義調(diào)度算法，分別進(jìn)行了FCFS(先來(lái)先服務(wù)算法)[11]、Backfilling(回填算法)[12]和RB_HAR調(diào)度算法的對(duì)比測(cè)試。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

本實(shí)驗(yàn)選取了目前高性能集群性能測(cè)試中常用的LINPACK-Benchmark的HPL作為測(cè)試作業(yè)集[13]。因?yàn)镠PL求解問(wèn)題規(guī)模是可變的，通過(guò)改變求解矩陣的大小和使用的CPU核數(shù)，能獲得不同規(guī)模的作業(yè)，便于比較分析調(diào)度策略性能。

結(jié)合本實(shí)驗(yàn)使用的集群規(guī)模以及Feitelson和Nitzberg對(duì)大量高性能計(jì)算中心作業(yè)分析得出的作業(yè)集特征[14]，構(gòu)造了由26.9%的串行作業(yè)和73.1%的并行作業(yè)組成的混合作業(yè)集：并行作業(yè)中28.3%的作業(yè)申請(qǐng)2個(gè)CPU核數(shù)，25.1%的作業(yè)申請(qǐng)4個(gè)CPU核數(shù)，17.1%的作業(yè)申請(qǐng)6個(gè)CPU核數(shù)，15.2%申請(qǐng)8個(gè)CPU核數(shù)，14.3申請(qǐng)10～12個(gè)CPU核數(shù)。每個(gè)作業(yè)實(shí)際運(yùn)行時(shí)間為50～200 s不等，申請(qǐng)節(jié)點(diǎn)數(shù)少的作業(yè)實(shí)際運(yùn)行時(shí)間較短。

本次實(shí)驗(yàn)構(gòu)造4個(gè)規(guī)模的作業(yè)集，作業(yè)個(gè)數(shù)分別為100、300、500和1 000，作業(yè)隨機(jī)到達(dá)，在保證等待隊(duì)列中作業(yè)數(shù)量大于5個(gè)的基礎(chǔ)上，作業(yè)到來(lái)時(shí)間間隔為0～1 000 s的隨機(jī)值。

3.3 實(shí)驗(yàn)比較參數(shù)

本節(jié)給出了實(shí)驗(yàn)涉及到的一些比較參數(shù)的定義及其作用。

參數(shù)1集群平均利用率。集群利用率是反應(yīng)調(diào)度算法優(yōu)劣的一個(gè)重要參數(shù)[15]，定義集群平均利用率，如下式所示：

J[i].bTime)×J[i].applyNode]

(7)

式中：M為作業(yè)總數(shù)；N為集群節(jié)點(diǎn)個(gè)數(shù)；totalTime是完成M個(gè)作業(yè)花費(fèi)的總時(shí)間；J[i].ftime、J[i].bTime、J[i].applyNode分別表示第i個(gè)作業(yè)的完成時(shí)刻、開始時(shí)刻和占用節(jié)點(diǎn)數(shù)。

參數(shù)2作業(yè)平均響應(yīng)比。作業(yè)響應(yīng)比反映了調(diào)度算法的公平性，好的調(diào)度算法應(yīng)該具有較小的響應(yīng)比。定義作業(yè)平均響應(yīng)比，如下式所示：

(8)

式中：J[i].ftime、J[i].aTime、J[i].bTime分別表示第i個(gè)作業(yè)的完成時(shí)刻、到達(dá)時(shí)刻和開始運(yùn)行時(shí)刻。

參數(shù)3填充作業(yè)完成率。在回填算法中，由于作業(yè)運(yùn)行時(shí)間的不準(zhǔn)確預(yù)估可能導(dǎo)致某些填充作業(yè)一次無(wú)法完成，還需進(jìn)行第2次調(diào)度。將填充作業(yè)中一次調(diào)度就完成的填充作業(yè)所占的比率稱為填充作業(yè)完成率。RB_HAR策略的提出旨在使用回填算法時(shí)提高填充作業(yè)完成率。

4 實(shí)驗(yàn)結(jié)果及分析

每組實(shí)驗(yàn)使用4個(gè)規(guī)模的作業(yè)集分別對(duì)FCFS、Backfilling和RB_HAR 3種調(diào)度算法進(jìn)行測(cè)試，計(jì)算的作業(yè)集規(guī)模有4種：100，300，500和1 000。收集了30組實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)，得到了作業(yè)完成總時(shí)間、集群平均利用率、作業(yè)平均響應(yīng)比、填充作業(yè)完成率的平均值。

4.1 批作業(yè)完成總時(shí)間比較

圖4所示為3種調(diào)度算法完成一定數(shù)量作業(yè)時(shí)間的比較如，在各組實(shí)驗(yàn)中RB_HAR算法和Backfilling算法完成一定量作業(yè)的總時(shí)間都明顯少于FCFS算法。相較于Backfilling算法， RB_HAR算法雖然完成總時(shí)間略長(zhǎng)，但劣勢(shì)并不明顯。且該算法兼顧了回填作業(yè)的完成率。

圖4 作業(yè)完成總時(shí)間比較

4.2 集群平均利用率比較

圖5所示為使用3種調(diào)度算法對(duì)集群的平均利用率進(jìn)行比較，RB_HAR算法很好的繼承了Backfilling算法集群資源高利用率的特點(diǎn)，且明顯優(yōu)于FCFS算法。

圖5 集群平均利用率比較

4.3 作業(yè)平均響應(yīng)比比較

圖6所示為3種作業(yè)調(diào)度算法對(duì)應(yīng)的作業(yè)平均相應(yīng)時(shí)間比較。由于小作業(yè)可以通過(guò)回填的方式提前得到調(diào)度，相比較于FCFS，RB_HAR和Backfilling有著更小的作業(yè)響應(yīng)比，很大程度上保證了作業(yè)調(diào)度的公平性。

圖6 作業(yè)平均響應(yīng)比比較

4.4 填充作業(yè)完成率比較

圖7所示為Backfilling算法和RB_HAR算法的回填作業(yè)完成率比較。RB_HAR算法兼顧了填充作業(yè)的完成率，相較于簡(jiǎn)單的Backfilling算法，填充作業(yè)完成率平均提升了13.29%。93%的填充作業(yè)完成率能滿足大多數(shù)用戶的要求，未完成的填充作業(yè)可接受2次調(diào)度。

圖7 填充作業(yè)完成率比較

4.5 綜合分析

RB_HAR算法繼承了Backfilling的集群資源高利用率、作業(yè)低響應(yīng)比等優(yōu)點(diǎn)，從對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析可以看出，RB_HAR算法的性能明顯優(yōu)于FCFS。RB_HAR與Backfilling算法回填作業(yè)完成率的比較實(shí)驗(yàn)，驗(yàn)證了RB_HAR能有效的提升回填作業(yè)的完成率。由此可見(jiàn)RB_HAR策略應(yīng)用于回填算法時(shí)，在面向系統(tǒng)和面向用戶[16]兩方面都有著出色的表現(xiàn)。

5 結(jié) 語(yǔ)

本文將HAR策略應(yīng)用于回填算法中，提出一種改進(jìn)的回填算法RB_HAR。該算法不僅繼承了一般預(yù)約回填算法的集群資源利用率高和作業(yè)低響應(yīng)比等優(yōu)點(diǎn)，同時(shí)還有效的提升了回填作業(yè)的完成率，減少回填作業(yè)2次運(yùn)行帶來(lái)的資源浪費(fèi)、作業(yè)調(diào)度的不公平性，最后的實(shí)驗(yàn)結(jié)果也證實(shí)了RB_HAR策略的優(yōu)越性。此外，研究過(guò)程中還存在某些問(wèn)題：比如，RB_HAR策略不能保證回填作業(yè)百分之百完成，無(wú)限制的允許回填作業(yè)運(yùn)行至結(jié)束，可能導(dǎo)致預(yù)約作業(yè)響應(yīng)比增加；由于條件限制，RB_HAR策略未能應(yīng)用于更大型的集群系統(tǒng)。解決存在的這些問(wèn)題將是今后工作的重點(diǎn)。