何文婷 崔慧敏 馮曉兵

(*中國科學(xué)院計算機體系結(jié)構(gòu)國家重點實驗室 北京 100190)(**中國科學(xué)院計算技術(shù)研究所 北京 100190)(***中國科學(xué)院大學(xué) 北京 100049)

?

HDAS:異構(gòu)集群上Hadoop+框架中的動態(tài)親和性調(diào)度①

何文婷②******崔慧敏③***馮曉兵***

(*中國科學(xué)院計算機體系結(jié)構(gòu)國家重點實驗室 北京 100190)(**中國科學(xué)院計算技術(shù)研究所 北京 100190)(***中國科學(xué)院大學(xué) 北京 100049)

針對現(xiàn)有異構(gòu)集群的編程框架著重于異構(gòu)資源的利用，沒有充分考慮共享資源競爭導(dǎo)致作業(yè)完成時間延長的情況，基于Hadoop+框架和異構(gòu)任務(wù)模型，提出并實現(xiàn)了異構(gòu)動態(tài)親和性調(diào)度(HDAS)算法，該算法利用Hadoop的心跳機制監(jiān)測各結(jié)點上的資源使用情況和實時負載，對系統(tǒng)中的異構(gòu)資源用不同的策略計算與任務(wù)的親和性，進行任務(wù)分派，使系統(tǒng)的資源利用更充分，從而降低共享資源競爭導(dǎo)致的任務(wù)延遲，提高系統(tǒng)的整體吞吐率，且提交到系統(tǒng)中的應(yīng)用都會在啟動后一定時間內(nèi)被執(zhí)行。對25種混合負載的試驗表明，Hadoop+框架使用HDAS相對于Hadoop的實現(xiàn)可獲得平均21.9x的加速比，明顯優(yōu)于基于異構(gòu)任務(wù)模型的調(diào)度策略(17.9x)，并使其中21個負載的任務(wù)平均延遲不超過6%，在任務(wù)對系統(tǒng)資源需求多樣性豐富的混合負載上優(yōu)化效果明顯。

MapReduce， 異構(gòu)， Hadoop+， 親和性， 調(diào)度

0 引 言

為高效處理數(shù)據(jù)中心中的異構(gòu)負載，提升性能功耗比，異構(gòu)加速器正越來越多地被大規(guī)模集群所采用。MARS[1]和MapCG[2]利用圖形處理單元(GPU)的多線程技術(shù)，給每個線程分配一部分對進行處理，嘗試在單個GPU上使用MapReduce編程框架。HadoopCL[3]、MRCL[4]、HAPI[5]和Glasswing[6]在MapReduce中通過OpenCL使多核CPU和加速器協(xié)作完成應(yīng)用。Glasswing還進一步引入管道機制提高系統(tǒng)并行程度。HadoopCL2[7]探索了機器學(xué)習(xí)算法在異構(gòu)集群中的編程框架。Hadoop+[8]框架允許用戶在單個Map或Reduce任務(wù)中顯式調(diào)用CUDA/OpenCL的并行實現(xiàn)，提升性能，并構(gòu)建模型刻畫了異構(gòu)集群中任務(wù)的異構(gòu)性，預(yù)測任務(wù)在共享資源競爭情況下的執(zhí)行時間，幫助選擇性能最佳的任務(wù)配置。在異構(gòu)集群的任務(wù)調(diào)度方面，LATE[9]選擇在異構(gòu)集群中投機執(zhí)行預(yù)計剩余完成時間最長的任務(wù)；SAMR[10]利用任務(wù)執(zhí)行的歷史信息動態(tài)調(diào)節(jié)應(yīng)用執(zhí)行時各階段的權(quán)重，更準確地預(yù)估需要投機執(zhí)行的任務(wù)；ESAMR[11]根據(jù)應(yīng)用在結(jié)點上執(zhí)行的歷史信息對其進行分類，利用每類應(yīng)用在不同結(jié)點上的執(zhí)行情況預(yù)估新應(yīng)用在結(jié)點上的執(zhí)行情況；MR-Predict[12]把MapReduce應(yīng)用根據(jù)其對資源的使用情況分類，對每類應(yīng)用分別調(diào)度，提高集群的整體吞率。但這些工作只關(guān)注多核CPU的異構(gòu)集群。隨著異構(gòu)加速器越來越多地在集群中使用，同一應(yīng)用在GPU和多核CPU上運行的任務(wù)行為差異明顯[8]，過多投機任務(wù)的執(zhí)行會使異構(gòu)集群的負載不均衡情況更明顯，加劇運行在GPU上的任務(wù)由于共享資源的競爭導(dǎo)致的性能下降，在混合負載中合理分配有限的異構(gòu)加速器資源仍是一大挑戰(zhàn)。

Schirahata等[13]根據(jù)集群中應(yīng)用歷史任務(wù)使用GPU的平均加速比決定剩余任務(wù)在兩種處理器上分配的比例，但未考察混合負載中的異構(gòu)資源分配。Hadoop+[8]根據(jù)應(yīng)用在系統(tǒng)中執(zhí)行的歷史信息，優(yōu)先分配GPU資源給混合負載中能通過GPU取得更高加速比的應(yīng)用，但不能根據(jù)集群的實時資源使用情況動態(tài)調(diào)節(jié)。本文使用Hadoop+[8]的異構(gòu)任務(wù)模型，提出了異構(gòu)動態(tài)親和性調(diào)度(heterogeneous dynamic affinity scheduling, HDAS)算法，根據(jù)系統(tǒng)實時負載，選擇與當前可用資源的親和性最高的備調(diào)度任務(wù)，減少同時運行的任務(wù)由于共享資源競爭導(dǎo)致的性能下降，使負載的執(zhí)行周期中系統(tǒng)資源保持較高的使用率，提高系統(tǒng)吞吐率。本文主要工作：

(1) 利用Hadoop 自帶的心跳機制，讓從結(jié)點實時反饋系統(tǒng)中的資源使用情況和任務(wù)執(zhí)行進度；

