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

曾 志 ，刘仁义 ，张 丰 ，刘 南

（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