• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2016-12-06 05:18:50何文婷崔慧敏馮曉兵
    高技術(shù)通訊 2016年4期
    關(guān)鍵詞:親和性結(jié)點(diǎn)異構(gòu)

    何文婷 崔慧敏 馮曉兵

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

    ?

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

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

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

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

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

    0 引 言

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

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

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

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

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

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

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

    對于混合負(fù)載,該模型根據(jù)各應(yīng)用通過GPU得到的性能提升高低依次將GPU分給各應(yīng)用。但若應(yīng)用的GPU任務(wù)對系統(tǒng)的IO需求較大,則同時運(yùn)行的任務(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ù)和單獨(dú)運(yùn)行的GPU(記作GPU_base)任務(wù)的各階段執(zhí)行時間和系統(tǒng)實(shí)時負(fù)載準(zhǔn)確預(yù)測異構(gòu)任務(wù)(根據(jù)其使用的資源,下文分別記作CPU任務(wù)和GPU任務(wù))在共享資源競爭下的數(shù)據(jù)處理速度,以及應(yīng)用在當(dāng)前的系統(tǒng)中所能達(dá)到的最優(yōu)數(shù)據(jù)處理速度。此處,單個的任務(wù)數(shù)據(jù)處理速度(dps)可以用下式計(jì)算,

    (1)

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

    (2)

    其中tpc0和tpg0分別是應(yīng)用的CPU_base任務(wù)和GPU_base任務(wù)的計(jì)算時間,由文獻(xiàn)[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)用的混合負(fù)載時,先根據(jù)公式

    (4)

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

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

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

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

    (5)

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

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

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

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

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

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

    圖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ù)的完成時間長,則會延長負(fù)載的整體完成時間。

    使用基于異構(gòu)任務(wù)模型的資源分配策略指導(dǎo)的調(diào)度算法運(yùn)行負(fù)載P時,調(diào)度器優(yōu)先分配GPU資源給BP應(yīng)用的任務(wù),并在KNN和NB應(yīng)用間公平分配分配非GPU資源執(zhí)行,當(dāng)BP應(yīng)用的所有任務(wù)執(zhí)行結(jié)束后,再將NB應(yīng)用的剩余任務(wù)分派到GPU上執(zhí)行,將系統(tǒng)的其余資源分配給KNN應(yīng)用,完成其余下的任務(wù)。因此,負(fù)載執(zhí)行的初始階段,單個BP應(yīng)用的任務(wù)對系統(tǒng)IO資源需求不大,系統(tǒng)的IO負(fù)載很低(如圖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)度時,雖然混合負(fù)載中用GPU加速效果更為明顯的BP應(yīng)用和NB應(yīng)用有更高比例的任務(wù)分配到GPU資源,但整個負(fù)載的運(yùn)行周期中,IO資源和GPU資源的使用不夠均勻,系統(tǒng)中階段性的共享資源競爭限制了混合負(fù)載的整體性能提升。對比圖 3和圖 4,可以發(fā)現(xiàn)兩種調(diào)度策略對資源的使用情況基本都可被明顯地分為幾個階段,每個階段中都有使用不夠充分的系統(tǒng)資源(GPU/IO)兩種資源調(diào)度策略都不能保持執(zhí)行周期中各時段的資源被充分使用。

    1.4 小結(jié)

    由1.2、1.3節(jié)的例子看出,當(dāng)系統(tǒng)的負(fù)載應(yīng)用種類增多時,已有的資源分配策略不能很好地感知系統(tǒng)中的實(shí)時負(fù)載,并根據(jù)系統(tǒng)的實(shí)時負(fù)載和系統(tǒng)中的任務(wù)特征調(diào)整調(diào)度策略,因此,需要根據(jù)系統(tǒng)的實(shí)時負(fù)載調(diào)整資源的新的分配策略,減少同時運(yùn)行的任務(wù)對系統(tǒng)中共享資源的競爭,提高負(fù)載執(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)用對計(jì)算資源的需求將應(yīng)用劃分為必須使用GPU資源,只需使用CPU資源和混合資源需求三類,并為三種類型的應(yīng)用分別維護(hù)一個應(yīng)用隊(duì)列。應(yīng)用被提交到集群中時,由資源管理器為該應(yīng)用創(chuàng)建一個ApplicationMaster,負(fù)責(zé)該應(yīng)用的資源請求并監(jiān)視任務(wù)的執(zhí)行進(jìn)度。本文中,除了原有Hadoop+框架中的Map和Reduce任務(wù)的資源需求向量,單個Map任務(wù)的輸入數(shù)據(jù)分片大小,ApplicationMaster還負(fù)責(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)用的資源需求提交到不同的隊(duì)列,以備調(diào)度執(zhí)行。

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

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

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

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

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

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

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

    2.2.1 GPU資源分配策略

    資源調(diào)度器根據(jù)結(jié)點(diǎn)的總體IO請求大小和當(dāng)前結(jié)點(diǎn)上發(fā)出IO請求的任務(wù)數(shù)和異構(gòu)任務(wù)模型,預(yù)測應(yīng)用隊(duì)列中各應(yīng)用的新GPU任務(wù)的數(shù)據(jù)處理速度,選擇在當(dāng)前系統(tǒng)資源使用情況下,新任務(wù)相對于其GPU_base任務(wù)延遲最小的應(yīng)用的任務(wù)進(jìn)行調(diào)度,并更新本次調(diào)度后該結(jié)點(diǎn)上的資源可用情況和總體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)度完,負(fù)載中只留下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)用的相對進(jìn)度如下式

    (6)

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

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

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

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

    2.2.3 復(fù)雜度分析

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

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

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

    3 試驗(yàn)與評價(jià)

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

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

    試驗(yàn)所用的負(fù)載是5個常見的機(jī)器學(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 基準(zhǔn)程序集

    3.2 整體性能評估

    試驗(yàn)比較了25種應(yīng)用的組合負(fù)載在先來先服務(wù),基于異構(gòu)任務(wù)模型指導(dǎo)的資源分配調(diào)度策略和本文的異構(gòu)動態(tài)親和性調(diào)度算法相對于混合負(fù)載的Hadoop實(shí)現(xiàn)的總體加速比,如圖 6所示。異構(gòu)動態(tài)親和性調(diào)度算法在25個負(fù)載中的最高加速比為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實(shí)現(xiàn)的整體加速比

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

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

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

    圖7[8]是表1中所示的5個基準(zhǔn)應(yīng)用在本研究的試驗(yàn)平臺上的異構(gòu)任務(wù)的特征。圖中各種應(yīng)用的CPU_base任務(wù)(各簇中左邊的柱子)和GPU_base任務(wù)(各簇中右邊的柱子)的運(yùn)行時間相對于每個應(yīng)用的CPU_base任務(wù)進(jìn)行了歸一化。由圖 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 基準(zhǔn)測試程序的任務(wù)特征

    相對而言,RS、BP應(yīng)用的CPU_base任務(wù)所需讀取的數(shù)據(jù)量較小,任務(wù)中計(jì)算階段的執(zhí)行時間占主導(dǎo),對共享集群中IO資源競爭不敏感。因此,若負(fù)載中的應(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)度策略的混合負(fù)載執(zhí)行時間(歸一化到每個負(fù)載在先來先服務(wù)調(diào)度策略下的執(zhí)行時間)?;诋悩?gòu)任務(wù)模型的資源分配調(diào)度策略相對于先來先服務(wù)調(diào)度策略最多減少35.7%,平均減少18.7%的運(yùn)行時間,異構(gòu)動態(tài)親和性調(diào)度策略相對于先來先服務(wù)的調(diào)度策略最多減少50.5%,平均減少33.6%的運(yùn)行時間。

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

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

    混合負(fù)載C中,三種策略使任務(wù)的執(zhí)行時間分別延長了3.0x,3.0x和2.9x。這是由于該負(fù)載中的KNN和NB應(yīng)用的GPU_base任務(wù)中的數(shù)據(jù)讀取階段的任務(wù)執(zhí)行時間都大于50%,因此對系統(tǒng)的IO資源的競爭無法通過調(diào)度明顯減小,導(dǎo)致分配了GPU資源執(zhí)行的任務(wù)的性能提升有限。此負(fù)載執(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é)果)?;旌县?fù)載I中,RS和BP應(yīng)用的任務(wù)都是對系統(tǒng)IO需求較小的,任務(wù)幾乎沒有因共享資源競爭導(dǎo)致的延遲。負(fù)載的執(zhí)行周期中IO資源利用率低,但GPU資源使用充分。對于負(fù)載A,B,D,F(xiàn),由于負(fù)載中的應(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個負(fù)載中,異構(gòu)動態(tài)親和性調(diào)度的平均任務(wù)延遲則明顯小于另外兩種調(diào)度策略,仍以負(fù)載P為例,負(fù)載的執(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)負(fù)載較低時由于任務(wù)基本不被延遲而被調(diào)度執(zhí)行),而KNN應(yīng)用的所有任務(wù)都被分配到CPU上執(zhí)行,這樣,就能使整個負(fù)載的執(zhí)行周期中GPU資源和IO資源的使用一直較為充分,如圖10所示。

    圖10 異構(gòu)動態(tài)親和性調(diào)度策略下實(shí)時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)實(shí)時負(fù)載,選擇與當(dāng)前可用資源的親和性最高的備調(diào)度任務(wù),減少混合負(fù)載中的任務(wù)由于共享資源競爭導(dǎo)致的延遲,使負(fù)載的執(zhí)行周期中系統(tǒng)資源保持較高的使用率,提高系統(tǒng)吞吐率。在本文的試驗(yàn)平臺上對25種混合應(yīng)用負(fù)載相對于Hadoop框架中的實(shí)現(xiàn)取得了最高為31.0x,平均為21.9x的加速比,并把混合負(fù)載中的單個任務(wù)的平均執(zhí)行時間減少為任務(wù)獨(dú)占系統(tǒng)時的1.2x(其中21個負(fù)載不超過1.06x),在任務(wù)對系統(tǒng)資源需求多樣性豐富的混合負(fù)載上優(yōu)化效果明顯。未來工作中將研究集群中有多種加速器導(dǎo)致結(jié)點(diǎn)間異構(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計(jì)劃(2011CB302504),863計(jì)劃(2012AA010902, 2015AA011505)和國家自然科學(xué)基金(61202055,61221062,61303053,61432016,61402445)資助項(xiàng)目。

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

    2015-12-21)

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

    猜你喜歡
    親和性結(jié)點(diǎn)異構(gòu)
    試論同課異構(gòu)之“同”與“異”
    部分薔薇與現(xiàn)代月季雜交親和性研究
    園林科技(2021年1期)2022-01-19 03:13:54
    ‘富有’甜柿砧木種質(zhì)早期親和性研究
    中國果樹(2020年2期)2020-07-25 02:14:22
    荔枝高接品種的選擇
    Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個數(shù)估計(jì)
    不結(jié)球白菜與西洋菜遠(yuǎn)緣雜交親和性研究
    overlay SDN實(shí)現(xiàn)異構(gòu)兼容的關(guān)鍵技術(shù)
    LTE異構(gòu)網(wǎng)技術(shù)與組網(wǎng)研究
    在新興異構(gòu)SoCs上集成多種系統(tǒng)
    基于Raspberry PI為結(jié)點(diǎn)的天氣云測量網(wǎng)絡(luò)實(shí)現(xiàn)
    午夜激情av网站| 高清黄色对白视频在线免费看| 只有这里有精品99| 制服人妻中文乱码| 欧美日韩av久久| 涩涩av久久男人的天堂| 蜜桃在线观看..| 亚洲欧美精品自产自拍| 成人国语在线视频| 国产精品久久久久成人av| 熟妇人妻不卡中文字幕| 成年人免费黄色播放视频| 1024视频免费在线观看| 丰满乱子伦码专区| 午夜激情av网站| 久久狼人影院| 精品免费久久久久久久清纯 | 国产亚洲欧美精品永久| 日韩免费高清中文字幕av| 男人舔女人的私密视频| 成人免费观看视频高清| 日韩不卡一区二区三区视频在线| 热re99久久国产66热| 女的被弄到高潮叫床怎么办| 九草在线视频观看| 精品国产乱码久久久久久小说| 黑人欧美特级aaaaaa片| 亚洲精品中文字幕在线视频| 欧美激情 高清一区二区三区| 国产精品 国内视频| 中文精品一卡2卡3卡4更新| 日日摸夜夜添夜夜爱| 久久 成人 亚洲| 欧美日本中文国产一区发布| 国产午夜精品一二区理论片| 18禁国产床啪视频网站| 精品人妻在线不人妻| 亚洲精品久久成人aⅴ小说| av在线老鸭窝| 成年动漫av网址| 99国产精品免费福利视频| 国产成人一区二区在线| 国产一区二区三区综合在线观看| 永久免费av网站大全| 国产欧美日韩综合在线一区二区| 十分钟在线观看高清视频www| 又粗又硬又长又爽又黄的视频| 中文精品一卡2卡3卡4更新| 久久ye,这里只有精品| 国产成人av激情在线播放| 久久人人爽av亚洲精品天堂| 国产97色在线日韩免费| 国产片内射在线| 欧美中文综合在线视频| 国产精品欧美亚洲77777| 久久人人爽av亚洲精品天堂| 美女扒开内裤让男人捅视频| 久久人人爽人人片av| 国产精品99久久99久久久不卡 | 欧美激情高清一区二区三区 | 免费不卡黄色视频| 亚洲成人国产一区在线观看 | 黄色一级大片看看| 亚洲人成电影观看| 亚洲免费av在线视频| 男女国产视频网站| 精品一区在线观看国产| 国产成人av激情在线播放| 黄色怎么调成土黄色| 在线观看国产h片| 啦啦啦在线免费观看视频4| 2021少妇久久久久久久久久久| 一区二区三区激情视频| 国产精品久久久人人做人人爽| 国产高清不卡午夜福利| av在线观看视频网站免费| 国产一区二区在线观看av| 多毛熟女@视频| 99九九在线精品视频| 亚洲一区中文字幕在线| 久久久精品免费免费高清| 国产片内射在线| 日本欧美国产在线视频| 最近中文字幕2019免费版| 国产一卡二卡三卡精品 | 亚洲三区欧美一区| 好男人视频免费观看在线| av天堂久久9| 日韩伦理黄色片| 亚洲av中文av极速乱| 午夜福利免费观看在线| 黄色视频不卡| 熟女av电影| 久久国产精品男人的天堂亚洲| 国产深夜福利视频在线观看| 欧美 日韩 精品 国产| 亚洲精品日本国产第一区| 久久ye,这里只有精品| 99香蕉大伊视频| 黄片无遮挡物在线观看| 18在线观看网站| 国产精品 国内视频| 最近中文字幕2019免费版| 午夜福利免费观看在线| 国产精品国产av在线观看| 天天躁狠狠躁夜夜躁狠狠躁| 国产爽快片一区二区三区| 一区二区三区激情视频| 欧美日韩精品网址| av女优亚洲男人天堂| 中文字幕精品免费在线观看视频| 天天躁日日躁夜夜躁夜夜| 在线观看免费高清a一片| √禁漫天堂资源中文www| 在线观看三级黄色| 亚洲欧美成人综合另类久久久| 麻豆av在线久日| 满18在线观看网站| 精品免费久久久久久久清纯 | 99热国产这里只有精品6| 男人操女人黄网站| 一区二区三区精品91| 天天躁夜夜躁狠狠久久av| 亚洲精品aⅴ在线观看| 欧美日韩亚洲综合一区二区三区_| 91精品三级在线观看| 国产又色又爽无遮挡免| 精品一品国产午夜福利视频| 日韩精品免费视频一区二区三区| 十八禁高潮呻吟视频| 韩国精品一区二区三区| 国产日韩欧美亚洲二区| 亚洲图色成人| 老汉色∧v一级毛片| 狂野欧美激情性bbbbbb| 国语对白做爰xxxⅹ性视频网站| 咕卡用的链子| 妹子高潮喷水视频| 国产片特级美女逼逼视频| 女人被躁到高潮嗷嗷叫费观| 亚洲精华国产精华液的使用体验| 欧美变态另类bdsm刘玥| 亚洲精品一区蜜桃| tube8黄色片| 美女中出高潮动态图| 国产日韩欧美在线精品| 国产淫语在线视频| 国产免费现黄频在线看| 男女床上黄色一级片免费看| 秋霞伦理黄片| 国产成人一区二区在线| 久久精品国产a三级三级三级| 国产亚洲一区二区精品| av国产久精品久网站免费入址| 成人18禁高潮啪啪吃奶动态图| 色吧在线观看| 成人漫画全彩无遮挡| 制服人妻中文乱码| 亚洲情色 制服丝袜| 免费久久久久久久精品成人欧美视频| 少妇的丰满在线观看| 亚洲av男天堂| 91国产中文字幕| 黄片无遮挡物在线观看| 日韩伦理黄色片| 精品一区二区免费观看| 色婷婷av一区二区三区视频| 国产精品秋霞免费鲁丝片| 菩萨蛮人人尽说江南好唐韦庄| 欧美日韩视频精品一区| 中文字幕人妻熟女乱码| 日本午夜av视频| 99久久精品国产亚洲精品| 可以免费在线观看a视频的电影网站 | 制服诱惑二区| 亚洲国产欧美一区二区综合| 黄片无遮挡物在线观看| 国产精品久久久久久人妻精品电影 | 亚洲色图 男人天堂 中文字幕| 制服诱惑二区| 日本wwww免费看| 观看av在线不卡| 免费观看a级毛片全部| 日韩伦理黄色片| 最新在线观看一区二区三区 | 亚洲av综合色区一区| 国产精品国产av在线观看| 丝袜美腿诱惑在线| 汤姆久久久久久久影院中文字幕| 精品一区二区三区四区五区乱码 | 日本wwww免费看| 国产激情久久老熟女| 日日摸夜夜添夜夜爱| 美女国产高潮福利片在线看| 国产爽快片一区二区三区| 久久天堂一区二区三区四区| 伦理电影大哥的女人| 最新的欧美精品一区二区| 色婷婷av一区二区三区视频| 欧美日韩视频高清一区二区三区二| 下体分泌物呈黄色| 欧美在线黄色| 中文字幕人妻丝袜制服| 亚洲情色 制服丝袜| 国产亚洲精品第一综合不卡| 两性夫妻黄色片| 欧美日韩国产mv在线观看视频| 久久精品aⅴ一区二区三区四区| 日本色播在线视频| 亚洲精品日本国产第一区| 老汉色av国产亚洲站长工具| 国产一区亚洲一区在线观看| 男人舔女人的私密视频| 色精品久久人妻99蜜桃| netflix在线观看网站| 一区二区日韩欧美中文字幕| 性少妇av在线| 欧美亚洲日本最大视频资源| 欧美在线一区亚洲| 午夜福利视频精品| 18禁国产床啪视频网站| 可以免费在线观看a视频的电影网站 | 久久精品人人爽人人爽视色| 久久久久精品国产欧美久久久 | 精品国产国语对白av| 精品一区二区三卡| 视频区图区小说| 日韩 亚洲 欧美在线| h视频一区二区三区| 国产国语露脸激情在线看| 亚洲国产精品成人久久小说| 女性生殖器流出的白浆| 一边亲一边摸免费视频| 男女午夜视频在线观看| 国产精品一国产av| 不卡av一区二区三区| 久久鲁丝午夜福利片| 日本猛色少妇xxxxx猛交久久| 亚洲精品国产av蜜桃| 久久99一区二区三区| av在线播放精品| 成年动漫av网址| 国产极品粉嫩免费观看在线| 亚洲精品第二区| 在线天堂最新版资源| 精品少妇久久久久久888优播| 在线观看一区二区三区激情| 日韩不卡一区二区三区视频在线| 老汉色∧v一级毛片| 男的添女的下面高潮视频| 少妇猛男粗大的猛烈进出视频| 久久精品aⅴ一区二区三区四区| 国产一区二区在线观看av| 亚洲精品成人av观看孕妇| 国产av精品麻豆| 久久久久久久精品精品| 国产精品国产av在线观看| 日韩大片免费观看网站| 国产一级毛片在线| 日韩av不卡免费在线播放| 嫩草影院入口| 18禁国产床啪视频网站| 欧美国产精品一级二级三级| av在线老鸭窝| 亚洲欧洲国产日韩| 欧美亚洲日本最大视频资源| 大香蕉久久成人网| 下体分泌物呈黄色| 久久99一区二区三区| 亚洲婷婷狠狠爱综合网| 久久精品国产亚洲av涩爱| 熟女少妇亚洲综合色aaa.| 国产在线一区二区三区精| 亚洲人成电影观看| 欧美精品亚洲一区二区| 精品国产乱码久久久久久男人| 国产av国产精品国产| 两个人免费观看高清视频| 菩萨蛮人人尽说江南好唐韦庄| 亚洲三区欧美一区| 婷婷色麻豆天堂久久| 一本大道久久a久久精品| 午夜免费男女啪啪视频观看| 精品午夜福利在线看| 亚洲av在线观看美女高潮| av在线观看视频网站免费| 在现免费观看毛片| 国产伦人伦偷精品视频| 夜夜骑夜夜射夜夜干| 国产欧美亚洲国产| 久久青草综合色| 国产av一区二区精品久久| 可以免费在线观看a视频的电影网站 | 电影成人av| 无限看片的www在线观看| 黄色一级大片看看| 久久久久人妻精品一区果冻| 涩涩av久久男人的天堂| 日日撸夜夜添| 伊人久久国产一区二区| 久久精品久久久久久噜噜老黄| 国产亚洲一区二区精品| 亚洲精品日韩在线中文字幕| 97精品久久久久久久久久精品| 国产熟女欧美一区二区| 高清不卡的av网站| 免费在线观看完整版高清| 考比视频在线观看| 日韩熟女老妇一区二区性免费视频| 丰满乱子伦码专区| 秋霞伦理黄片| 亚洲国产中文字幕在线视频| 国产精品麻豆人妻色哟哟久久| 国产精品秋霞免费鲁丝片| 亚洲国产欧美日韩在线播放| 91aial.com中文字幕在线观看| av卡一久久| 亚洲成av片中文字幕在线观看| 国产人伦9x9x在线观看| 国产一卡二卡三卡精品 | 亚洲少妇的诱惑av| 日本wwww免费看| 中文字幕制服av| 在线观看免费日韩欧美大片| 国产精品一区二区精品视频观看| 日韩av不卡免费在线播放| 中文乱码字字幕精品一区二区三区| 精品国产乱码久久久久久男人| 大片免费播放器 马上看| 黄色视频不卡| 久久久久久久精品精品| 日韩,欧美,国产一区二区三区| 成人影院久久| 久久天堂一区二区三区四区| 激情五月婷婷亚洲| 国产日韩欧美亚洲二区| 18禁裸乳无遮挡动漫免费视频| 最近最新中文字幕免费大全7| 蜜桃国产av成人99| 亚洲一卡2卡3卡4卡5卡精品中文| 国产欧美日韩一区二区三区在线| 99精品久久久久人妻精品| 亚洲熟女毛片儿| 精品一区二区三区四区五区乱码 | 丝瓜视频免费看黄片| av免费观看日本| 热re99久久精品国产66热6| 久久天躁狠狠躁夜夜2o2o | 国产淫语在线视频| 国产亚洲午夜精品一区二区久久| 久久婷婷青草| 国产片内射在线| 欧美变态另类bdsm刘玥| 中国国产av一级| 欧美97在线视频| 精品午夜福利在线看| 亚洲国产毛片av蜜桃av| 国产一区亚洲一区在线观看| 久久精品熟女亚洲av麻豆精品| 啦啦啦在线观看免费高清www| 国产亚洲av片在线观看秒播厂| 日本wwww免费看| 韩国精品一区二区三区| 国产成人免费观看mmmm| 午夜影院在线不卡| 午夜久久久在线观看| 成年动漫av网址| 亚洲国产中文字幕在线视频| 国产又色又爽无遮挡免| 天堂8中文在线网| 国产午夜精品一二区理论片| 欧美久久黑人一区二区| 午夜福利,免费看| 青青草视频在线视频观看| 亚洲成人国产一区在线观看 | 亚洲成人一二三区av| 亚洲精品久久久久久婷婷小说| 最近的中文字幕免费完整| 1024视频免费在线观看| 久久精品久久久久久久性| 91国产中文字幕| 妹子高潮喷水视频| 久久精品久久久久久噜噜老黄| 自线自在国产av| 国产国语露脸激情在线看| 黑人巨大精品欧美一区二区蜜桃| 成人国产av品久久久| 亚洲色图 男人天堂 中文字幕| 婷婷成人精品国产| 看非洲黑人一级黄片| 成年av动漫网址| 国产极品粉嫩免费观看在线| 男女午夜视频在线观看| 又粗又硬又长又爽又黄的视频| 久久精品熟女亚洲av麻豆精品| 国产一区亚洲一区在线观看| 久久人人97超碰香蕉20202| 国产精品成人在线| 这个男人来自地球电影免费观看 | av不卡在线播放| 在线观看一区二区三区激情| 男女无遮挡免费网站观看| 日本vs欧美在线观看视频| 美女视频免费永久观看网站| 精品福利永久在线观看| 王馨瑶露胸无遮挡在线观看| 一本一本久久a久久精品综合妖精| 亚洲精品乱久久久久久| 晚上一个人看的免费电影| 最近最新中文字幕大全免费视频 | 久久 成人 亚洲| 国产伦理片在线播放av一区| 久久久久国产一级毛片高清牌| 国产精品久久久久久久久免| 亚洲精品视频女| 女性被躁到高潮视频| 国产精品.久久久| 久久影院123| 日韩电影二区| 一本—道久久a久久精品蜜桃钙片| 国产精品久久久久久久久免| 最新的欧美精品一区二区| 老司机亚洲免费影院| 欧美最新免费一区二区三区| 欧美日韩亚洲国产一区二区在线观看 | 国产精品麻豆人妻色哟哟久久| 中文字幕人妻熟女乱码| 黄网站色视频无遮挡免费观看| 大话2 男鬼变身卡| 丰满少妇做爰视频| 亚洲成av片中文字幕在线观看| 国产精品三级大全| 狠狠精品人妻久久久久久综合| 国产极品天堂在线| 一级毛片我不卡| 黄色视频不卡| 久久热在线av| 久久久久久免费高清国产稀缺| 老鸭窝网址在线观看| 国产成人啪精品午夜网站| 亚洲精品国产区一区二| 亚洲av日韩在线播放| 国产免费视频播放在线视频| 午夜福利乱码中文字幕| www.熟女人妻精品国产| 国产又色又爽无遮挡免| 国产99久久九九免费精品| 老司机影院毛片| 我要看黄色一级片免费的| 国产成人精品久久二区二区91 | 亚洲av日韩在线播放| 亚洲精品第二区| 国产熟女午夜一区二区三区| 高清在线视频一区二区三区| 国产精品三级大全| 男女床上黄色一级片免费看| 亚洲欧美一区二区三区久久| 电影成人av| 999精品在线视频| 亚洲欧洲国产日韩| 久久国产精品男人的天堂亚洲| 激情五月婷婷亚洲| 成年人免费黄色播放视频| 精品卡一卡二卡四卡免费| 亚洲一码二码三码区别大吗| 久久久久久免费高清国产稀缺| 亚洲美女视频黄频| 美女午夜性视频免费| 成人18禁高潮啪啪吃奶动态图| 亚洲中文av在线| 2021少妇久久久久久久久久久| 亚洲一区二区三区欧美精品| 999久久久国产精品视频| 国产成人欧美在线观看 | 在线观看免费日韩欧美大片| 亚洲av在线观看美女高潮| 大片电影免费在线观看免费| 精品少妇黑人巨大在线播放| 卡戴珊不雅视频在线播放| 国产有黄有色有爽视频| 777久久人妻少妇嫩草av网站| 欧美日韩视频精品一区| 精品亚洲成国产av| svipshipincom国产片| 午夜福利,免费看| 午夜日韩欧美国产| 免费女性裸体啪啪无遮挡网站| 亚洲欧美日韩另类电影网站| 国产精品无大码| 欧美日韩av久久| 国产女主播在线喷水免费视频网站| 好男人视频免费观看在线| 精品酒店卫生间| 一区二区三区四区激情视频| 久久毛片免费看一区二区三区| www.精华液| 女人高潮潮喷娇喘18禁视频| 亚洲伊人久久精品综合| 国产深夜福利视频在线观看| 精品一区二区三区四区五区乱码 | 亚洲,一卡二卡三卡| 日韩精品免费视频一区二区三区| 久久久久视频综合| 亚洲av成人不卡在线观看播放网 | 亚洲视频免费观看视频| 中国三级夫妇交换| 欧美成人精品欧美一级黄| 国产精品国产三级专区第一集| 亚洲欧美精品综合一区二区三区| 久久鲁丝午夜福利片| 校园人妻丝袜中文字幕| 亚洲视频免费观看视频| www.熟女人妻精品国产| 午夜福利乱码中文字幕| 一级毛片 在线播放| 免费看av在线观看网站| 在线观看免费日韩欧美大片| 亚洲精品第二区| 交换朋友夫妻互换小说| 精品久久久精品久久久| 欧美日韩综合久久久久久| 亚洲 欧美一区二区三区| 国产探花极品一区二区| 多毛熟女@视频| 国产一卡二卡三卡精品 | 麻豆精品久久久久久蜜桃| 十八禁人妻一区二区| 9热在线视频观看99| 亚洲激情五月婷婷啪啪| 水蜜桃什么品种好| 日韩av在线免费看完整版不卡| 九色亚洲精品在线播放| 日韩一本色道免费dvd| 9热在线视频观看99| av网站免费在线观看视频| 丝袜脚勾引网站| 欧美xxⅹ黑人| 国产精品久久久久久精品电影小说| 成人毛片60女人毛片免费| 国产 精品1| 日韩大码丰满熟妇| 国产无遮挡羞羞视频在线观看| 国产精品成人在线| 欧美 日韩 精品 国产| 亚洲美女视频黄频| 国产亚洲av片在线观看秒播厂| 大码成人一级视频| 午夜免费观看性视频| 欧美另类一区| 欧美黄色片欧美黄色片| 免费观看性生交大片5| 国产免费现黄频在线看| 一本大道久久a久久精品| 国产成人精品久久二区二区91 | 黄片小视频在线播放| 久久久久久久久免费视频了| www.av在线官网国产| 一本久久精品| 制服诱惑二区| 国产精品香港三级国产av潘金莲 | 亚洲伊人色综图| 久久久久人妻精品一区果冻| 欧美日韩一区二区视频在线观看视频在线| 免费看av在线观看网站| av网站在线播放免费| 日韩熟女老妇一区二区性免费视频| 少妇 在线观看| 精品一区二区免费观看| 亚洲男人天堂网一区| 老司机影院成人| 国产精品无大码| 国产淫语在线视频| 午夜日韩欧美国产| 91国产中文字幕| 男人添女人高潮全过程视频| 毛片一级片免费看久久久久| 亚洲激情五月婷婷啪啪| 在线观看人妻少妇| av在线播放精品| 麻豆av在线久日| 波多野结衣av一区二区av| 综合色丁香网| 伊人亚洲综合成人网| 国产乱人偷精品视频| 综合色丁香网| 天天躁夜夜躁狠狠久久av| av在线app专区| 久久久久久久精品精品| 亚洲国产欧美一区二区综合| 精品亚洲成a人片在线观看| 天堂8中文在线网| 交换朋友夫妻互换小说| 十八禁高潮呻吟视频| 日韩成人av中文字幕在线观看| 伊人亚洲综合成人网| 精品亚洲成a人片在线观看| 亚洲精品久久午夜乱码| 久久久亚洲精品成人影院| 免费黄频网站在线观看国产| 亚洲精品av麻豆狂野| 亚洲精品久久久久久婷婷小说| 一级爰片在线观看| 日日爽夜夜爽网站| 久久久亚洲精品成人影院| 久久久国产欧美日韩av| 亚洲精品久久午夜乱码| 久久天躁狠狠躁夜夜2o2o | 亚洲国产精品一区二区三区在线| 九九爱精品视频在线观看| 国产精品女同一区二区软件| 亚洲av欧美aⅴ国产| 国产野战对白在线观看| 中文字幕av电影在线播放| 欧美亚洲 丝袜 人妻 在线| 日韩 欧美 亚洲 中文字幕|