面向云計(jì)算的分布式集群任務(wù)分配策略研究

面向云計(jì)算的分布式集群任務(wù)分配策略研究

1云計(jì)算網(wǎng)絡(luò)技術(shù)及應(yīng)用云計(jì)算被認(rèn)為是當(dāng)今計(jì)算和開發(fā)的主流。參考文獻(xiàn)和詳細(xì)地分析了云計(jì)算的幾大特征與瓶頸,指出了以數(shù)據(jù)為中心的高性能計(jì)算是分布式集群計(jì)算的基礎(chǔ)。云計(jì)算是一種計(jì)算模式,它主要用來(lái)解決服務(wù)器與PC之間存儲(chǔ)資源共享和數(shù)據(jù)共享的問題。參考文獻(xiàn)從成本的角度研究了云環(huán)境下集群系統(tǒng)釋放CO2的影響,從能效的角度研究了計(jì)算能耗的數(shù)學(xué)模型。根據(jù)云計(jì)算的特征,云計(jì)算技術(shù)必須是建立在高速、穩(wěn)定、低廉、基于應(yīng)用的網(wǎng)絡(luò)基礎(chǔ)之上,所提供的各種服務(wù)以高性能計(jì)算為主要技術(shù)手段。云計(jì)算被認(rèn)為提供3種服務(wù),分別是基礎(chǔ)設(shè)施服務(wù)(IaaS)、軟件服務(wù)(SaaS)以及平臺(tái)服務(wù)(PaaS)。軟件作為服務(wù)的前提是能提供高效可靠的海量數(shù)據(jù)并行處理能力。2面向云的集群環(huán)境圖像處理的任務(wù)分配問題隨著遙感圖像分辨率的不斷提高,每一景圖像的數(shù)據(jù)量大增,計(jì)算量也相應(yīng)增加。根據(jù)圖像數(shù)據(jù)本身存儲(chǔ)的規(guī)律性以及相關(guān)性等特點(diǎn),其算法也具有一致性、鄰域性、行順序性的特點(diǎn),為圖像并行計(jì)算創(chuàng)造了良好的條件。并行總的來(lái)說(shuō)可以分為兩類:數(shù)據(jù)并行和任務(wù)并行。目前,對(duì)于任務(wù)分配的研究取得了一定的成果,提出了很多算法模型以及各種任務(wù)優(yōu)先圖。如參考文獻(xiàn)提出了一種基于小波分解的大數(shù)據(jù)圖像數(shù)字融合處理的任務(wù)分解算法模型,啟發(fā)式任務(wù)分配算法多核處理器與網(wǎng)絡(luò)處理器任務(wù)分配算法的研究等。但專門針對(duì)面向云的集群環(huán)境圖像處理的任務(wù)分配研究相對(duì)較少,雖然圖像融合的算法和應(yīng)用取得了一定的成果,但如何提高計(jì)算效率仍是一個(gè)具有挑戰(zhàn)性的研究課題。鑒于此我們采用集群任務(wù)并行處理的思路,監(jiān)測(cè)網(wǎng)絡(luò)節(jié)點(diǎn)計(jì)算力,吸納動(dòng)態(tài)負(fù)載均衡的任務(wù)分配思想,提出基于四叉樹結(jié)構(gòu)的并行計(jì)算任務(wù)分配模型。3關(guān)鍵技術(shù)3.1任務(wù)分配策略圖1為云環(huán)境集群計(jì)算體系結(jié)構(gòu),Web客戶端首先向具有集中控制權(quán)的Web應(yīng)用服務(wù)器發(fā)出服務(wù)請(qǐng)求,依據(jù)負(fù)載均衡的思想和集群環(huán)境下網(wǎng)絡(luò)節(jié)點(diǎn)計(jì)算力估算值,將任務(wù)分派給不同計(jì)算節(jié)點(diǎn)進(jìn)行并發(fā)計(jì)算,再將結(jié)果返回給控制服務(wù)器進(jìn)行整合,最后將結(jié)果發(fā)送回Web客戶端。整個(gè)過程的運(yùn)行效率取決于任務(wù)分派的方式和并行計(jì)算的粒度。這里講的任務(wù)分配策略包括任意分配策略、可計(jì)算力的任務(wù)分配策略、數(shù)據(jù)節(jié)點(diǎn)鄰近分配策略等。下面探討在集群體系下的節(jié)點(diǎn)計(jì)算力模型。3.2節(jié)點(diǎn)節(jié)點(diǎn)vj的估計(jì)定義1網(wǎng)絡(luò)節(jié)點(diǎn):在集群環(huán)境中,除主控服務(wù)器外的通過網(wǎng)絡(luò)相連的計(jì)算機(jī)。定義2任務(wù)粒度:指在一個(gè)服務(wù)中可以分解的任務(wù)數(shù)。定義3網(wǎng)絡(luò)節(jié)點(diǎn)計(jì)算力:通常是指節(jié)點(diǎn)計(jì)算機(jī)在運(yùn)行狀態(tài)下,根據(jù)其自身的CPU內(nèi)核個(gè)數(shù)、CPU頻率、內(nèi)存、IO傳輸速度、硬盤容量以及任務(wù)粒度大小等指標(biāo)所決定的一個(gè)標(biāo)量。具體見式(1):其中,p表示節(jié)點(diǎn)計(jì)算力,Tcomputer(ti)為完成一個(gè)任務(wù)耗時(shí)量;vp=1/fp,其中fp表示CPU頻率,vp為處理速度;Data表示待處理的數(shù)據(jù)量,vp、vB、vIO分別表示處理器速度、總線速度、IO速度,Mem、Num分別表示內(nèi)存容量與CPU核的個(gè)數(shù),Wj,…,n表示權(quán)值,依據(jù)經(jīng)驗(yàn)數(shù)據(jù)進(jìn)行估算,Vol表示硬盤容量。在集群環(huán)境下,完成一個(gè)計(jì)算任務(wù)的耗時(shí)與數(shù)據(jù)傳輸量也有一定的關(guān)系,節(jié)點(diǎn)vi、vj間的傳輸時(shí)間可由式(2)進(jìn)行估算。其中,vi、vj分別表示控制機(jī)與處理機(jī)節(jié)點(diǎn),Data表示待處理的數(shù)據(jù)量,bi,j表示節(jié)點(diǎn)i、j間的帶寬,di,j表示延遲時(shí)間。因此,計(jì)算節(jié)點(diǎn)vj的計(jì)算力可用式(3)表示,為數(shù)據(jù)傳輸時(shí)間與節(jié)點(diǎn)計(jì)算時(shí)間和的倒數(shù),時(shí)間越小,計(jì)算力越大。依據(jù)上述定義,表1、表2、表3分別描述了存儲(chǔ)在主控節(jié)點(diǎn)的3種數(shù)據(jù)結(jié)構(gòu),用于監(jiān)控當(dāng)前系統(tǒng)各節(jié)點(diǎn)的狀態(tài)與任務(wù)分配情況,其中表1是依據(jù)經(jīng)驗(yàn)值得出節(jié)點(diǎn)狀態(tài)參數(shù)權(quán)值表,為表2中的節(jié)點(diǎn)計(jì)算力估算提供參考,表3的作用是記錄整個(gè)系統(tǒng)任務(wù)分配執(zhí)行情況。3.3節(jié)點(diǎn)4的結(jié)構(gòu)四叉樹結(jié)構(gòu)模型實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)的分級(jí),如圖2所示,其中主控服務(wù)器節(jié)點(diǎn)負(fù)責(zé)各級(jí)網(wǎng)絡(luò)節(jié)點(diǎn)性能測(cè)試與整個(gè)系統(tǒng)任務(wù)消息的發(fā)送與處理結(jié)果的回收。3.4級(jí)節(jié)點(diǎn)算法分布式集群體系結(jié)構(gòu)四叉樹任務(wù)分配模型可以考慮兩方面的內(nèi)容。其一就是任務(wù)粒度的劃分;其二就是各處理節(jié)點(diǎn)的任務(wù)分配。下面主要討論節(jié)點(diǎn)的任務(wù)分配問題。如圖3所示,首先將系統(tǒng)中所有的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分級(jí),初始時(shí)分級(jí)方法對(duì)應(yīng)四叉樹結(jié)構(gòu),主控節(jié)點(diǎn)對(duì)應(yīng)根節(jié)點(diǎn),依次類推。其中,主控節(jié)點(diǎn)負(fù)責(zé)向各二級(jí)節(jié)點(diǎn)分配任務(wù),并收集各二級(jí)節(jié)點(diǎn)的負(fù)載信息;二級(jí)節(jié)點(diǎn)在收到主控節(jié)點(diǎn)分配的任務(wù)之后,對(duì)三級(jí)節(jié)點(diǎn)進(jìn)行調(diào)度,安排三級(jí)節(jié)點(diǎn)進(jìn)行相應(yīng)的工作;二級(jí)節(jié)點(diǎn)同時(shí)將自己的負(fù)載情況向主控節(jié)點(diǎn)匯報(bào),主控節(jié)點(diǎn)根據(jù)提供的消息在二級(jí)節(jié)點(diǎn)之間進(jìn)行負(fù)載平衡;三級(jí)節(jié)點(diǎn)在收到二級(jí)節(jié)點(diǎn)的命令之后,開始執(zhí)行相應(yīng)的任務(wù),并將執(zhí)行結(jié)果返還給二級(jí)節(jié)點(diǎn)?？紤]到二級(jí)節(jié)點(diǎn)所起的橋梁作用,有必要重點(diǎn)討論一下該二級(jí)節(jié)點(diǎn)的具體算法,描述如下。步驟1:準(zhǔn)備接收其他節(jié)點(diǎn)(一級(jí)主控節(jié)點(diǎn)、二級(jí)計(jì)算節(jié)點(diǎn)、自己所轄三級(jí)計(jì)算節(jié)點(diǎn))的消息。(1)接收一級(jí)主控節(jié)點(diǎn)分配的任務(wù)。(2)接收其他二級(jí)節(jié)點(diǎn)廣播的負(fù)載信息。(3)如果有可能,接收同級(jí)節(jié)點(diǎn)向自己轉(zhuǎn)移的任務(wù)。(4)接收自己所轄下一級(jí)節(jié)點(diǎn)的響應(yīng)消息。步驟2:如果沒有消息傳遞或收到的任務(wù)不合法,轉(zhuǎn)步驟1,否則執(zhí)行步驟3。步驟3:若本二級(jí)計(jì)算節(jié)點(diǎn)負(fù)載不為空,則開始計(jì)算預(yù)計(jì)所需時(shí)間及資源。(1)在三級(jí)節(jié)點(diǎn)大于等于8個(gè)的情況下,不必考慮三級(jí)節(jié)點(diǎn)的負(fù)載均衡情況,直接將需要計(jì)算的任務(wù)分配給三級(jí)節(jié)點(diǎn);在三級(jí)節(jié)點(diǎn)小于8個(gè)的情況下,依次給三級(jí)節(jié)點(diǎn)分配計(jì)算任務(wù)。此時(shí)由于分配的任務(wù)不均衡,故需要考慮負(fù)載均衡的問題。二級(jí)節(jié)點(diǎn)依據(jù)任務(wù)優(yōu)先級(jí)分配任務(wù)完成后,在一級(jí)主控節(jié)點(diǎn)按照節(jié)點(diǎn)計(jì)算力更新上述節(jié)點(diǎn)狀態(tài)與任務(wù)表。(2)三級(jí)節(jié)點(diǎn)每計(jì)算完成一個(gè)點(diǎn)向二級(jí)節(jié)點(diǎn)發(fā)送一完成信息,二級(jí)節(jié)點(diǎn)每收到一個(gè)完成信息將更新監(jiān)控任務(wù)表(相應(yīng)的任務(wù)數(shù)減1)。當(dāng)三級(jí)節(jié)點(diǎn)空閑時(shí),從表中選擇某一任務(wù)項(xiàng)。(3)當(dāng)任務(wù)表中的三級(jí)節(jié)點(diǎn)所有任務(wù)數(shù)為0,二級(jí)節(jié)點(diǎn)收到所有計(jì)算的完成結(jié)果。(4)計(jì)算并更新自己的負(fù)載信息(任務(wù)數(shù))。(5)定期向其他二級(jí)節(jié)點(diǎn)廣播自己的負(fù)載信息。步驟4:判斷自己的負(fù)載量,如果自己的載荷情況比較重,從任務(wù)表中挑選一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)作為接收者,向該接收者發(fā)送一部分負(fù)載。步驟5:如果收到其他二級(jí)節(jié)點(diǎn)向本核遷移的任務(wù),轉(zhuǎn)步驟3。步驟6:如果自己的任務(wù)完成了,并且其他二級(jí)節(jié)點(diǎn)的負(fù)載均不大于原始負(fù)載情況的45%,則本二級(jí)節(jié)點(diǎn)的工作已經(jīng)完成,向主控節(jié)點(diǎn)進(jìn)行匯報(bào),然后結(jié)束本輪的工作,退出。4分配任務(wù)性能分析為了驗(yàn)證四叉樹任務(wù)分配策略(圖表中簡(jiǎn)寫為QuadTree)性能在同類算法中的優(yōu)劣,設(shè)計(jì)了兩種任務(wù)調(diào)度算法對(duì)比試驗(yàn):FCFS算法和Min-Min算法。FCFS算法的思想是:按照任務(wù)請(qǐng)求的到達(dá)順序給各子節(jié)點(diǎn)分配任務(wù)。Min-Min算法使用所有計(jì)算節(jié)點(diǎn),其思想是:盡量把更多的任務(wù)分配到執(zhí)行速度最快并能最早完成的機(jī)器上,其常用作調(diào)度算法的評(píng)測(cè)基準(zhǔn)。本文以標(biāo)準(zhǔn)的數(shù)字圖像融合過程為例,按如下三大步驟進(jìn)行,分別按任務(wù)粒度為10、50、250、1000任務(wù)數(shù)進(jìn)行性能比較:·將原始圖像增強(qiáng)、消畸變、校準(zhǔn)、去噪;·對(duì)多光譜圖像進(jìn)行RGB到IHS的變換;·對(duì)真彩色圖像和IHS多光譜圖像的亮度成分進(jìn)行直方圖匹配。SimGrid特別適合于集群任務(wù)調(diào)度的模擬和研究,我們利用SimGrid分別模擬和實(shí)現(xiàn)以上3種任務(wù)分配算法,分別對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為4、8進(jìn)行了相關(guān)測(cè)試,測(cè)試結(jié)果見圖4和圖5。5節(jié)點(diǎn)任務(wù)并行機(jī)制本文提出的分布式集群四叉樹任務(wù)分配模型,首先必須對(duì)集群計(jì)算節(jié)點(diǎn)依據(jù)四叉樹結(jié)構(gòu)進(jìn)行劃分,然后對(duì)任務(wù)進(jìn)行適當(dāng)粒度的分解,依據(jù)動(dòng)態(tài)均衡的思想實(shí)時(shí)監(jiān)測(cè)各節(jié)點(diǎn)的計(jì)算力,通過消息機(jī)制及時(shí)更新節(jié)點(diǎn)狀態(tài)表、任務(wù)表,把分解的任務(wù)動(dòng)態(tài)映射到各網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行并