面向GPU異構(gòu)集群的自學(xué)習(xí)負(fù)載均衡調(diào)度算法

劉 惠，王繼剛，葛錚錚，顧 群，陳 倩，杜軍朝

(1.西安電子科技大學(xué) 軟件學(xué)院，陜西 西安 710071; 2 中興通訊股份有限公司，四川 成都 610041)

面向GPU異構(gòu)集群的自學(xué)習(xí)負(fù)載均衡調(diào)度算法

劉 惠1，王繼剛2，葛錚錚1，顧 群1，陳 倩1，杜軍朝1

(1.西安電子科技大學(xué) 軟件學(xué)院，陜西 西安 710071; 2 中興通訊股份有限公司，四川 成都 610041)

由于GPU的高性能計(jì)算能力，越來(lái)越多地被用于集群系統(tǒng)中，但同時(shí)也給集群帶來(lái)節(jié)點(diǎn)級(jí)的異構(gòu)問(wèn)題，使原來(lái)適用于同構(gòu)集群的調(diào)度算法在異構(gòu)集群中性能大大降低。為使異構(gòu)節(jié)點(diǎn)間的負(fù)載均衡，降低總的作業(yè)執(zhí)行時(shí)間，提出了一個(gè)面向GPU異構(gòu)集群的自學(xué)習(xí)負(fù)載均衡調(diào)度算法。首先對(duì)Torque調(diào)度器進(jìn)行擴(kuò)展，使其支持GPU作業(yè)調(diào)度，然后將提出的自學(xué)習(xí)調(diào)度算法在Rocks操作系統(tǒng)及Torque調(diào)度器軟件中實(shí)現(xiàn)。真實(shí)物理集群上的實(shí)驗(yàn)結(jié)果表明，擴(kuò)展后的Torque調(diào)度器很好地支持GPU任務(wù)的調(diào)度，自學(xué)習(xí)調(diào)度算法較原來(lái)的Torque調(diào)度算法能達(dá)到更好的負(fù)載均衡。

異構(gòu)集群； GPU；自學(xué)習(xí)調(diào)度算法；負(fù)載均衡

任務(wù)調(diào)度是集群系統(tǒng)的核心，它能大大提高資源利用率，提高集群總體性能。文獻(xiàn)[1]提出了一個(gè)基于熵的變化趨勢(shì)的負(fù)載均衡算法，文獻(xiàn)[2]提出了一個(gè)基于集群的動(dòng)態(tài)負(fù)載均衡算法，文獻(xiàn)[3]提出了一種面向集群系統(tǒng)的兩階段節(jié)能調(diào)度算法，文獻(xiàn)[4]提出了一個(gè)基于集群的能量有效性調(diào)度算法，但它們都是針對(duì)同構(gòu)集群提出的算法。文獻(xiàn)[5]提出了異構(gòu)集群環(huán)境下的作業(yè)調(diào)度方法，文獻(xiàn)[6]提出一個(gè)基于異構(gòu)集群的折衷能耗有效性和負(fù)載均衡的調(diào)度算法，文獻(xiàn)[7-8]提出一個(gè)異構(gòu)集群的基于歷史任務(wù)運(yùn)行時(shí)間的調(diào)度算法，文獻(xiàn)[9-13]提出基于負(fù)載均衡的調(diào)度算法。但這些算法或是基于同構(gòu)集群，或者基于的異構(gòu)集群只是各個(gè)節(jié)點(diǎn)的計(jì)算能力不同，并沒(méi)有考慮差異很大的GPU[14-15]所構(gòu)成的異構(gòu)集群。本文研究由CPU和GPU計(jì)算節(jié)點(diǎn)所構(gòu)成的異構(gòu)集群的調(diào)度問(wèn)題，提出一個(gè)自學(xué)習(xí)負(fù)載均衡調(diào)度算法，并且在Torque集群平臺(tái)上用H.264軟件進(jìn)行了實(shí)驗(yàn)。

1 面向GPU的Torque集群平臺(tái)擴(kuò)展

