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

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

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

1 引言

云計算普遍被認為是當今計算發(fā)展的主流。參考文獻[1]和[2]詳細地分析了云計算的幾大特征與瓶頸，指出了以數(shù)據(jù)為中心的高性能計算是分布式集群計算的基礎(chǔ)。云計算是一種計算模式，它主要用來解決服務(wù)器與PC之間存儲資源共享和數(shù)據(jù)共享的問題。參考文獻[3]從成本的角度研究了云環(huán)境下集群系統(tǒng)釋放CO2的影響，從能效的角度研究了計算能耗的數(shù)學模型。根據(jù)云計算的特征，云計算技術(shù)必須是建立在高速、穩(wěn)定、低廉、基于應(yīng)用的網(wǎng)絡(luò)基礎(chǔ)之上，所提供的各種服務(wù)以高性能計算為主要技術(shù)手段。云計算被認為提供3種服務(wù)，分別是基礎(chǔ)設(shè)施服務(wù)（IaaS）、軟件服務(wù)（SaaS）以及平臺服務(wù)（PaaS）。軟件作為服務(wù)的前提是能提供高效可靠的海量數(shù)據(jù)并行處理能力。

2 問題提出

隨著遙感圖像分辨率的不斷提高，每一景圖像的數(shù)據(jù)量大增，計算量也相應(yīng)增加。根據(jù)圖像數(shù)據(jù)本身存儲的規(guī)律性以及相關(guān)性等特點，其算法也具有一致性、鄰域性、行順序性的特點，為圖像并行計算創(chuàng)造了良好的條件。并行總的來說可以分為兩類：數(shù)據(jù)并行和任務(wù)并行。目前，對于任務(wù)分配的研究取得了一定的成果，提出了很多算法模型以及各種任務(wù)優(yōu)先圖。如參考文獻[4]提出了一種基于小波分解的大數(shù)據(jù)圖像數(shù)字融合處理的任務(wù)分解算法模型，啟發(fā)式任務(wù)分配算法[5]多核處理器與網(wǎng)絡(luò)處理器任務(wù)分配算法的研究等。但專門針對面向云的集群環(huán)境圖像處理的任務(wù)分配研究相對較少，雖然圖像融合的算法和應(yīng)用取得了一定的成果，但如何提高計算效率仍是一個具有挑戰(zhàn)性的研究課題。鑒于此我們采用集群任務(wù)并行處理的思路，監(jiān)測網(wǎng)絡(luò)節(jié)點計算力，吸納動態(tài)負載均衡的任務(wù)分配思想，提出基于四叉樹結(jié)構(gòu)的并行計算任務(wù)分配模型。

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

3.1 集群體系模型

圖1為云環(huán)境集群計算體系結(jié)構(gòu)，Web客戶端首先向具有集中控制權(quán)的Web應(yīng)用服務(wù)器發(fā)出服務(wù)請求，依據(jù)負載均衡的思想和集群環(huán)境下網(wǎng)絡(luò)節(jié)點計算力估算值，將任務(wù)分派給不同計算節(jié)點進行并發(fā)計算，再將結(jié)果返回給控制服務(wù)器進行整合，最后將結(jié)果發(fā)送回Web客戶端。整個過程的運行效率取決于任務(wù)分派的方式和并行計算的粒度。這里講的任務(wù)分配策略包括任意分配策略、可計算力的任務(wù)分配策略、數(shù)據(jù)節(jié)點鄰近分配策略等。下面探討在集群體系下的節(jié)點計算力模型。

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

定義1網(wǎng)絡(luò)節(jié)點：在集群環(huán)境中，除主控服務(wù)器外的通過網(wǎng)絡(luò)相連的計算機。

定義2任務(wù)粒度：指在一個服務(wù)中可以分解的任務(wù)數(shù)。

定義3網(wǎng)絡(luò)節(jié)點計算力：通常是指節(jié)點計算機在運行狀態(tài)下，根據(jù)其自身的CPU內(nèi)核個數(shù)、CPU頻率、內(nèi)存、IO傳輸速度、硬盤容量以及任務(wù)粒度大小等指標所決定的一個標量。具體見式（1）：

其中，p表示節(jié)點計算力，Tcomputer(ti)為完成一個任務(wù)耗時量；vp=1/fp，其中 fp表示 CPU 頻率，vp為處理速度；Data表示待處理的數(shù)據(jù)量，vp、vB、vIO分別表示處理器速度、總線速度、IO速度，Mem、Num分別表示內(nèi)存容量與CPU核的個數(shù)，Wj,…,n表示權(quán)值，依據(jù)經(jīng)驗數(shù)據(jù)進行估算，Vol表示硬盤容量。

在集群環(huán)境下，完成一個計算任務(wù)的耗時與數(shù)據(jù)傳輸量也有一定的關(guān)系，節(jié)點vi、vj間的傳輸時間可由式（2）進行估算。

其中，vi、vj分別表示控制機與處理機節(jié)點，Data表示待處理的數(shù)據(jù)量，bi,j表示節(jié)點i、j間的帶寬，di,j表示延遲時間。因此，計算節(jié)點vj的計算力可用式（3）表示，為數(shù)據(jù)傳輸時間與節(jié)點計算時間和的倒數(shù)，時間越小，計算力越大。

依據(jù)上述定義，表1、表2、表3分別描述了存儲在主控節(jié)點的3種數(shù)據(jù)結(jié)構(gòu)，用于監(jiān)控當前系統(tǒng)各節(jié)點的狀態(tài)與任務(wù)分配情況，其中表1是依據(jù)經(jīng)驗值得出節(jié)點狀態(tài)參數(shù)權(quán)值表，為表2中的節(jié)點計算力估算提供參考，表3的作用是記錄整個系統(tǒng)任務(wù)分配執(zhí)行情況。

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

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

