一種對集群回填作業(yè)調度改進的RB_HAR策略

李薛劍， 雷 政

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

0 引 言

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

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

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

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

1 一般回填算法分析

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

1.1 高性能計算集群模型

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

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

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

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

1.2 一般回填算法流程

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

圖2 Backfilling算法流程圖

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

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

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

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

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

1.3 一般回填算法分析

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

2 RB_HAR策略及實現

2.1 RB_HAR策略思想

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

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

2.2 RB_HAR策略描述

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

表1 CPU核心相關屬性及說明

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

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

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

圖3 結合了RB_HAR的回填算法流程圖

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

(1)

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

條件1 下式成立：

(2)

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

條件2

Job[0].aNode

(3)

X.aNode

(4)

minTime>X.aNode

(5)

式(3)成立且式(4)式(5)不同時成立。式(3)表示當前空閑節(jié)點小于等待隊列隊首作業(yè)申請節(jié)點數。式(4)、(5)同時成立表示能在等待隊列中找到一個作業(yè)X填充到因等待隊列隊首作業(yè)預約而形成的資源碎片中。minTime表示當前集群運行作業(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è)FJ延長運行，增加的運行時間為minTime，即允許FJ延長運行的時間等于當前集群正在運行作業(yè)的最短剩余運行時間。如果FJ繼續(xù)運行minTime后仍沒有完成，則殺死該作業(yè)，反饋給用戶，檢查作業(yè)并重新預估運行時間后再重新放入等待隊列中接受調度。

3 實驗設計

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

3.1 實驗環(huán)境

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

3.2 實驗數據集

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

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

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

3.3 實驗比較參數

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

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

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

(7)

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

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

(8)

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

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

4 實驗結果及分析

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

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

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

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

4.2 集群平均利用率比較

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

圖5 集群平均利用率比較

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

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

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

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

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

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

4.5 綜合分析

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

5 結 語

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