Torque是一個(gè)開(kāi)源的集群資源管理軟件，被廣泛地應(yīng)用于高校和其他研究機(jī)構(gòu)的高性能計(jì)算集群中。Torque在資源管理方面功能強(qiáng)大，支持超過(guò)1 500個(gè)計(jì)算節(jié)點(diǎn)，支持幾乎全部UNIX/Linux系的操作系統(tǒng)，并且在不斷更新中。但是在實(shí)際使用過(guò)程中發(fā)現(xiàn)，Torque調(diào)度性能差，集群的負(fù)載嚴(yán)重不平衡，并且無(wú)法識(shí)別和調(diào)度GPU作業(yè)。所以，現(xiàn)有Torque集群平臺(tái)不支持有GPU計(jì)算節(jié)點(diǎn)的異構(gòu)集群，GPU可以提供數(shù)十倍乃至于上百倍于CPU的性能，在大數(shù)據(jù)時(shí)代，支持GPU成為技術(shù)發(fā)展的必然。

本文對(duì)Torque上萬(wàn)行源碼進(jìn)行分析，對(duì)Torque源碼進(jìn)行了擴(kuò)展和實(shí)現(xiàn)，使其支持對(duì)GPU作業(yè)的調(diào)度。具體對(duì)Torque調(diào)度器的調(diào)度和資源獲取2個(gè)模塊進(jìn)行了改進(jìn)。首先，針對(duì)GPU資源的獲取和保存進(jìn)行改進(jìn)，使得Torque調(diào)度器能夠解析并獲取計(jì)算節(jié)點(diǎn)的GPU資源信息并且保存下來(lái)；其次，在作業(yè)請(qǐng)求GPU資源的解析這個(gè)關(guān)鍵技術(shù)點(diǎn)上進(jìn)行改進(jìn)，使得調(diào)度器能夠解析出哪些作業(yè)請(qǐng)求GPU資源，從而在調(diào)度的時(shí)候?qū)⒄?qǐng)求GPU計(jì)算資源的作業(yè)分配到配置有GPU的計(jì)算節(jié)點(diǎn)上。這部分?jǐn)U展工作涉及到大量數(shù)據(jù)結(jié)構(gòu)和源代碼剖析，在此不作深入闡述。本文重點(diǎn)論述面向GPU異構(gòu)集群基于歷史信息的自學(xué)習(xí)動(dòng)態(tài)負(fù)載均衡調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn)。

2 問(wèn)題定義

本文提出了一個(gè)面向GPU異構(gòu)集群的基于歷史信息的自學(xué)習(xí)動(dòng)態(tài)負(fù)載均衡調(diào)度算法，本章闡述集群平臺(tái)架構(gòu)模型、性能指標(biāo)和作業(yè)模型及問(wèn)題定義。

異構(gòu)集群架構(gòu)模型：集群由若干服務(wù)器組成，包含1個(gè)主節(jié)點(diǎn)和m個(gè)計(jì)算節(jié)點(diǎn)。主節(jié)點(diǎn)主要負(fù)責(zé)集群上作業(yè)的調(diào)度和資源管理等工作，計(jì)算節(jié)點(diǎn)則負(fù)責(zé)具體的計(jì)算任務(wù)。節(jié)點(diǎn)間通過(guò)高速局域網(wǎng)互連，計(jì)算節(jié)點(diǎn)和主節(jié)點(diǎn)間通過(guò)高速網(wǎng)絡(luò)進(jìn)行通信，計(jì)算節(jié)點(diǎn)間不發(fā)生數(shù)據(jù)交換。集群中的節(jié)點(diǎn)是異構(gòu)的，有些節(jié)點(diǎn)配置有GPU+CPU，可以針對(duì)CUDA和OpenCL程序進(jìn)行并行計(jì)算；而有些節(jié)點(diǎn)則僅包含CPU。

符號(hào)定義：設(shè)m個(gè)計(jì)算節(jié)點(diǎn)為SNODE={N1,N2,…,Nm}，對(duì)于任意一個(gè)計(jì)算節(jié)點(diǎn)Ni，關(guān)注其4個(gè)實(shí)際性能參數(shù)，即CPU頻率、內(nèi)存大小、GPU頻率、GPU_MEM大小，分別用rate_cpui、memi、rate_gpui、mem_gpuiCPU來(lái)表示?；诖?，再定義出計(jì)算節(jié)點(diǎn)Ni的4個(gè)負(fù)載參數(shù)：CPU利用率、內(nèi)存利用率、GPU利用率、GPU內(nèi)存利用率，分別用utlz_cpui、utlz_memi、utlz_gpui、utlz_gpumemi表示。

