论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　摘要：遥感技术的进步使遥感数据质量得以提高，体量急剧增长，因此有必要研制高效的遥感数据处理集群系统用于提高遥感数据处理的效能。对遥感数据处理的时效性评估可以从处理效率和计算资源利用率两个角度进行评估。提出一种结合遥感数据处理先验值的动态双向实时匹配调度算法，即同步考虑先验值、任务情况和计算节点状态的双向调度的方法。实验结果表明，该算法有效的提高了集群系统的遥感数据处理效能。

　　关键词：任务调度；动态双向匹配；遥感数据处理；集群

　　引言

　　随着遥感技术的快速发展，遥感数据量呈现几何级增长，实际应用中对遥感数据处理的时间和精度要求越来越高。集群处理系统的出现大大提高了遥感数据处理的速度。高效的遥感数据处理集群调度方法，是充分发挥集群平台优势的关键所在。

　　中国科学院遥感与数字地球研究所研制的面向遥感数据高性能处理集群系统[1，11]具有成本可控、可靠性高、扩展性强等特点，该集群系统的作业调度模块包括调度节点和计算节点两个部分。调度节点是集群系统中某一台计算机，负责整个集群系统资源分配和任务的调度，保存有面向任务队列和面向计算节点队列。此外，调度节点上存储有各个计算节点的负载信息表，表中保存有计算节点的一些实时信息如计算节点MAC地址，CPU利用率等，还存有生产各种遥感产品所需要的平均时间等。计算节点是集群系统中所有计算机，调度节点也可作为计算节点使用。每个（台）计算节点都连接到调度节点，负责接收调度发来的产品生产任务，和调度节点协同完成工作，计算节点还带有各种产品生产所需要的动态库、参数等信息；数据的组织管理采用五层十五级标准[2]。

　　目前，常用的任务调度算法有：先来先服务算法、双匹配动态模型算法、截止期最早优先等。这些算法都各有特点。先来先服务算法[10]就是根据到达的先后顺序调度执行，结构简单容易实现，但该算法短作业在系统中的驻留平均时间与长作业的驻留平均时间相同，这对短作业是不利的；双匹配动态算法[6]能够较好地实现负载与系统吞吐率的平衡，但当系统中任务量逐渐增多时，性能快速下降；截止期最早最优先算法[12]根据任务截止期来决定任务执行顺序，让截止期最早的任务优先执行，但是截止期最早的任务并不一定是最重要的任务。然而上述任务调度算法，均未考虑到遥感影像数据量大、产品算法耗时长的特点。

　　1集群调度算法模型

　　本文设计的集群调度算法模型是一种结合遥感数据处理先验值的动态双向实时匹配调度算法模型，由面向任务队列模型和面向计算节点队列模型两个部分组成。其主要思路是：在结合先验值的情况下，一方面，面向任务时考虑任务等待时间和任务量大小等因素来确定任务队列；另一方面，面向计算资源时，在动态获取计算资源负载率的情况下，形成一个计算资源队列；将最优计算资源匹配给优先级最高的任务，从而完成任务和计算资源的动态双向匹配。

　　1.1先验值获取

　　本文使用的先验值定义为集群处理某类产品时，根据各个并行节点反馈到调度节点上的该类产品的处理时间，取平均值。

　　先验值是动态更新的，这种动态更新使先验值的存在更具参考性，当节点上反馈新的该类产品生产时间信息时，和该先验值再取平均值作为新的先验值。得到的先验值在调度中的数据结构，用Map型数据结构方式记录下来，Key代表是计算节点处理的任务类型，Value是代表节点处理此类型任务所用的时间。

　　1.2面向任务队列模型

　　当有任务提交时，这些任务首先被分成两类：有权重任务和无权重任务（权重即任务的紧急程度，由提交任务指定）。分别对其进行处理：对有权重值的任务，进行权重比较，根据权重大小顺序将任务放入任务队列；对待无权重的任务，根据待处理任务的基本信息（包括任务量大小、作业类型、等待时间等），结合之前处理该类型作业的时间进行执行时间的预估。任务队列用Q={T1，T2，…，Tn}表示。

　　⑴Ti：第i个任务的加权时间和。

　　⑵Si：第i种任务的任务量。

　　⑶Twait（i）：执行Si需等待时间，刚进入队列时，初始化Twait（i）为0。

　　⑷Ttype（i）：任务的类型。用这个值可以查阅每种类型任务的平均执行时间，做出任务执行时间的参考。

　　其中i=1，2，3，…，n，考虑到每个任务从提交到执行会有一个等待时间Twait（i），得到Ti计算公式：

　　⑴

　　公式⑴中的Ti表示任务从提交到执行完成需要的时间的一个加权时间和（等待时间和预估完成时间加权和），Txi（Si，Ttype（i））代表根据先验值预估出任务开始执行到结束的时间，任务量大小Si和根据任务类型Ttype（i）（如生产NDVI产品），如任务量大小是100个瓦片数据（瓦片数据：对原始遥感影像按照五层十五级标准进行规格化处理），类型是NDVI产品，根据表1中NDVI产品的先验值（这些先验值是通过在表2所示的软硬件环境中测得），查表可知生产一个NDVI产品所需要的时间的平均值是0.191s，所以预估时间Txi为100*0.191=19.1s，最后根据获得的Ti（i=1，2...n）的大小得到一个顺序加入任务队列Q。公式中⑴中的α，β值分别是Twait（i）和Txi（Si，Ttype（i））的比重系数，前期实验时分别设置α，β的值均为0.5和0.5，经过多次试验得到一组效果相对较好的数值{0.6，0.4}，本文运用这组系数进行仿真实验，也可以根据实际情况修正该参数，最终找到一组合适的系数。

　　其中j=1，2，3，…，n，根据收集到的这些负载参数依各自的权值按公式⑵计算每个节点的负载：