基于超图分割的空间数据并行处理任务调度机制研究

In recent years the improvements of spatial data acquisition technologies resulted in an explosive increase in the volume of spatial data, which brought in unprecedented challenges to current computation capacity. High performance clusters are the only economically viable solution to real-time data processing. Massive spatial data processing contains heavy I/O operations however, and should be characterized as a data-intensive application. The parallelization strategy of data-intensive applications, such as decomposition, scheduling, load-balance, are much different from that of traditional compute-intensive applications. It is of great importance to develop a brand-new scheduling model and strategy for parallel spatial data processing. The research of this proposal is on the scheduling of massive spatial data processing. Firstly, the characteristics of data decomposition and task collection will be evaluated, including task precedence, input dependence, and data transmission. A hypergraph-based scheduling model, which contains data, task and platform, will be constructed.This model can truly represent the whole data processing. Secondly, a task scheduling strategy will be designed from the hypergraph-based scheulding model. The scheduling problem can be resolved by partitioning the constructed hypergraph model. Additional optimization to hypergraph partitioning is also carried out with the help of data locality and task hierachy. Finally, a robust parallel framework will be developed on a distributed platform. Two common spatial algorithms, IDW interpolation and Delaunay triangulation, will be implemented on this framework to evaluate its efficiency and scalability. The research results of this proposal will provide a parallel solution to massive spatial data processing, which can speedup the transformation of spatial data to information and also facilitate spatial analysis and decision support.

采用分布式计算平台来并行处理海量空间数据是当前的一个研究热点。现有并行空间数据处理系统，还没有成熟通用的任务调度模型和调度策略，多直接借用基于有向无环图的调度手段，然而在模型上无法包容海量数据要素，在策略上忽略数据I/O成本，导致并行计算资源无法高效利用。本项目的研究将围绕海量空间数据并行处理的任务调度机制展开，首先利用超图理论建立任务、数据、平台一体化的调度模型，顾及数据的空间邻近性及任务的层次性，以期解决调度模型完整性问题；进而提出实现任务负载均衡及传输数据量最小的调度目标，制定基于超图分割的任务调度策略；同时利用处理算法的局部空间数据参与特征对调度策略进行优化，简化其时间复杂度；最后设计开发分布式的调度原型系统，对上述调度模型及策略进行验证。该调度机制的研究与应用将大大优化空间数据处理过程中I/O传输成本，缩短整体处理时间，提高并行处理效率，实现数据到信息的快速转化。

海量空间数据处理作为典型的数据密集型应用，采用分布式计算平台来并行处理海量空间数据是当前的一个研究热点。目前在并行空间数据处理系统设计过程中，还没有成熟通用的任务调度模型和调度策略可使用，大多直接借用传统计算密集型应用的调度手段。传统计算密集型应用，基于有向无环图（Directed Acyclic Graph， DAG）的任务建模和调度方案已经比较成熟。但是直接将DAG方案应用到空间数据处理，调度模型上无法包容海量数据要素，调度策略的制定忽略空间数据I/O传输成本，进而无法实现处理任务的最优调度。因此在分布式计算平台如何实现海量空间数据并行处理任务的高效调度一个亟待解决的问题。.本项目研究：1）首先利用超图理论建立了全新的面向海量空间数据处理的任务调度模型，将任务和数据映射为超图的超边和数据节点，相较传统基于有向无环图的调度模型，涵盖了海量空间数据要素，同时顾及数据的空间邻近性及任务的层次性，解决了现有调度模型完整性问题；2）以全新的超图调度模型为基础，提出了实现任务负载均衡及传输数据量最小的调度目标，制定基于超图分割的任务调度策略；3）考虑到单一超图分割结果非最优，提出了迭代精化的Hypergraph+调度算法，超图模型各参数通过迭代收敛精确，传输数据减少量优化至最大；4）最后设计了分布式的调度原型系统，对上述调度模型及策略进行应用。.现有实验结果显示，与现有MinMin、XSufferage和Hypergraph算法相比， Hypergraph+算法makespan最低，即完成所有计算任务所需要的时间最少；随着任务数量的增加，减少的传输数据量对比，MinMin算法达到输入总数据量的40%，XSufferage算法为55%，Hypergraph算法为80%，而Hypergraph+算法缩减达到了输入总数据量的85%，该算法传输的数据量最少，有效的解决了并行处理的瓶颈问题。.因此基于超图分割的空间数据并行处理任务调度机制研究与应用，大大优化空间数据处理过程中I/O传输成本，缩短了整体处理时间，提高了并行处理效率，有助于实现数据到信息的快速转化。