作業(yè)模型：多用戶可以在集群上提交多個(gè)作業(yè)，用戶提交的n個(gè)作業(yè)記為集合SJOB={J1,J2,…,Jn}，設(shè)各個(gè)作業(yè)之間沒(méi)有依賴關(guān)系，相同類型的作業(yè)可以反復(fù)多次提交(比如反復(fù)進(jìn)行的科學(xué)計(jì)算，程序執(zhí)行過(guò)程都相同，只不過(guò)輸入數(shù)據(jù)不同)。

問(wèn)題描述：基于以上GPU異構(gòu)集群架構(gòu)模型和作業(yè)模型，給定SJOB和SNODE兩個(gè)集合，找到集合SJOB到集合SNODE的一個(gè)映射，滿足以下2個(gè)條件：①若作業(yè)需求GPU資源，則作業(yè)被映射到GPU+CPU節(jié)點(diǎn)上，反之則可以被映射到CPU節(jié)點(diǎn)上，也可以被映射到GPU+CPU節(jié)點(diǎn)上；②最終映射使得集群所有節(jié)點(diǎn)之間達(dá)到負(fù)載均衡，減少作業(yè)總的執(zhí)行時(shí)間。

3 算法概述

3.1 最大剩余能力算法

本文所提出的面向GPU異構(gòu)集群的自學(xué)習(xí)調(diào)度算法主要思想是根據(jù)每個(gè)節(jié)點(diǎn)的相對(duì)性能值以及實(shí)時(shí)負(fù)載信息估算出節(jié)點(diǎn)的剩余計(jì)算能力，從而將作業(yè)發(fā)送到剩余計(jì)算能力最強(qiáng)的節(jié)點(diǎn)執(zhí)行，以達(dá)到集群負(fù)載均衡。算法偽代碼見(jiàn)算法3.1。

算法3.1GPUCluster-SCHEDULINGInput:作業(yè)集SJOB={Ji,i=1,2,3,…,n},資源集SNODE={Ni,i=1,2,3,…,m}Output:調(diào)度結(jié)果O={O1,O2,O3,…,;Ok=}1. SNODE←GETALLNODES()//獲取所有節(jié)點(diǎn)的信息2. SJOB←GETALLJOBS()//獲取所有作業(yè)的信息3. INIT_LOADS(tab_node)//初始化節(jié)點(diǎn)信息表4. INIT_OLDJOBS(tab_job)//讀取作業(yè)歷史信息表5. WHILE(SJOB!=?)6.UPDATANODEVALUE(SNODE)//更新所有節(jié)點(diǎn)的剩余能力7. j←CHOOSEONEJOB(SJOB)//選擇一個(gè)待調(diào)度作業(yè)8. 法IF(CHECKJOB(j)=FALSE)//檢查作業(yè)是否可以運(yùn)行9. CONTINUE10. ELSE11. Sn←CHOOSENODES(SNODE,j) //篩選備選節(jié)點(diǎn)12. IF(Sn=?)CONTINUE13. ELSEn←MOSTAVAILABLE(Sn) //選擇剩余能力最強(qiáng)的節(jié)點(diǎn)14. RUNJOB(j,n)15. μ←PRIDICTION(tab_job,j,n)//估計(jì)作業(yè)帶來(lái)的負(fù)載變化16. UPDATETABLE(tab_node,μ)//更新節(jié)點(diǎn)負(fù)載信息17. CONTINUE18. RETURN

