李薛劍， 雷 政

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

0 引 言

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

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

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

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

1 一般回填算法分析

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

1.1 高性能計算集群模型

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

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

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

圖1 高性能計算集群模型圖

1.2 一般回填算法流程

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

圖2 Backfilling算法流程圖

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

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

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

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

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

1.3 一般回填算法分析

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

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

2.1 RB_HAR策略思想

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

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

2.2 RB_HAR策略描述

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

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

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

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

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

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

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

(1)

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

條件1 下式成立：

(2)

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

條件2

Job[0].aNode

(3)

X.aNode

(4)

minTime>X.aNode

(5)

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

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

N[n].ocTime)

(6)

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

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

3 實驗設(shè)計

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

3.1 實驗環(huán)境

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

3.2 實驗數(shù)據(jù)集

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

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

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

3.3 實驗比較參數(shù)

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

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

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

(7)

式中：M為作業(yè)總數(shù)；N為集群節(jié)點個數(shù)；totalTime是完成M個作業(yè)花費的總時間；J[i].ftime、J[i].bTime、J[i].applyNode分別表示第i個作業(yè)的完成時刻、開始時刻和占用節(jié)點數(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個作業(yè)的完成時刻、到達時刻和開始運行時刻。

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

4 實驗結(jié)果及分析

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

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

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

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

4.2 集群平均利用率比較

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

圖5 集群平均利用率比較

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

圖6所示為3種作業(yè)調(diào)度算法對應(yīng)的作業(yè)平均相應(yīng)時間比較。由于小作業(yè)可以通過回填的方式提前得到調(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è)的完成率，相較于簡單的Backfilling算法，填充作業(yè)完成率平均提升了13.29%。93%的填充作業(yè)完成率能滿足大多數(shù)用戶的要求，未完成的填充作業(yè)可接受2次調(diào)度。

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

4.5 綜合分析

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

5 結(jié) 語

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