(2) 根據(jù)異構(gòu)任務(wù)模型，計算備選任務(wù)的實時資源親和性，把計算資源合理地分配給受系統(tǒng)中共享資源的競爭影響小且與計算資源親和性大的任務(wù)執(zhí)行，降低混合負載中所有任務(wù)的平均延遲，提高系統(tǒng)的資源使用率和整體吞吐率；

(3) 在本文的實驗的25種混合應(yīng)用負載相對于Hadoop框架中的實現(xiàn)取得最高31.0x，平均21.9x的加速比，明顯優(yōu)于先來先服務(wù)的調(diào)度策略(平均14.3x)和基于異構(gòu)任務(wù)模型的資源分配調(diào)度策略(平均17.9x)，并把混合負載中的單個任務(wù)的平均執(zhí)行時間減少為任務(wù)獨占系統(tǒng)時的1.2x(其中21個負載不超過1.06x)，在任務(wù)對系統(tǒng)資源需求多樣性豐富的混合負載上優(yōu)化效果明顯。

1 Hadoop+與異構(gòu)任務(wù)模型

Hadoop+框架擴展了原有的Hadoop框架，允許在Map/Reduce任務(wù)中顯式調(diào)用CUDA/OpenCL等并行加速的任務(wù)實現(xiàn)，并通過異構(gòu)任務(wù)模型指導(dǎo)單個應(yīng)用選擇最佳的任務(wù)配置，提高應(yīng)用在異構(gòu)集群上的數(shù)據(jù)處理速度。

對于混合負載，該模型根據(jù)各應(yīng)用通過GPU得到的性能提升高低依次將GPU分給各應(yīng)用。但若應(yīng)用的GPU任務(wù)對系統(tǒng)的IO需求較大，則同時運行的任務(wù)會由于共享資源競爭導(dǎo)致數(shù)據(jù)讀取階段延遲，系統(tǒng)GPU不能被高效利用。

1.1 異構(gòu)任務(wù)模型

該模型能刻畫異構(gòu)集群中的任務(wù)的異構(gòu)性，根據(jù)應(yīng)用的單線程CPU(記作CPU_base)任務(wù)和單獨運行的GPU(記作GPU_base)任務(wù)的各階段執(zhí)行時間和系統(tǒng)實時負載準確預(yù)測異構(gòu)任務(wù)(根據(jù)其使用的資源，下文分別記作CPU任務(wù)和GPU任務(wù))在共享資源競爭下的數(shù)據(jù)處理速度，以及應(yīng)用在當前的系統(tǒng)中所能達到的最優(yōu)數(shù)據(jù)處理速度。此處，單個的任務(wù)數(shù)據(jù)處理速度(dps)可以用下式計算，

(1)

其中V表示任務(wù)所要處理的數(shù)據(jù)分片的大小，T表示任務(wù)的執(zhí)行時間，可以用下式計算：

(2)

其中tpc0和tpg0分別是應(yīng)用的CPU_base任務(wù)和GPU_base任務(wù)的計算時間，由文獻[8]的分析可知，Hadoop+框架中應(yīng)用的任務(wù)該部分時間對共享資源競爭不敏感，tdcg是GPU任務(wù)的數(shù)據(jù)在CPU和GPU間的傳輸時間，與tdg相比可忽略。tdc和tdg分別是共享集群中應(yīng)用的CPU任務(wù)和GPU任務(wù)讀取數(shù)據(jù)的時間，可用下式預(yù)測：

(3)

其中sumio是系統(tǒng)總體IO請求大小，n是系統(tǒng)中發(fā)出IO請求的任務(wù)數(shù)，tdc0和tdg0分別是應(yīng)用的CPU_base任務(wù)和GPU_base任務(wù)數(shù)據(jù)讀取時間。

1.2 基于異構(gòu)任務(wù)模型的資源分配調(diào)度策略

在Hadoop+中處理多種應(yīng)用的混合負載時，先根據(jù)公式

(4)

計算各應(yīng)用與GPU的親和性，其中Tk_GPU表示只有k個該應(yīng)用的GPU任務(wù)同時在一個結(jié)點中執(zhí)行時，任務(wù)的平均執(zhí)行時間，g為結(jié)點的GPU個數(shù)。該策略將GPU資源優(yōu)先分配給使用GPU可以獲得更高加速比且對系統(tǒng)共享資源競爭不敏感的應(yīng)用的任務(wù)，并使用優(yōu)勢資源公正(dominant resource fairness, DRF)策略[14]分配系統(tǒng)中的剩余資源，保證沒有應(yīng)用被餓死。

但混合負載中有GPU任務(wù)對系統(tǒng)IO需求較大的應(yīng)用時，使用該策略的性能提升效果并不明顯。圖1是基于異構(gòu)的任務(wù)模型的資源分配策略在3.1節(jié)介紹的試驗平臺和包含三個應(yīng)用的混合負載K-T上相對于先來先服務(wù)(FIFO)調(diào)度策略的調(diào)度效果的改進，在10種混合負載組合上得到的性能提升最高為29.9%，平均為17.5%。

圖1 基于異構(gòu)任務(wù)模型的資源分配調(diào)度策略相對于先來先服務(wù)調(diào)度策略在三個應(yīng)用的混合負載上的調(diào)度效果的改進