算法第1步從異構(gòu)集群的主節(jié)點(diǎn)獲取所有計(jì)算節(jié)點(diǎn)的信息，即rate_cpu、mem、rate_gpu、mem_gpu、utlz_cpu、utlz_mem、utlz_gpu、utlz_gpumem這幾個(gè)參數(shù)及當(dāng)前正在運(yùn)行的作業(yè)數(shù)目。在設(shè)計(jì)動(dòng)態(tài)負(fù)載均衡調(diào)度算法時(shí)，負(fù)載信息的實(shí)時(shí)獲取是重點(diǎn)，需協(xié)調(diào)“獲取方式”和“獲取間隔”這2個(gè)參數(shù)間的關(guān)系。本算法采取集中式調(diào)度思想，選取PUSH機(jī)制作為獲取方式，即在集群的每個(gè)計(jì)算節(jié)點(diǎn)部署一個(gè)“心跳程序”，該程序定期收集每個(gè)計(jì)算節(jié)點(diǎn)的狀態(tài)信息，并將信息發(fā)送給主節(jié)點(diǎn)。在設(shè)置“獲取間隔”參數(shù)時(shí)，若太大則導(dǎo)致負(fù)載信息陳舊調(diào)度不準(zhǔn)確，若太小又會(huì)給主節(jié)點(diǎn)帶來(lái)太多額外通信與計(jì)算開(kāi)銷。根據(jù)集群實(shí)測(cè)出的經(jīng)驗(yàn)值，本算法將心跳頻率設(shè)置為每300s1次。在這300s內(nèi)，若某計(jì)算節(jié)點(diǎn)上的某作業(yè)執(zhí)行完成，則該計(jì)算節(jié)點(diǎn)會(huì)向主節(jié)點(diǎn)報(bào)告作業(yè)執(zhí)行完畢，同時(shí)將該節(jié)點(diǎn)的當(dāng)前負(fù)載信息捎帶上報(bào)。這樣，當(dāng)主節(jié)點(diǎn)調(diào)度算法調(diào)度新作業(yè)時(shí)，能夠根據(jù)作業(yè)執(zhí)行的歷史信息對(duì)負(fù)載進(jìn)行估計(jì)。

算法第2步獲取所有在隊(duì)列中等待調(diào)度的作業(yè)信息，包括每個(gè)作業(yè)請(qǐng)求的資源特征，其是否需GPU資源等。算法第3步對(duì)計(jì)算節(jié)點(diǎn)的負(fù)載信息表tab_node進(jìn)行初始化。算法第4步讀取歷史作業(yè)信息表tab_job，該表主要記錄了歷史作業(yè)在哪個(gè)計(jì)算節(jié)點(diǎn)上運(yùn)行、運(yùn)行的總時(shí)間以及其平均的CPU、GPU和內(nèi)存使用率等數(shù)據(jù)。特別說(shuō)明的是，要獲得程序運(yùn)行期間的CPU、GPU和內(nèi)存的平均利用率，需要對(duì)作業(yè)整個(gè)運(yùn)行期間的CPU、GPU利用率和內(nèi)存利用率進(jìn)行采樣記錄。系統(tǒng)采樣的時(shí)間間隔選取很關(guān)鍵，本文選取的采樣間隔為10s。

算法第6步到第17步是主調(diào)度循環(huán)，第6步更新所有計(jì)算節(jié)點(diǎn)的剩余計(jì)算能力，任意一個(gè)節(jié)點(diǎn)Ni剩余計(jì)算能力的計(jì)算式為

VALUEi=k2Q1+k2Q2-k3Q3+k4Q4，

(1)

(2)

(3)

(4)

(5)

式(1)中，VALUEi的值代表節(jié)點(diǎn)Ni的剩余計(jì)算能力，VALUEi的值越大，該節(jié)點(diǎn)就越可能成為作業(yè)的執(zhí)行節(jié)點(diǎn)，k1、k2、k3、k4是用來(lái)調(diào)節(jié)CPU、內(nèi)存、GPU、GPU內(nèi)存4者對(duì)節(jié)點(diǎn)剩余計(jì)算能力影響程度比重的權(quán)值，它們的和為1。

