Explorations of the implementation of a parallel IDW interpolation algorithm in a Linux cluster-based parallel GIS
Explorations of the implementation of a parallel IDW interpolation algorithm in a Linux cluster-based parallel GIS
复制标题
基于Linux集群的并行GIS中并行IDW插值算法的实现探索
DOI：
10.1016/j.cageo.2010.05.024
复制
发表时间：
2011-04-01
影响因子：
4.4
通讯作者：
He, Binbin
中科院分区：
文献类型：
--
作者：
Huang, Fang;Liu, Dingsheng;He, Binbin
为设计和实现基于Linux集群的开源并行GIS (OP-GIS)，以并行逆距离加权（IOW）插值算法为例，探讨了OP-GIS并行化模式之一的算法并行模式（APP）的工作模型和原理。在分析GRASS GIS串行IDW插值算法的基础上，提出并设计了一种具体的并行IDW插值算法，该算法结合了单进程多数据（SPMD）和主从（MIS）编程模式。并行IDW插值算法的主要步骤是：(1)主节点将相关信息打包后广播到从节点；(2)每个节点沿一行使用串行算法计算其分配的数据范围；(3)主节点收集所有节点的数据；(4)继续迭代，直到处理完所有行，然后输出结果。根据本工作过程中进行的实验，与同类算法相比，并行IDW插值算法的效率大于0.93，这表明并行算法可以大大减少处理时间，最大限度地提高速度和性能。(c) 2010 Elsevier Ltd.版权所有。
To design and implement an open-source parallel GIS (OP-GIS) based on a Linux cluster, the parallel inverse distance weighting (IOW) interpolation algorithm has been chosen as an example to explore the working model and the principle of algorithm parallel pattern (APP), one of the parallelization patterns for OP-GIS. Based on an analysis of the serial IDW interpolation algorithm of GRASS GIS, this paper has proposed and designed a specific parallel IDW interpolation algorithm, incorporating both single process, multiple data (SPMD) and master/slave (MIS) programming modes. The main steps of the parallel IDW interpolation algorithm are: (1) the master node packages the related information, and then broadcasts it to the slave nodes; (2) each node calculates its assigned data extent along one row using the serial algorithm; (3) the master node gathers the data from all nodes; and (4) iterations continue until all rows have been processed, after which the results are outputted. According to the experiments performed in the course of this work, the parallel IDW interpolation algorithm can attain an efficiency greater than 0.93 compared with similar algorithms, which indicates that the parallel algorithm can greatly reduce processing time and maximize speed and performance. (c) 2010 Elsevier Ltd. All rights reserved.