試驗中，該策略相對于先來先服務(wù)調(diào)度策略性能優(yōu)化效果最不明顯的負載P(K近鄰(KNN)，樸素貝葉斯(NB)，反向傳播(BP)應(yīng)用的混合負載)的性能提升僅為8.9%。該負載中，KNN和NB應(yīng)用的GPU任務(wù)都對系統(tǒng)有較大的IO帶寬需求，而為了更高效地使用GPU，這兩種任務(wù)需讀取1GB的數(shù)據(jù)作為輸入。因此同時執(zhí)行的GPU任務(wù)會由于競爭IO導(dǎo)致單個任務(wù)的執(zhí)行時間延長，而這兩種策略都不能有效避免這種競爭，導(dǎo)致KNN應(yīng)用的GPU任務(wù)的執(zhí)行時間平均任務(wù)延遲分別高達4.8x和4.2x，NB應(yīng)用的GPU任務(wù)也分別有2.7x和3.1x的延遲(詳細的分析在3.3中展開)，而CPU任務(wù)由于對系統(tǒng)的資源需求較為和緩，幾乎不受影響。對于BP應(yīng)用，其單個任務(wù)讀取的數(shù)據(jù)只有4MB，且在GPU上的計算時間平均為23.6s，因而該應(yīng)用的GPU任務(wù)對系統(tǒng)的IO競爭不敏感。此外，基于異構(gòu)的任務(wù)模型的資源分配策略會給所有的BP應(yīng)用的任務(wù)都分配GPU執(zhí)行，因此該策略下負載執(zhí)行的結(jié)果中BP應(yīng)用的CPU任務(wù)(BP_CPU)。兩種調(diào)度策略下，所有任務(wù)的平均延遲均達到1.6x，如圖 2所示，其中，任務(wù)的平均延遲用下式

(5)

計算，其中，C，G代表只運行在CPU處理器和需要使用GPU處理器的任務(wù)集合；Tt，TCPU_base，TGPU_base分別代表任務(wù)t在混合負載中的執(zhí)行時間、應(yīng)用的CPU_base任務(wù)執(zhí)行時間和GPU_base任務(wù)的執(zhí)行時間。

圖2 先來先服務(wù)調(diào)度策略和基于異構(gòu)的任務(wù)模型的資源分配調(diào)度策略下負載P中各類任務(wù)的歸一化運行時間

1.3 兩種調(diào)度策略下的系統(tǒng)資源使用情況

本文在集群的一個結(jié)點上統(tǒng)計了負載P的執(zhí)行周期中GPU的使用情況和系統(tǒng)IO的實時負載。

使用先來先服務(wù)調(diào)度算法運行負載P時，調(diào)度器會依次分派KNN，NB和BP應(yīng)用提交的所有任務(wù)。KNN和NB應(yīng)用運行階段，單個GPU任務(wù)對系統(tǒng)IO需求較大，多任務(wù)同時執(zhí)行會競爭系統(tǒng)IO，因此任務(wù)的數(shù)據(jù)讀取階段延遲明顯，運行的初始階段系統(tǒng)中同時活躍的GPU個數(shù)較少(如圖3深色曲線所示)，而系統(tǒng)IO負載較高(如淺色曲線所示)。

混合負載開始執(zhí)行BP應(yīng)用的任務(wù)后，其CPU和GPU任務(wù)對系統(tǒng)IO需求都很低，各個任務(wù)能接連被分配到相應(yīng)的資源高效執(zhí)行，系統(tǒng)中幾乎所有的GPU都處于活躍狀態(tài)(如圖 3深色曲線所示)，但IO資源(如淺色曲線所示)未得以充分利用。

圖3 先來先服務(wù)調(diào)度策略下系統(tǒng)的資源使用情況

此外，使用Hadoop系統(tǒng)的先來先服務(wù)調(diào)度算法，每個應(yīng)用不可避免地有一部分任務(wù)被調(diào)度到CPU上執(zhí)行，如果該應(yīng)用的一個任務(wù)在CPU上的執(zhí)行時間比其他所有分配到GPU資源執(zhí)行的任務(wù)的完成時間長，則會延長負載的整體完成時間。

使用基于異構(gòu)任務(wù)模型的資源分配策略指導(dǎo)的調(diào)度算法運行負載P時，調(diào)度器優(yōu)先分配GPU資源給BP應(yīng)用的任務(wù)，并在KNN和NB應(yīng)用間公平分配分配非GPU資源執(zhí)行，當BP應(yīng)用的所有任務(wù)執(zhí)行結(jié)束后，再將NB應(yīng)用的剩余任務(wù)分派到GPU上執(zhí)行，將系統(tǒng)的其余資源分配給KNN應(yīng)用，完成其余下的任務(wù)。因此，負載執(zhí)行的初始階段，單個BP應(yīng)用的任務(wù)對系統(tǒng)IO資源需求不大，系統(tǒng)的IO負載很低(如圖4淺色曲線所示)，GPU資源使用充分(如深色曲線所示)。NB應(yīng)用開始使用GPU資源后，單個任務(wù)對系統(tǒng)的IO資源需求增大，同時執(zhí)行的GPU任務(wù)間資源競爭明顯，任務(wù)的數(shù)據(jù)讀取階段延遲明顯，系統(tǒng)的GPU使用率降低。

圖4 異構(gòu)任務(wù)模型的資源分配策略下系統(tǒng)資源使用情況

該策略調(diào)度時，雖然混合負載中用GPU加速效果更為明顯的BP應(yīng)用和NB應(yīng)用有更高比例的任務(wù)分配到GPU資源，但整個負載的運行周期中，IO資源和GPU資源的使用不夠均勻，系統(tǒng)中階段性的共享資源競爭限制了混合負載的整體性能提升。對比圖 3和圖 4，可以發(fā)現(xiàn)兩種調(diào)度策略對資源的使用情況基本都可被明顯地分為幾個階段，每個階段中都有使用不夠充分的系統(tǒng)資源(GPU/IO)兩種資源調(diào)度策略都不能保持執(zhí)行周期中各時段的資源被充分使用。

1.4 小結(jié)

由1.2、1.3節(jié)的例子看出，當系統(tǒng)的負載應(yīng)用種類增多時，已有的資源分配策略不能很好地感知系統(tǒng)中的實時負載，并根據(jù)系統(tǒng)的實時負載和系統(tǒng)中的任務(wù)特征調(diào)整調(diào)度策略，因此，需要根據(jù)系統(tǒng)的實時負載調(diào)整資源的新的分配策略，減少同時運行的任務(wù)對系統(tǒng)中共享資源的競爭，提高負載執(zhí)行周期中系統(tǒng)的資源使用率和系統(tǒng)整體吞吐率。