算法第7步根據(jù)改進(jìn)的FCFS策略選取一個(gè)作業(yè)j。算法第8步到第11步用于檢查選定的作業(yè)是否可以運(yùn)行，這個(gè)階段的檢查主要是看作業(yè)請(qǐng)求的資源是否超過(guò)了系統(tǒng)規(guī)定的限制，或者是否超過(guò)了用戶的資源使用限制等。如果超過(guò)了，則重新選擇一個(gè)作業(yè)；如果沒(méi)有超過(guò)，則根據(jù)作業(yè)請(qǐng)求的資源信息匹配所有計(jì)算節(jié)點(diǎn)，篩選出備選節(jié)點(diǎn)集Sn。算法第13步，若備選節(jié)點(diǎn)集Sn不為空，則選擇其中能提供最大計(jì)算能力的節(jié)點(diǎn)作為運(yùn)行節(jié)點(diǎn)。算法15步啟用負(fù)載預(yù)測(cè)機(jī)制來(lái)預(yù)估作業(yè)給節(jié)點(diǎn)帶來(lái)的負(fù)載變化μ。算法16步根據(jù)預(yù)測(cè)值來(lái)更新節(jié)點(diǎn)負(fù)載信息表。接著，算法繼續(xù)選擇下一個(gè)作業(yè)進(jìn)行調(diào)度并重復(fù)上述過(guò)程。

3.2 基于歷史信息的自學(xué)習(xí)負(fù)載更新算法

由前所述，算法第15步對(duì)被調(diào)度節(jié)點(diǎn)的負(fù)載增值進(jìn)行預(yù)測(cè)，本文提出了基于歷史信息自學(xué)習(xí)的負(fù)載變化估計(jì)，用來(lái)修正作業(yè)調(diào)度后帶來(lái)的負(fù)載變化。算法3.2給出了負(fù)載估計(jì)函數(shù)偽代碼，其算法原理是根據(jù)同一類作業(yè)運(yùn)行的歷史信息來(lái)推斷本次作業(yè)運(yùn)行所帶來(lái)的負(fù)載變化，因?yàn)樽鳂I(yè)的資源使用量是由自身的屬性決定的，在不同節(jié)點(diǎn)上雖然帶來(lái)的負(fù)載不同，但使用的資源總量是一定的，如總的CPU時(shí)間和物理內(nèi)存。前文中對(duì)作業(yè)的跟蹤記錄所形成的已運(yùn)行作業(yè)負(fù)載信息表，是本負(fù)載變化估計(jì)算法的輸入。

下面分3種情況說(shuō)明預(yù)測(cè)算法的執(zhí)行過(guò)程，其中前2種情況對(duì)應(yīng)于算法3.2的第1、2步，最后一種情況對(duì)應(yīng)于算法3.2的剩余部分。

算法3.2 PRIDICTION(tab_job,j,n)1.IF(MATCH(tab_job,j)=TRUE) //有作業(yè)歷史信息2.μ←GETLOAD(tab_job,j)//從表中直接獲取負(fù)載3. ELSE//沒(méi)有作業(yè)歷史信息4. L←用戶設(shè)定一個(gè)值5. N←TOTALJOBNUM(tab_job)//作業(yè)總數(shù)6. IF(N=0)7. μ←total_loadn/job_numn//節(jié)點(diǎn)總負(fù)載與任務(wù)數(shù)的比值8. ELSEIF(N=1)9. μ←GETLOAD(tab_job,1)10. ELSE IF(N>1)11. IF(L>N) L←N12. μi←GETLOAD(tab_job,L)//最近L個(gè)作業(yè)的負(fù)載信息13. L1←[0.2L]14. μ←FORECAST(μi)15. RETURNμ

(1)若作業(yè)在表中出現(xiàn)一次，則根據(jù)歷史作業(yè)信息即可求得新節(jié)點(diǎn)負(fù)載變化的估計(jì)值。

(2)若作業(yè)在表中出現(xiàn)多次，則根據(jù)這n次歷史作業(yè)的信息分別求得新節(jié)點(diǎn)負(fù)載變化的估計(jì)值，然后將這些估計(jì)值的平均值作為新節(jié)點(diǎn)負(fù)載變化的估計(jì)值。

