面向云的分布式集群四叉樹(shù)任務(wù)分配策略*

曾 志 ，劉仁義 ，張 豐 ，劉 南

（1.浙江大學(xué)省資源與環(huán)境重點(diǎn)實(shí)驗(yàn)室 杭州310028；2.浙江大學(xué)地理信息科學(xué)研究所 杭州 310028）

1 引言

云計(jì)算普遍被認(rèn)為是當(dāng)今計(jì)算發(fā)展的主流。參考文獻(xiàn)[1]和[2]詳細(xì)地分析了云計(jì)算的幾大特征與瓶頸，指出了以數(shù)據(jù)為中心的高性能計(jì)算是分布式集群計(jì)算的基礎(chǔ)。云計(jì)算是一種計(jì)算模式，它主要用來(lái)解決服務(wù)器與PC之間存儲(chǔ)資源共享和數(shù)據(jù)共享的問(wèn)題。參考文獻(xiàn)[3]從成本的角度研究了云環(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 問(wèn)題提出

隨著遙感圖像分辨率的不斷提高，每一景圖像的數(shù)據(jù)量大增，計(jì)算量也相應(yīng)增加。根據(jù)圖像數(shù)據(jù)本身存儲(chǔ)的規(guī)律性以及相關(guān)性等特點(diǎn)，其算法也具有一致性、鄰域性、行順序性的特點(diǎn)，為圖像并行計(jì)算創(chuàng)造了良好的條件。并行總的來(lái)說(shuō)可以分為兩類(lèi)：數(shù)據(jù)并行和任務(wù)并行。目前，對(duì)于任務(wù)分配的研究取得了一定的成果，提出了很多算法模型以及各種任務(wù)優(yōu)先圖。如參考文獻(xiàn)[4]提出了一種基于小波分解的大數(shù)據(jù)圖像數(shù)字融合處理的任務(wù)分解算法模型，啟發(fā)式任務(wù)分配算法[5]多核處理器與網(wǎng)絡(luò)處理器任務(wù)分配算法的研究等。但專(zhuān)門(mén)針對(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ù)分配思想，提出基于四叉樹(shù)結(jié)構(gòu)的并行計(jì)算任務(wù)分配模型。

3 關(guān)鍵技術(shù)

3.1 集群體系模型

圖1為云環(huán)境集群計(jì)算體系結(jié)構(gòu)，Web客戶(hù)端首先向具有集中控制權(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客戶(hù)端。整個(gè)過(guò)程的運(yùn)行效率取決于任務(wù)分派的方式和并行計(jì)算的粒度。這里講的任務(wù)分配策略包括任意分配策略、可計(jì)算力的任務(wù)分配策略、數(shù)據(jù)節(jié)點(diǎn)鄰近分配策略等。下面探討在集群體系下的節(jié)點(diǎn)計(jì)算力模型。

3.2 網(wǎng)絡(luò)節(jié)點(diǎn)計(jì)算力模型

定義1網(wǎng)絡(luò)節(jié)點(diǎn)：在集群環(huán)境中，除主控服務(wù)器外的通過(guò)網(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傳輸速度、硬盤(pán)容量以及任務(wù)粒度大小等指標(biāo)所決定的一個(gè)標(biāo)量。具體見(jiàn)式（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表示硬盤(pán)容量。

在集群環(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í)行情況。

表1 節(jié)點(diǎn)狀態(tài)參數(shù)權(quán)值分配表

表2 節(jié)點(diǎn)狀態(tài)登記表

表3 任務(wù)登記表

3.3 四叉樹(shù)結(jié)構(gòu)計(jì)算節(jié)點(diǎn)

四叉樹(shù)結(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 集群環(huán)境四叉樹(shù)任務(wù)分配模型

分布式集群體系結(jié)構(gòu)四叉樹(shù)任務(wù)分配模型可以考慮兩方面的內(nèi)容。其一就是任務(wù)粒度的劃分；其二就是各處理節(jié)點(diǎn)的任務(wù)分配。下面主要討論節(jié)點(diǎn)的任務(wù)分配問(wèn)題。

如圖3所示，首先將系統(tǒng)中所有的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分級(jí)，初始時(shí)分級(jí)方法對(duì)應(yīng)四叉樹(shù)結(jié)構(gòu)，主控節(jié)點(diǎn)對(duì)應(yīng)根節(jié)點(diǎn)，依次類(lèi)推。其中，主控節(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)的命令之后，開(kāi)始執(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))的消息。

①接收一級(jí)主控節(jié)點(diǎn)分配的任務(wù)。

②接收其他二級(jí)節(jié)點(diǎn)廣播的負(fù)載信息。

③ 如果有可能，接收同級(jí)節(jié)點(diǎn)向自己轉(zhuǎn)移的任務(wù)。

④接收自己所轄下一級(jí)節(jié)點(diǎn)的響應(yīng)消息。

步驟2：如果沒(méi)有消息傳遞或收到的任務(wù)不合法，轉(zhuǎn)步驟1，否則執(zhí)行步驟3。

步驟3：若本二級(jí)計(jì)算節(jié)點(diǎn)負(fù)載不為空，則開(kāi)始計(jì)算預(yù)計(jì)所需時(shí)間及資源。

① 在三級(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ù)載均衡的問(wèn)題。二級(jí)節(jié)點(diǎn)依據(jù)任務(wù)優(yōu)先級(jí)分配任務(wù)完成后，在一級(jí)主控節(jié)點(diǎn)按照節(jié)點(diǎn)計(jì)算力更新上述節(jié)點(diǎn)狀態(tài)與任務(wù)表。

②三級(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)。

③ 當(dāng)任務(wù)表中的三級(jí)節(jié)點(diǎn)所有任務(wù)數(shù)為0，二級(jí)節(jié)點(diǎn)收到所有計(jì)算的完成結(jié)果。

④ 計(jì)算并更新自己的負(fù)載信息（任務(wù)數(shù)）。

⑤ 定期向其他二級(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 系統(tǒng)實(shí)例與性能分析

為了驗(yàn)證四叉樹(shù)任務(wù)分配策略（圖表中簡(jiǎn)寫(xiě)為QuadTree）性能在同類(lèi)算法中的優(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)[10]。本文以標(biāo)準(zhǔn)的數(shù)字圖像融合過(guò)程為例，按如下三大步驟進(jìn)行，分別按任務(wù)粒度為10、50、250、1 000 任務(wù)數(shù)進(jìn)行性能比較：

· 將原始圖像增強(qiáng)、消畸變、校準(zhǔn)、去噪；

·對(duì)多光譜圖像進(jìn)行RGB到IHS的變換；

·對(duì)真彩色圖像和IHS多光譜圖像的亮度成分進(jìn)行直方圖匹配。

SimGrid特別適合于集群任務(wù)調(diào)度的模擬和研究[3]，我們利用 SimGrid[7]分別模擬和實(shí)現(xiàn)以上3種任務(wù)分配算法，分別對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為4、8進(jìn)行了相關(guān)測(cè)試,測(cè)試結(jié)果見(jiàn)圖4和圖5。

5 結(jié)束語(yǔ)

本文提出的分布式集群四叉樹(shù)任務(wù)分配模型，首先必須對(duì)集群計(jì)算節(jié)點(diǎn)依據(jù)四叉樹(shù)結(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ì)算力，通過(guò)消息機(jī)制及時(shí)更新節(jié)點(diǎn)狀態(tài)表、任務(wù)表，把分解的任務(wù)動(dòng)態(tài)映射到各網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行并行計(jì)算的一個(gè)過(guò)程。通過(guò)實(shí)驗(yàn)得出以下結(jié)論：

（1）基于四叉樹(shù)結(jié)構(gòu)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的劃分，方便網(wǎng)絡(luò)節(jié)點(diǎn)的控制，分工明確合理；

（2）采用負(fù)載均衡思想的集群任務(wù)并行機(jī)制運(yùn)算提高了算法執(zhí)行速度；

（3）任務(wù)粒度的劃分，也將不同程度地影響計(jì)算的整體效率；

（4）集群環(huán)境四叉樹(shù)任務(wù)分配策略能有效提高云計(jì)算的性能，為高性能計(jì)算系統(tǒng)級(jí)控制提供了一個(gè)有效的實(shí)例。

1 Saurabh K G,Chee S Y,etal.Environment-conscious scheduling of HPC applications on distributed cloud-oriented data centers.Journal of Parallel and Distributed Computing,May 2010

2 林偉偉等.樹(shù)型網(wǎng)格計(jì)算環(huán)境下的獨(dú)立任務(wù)調(diào)度.軟件學(xué)報(bào)，2006，17（11）

3 Ian Foster,ZhaoYong,etal.Cloud computing and grid computing 360-degree compared.In:International Conference on GCE08 Clouds Grids,2008

4 程英蕾,趙榮椿.一種基于小波包變換的SAR圖像與TM圖像融合方法.西北工業(yè)大學(xué)學(xué)報(bào)，2004(5)：89～92

5 劉軼等.一種面向多核處理器并行系統(tǒng)的啟發(fā)式任務(wù)分配算法.計(jì)算機(jī)研究與發(fā)展，2009,46(6)：1058～1064

6 Casanova H.Simgrid:a toolkit for the simulation of application scheduling.Brisbane:IEEE Computer Society Press,2001

7 Stefan Chevul,Andreas Binzenhfer,Matthias Schmid,et al.A self-organizing concept for distributed end-to-end quality monitoring. University of Wurzburg Institute, Wurzburg,Germany,2006

8 劉振英等.一個(gè)有效的動(dòng)態(tài)負(fù)載平衡算法.軟件學(xué)報(bào)，2001,12(4)：563～569

9 Braun T D,Siegel H J,Beck N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems.Journal of Parallel and Distributed Computing,2001,61(6):810～837

10 Kwok Y K， Ahmad I.On multiprocessor task scheduling using efficient state space search approaches.Journal of Parallel and Distributed Computing,2005,65(12)：1515～1532

11 Liu Zhen,Rhonda R.Optimal parallel processing of random task graphs.Journal of Scheduling 2001,3(4):139～156

12 Wu Qishi,Zhu Mengxia,et al.System design and algorithmic development for computational steering in distributed environments.In：Proc of the 14th IEEE Int Conf on Parallel and Distributed Systems,Melbourne,Australia,Dec 2008