云环境下的一种并行任务划分方法研究

牛伟伟 张千

摘 要： 并行任务划分一直是高性能计算的研究重点。结合地震资料数据处理的应用云环境，以任务运行时间估计模型作为优化目标函数，提出了一种改进的粒子群优化算法，用以解决地震资料任务划分问题。仿真实验证明，改进后的算法增强了全局搜索能力，提高了收敛速度和收敛精度，有效提高了云环境下任务的执行效率。

关键词： 云计算； 地震资料数据处理； 任务划分； 粒子群优化算法； 全局最优

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2014）06-15-04

0 引言

任务划分是实现程序并行化的基础，任务划分策略的好坏直接影响到负载平衡性、通信复杂度、任务间的依赖性以及任务间的同步方式等。在并行计算中常用的任务划分方法是基于任务图划分的方法[1]，但这种方式也存在不足之处，例如对语句的并行性分析过细，导致对任务划分过于复杂。因此，本文结合地震资料处理云处理平台，以任务运行时间估计模型作为优化目标函数，提出了一种改进的粒子群优化算法来解决地震资料数据划分问题。

1 任务划分条件

地震资料数据要充分利用云节点进行处理就必须对其进行划分。地震道是地震数据的基本单位[2]，本文采用的并行方式是把地震资料数据按炮点进行并行化[3-4] ，基于炮点划分的数据任务之间基本不需要通信，其先天的独立性使其能够更好地进行并行计算。综合上述地震数据资料的分析，考虑所搭建的云计算平台的处理性能，将地震资料数据进行作业划分有几个条件。

⑴ 基于共炮集并行划分作业的处理方式具有一定的优点，如在具体划分过程中，可以将一炮数据划分为一个子任务，数据量较大时也可以将几炮数据划为一个子任务，同时这样划分后各个子任务之间的耦合程度非常低，所以这种方式的作业划分类似于批作业松耦合并行调度。

⑵ 云计算节点划分时，结合模糊聚类中“物以类聚”的思想，将计算存储等性能相差不大的节点归为一类，让每个作业队列面对一个自治的节点区域，该种处理方式能够结合作业大小的划分，体现出高性能节点处理复杂任务，低性能节点处理简单任务的优势。

⑶ 划分完地震资料数据后，可采用基于HDFS的共享分布式存储方式，通过这种方式，所有子任务的数据都通过NameNode集中式管理，在具体的任务执行开始，作业服务器会初始的数据进行按队列与资源节点匹配程度分发，将要处理的任务分配到数据存在的节点执行，这样在任务执行过程可以减少网络通信要求，任务结束后再从各处理结点返回处理结果到共享存储结点，进行结果的合并处理。这种存储方式能够显著提高处理海量数据时系统的整体效率。

2 任务划分策略

由于地震数据资料具有粗粒度、松耦合的并行化特点，数据之间联系较少，因此不适合用基于图划分工具的任务划分方法[9]，并且云计算环境的广域性和动态性决定了任务划分要受到诸多因素的影响，对于可分任务，对其分解策略要视环境而定。根据资源的负载能力进行合理的划分，如果粒度划分太细，网速传输及任务启动等消耗太大，而如果粒度太大就不能充分利用现有的计算资源。因此，云环境下的任务划分可以归结为优化问题，本文以任务运行时间估计模型作为优化目标函数，采用了一种改进的粒子群优化算法对任务进行优化划分。

2.1 任务运行时间模型

如图1所示，根据云资源节点信息对数据块进行预处理，将处理后的任务装载到活动池，活动与服务映射程序从活动池取活动执行映射，在活动执行过程中对主数据块进行处理。在预处理阶段对前驱数据PWD进行划分，然后将数据进行分解加入到活动池中，分解过程可能要附加额外数据，所以，在分解过程中引入膨胀因子inf，并且inf≥1。

预处理过程中用到的资源属性参数定义如下。

2.2 改进的粒子群优化算法

粒子在二维空间迭代过程如图2所示，展示了该粒子从位置zk迭代到位置zk+1的过程，并反映了式⑸的迭代过程，图2中v1是局部最优值pbest导致的改变速度，vk是这一时刻此粒子所具有的速度，v3是改进算法后加入的改变量，它使粒子更趋向于全局最优解，v2是全局最优值gbest引起的该粒子向gbest方向的改变速度，而速度v是使用经典粒子群公式⑵所产生的改变后的速度，速度v是受vk，v1，v2共同影响下所产生的速度矢量，由此位置矢量改为zk+1，速度vk+1是采用公式⑷所改变的速度矢量，速度vk+1是受vk，v1，v2，v3的共同影响下所产生的速度矢量，由此产生的位置迭代为为zk+1。下一时刻，该粒子会从位置zk迭代到位置zk+1，经历如此迭代过程后，所有粒子将向全局最优点靠近，最终达到精度要求的较优解。