(3)如果同類任務(wù)沒(méi)有出現(xiàn)過(guò)，那么需要預(yù)測(cè)任務(wù)的負(fù)載。本文的策略是，根據(jù)局部性原理，利用已經(jīng)存在的其他作業(yè)歷史信息做出預(yù)測(cè)。假設(shè)目前任務(wù)負(fù)載表中總共有N條記錄：

①若N為0，則將節(jié)點(diǎn)當(dāng)前的負(fù)載除以當(dāng)前任務(wù)數(shù)，算得任務(wù)負(fù)載的平均值，作為負(fù)載變化的預(yù)測(cè)值。在“心跳程序”中，可以同時(shí)向主節(jié)點(diǎn)發(fā)送本地正在運(yùn)行的任務(wù)數(shù)目信息。

②若N為1，則以唯一的作業(yè)負(fù)載作為預(yù)測(cè)負(fù)載。僅以一個(gè)作業(yè)負(fù)載歷史信息來(lái)預(yù)測(cè)是很不準(zhǔn)確的，但是本文設(shè)計(jì)的是一個(gè)自學(xué)習(xí)的過(guò)程，隨著時(shí)間的推移，已完成的任務(wù)會(huì)越來(lái)越多，預(yù)測(cè)也會(huì)越來(lái)越準(zhǔn)確。

③若N>1，考慮最近的L個(gè)作業(yè)，L由用戶設(shè)定，若L>N，則令L等于N。將L分為L(zhǎng)1和L2兩部分來(lái)計(jì)算平均負(fù)載，其中L1部分時(shí)間更近。根據(jù)局部性原則，設(shè)置L1部分的權(quán)值大于L2部分。據(jù)此算出L個(gè)節(jié)點(diǎn)的加權(quán)平均值作為新節(jié)點(diǎn)的負(fù)載估計(jì)值。

由于本文提出的預(yù)測(cè)算法是基于自學(xué)習(xí)的，隨著執(zhí)行任務(wù)的增加，任務(wù)負(fù)載信息表中的記錄不斷增多，從而任務(wù)負(fù)載的預(yù)測(cè)精度也隨之提高。準(zhǔn)確的預(yù)測(cè)對(duì)保持負(fù)載信息的實(shí)時(shí)性具有至關(guān)重要的作用。

4 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)硬件平臺(tái)是基于CPU+GPU異構(gòu)集群，共有4個(gè)節(jié)點(diǎn)，具體參數(shù)見(jiàn)表1。其中，cluster是集群的主節(jié)點(diǎn)，它也可同時(shí)作為一個(gè)計(jì)算節(jié)點(diǎn)使用；compute-0-0是一個(gè)性能較弱的計(jì)算節(jié)點(diǎn)；compute-0-1是一個(gè)配置了Tesla系列GPU的計(jì)算節(jié)點(diǎn)，性能

表1 集群節(jié)點(diǎn)的性能參數(shù)

最強(qiáng)；compute-0-2是一個(gè)配置了Quadro系列GPU 的計(jì)算節(jié)點(diǎn)，性能較弱。軟件方面，作為主節(jié)點(diǎn)，cluster安裝的操作系統(tǒng)是Rocks的管理節(jié)點(diǎn)版本FrontEnd，F(xiàn)rontEnd可以讓主節(jié)點(diǎn)輕松地管理計(jì)算節(jié)點(diǎn)；計(jì)算節(jié)點(diǎn)安裝的是Rocks的計(jì)算節(jié)點(diǎn)版本Compute。另外，主節(jié)點(diǎn)cluster上還安裝了集群管理軟件Torque的全部組件，包括服務(wù)器組件pbs_server、作業(yè)執(zhí)行組件pbs_mom以及調(diào)度器組件pbs_sched；compute-0-0、compute-0-1、compute-0-2計(jì)算節(jié)點(diǎn)則安裝了作業(yè)執(zhí)行組件pbs_mom。

本文選取圖像卷積算法和H.264視頻編碼作為應(yīng)用實(shí)例。在實(shí)驗(yàn)中，將作業(yè)亂序地、反復(fù)地提交到集群。為了能更方便地觀測(cè)集群各個(gè)節(jié)點(diǎn)的負(fù)載變化，利用集群監(jiān)控工具Ganglia觀察集群的實(shí)時(shí)負(fù)載并作記錄。首先采用Torque原有的調(diào)度器進(jìn)行實(shí)驗(yàn)，接著將本文提出的算法部署到擴(kuò)展后的Torque調(diào)度器中進(jìn)行實(shí)驗(yàn)，得到如圖1—圖4的實(shí)驗(yàn)結(jié)果。