2 異構(gòu)動態(tài)親和性調(diào)度算法

2.1 異構(gòu)動態(tài)親和調(diào)度的總體流程

圖5描述了本文提出的異構(gòu)動態(tài)親和性調(diào)度(HDAS)的總體流程。

2.1.1 應(yīng)用管理

本文中，集群的資源管理器根據(jù)應(yīng)用對計算資源的需求將應(yīng)用劃分為必須使用GPU資源，只需使用CPU資源和混合資源需求三類，并為三種類型的應(yīng)用分別維護一個應(yīng)用隊列。應(yīng)用被提交到集群中時，由資源管理器為該應(yīng)用創(chuàng)建一個ApplicationMaster，負責(zé)該應(yīng)用的資源請求并監(jiān)視任務(wù)的執(zhí)行進度。本文中，除了原有Hadoop+框架中的Map和Reduce任務(wù)的資源需求向量，單個Map任務(wù)的輸入數(shù)據(jù)分片大小，ApplicationMaster還負責(zé)為應(yīng)用提供基本特征描述：可以使用集群中的GPU資源執(zhí)行任務(wù)的應(yīng)用，需提供GPU_base任務(wù)的IO帶寬請求大小和GPU Kernel執(zhí)行時間；可以使用集群中的CPU資源執(zhí)行任務(wù)的應(yīng)用，需提供CPU_base任務(wù)的數(shù)據(jù)處理速率，并按應(yīng)用的資源需求提交到不同的隊列，以備調(diào)度執(zhí)行。

2.1.2 集群資源管理與調(diào)度

集群的資源管理器維護當前集群中的可用資源情況及各結(jié)點的總體IO請求大小及按優(yōu)先級排列的應(yīng)用隊列。集群的每個從結(jié)點啟動時，向集群的資源管理器注冊當前結(jié)點上可供Hadoop Yarn框架使用的資源，磁盤IO帶寬上限。集群中從結(jié)點的NodeManager通過心跳機制更新資源管理器中當前該結(jié)點上的可用資源，總體IO請求大小和發(fā)出IO資源請求的任務(wù)數(shù)，結(jié)點上執(zhí)行的任務(wù)的進度，并發(fā)出一個NODE_UPDATE事件，觸發(fā)資源調(diào)度器回收結(jié)點上已完成的任務(wù)的資源，用算法1所示的異構(gòu)動態(tài)親和性調(diào)度算法找到最適合在當前結(jié)點上運行的一個應(yīng)用的任務(wù)，分派到該結(jié)點上執(zhí)行。應(yīng)用的ApplicationMaster通過周期性的心跳得到任務(wù)分派結(jié)果，并與相應(yīng)的結(jié)點通信，進行任務(wù)的資源本地化，啟動任務(wù)執(zhí)行。

圖5 異構(gòu)動態(tài)親和性調(diào)度流程

2.2 異構(gòu)動態(tài)親和性調(diào)度算法

不同于虛擬化環(huán)境中對進程的親和性調(diào)度需要將其綁定到固定的邏輯CPU上，本文中，每個GPU任務(wù)分配到的GPU資源與平臺上實際的設(shè)備綁定，而CPU資源則不與邏輯CPU綁定，由操作系統(tǒng)完成平臺上CPU間的進程調(diào)度和負載均衡。具體地，資源管理器收到從結(jié)點的NodeManager匯報的該結(jié)點上的資源可用情況和結(jié)點上的任務(wù)執(zhí)行情況后，更新資源并發(fā)出NODE_UPDATE事件，觸發(fā)資源調(diào)度器進行調(diào)度，詳見算法1。

