Explorations of the implementation of a parallel IDW interpolation algorithm in a Linux cluster-based parallel GIS

被引:79
作者
Huang, Fang [1 ]
Liu, Dingsheng [2 ]
Tan, Xicheng [3 ]
Wang, Jian [2 ]
Chen, Yunping [1 ]
He, Binbin [1 ]
机构
[1] Univ Elect Sci & Technol China, Coll Automat, Inst Geospatial Informat Technol, Chengdu 611731, Peoples R China
[2] Chinese Acad Sci, Ctr Earth Observat & Digital Earth, Beijing 100086, Peoples R China
[3] Wuhan Univ, Int Sch Software, Wuhan 430079, Peoples R China
基金
中国国家自然科学基金;
关键词
IDW interpolation algorithm; PCs cluster; GRASS GIS; MPI; LiDAR;
D O I
10.1016/j.cageo.2010.05.024
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
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.
引用
收藏
页码:426 / 434
页数:9
相关论文
共 27 条
[1]  
ARMSTRONG MP, 1994, PHOTOGRAMM ENG REM S, V60, P1097
[2]  
Armstrong MP, 1996, INT J GEOGR INF SYST, V10, P713, DOI 10.1080/026937996137800
[3]   Multivariate interpolation to incorporate thematic surface data using inverse distance weighting (IDW) [J].
Bartier, PM ;
Keller, CP .
COMPUTERS & GEOSCIENCES, 1996, 22 (07) :795-799
[4]  
BRAWER B, 1989, INTRO PARALLEL PROGR
[5]  
Brovelli M., 2002, P OP SOURC GIS GRASS
[6]   The parameter optimization in the inverse distance method by genetic algorithm for estimating precipitation [J].
Chang, Chia-Ling ;
Lo, Shang-Lien ;
Yu, Shaw-L .
ENVIRONMENTAL MONITORING AND ASSESSMENT, 2006, 117 (1-3) :145-155
[7]  
Clarke K., 1990, ANAL COMPUTER CARTOG
[8]  
*GDF HANN, 2005, INTR PRACT US FREE G
[9]  
Grama A., 2003, Introduction to Parallel Computing, V2
[10]  
GUAN XF, 2008, P GEOINF 2008 JOINT