從圖1和圖2可以看出，使用Torque原有的調(diào)度算法集群的負(fù)載嚴(yán)重不平衡。集群中第1個(gè)節(jié)點(diǎn)迅速地到達(dá)約70%的負(fù)載水平之后，第2個(gè)節(jié)點(diǎn)的

圖1 采用Torque原有調(diào)度算法的CPU負(fù)載變化

圖2 采用Torque原有調(diào)度算法的內(nèi)存負(fù)載變化

負(fù)載才開(kāi)始增加。此外還發(fā)現(xiàn)，在第1個(gè)和第2個(gè)節(jié)點(diǎn)接近滿載時(shí)，后2個(gè)節(jié)點(diǎn)還沒(méi)什么變化。由此可以證明Torque原有調(diào)度算法的性能很差。

通過(guò)對(duì)圖3和圖4的觀察，發(fā)現(xiàn)4個(gè)節(jié)點(diǎn)的CPU和內(nèi)存負(fù)載大體上一致增長(zhǎng)，達(dá)到了近似的負(fù)載均衡。因此，本文設(shè)計(jì)的算法可行、有效，成功地對(duì)Torque進(jìn)行了擴(kuò)展，不但使其增加了對(duì)GPU作業(yè)的支持，而且實(shí)現(xiàn)了一種效果良好的負(fù)載均衡調(diào)度。

圖3 采用本文調(diào)度算法的CPU負(fù)載變化

圖4 采用本文調(diào)度算法的內(nèi)存負(fù)載變化

5 結(jié) 語(yǔ)

本文研究了由CPU和GPU計(jì)算節(jié)點(diǎn)所構(gòu)成的異構(gòu)集群的調(diào)度問(wèn)題，提出一個(gè)自學(xué)習(xí)負(fù)載均衡調(diào)度算法，并且在Torque集群平臺(tái)上用H.264應(yīng)用軟件進(jìn)行了實(shí)驗(yàn)。本文的主要貢獻(xiàn)有：①研究同時(shí)包含CPU和GPU節(jié)點(diǎn)的異構(gòu)集群的調(diào)度問(wèn)題，提出了一種面向GPU異構(gòu)集群的基于歷史信息自學(xué)習(xí)的動(dòng)態(tài)負(fù)載均衡調(diào)度算法。②與模擬數(shù)據(jù)算法仿真驗(yàn)證不同，本文在真實(shí)物理Torque集群環(huán)境中實(shí)現(xiàn)了所提調(diào)度算法，實(shí)現(xiàn)部署、編寫(xiě)、運(yùn)行H.264應(yīng)用程序和視頻數(shù)據(jù)，得出實(shí)驗(yàn)結(jié)果。③由于傳統(tǒng)Torque集群平臺(tái)不支持GPU計(jì)算節(jié)點(diǎn)，且其調(diào)度算法非常簡(jiǎn)單。因此，本文研究了Torque上萬(wàn)行源碼，發(fā)現(xiàn)了Torque在作業(yè)調(diào)度方面存在的缺陷和不足，對(duì)Torque集群平臺(tái)進(jìn)行擴(kuò)展，使其能夠識(shí)別、管理、調(diào)度GPU資源。然后提出一種面向GPU異構(gòu)集群的基于歷史信息自學(xué)習(xí)的動(dòng)態(tài)負(fù)載均衡調(diào)度算法，并且算法在現(xiàn)有Torque平臺(tái)中實(shí)現(xiàn)、部署和運(yùn)行。

[1] Wu Kehe,Chen Long,Ye Shichao,et al.A load balancing algorithm based on the variation trend of entropy in homogeneous cluster[J].International Journal of Grid and Distributed Computing,2014,7(2):11-20.