算法1 異構(gòu)動態(tài)親和性調(diào)度算法輸入：結(jié)點的可用資源A=，IO帶寬上限 總體IO請求大小(TotalIO)； 發(fā)起IO請求的任務(wù)數(shù)(#IOtask) 按優(yōu)先級高低排列的應(yīng)用調(diào)度隊列調(diào)度算法：1． Foreachpriority2． While(結(jié)點上有可用GPU)3． Foreach(純GPU資源需求/混合資源需求隊列中可調(diào)度的應(yīng)用)4． 根據(jù)式(1)-(3)預(yù)測應(yīng)用的新任務(wù)在當前資源使用情況下的數(shù)據(jù)處理速度5． endFor6． 按新任務(wù)數(shù)據(jù)處理速度延遲最小、已執(zhí)行GPU任務(wù)數(shù)最少、純GPU資源需求的應(yīng)用優(yōu)先，Ap?plicationMaster啟動時間早的應(yīng)用優(yōu)先的原則選擇一個應(yīng)用的任務(wù)執(zhí)行7． 更新結(jié)點上的可用資源，TotalIO，#IOtask8． endWhile9． While(結(jié)點上有可用資源)10． Foreach(純CPU資源需求/混合資源需求隊列中可調(diào)度的應(yīng)用)11． 使用公式(6)計算應(yīng)用的相對進度；12． 根據(jù)公式(1)-(3)預(yù)測應(yīng)用的新任務(wù)在當前資源使用情況下的數(shù)據(jù)處理速度13． endFor14． 按相對進度最慢、新任務(wù)的預(yù)計數(shù)據(jù)處理速度占它獨占系統(tǒng)時的最大數(shù)據(jù)處理速度的比例最大的、純CPU資源需求的應(yīng)用優(yōu)先的原則選擇一個應(yīng)用的任務(wù)調(diào)度執(zhí)行15． 更新結(jié)點上的可用資源，TotalIO，#IOtask16． endWhile17． endFor

通常情況下，CPU任務(wù)使用的是傳統(tǒng)Hadoop實現(xiàn)，任務(wù)的數(shù)據(jù)讀取和相應(yīng)的計算交替進行，對系統(tǒng)的IO資源需求較低，對集群中的共享資源競爭不敏感；而GPU任務(wù)為了高效利用GPU資源，則需先完成數(shù)據(jù)讀取，再將整個數(shù)據(jù)分片中的數(shù)據(jù)傳送到GPU上計算，任務(wù)在開始執(zhí)行階段會對系統(tǒng)有明顯的IO資源請求。同一應(yīng)用的任務(wù)在異構(gòu)平臺上的程序行為具有明顯的不對稱性。算法1中，本文采用了兩種不同的策略計算應(yīng)用與資源的實時親和性，分派使用不同資源的任務(wù)。

2.2.1 GPU資源分配策略

資源調(diào)度器根據(jù)結(jié)點的總體IO請求大小和當前結(jié)點上發(fā)出IO請求的任務(wù)數(shù)和異構(gòu)任務(wù)模型，預(yù)測應(yīng)用隊列中各應(yīng)用的新GPU任務(wù)的數(shù)據(jù)處理速度，選擇在當前系統(tǒng)資源使用情況下，新任務(wù)相對于其GPU_base任務(wù)延遲最小的應(yīng)用的任務(wù)進行調(diào)度，并更新本次調(diào)度后該結(jié)點上的資源可用情況和總體IO請求大小，發(fā)起IO請求的任務(wù)數(shù)等相關(guān)信息。

此外，若多個應(yīng)用的任務(wù)所受性能影響程度相同，則按已執(zhí)行GPU任務(wù)數(shù)最少、純GPU資源需求的應(yīng)用優(yōu)先，ApplicationMaster啟動時間早的應(yīng)用優(yōu)先的原則選擇，避免GPU_base任務(wù)的IO請求較少的應(yīng)用的任務(wù)先被系統(tǒng)調(diào)度完，負載中只留下GPU_base任務(wù)對系統(tǒng)IO請求較大的應(yīng)用，出現(xiàn)無法通過調(diào)度優(yōu)化系統(tǒng)的IO資源競爭，影響系統(tǒng)的整體吞吐率的提升。

2.2.2 非GPU資源分配策略

分配非GPU資源時，我們定義應(yīng)用的相對進度如下式

(6)

所示，其中#(Alloc_task)是應(yīng)用在已經(jīng)被分派執(zhí)行的任務(wù)數(shù)，已經(jīng)被分派的任務(wù)數(shù)越多，則該應(yīng)用的相對進度越快。使用已分派的任務(wù)數(shù)而不是應(yīng)用的進度，避免系統(tǒng)傾向調(diào)度任務(wù)數(shù)較多的應(yīng)用；start_time是應(yīng)用的ApplicationMaster啟動時間，該時間越早，則該應(yīng)用的相對進度值越小，使得應(yīng)用在此次調(diào)度中優(yōu)先級越高，TCPU_base是應(yīng)用的CPU_base任務(wù)的執(zhí)行時間，該時間越短，則其相對進度值越小，說明該應(yīng)用的任務(wù)在CPU上的數(shù)據(jù)處理速度越快，在此次調(diào)度中應(yīng)該被優(yōu)先調(diào)度。

該分配策略使用相對進度而非動態(tài)優(yōu)先級，因為Hadoop系統(tǒng)中，一個應(yīng)用的優(yōu)先級為固定值，若變更應(yīng)用的優(yōu)先級，將影響GPU資源的調(diào)度。

使用該策略將選相對進度最慢且新任務(wù)在當前系統(tǒng)負載下數(shù)據(jù)處理速度與應(yīng)用獨占系統(tǒng)時所能達到的最優(yōu)數(shù)據(jù)處理速度比例最大的應(yīng)用的任務(wù)進行調(diào)度。這種策略能夠有效避免應(yīng)用由于其GPU_base任務(wù)對系統(tǒng)IO資源競爭較敏感，而在混合負載中又不是在CPU上所能獲得的相對性能最優(yōu)而一直得不到調(diào)度；又能在混合負載中選擇新任務(wù)不使用GPU就能獲得較為理想的性能的應(yīng)用，為其分配使用CPU資源，使得能在GPU上獲得較為明顯的性能提升的應(yīng)用的任務(wù)更多地使用GPU資源完成，提高系統(tǒng)的整體吞吐率，并保證系統(tǒng)中的所有應(yīng)用不被餓死。

每次調(diào)度都是根據(jù)系統(tǒng)的實時負載重新計算應(yīng)用與資源的親和性分配資源，使GPU任務(wù)執(zhí)行時最大程度地得到它在GPU上應(yīng)有的性能提升，又將GPU資源最大程度地留給負載中使用GPU資源能得到更大程度性能提升的應(yīng)用。

2.2.3 復(fù)雜度分析

由第2節(jié)的分析可知，應(yīng)用新任務(wù)在當前負載下的數(shù)據(jù)處理速度在O(1)時間內(nèi)求得，因此每個調(diào)度決策的最壞時間復(fù)雜度為O(n)，其中n為集群混合負載中的應(yīng)用個數(shù)。

由于本文對不同資源需求的應(yīng)用分隊列管理且Hadoop2.6以上版本中引入了基于標簽的調(diào)度[15]，各結(jié)點配置時可標記出本結(jié)點上的資源特征(如“有GPU”，等)，進一步減小了調(diào)度空間。

此外，在Hadoop 2.0及以上版本中，任務(wù)的調(diào)度和執(zhí)行是異步的，資源調(diào)度器異步地處理調(diào)度事件，在主結(jié)點進行資源分配和任務(wù)調(diào)度時不會阻塞正在執(zhí)行的任務(wù)，進一步減小了任務(wù)調(diào)度的開銷。

3 試驗與評價

3.1 試驗平臺與環(huán)境

試驗所用的異構(gòu)集群由1個主結(jié)點和6個從結(jié)點組成。每個從結(jié)點有一個Intel 2.00GHz Xeon E5-2620 CPU，含6個物理核，關(guān)閉超線程技術(shù)。每個結(jié)點有1TB SATA硬盤，最高讀/寫速率為128MB/s。每個從結(jié)點有4個NVIDIA Tesla C2050 GPU。調(diào)度器基于Hadoop+框架實現(xiàn)。由于Hadoop+框架中應(yīng)用的GPU任務(wù)和CPU任務(wù)的數(shù)據(jù)處理速度相差甚多，本試驗關(guān)閉Hadoop的任務(wù)推測執(zhí)行機制，以防運行在CPU上的任務(wù)總是被判定為落后任務(wù)，啟動備份任務(wù)的執(zhí)行，造成不必要的資源浪費。

試驗所用的負載是5個常見的機器學(xué)習(xí)算法(詳見表1)的不同組合：A-J是5個應(yīng)用的兩兩組合，如A是(KNN，K均值(Kmeans))的組合，B是(KNN，RS)的組合，依此類推，K-T是其中每3個應(yīng)用的組合，如K是(KNN，Kmeans，RS)的組合，L是(KNN，Kmeans，NB)的組合，依此類推，U-Y是其中每4個應(yīng)用的組合。

表1 基準程序集

3.2 整體性能評估

試驗比較了25種應(yīng)用的組合負載在先來先服務(wù)，基于異構(gòu)任務(wù)模型指導(dǎo)的資源分配調(diào)度策略和本文的異構(gòu)動態(tài)親和性調(diào)度算法相對于混合負載的Hadoop實現(xiàn)的總體加速比，如圖 6所示。異構(gòu)動態(tài)親和性調(diào)度算法在25個負載中的最高加速比為31.0x，平均加速比是21.9x，明顯優(yōu)于先來先服務(wù)策略的14.3x和基于異構(gòu)任務(wù)模型調(diào)度策略的17.9x。

圖6 Hadoop+中FIFO策略、基于異構(gòu)任務(wù)模型的調(diào)度策略和異構(gòu)動態(tài)親和性調(diào)度策略相對于Hadoop實現(xiàn)的整體加速比

負載C中兩種應(yīng)用的GPU任務(wù)都對系統(tǒng)IO需求較大且需讀取較多數(shù)據(jù)，資源競爭無法通過調(diào)度減緩，三種調(diào)度策略都只有不超過2.8x的加速比；負載I中兩種應(yīng)用的GPU任務(wù)單次所讀的數(shù)據(jù)都較少，隨著負載的執(zhí)行，瞬時高帶寬的數(shù)據(jù)讀取基本被錯開，三種策略都能通過引入GPU獲得大于21.0x的加速比；負載B, D都由一個GPU任務(wù)加速明顯更大且對系統(tǒng)IO需求小的應(yīng)用和一個GPU任務(wù)對系統(tǒng)IO資源需求大且數(shù)據(jù)讀取階段時間比例較高的應(yīng)用組成，異構(gòu)動態(tài)親和性調(diào)度和基于異構(gòu)任務(wù)模型的調(diào)度策略都更多地把GPU分給前者，比先來先服務(wù)調(diào)度策略能取得相近程度的性能提升；負載A, F, L中，幾種應(yīng)用的GPU任務(wù)都有較大IO資源需求而由系統(tǒng)IO競爭影響導(dǎo)致的延遲程度不同，這兩種調(diào)度策略都會把GPU更多地分配給延遲程度較小的任務(wù)，因此能比先來先服務(wù)調(diào)度策略取得相同程度的性能提升；對其他18種應(yīng)用的資源需求多樣性的負載，異構(gòu)動態(tài)親和性調(diào)度策略的性能提升則明顯優(yōu)于其他二者，因此在大規(guī)模數(shù)據(jù)中心中有良好的適用性。詳細分析見3.3和3.4節(jié)。

3.3 基準測試程序的任務(wù)特征分析

異構(gòu)動態(tài)親和性調(diào)度算法在分派任務(wù)時，應(yīng)用的GPU任務(wù)和CPU任務(wù)對系統(tǒng)的共享資源競爭敏感程度會影響它在每次調(diào)度所計算的動態(tài)親和性的排名，本節(jié)將簡要分析試驗所用5種應(yīng)用的任務(wù)特征。

圖7[8]是表1中所示的5個基準應(yīng)用在本研究的試驗平臺上的異構(gòu)任務(wù)的特征。圖中各種應(yīng)用的CPU_base任務(wù)(各簇中左邊的柱子)和GPU_base任務(wù)(各簇中右邊的柱子)的運行時間相對于每個應(yīng)用的CPU_base任務(wù)進行了歸一化。由圖 7可以看出，KNN、Kmeans，NB應(yīng)用的GPU_base任務(wù)都有較高的系統(tǒng)IO需求，但三者的數(shù)據(jù)讀取時間分別占其任務(wù)的執(zhí)行時間的82.8%，24.0%和53.9%，因此，三者由于與其他任務(wù)競爭系統(tǒng)IO，導(dǎo)致數(shù)據(jù)讀取階段延遲的比例也不同。

圖7 基準測試程序的任務(wù)特征

相對而言，RS、BP應(yīng)用的CPU_base任務(wù)所需讀取的數(shù)據(jù)量較小，任務(wù)中計算階段的執(zhí)行時間占主導(dǎo)，對共享集群中IO資源競爭不敏感。因此，若負載中的應(yīng)用都屬于以上同一類(如A, C, F, I, L)或是兩種類型中的應(yīng)用各占其一且前一類應(yīng)用的GPU_base任務(wù)的執(zhí)行時間中數(shù)據(jù)讀取階段比例較高(如B，D)，則基于異構(gòu)的任務(wù)模型的資源調(diào)度和異構(gòu)動態(tài)親和性調(diào)度有幾乎相同的調(diào)度結(jié)果，所獲得的性能提升也相同。其他情況下，異構(gòu)動態(tài)親和性調(diào)度算法的性能提升更為明顯。

3.4 三種調(diào)度策略的效果分析

圖8是基于異構(gòu)任務(wù)模型的資源分配調(diào)度策略和異構(gòu)動態(tài)親和性調(diào)度策略相對于先來先服務(wù)調(diào)度策略的混合負載執(zhí)行時間(歸一化到每個負載在先來先服務(wù)調(diào)度策略下的執(zhí)行時間)?；诋悩?gòu)任務(wù)模型的資源分配調(diào)度策略相對于先來先服務(wù)調(diào)度策略最多減少35.7%，平均減少18.7%的運行時間，異構(gòu)動態(tài)親和性調(diào)度策略相對于先來先服務(wù)的調(diào)度策略最多減少50.5%，平均減少33.6%的運行時間。