表3 任務(wù)登記表

3.3 四叉樹結(jié)構(gòu)計算節(jié)點

四叉樹結(jié)構(gòu)模型實現(xiàn)網(wǎng)絡(luò)節(jié)點的分級，如圖2所示，其中主控服務(wù)器節(jié)點負責各級網(wǎng)絡(luò)節(jié)點性能測試與整個系統(tǒng)任務(wù)消息的發(fā)送與處理結(jié)果的回收。

3.4 集群環(huán)境四叉樹任務(wù)分配模型

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

如圖3所示，首先將系統(tǒng)中所有的網(wǎng)絡(luò)節(jié)點進行分級，初始時分級方法對應(yīng)四叉樹結(jié)構(gòu)，主控節(jié)點對應(yīng)根節(jié)點，依次類推。其中，主控節(jié)點負責向各二級節(jié)點分配任務(wù)，并收集各二級節(jié)點的負載信息；二級節(jié)點在收到主控節(jié)點分配的任務(wù)之后，對三級節(jié)點進行調(diào)度，安排三級節(jié)點進行相應(yīng)的工作；二級節(jié)點同時將自己的負載情況向主控節(jié)點匯報，主控節(jié)點根據(jù)提供的消息在二級節(jié)點之間進行負載平衡；三級節(jié)點在收到二級節(jié)點的命令之后，開始執(zhí)行相應(yīng)的任務(wù)，并將執(zhí)行結(jié)果返還給二級節(jié)點?？紤]到二級節(jié)點所起的橋梁作用，有必要重點討論一下該二級節(jié)點的具體算法，描述如下。

步驟1：準備接收其他節(jié)點(一級主控節(jié)點、二級計算節(jié)點、自己所轄三級計算節(jié)點)的消息。

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

②接收其他二級節(jié)點廣播的負載信息。

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

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

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

步驟3：若本二級計算節(jié)點負載不為空，則開始計算預(yù)計所需時間及資源。

① 在三級節(jié)點大于等于8個的情況下，不必考慮三級節(jié)點的負載均衡情況，直接將需要計算的任務(wù)分配給三級節(jié)點；在三級節(jié)點小于8個的情況下，依次給三級節(jié)點分配計算任務(wù)。此時由于分配的任務(wù)不均衡，故需要考慮負載均衡的問題。二級節(jié)點依據(jù)任務(wù)優(yōu)先級分配任務(wù)完成后，在一級主控節(jié)點按照節(jié)點計算力更新上述節(jié)點狀態(tài)與任務(wù)表。

②三級節(jié)點每計算完成一個點向二級節(jié)點發(fā)送一完成信息，二級節(jié)點每收到一個完成信息將更新監(jiān)控任務(wù)表(相應(yīng)的任務(wù)數(shù)減1)。當三級節(jié)點空閑時，從表中選擇某一任務(wù)項。

③ 當任務(wù)表中的三級節(jié)點所有任務(wù)數(shù)為0，二級節(jié)點收到所有計算的完成結(jié)果。

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

⑤ 定期向其他二級節(jié)點廣播自己的負載信息。

步驟4：判斷自己的負載量，如果自己的載荷情況比較重，從任務(wù)表中挑選一個網(wǎng)絡(luò)節(jié)點作為接收者，向該接收者發(fā)送一部分負載。

步驟5：如果收到其他二級節(jié)點向本核遷移的任務(wù)，轉(zhuǎn)步驟3。

步驟6：如果自己的任務(wù)完成了，并且其他二級節(jié)點的負載均不大于原始負載情況的45%，則本二級節(jié)點的工作已經(jīng)完成，向主控節(jié)點進行匯報，然后結(jié)束本輪的工作，退出。

4 系統(tǒng)實例與性能分析

為了驗證四叉樹任務(wù)分配策略（圖表中簡寫為QuadTree）性能在同類算法中的優(yōu)劣，設(shè)計了兩種任務(wù)調(diào)度算法對比試驗：FCFS算法和Min-Min算法。FCFS算法的思想是：按照任務(wù)請求的到達順序給各子節(jié)點分配任務(wù)。Min-Min算法使用所有計算節(jié)點,其思想是：盡量把更多的任務(wù)分配到執(zhí)行速度最快并能最早完成的機器上,其常用作調(diào)度算法的評測基準[10]。本文以標準的數(shù)字圖像融合過程為例，按如下三大步驟進行，分別按任務(wù)粒度為10、50、250、1 000 任務(wù)數(shù)進行性能比較：

· 將原始圖像增強、消畸變、校準、去噪；

·對多光譜圖像進行RGB到IHS的變換；

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

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

5 結(jié)束語

本文提出的分布式集群四叉樹任務(wù)分配模型，首先必須對集群計算節(jié)點依據(jù)四叉樹結(jié)構(gòu)進行劃分，然后對任務(wù)進行適當粒度的分解，依據(jù)動態(tài)均衡的思想實時監(jiān)測各節(jié)點的計算力，通過消息機制及時更新節(jié)點狀態(tài)表、任務(wù)表，把分解的任務(wù)動態(tài)映射到各網(wǎng)絡(luò)節(jié)點進行并行計算的一個過程。通過實驗得出以下結(jié)論：

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

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

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

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

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 林偉偉等.樹型網(wǎng)格計算環(huán)境下的獨立任務(wù)調(dià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è)大學學報，2004(5)：89～92

5 劉軼等.一種面向多核處理器并行系統(tǒng)的啟發(fā)式任務(wù)分配算法.計算機研究與發(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 劉振英等.一個有效的動態(tài)負載平衡算法.軟件學報，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