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

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

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

1 引言

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

2 問題提出

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

3 關鍵技術

3.1 集群體系模型

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

3.2 網絡節點計算力模型

定義1網絡節點：在集群環境中，除主控服務器外的通過網絡相連的計算機。

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

定義3網絡節點計算力：通常是指節點計算機在運行狀態下，根據其自身的CPU內核個數、CPU頻率、內存、IO傳輸速度、硬盤容量以及任務粒度大小等指標所決定的一個標量。具體見式（1）：

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

在集群環境下，完成一個計算任務的耗時與數據傳輸量也有一定的關系，節點vi、vj間的傳輸時間可由式（2）進行估算。

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

依據上述定義，表1、表2、表3分別描述了存儲在主控節點的3種數據結構，用于監控當前系統各節點的狀態與任務分配情況，其中表1是依據經驗值得出節點狀態參數權值表，為表2中的節點計算力估算提供參考，表3的作用是記錄整個系統任務分配執行情況。

表1 節點狀態參數權值分配表

表2 節點狀態登記表

表3 任務登記表

3.3 四叉樹結構計算節點

四叉樹結構模型實現網絡節點的分級，如圖2所示，其中主控服務器節點負責各級網絡節點性能測試與整個系統任務消息的發送與處理結果的回收。

3.4 集群環境四叉樹任務分配模型

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

如圖3所示，首先將系統中所有的網絡節點進行分級，初始時分級方法對應四叉樹結構，主控節點對應根節點，依次類推。其中，主控節點負責向各二級節點分配任務，并收集各二級節點的負載信息；二級節點在收到主控節點分配的任務之后，對三級節點進行調度，安排三級節點進行相應的工作；二級節點同時將自己的負載情況向主控節點匯報，主控節點根據提供的消息在二級節點之間進行負載平衡；三級節點在收到二級節點的命令之后，開始執行相應的任務，并將執行結果返還給二級節點。考慮到二級節點所起的橋梁作用，有必要重點討論一下該二級節點的具體算法，描述如下。

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

①接收一級主控節點分配的任務。

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

③ 如果有可能，接收同級節點向自己轉移的任務。

④接收自己所轄下一級節點的響應消息。

步驟2：如果沒有消息傳遞或收到的任務不合法，轉步驟1，否則執行步驟3。

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

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

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

③ 當任務表中的三級節點所有任務數為0，二級節點收到所有計算的完成結果。

④ 計算并更新自己的負載信息（任務數）。

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

步驟4：判斷自己的負載量，如果自己的載荷情況比較重，從任務表中挑選一個網絡節點作為接收者，向該接收者發送一部分負載。

步驟5：如果收到其他二級節點向本核遷移的任務，轉步驟3。

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

4 系統實例與性能分析

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

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

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

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

SimGrid特別適合于集群任務調度的模擬和研究[3]，我們利用 SimGrid[7]分別模擬和實現以上3種任務分配算法，分別對網絡節點數為4、8進行了相關測試,測試結果見圖4和圖5。

5 結束語

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

（1）基于四叉樹結構對網絡節點的劃分，方便網絡節點的控制，分工明確合理；

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

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

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

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 林偉偉等.樹型網格計算環境下的獨立任務調度.軟件學報，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圖像融合方法.西北工業大學學報，2004(5)：89～92

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