圖8 Hadoop+中先來先服務(wù)策略，基于異構(gòu)任務(wù)模型的調(diào)度策略和異構(gòu)動態(tài)親和性調(diào)度策略下負載的歸一化運行時間

由1.2節(jié)的分析可知，基于異構(gòu)任務(wù)模型的資源分配調(diào)度策略更傾向于把集群中的GPU資源分配給混合負載中使用GPU資源能獲得更高加速比的應(yīng)用，但這種分配策略不會避免把具有較高IO資源需求的GPU任務(wù)同時或在較短的時間間隔內(nèi)分派到同一個結(jié)點上執(zhí)行，因此，相同應(yīng)用內(nèi)的對系統(tǒng)IO需求較大的任務(wù)之間由于對IO資源的競爭導(dǎo)致單個任務(wù)的運行時間延長的概率較大，在本文試驗的25種混合負載中所有任務(wù)的平均延遲為1.6x。相對來說，異構(gòu)動態(tài)親和性調(diào)度策略則能根據(jù)資源管理器中所記錄的該結(jié)點上的負載和資源可用情況，把資源公平地分配給預(yù)計調(diào)度后任務(wù)執(zhí)行時間延遲最少者，從而減少每個被調(diào)度的任務(wù)相對于它單獨在該結(jié)點上運行時的性能下降。本試驗的25種混合負載中所有任務(wù)的平均延遲僅為1.2x，對其中的21種負載，所有任務(wù)的平均延遲都在的范圍內(nèi)，如圖9所示。