综上所述，云环境下使用改进的粒子群算法，进行地震数据资料任务划分的步骤如下：

① 对总数据快进行预处理，划分PWD数据块；

② 对PWD数据划分，把划分后的活动压入到活动池中等待处理；

③ 对主数据MainD进行划分。

选择最大迭代次数Nmax和阈值ξ；

3 实验结果与性能分析

3.1 实验设计

采用标准测试函数Schaffers F6函数[11]来分析和测试该改进算法的性能，如下所示：

此函数只有一个全局最大值点f（0，0）=1，在全局最大值周围有一圈极值点，均值为0.990283。为了和原粒子群算法公平比较，两种算法在同样的实验环境下运行，采用下面三种测试方法。

TEST 1：测试算法在达到预设的最大迭代次数时的最优值。针对基准函数测试10次，然后取最优解的平均，目的是比较改进的算法与原算法的寻优结果。

TEST 2：测试算法在达到预设的运算精度的耗时。目的是比较两个算法的收敛速度。针对函数每次测试10次，然后取平均。

TEST 3：测试改进后算法对任务调度性能的影响。测试用例采用了100×1000和1000×1000的矩阵相乘，采用改进后算法将任务进行分解，然后采用FCFS算法进行任务的调度，测试运行的时间。

3.2 实验结果及分析

TEST 1和TEST 2的测试结果如表1和表2所示，由于篇幅原因只列出5次测试的结果。通过分析表1和表2中的数据，我们归纳为以下两点。

⑴ 当迭代次数固定为2000次时，表1中经典粒子群算法所得到的解的平均值为0.9909125，表2中改进的粒子群算法的解的平均值为0.9937346。由此可知，在相同迭代次数的情况下，改进的粒子群算法比经典粒子群算法寻优能力更强，求出的最优解更精确。

4 结束语

本文结合地震资料数据处理，研究了云环境下的任务划分问题，对于可分任务，对其分解策略要视环境而定。根据资源的负载能力进行合理的划分，如果粒度的太细，网速传输、任务启动等消耗太大；而如果粒度太大，又不能充分地利用现有的计算资源。因此结合地震资料任务粗粒度、松耦合的并行化特点，提出了一种改进的粒子群优化算法进行任务优化划分。

实验结果表明，改进后的算法收敛速度更快，达到了提高整体任务执行效率的目的。下一步的研究是如何实现更为复杂的数据处理与调度工作。

参考文献：

[1] 郝水侠，曾国荪，谭一鸣等.一种基于DAG图的异构可重构任务划分方法[J].同济大学学报（自然科学版），2011.39（11）：1693-1698

[2] 赵长海，晏海华，王宏琳，史晓华，王雷.面向地震数据处理的并行与分布式编程框架[J].石油地球物理勘探，2010.12（1）：146-155

[3] 李建江，舒继武，王有新，王鼎兴，郑纬民.一种基于共享存储的叠前深度偏移并行算法[J].软件学报，2002.13（12）：2231-2236

[4] 王宏琳.基于网络的地震数据处理—从集群计算系统到云计算系统[J].石油地球物理勘探，2003.38（4）：381-386

[5] Saaty T. Decision making with the analytic hierarchy process.International Journal of Services Sciences，2008.1：83-98

[6] 张伟哲，田志宏，张宏莉，何慧，刘文懋.虚拟计算环境中的多机群协同调度算法[J].Journal of Software，2007.18（8）：2027-2037

[7] Lech Kurowski， David Sussman， Investment Project Design： AGuide to Financial and Economic Analysis with Constraints[M]，2011：354

[8] Shufen Zhang， Shuai Zhang， Xuebin Chen， Shangzhuo Wu.Analysis and Research of Cloud Computing System Instance[J].2010 Second International Conference on Future Networks，2010.60：88-92

[9] 蒋廷耀，李庆华.DAG任务图的一种调度算法[J].小型微型计算机系统，2003.24（10）：1796-1799

[10] 李民，蒋慕蓉，肖清，高毅.云计算中的简单任务划分方法[J].云南大学学报（自然科学版），2007.29（S1）：59-63

[11] Jun Sun， Bin Feng， Wenbo XU. Particle Swarm Optimizationwith Particles Having Quantum Behavior[A].Proc 2004 Congress on Evolutionary Computation[C]，2004：325-331