[2] Patil S,Gopal A.Cluster performance evaluation using load balancing algorithm[C].International Conference on Information Communication and Embedded Systems.Piscataway:IEEE,2013:104-108

[3] 劉偉,尹行,段玉光，等.同構(gòu)DVS集群中基于自適應(yīng)閾值的并行任務(wù)節(jié)能調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(2):393-407. LIU Wei,YIN-Hang,DUAN Yu-Guang,et al.Adaptive threshold-based energy-efficient scheduling algorithm for parallel tasks on homogeneous DVS-enabled clusters[J].Chinese Journal of Computers,2013,36(2):393-407.

[4] Liu Wei,Li Hongfeng,Shi Feiyan.Energy-efficient task clustering scheduling on homogeneous clusters[C].Proceedings 201011th International Conference on Parallel and Distributed Computing,Applications and Technologies(PDCAT 2010).Los Alamitos:IEEE Computer Society,2010:382-385.

[5] 劉莉,姜明華.異構(gòu)集群下的任務(wù)調(diào)度算法研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(1):80-84. LIU Li,JIANG Ming-hua.Research of task scheduling algorithm on heterogeneous cluster[J].Application Research of Computers,2014,31(1):80-84.

[6] Terzopoulos G,Karatza H.Power-aware load balancing in heterogeneous clusters[C].Proceedings of the 2013 International Symposium on Performance Evaluation of Computer and Telecommunication Systems.Toronto:IEEE,2013:148-154.

[7] Ye Bin,Dong Xiaoshe,Zheng Pengfei,et al.A delay scheduling algorithm based on history time in heterogeneous environments[C].ChinaGrid Annual Conference.Piscataway:IEEE,2013:86-91.

[8] Gregg C,Boyer M,Hazelwood K,et al.Dynamic heterogeneous scheduling decisions using historical runtime data[C/OL].[2014-05-03].http://www.cs.virginia.edu/～skadron/Papers/gregg_a4mmc11.pdf.

[9] 史琰,劉增基,盛敏.一種保證負(fù)載均衡的網(wǎng)絡(luò)資源分配算法[J].西安電子科技大學(xué)學(xué)報(bào),2005,32(6):885-889. SHI Yan,LIU Zeng-ji,SHENG Min.A novel network resource allocation algorithm with load balance guarantees[J].Journal of Xidian University,2005,32(6):885-889.

[10] Zhang Keliang,Wu Baifeng.Task scheduling for GPU Heterogeneous cluster[C].Cluster Computing Workshops(Cluster Workshops),2012 IEEE International Conference.Beijing:IEEE,2012:161-169.

[11] Payli RU,Erciyes K,Dagdeviren O.Cluster-based loadbalancing algorithms for grids[J].International Journal of ComputerNetworks & Communications(IJCNC),2011,3(5):253-269.

[12] Youn Cand,Chung L.An efficient load balancing algorithm for clustersystem[C].IFIP International Conference on Network and Parallel Computing.Berlin:Springer Berlin Heidelberg,2005:176-179.

[13] Terzopoulos G,Karatza H.Power-aware Load Balancing in Heterogeneous Clusters[C].Performance Evaluation of Computer and Telecommunication Systems(SPECTS).Toronto:IEEE,2013:148-154.

[14] Kindratenko V V,Enos J J,Guochun Shi,et al.GPU clusters for high-performance computing[C].Workshop on Parallel Programming on Accelerator Clusters(PPAC).New Orleans:IEEE,2009:1-8.

[15] Showerman M,Enos J,Steffen C,et al.A power-efficient GPU cluster architecture for scientificcomputing[J].Computing in Science Engineering,2011,13(2):83-87.

責(zé)任編輯：張新寶

2014-12-15

國(guó)家自然科學(xué)基金項(xiàng)目(編號(hào)：61100075、61272456)；高等院?；究蒲袠I(yè)務(wù)費(fèi)項(xiàng)目(編號(hào)：K5051323005，BDY041409)

劉惠(1976-)，女，副教授，博士，主要從事大數(shù)據(jù)、并行計(jì)算、移動(dòng)計(jì)算等研究。E-mail:liuhui@xidian.edu.cn

1673-064X(2015)03-0105-06

TP393

A