混合負載C中，三種策略使任務(wù)的執(zhí)行時間分別延長了3.0x，3.0x和2.9x。這是由于該負載中的KNN和NB應(yīng)用的GPU_base任務(wù)中的數(shù)據(jù)讀取階段的任務(wù)執(zhí)行時間都大于50%，因此對系統(tǒng)的IO資源的競爭無法通過調(diào)度明顯減小，導(dǎo)致分配了GPU資源執(zhí)行的任務(wù)的性能提升有限。此負載執(zhí)行周期的資源使用情況與圖3的前一階段和圖4的后一階段相同(由于NB應(yīng)用的GPU_base任務(wù)中數(shù)據(jù)執(zhí)行階段的執(zhí)行時間所占比例比KNN應(yīng)用小，異構(gòu)動態(tài)親和性調(diào)度會有與基于異構(gòu)任務(wù)模型的調(diào)度有近似的資源分配結(jié)果)?；旌县撦dI中，RS和BP應(yīng)用的任務(wù)都是對系統(tǒng)IO需求較小的，任務(wù)幾乎沒有因共享資源競爭導(dǎo)致的延遲。負載的執(zhí)行周期中IO資源利用率低，但GPU資源使用充分。對于負載A，B，D，F(xiàn)，由于負載中的應(yīng)用的GPU任務(wù)在共享資源競爭時延遲比例差異較大，基于異構(gòu)任務(wù)模型的調(diào)度和異構(gòu)動態(tài)親和性調(diào)度都會把GPU分配給延遲較小者，因此相對于FIFO調(diào)度減小了任務(wù)的平均延遲。

圖9 Hadoop+中先來先服務(wù)策略，基于異構(gòu)任務(wù)模型的調(diào)度策略和異構(gòu)動態(tài)親和性調(diào)度策略下單個任務(wù)的平均延遲

在其他18個負載中，異構(gòu)動態(tài)親和性調(diào)度的平均任務(wù)延遲則明顯小于另外兩種調(diào)度策略，仍以負載P為例，負載的執(zhí)行周期中，異構(gòu)動態(tài)親和性調(diào)度能讓對系統(tǒng)IO資源需求大小不一的BP應(yīng)用和NB應(yīng)用的GPU任務(wù)交替執(zhí)行(NB應(yīng)用的GPU任務(wù)會在系統(tǒng)負載較低時由于任務(wù)基本不被延遲而被調(diào)度執(zhí)行)，而KNN應(yīng)用的所有任務(wù)都被分配到CPU上執(zhí)行，這樣，就能使整個負載的執(zhí)行周期中GPU資源和IO資源的使用一直較為充分，如圖10所示。

圖10 異構(gòu)動態(tài)親和性調(diào)度策略下實時IO和GPU使用情況

4 結(jié) 論

經(jīng)典多處理器上的作業(yè)最優(yōu)化調(diào)度是NP-hard的[19]，本文使用Hadoop+的異構(gòu)任務(wù)模型，提出了異構(gòu)動態(tài)親和性調(diào)度算法，根據(jù)系統(tǒng)實時負載，選擇與當前可用資源的親和性最高的備調(diào)度任務(wù)，減少混合負載中的任務(wù)由于共享資源競爭導(dǎo)致的延遲，使負載的執(zhí)行周期中系統(tǒng)資源保持較高的使用率，提高系統(tǒng)吞吐率。在本文的試驗平臺上對25種混合應(yīng)用負載相對于Hadoop框架中的實現(xiàn)取得了最高為31.0x，平均為21.9x的加速比，并把混合負載中的單個任務(wù)的平均執(zhí)行時間減少為任務(wù)獨占系統(tǒng)時的1.2x(其中21個負載不超過1.06x)，在任務(wù)對系統(tǒng)資源需求多樣性豐富的混合負載上優(yōu)化效果明顯。未來工作中將研究集群中有多種加速器導(dǎo)致結(jié)點間異構(gòu)的情況，如何合理分配資源，有效提高系統(tǒng)吞吐率。

[1] He B, Fang W, Luo Q, et al. Mars: a MapReduce framework on graphics processors. In: Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques,New York, USA, 2008.260-269

[2] Hong C, Chen D, Chen W, et al. MapCG: writing parallel program portable between CPU and GPU. In: Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques, New York, USA, 2010. 217-226

[3] Grossman M, Breternitz M, Sarkar, V, HadoopCL: MapReduce on distributed heterogeneous platforms through seamless integration of Hadoop and OpenCL, In: Proceedings of the 27th IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, Washington, DC, USA, 2013. 1918-1927

[4] Xin M, Li H, An implementation of GPU accelerated MapReduce: using Hadoop with OpenCL for data- and compute-intensive jobs. In: Proceedings of the 2012 International Joint Conference on Service Sciences, Shanghai, China, 2012. 6-11

[5] Okur S, Radio C, Lin Y. Hadoop+Aparapi: making heterogeneous mapreduce programming easier. http://hgpu.org/?p=7413: HGPU, 2012

[6] El-Helw I,Hofman R,Bal H, Scaling MapReduce vertically and horizontally. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Piscataway, USA, 2014. 525-535

[7] Grossman, M, Breternitz M, Sarkar V. HadoopCL2: motivating the design of a distributed, heterogeneous programming system with machine-learning applications.IEEETransactionsonParallelandDistributedSystems, 2015, 27(3): 1-1

[8] He W, Cui H, Lu B, et al. Hadoop+: Modeling and evaluating the heterogeneity for MapReduce applications in heterogeneous clusters. In: Proceedings of the 29th ACM on International Conference on Supercomputing, New York, USA, 2015. 143-153

[9] Zaharia M, Konwinski A, Joseph A, et al. Improving mapreduce performance in heterogeneous environments. In: Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, Berkeley, USA, 2008. 29-42

[10] Chen Q, Zhang D, Guo M, et al. SAMR: A self-adaptive MapReduce scheduling algorithm in heterogeneous environment. In: Proceedings of the 10th IEEE International Conference on Computer and Information Technology, Washington, DC, USA, 2010. 2736-2743

[11] Sun X, He C, Lu Y, ESAMR: an enhanced self-adaptive MapReduce scheduling algorithm. In: Proceedings of the 18th IEEE International Conference on Parallel and Distributed Systems, Singapore, 2012. 148-155

[12] Tian C, Zhou H, He Y, et al. A dynamic MapReduce scheduler for heterogeneous workloads. In: Proceedings of the 8th International Conference on Grid and Cooperative Computing, Washington, DC, USA, 2009. 218-224

[13] Schirahata K, Sato H, Matsuoka S. Hybrid map task scheduling for GPU-based heterogeneous clusters. In: Proceedings of the 2nd IEEE International Conference on Cloud Computing Technology and Science, Washington, DC, USA, 2010. 733-740

[14] Ghodsi A, Zaharia M, Hindman B, et al. Dominant resource fairness: fair allocation of multiple resource types. In: Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, Berkeley, USA, 2011. 323-336

[15] Label-Based Scheduling for Hadoop Clusters. https://www.mapr.com/blog/label-based-scheduling-hadoop-clusters:MAPR.Blog, 2014

[16] Cover T, Hart P. Nearest neighbor pattern classification.IEEETransactionsonInformationTheory, 2006, 13(1):21-27

[17] Apache mahout. http://mahout.apache.org: Apache Software Foundation, 2014

[18] Liu Z, Li H, Miao G. Mapreduce-based back-propagation neural network over large scale mobile data. In: Proceedings of the International Conference on Neural Computation, Valencia, Spain, 2010. 1726-1730

[19] Garey M, Johnson D. Computers & Intractability: Aguide to the Theory of NP-Completeness. New York, NY, USA:W. H. Freeman & Co. 1990. 238

HDAS：heterogeneous dynamic affinity scheduling in Hadoop+

He Wenting******, Cui Huimin***, Feng Xiaobing***

(*State Key Laboratory of Computer Architecture, Chinese Academy of Sciences, Beijing 100190)(**Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)(***University of Chinese Academy of Sciences, Beijing 100049)

Aiming at the problem that the existing programming frameworks for heterogeneous clusters focus on utilizing heterogeneous resources in clusters while ignoring the delay of the working time caused by the contention of shared resources, this study proposed and implemented the heterogeneous dynamic affinity scheduling (HDAS) algorithm based on the Hadoop+ and the heterogeneity model, which dynamically calculates the real-time resource affinity of each available task according to the corresponding strategy of each resource and dispatches the most appropriate task launch in the system within a reasonable time to minimize the shared resource contention among simultaneously running tasks to improve the overall throughput of the system. The experimental result showed an average 21.9x overall speedup of the HDAS compared to the Hadoop implementation on 25 hybrid workloads, while the original heterogeneous model based scheduling strategy in Hadoop only obtained 17.9x speedup. And it showed obvious improvement on the hybrid workloads consisting of the tasks with more diverse resource requirements, and 21 of the 25 workloads presented the task delay of less than 1.06x in average.

MapReduce, heterogeneous, Hadoop+, affinity, scheduling

10.3772/j.issn.1002-0470.2016.04.002

①973計劃(2011CB302504)，863計劃(2012AA010902， 2015AA011505)和國家自然科學(xué)基金(61202055，61221062，61303053，61432016，61402445)資助項目。

，E-mail: huimin.cui@gmail.com(

2015-12-21)

②女，1988年生，博士生；研究方向：計算機系統(tǒng)結(jié)構(gòu)；E-mail: hewenting@ict.ac.cn