Accelerating adaptive inverse distance weighting interpolation algorithm on a graphics processing unit.

Area of Science:

• Computational Science
• Geospatial Analysis
• High-Performance Computing

Background:

• Standard Inverse Distance Weighting (IDW) has limitations in prediction accuracy.
• Adaptive Inverse Distance Weighting (AIDW) improves accuracy by adaptively determining the power parameter based on spatial data distribution.
• Efficient implementation of AIDW is crucial for large-scale geospatial analysis.

Purpose of the Study:

• To design and implement parallel Adaptive Inverse Distance Weighting (AIDW) interpolation algorithms utilizing Graphics Processing Units (GPUs).
• To evaluate the performance and efficiency of GPU-accelerated AIDW compared to serial implementations.
• To make the parallel AIDW algorithms and testing data publicly accessible to the research community.

Main Methods:

• Development of two GPU-accelerated AIDW versions: a naive version and a tiled version leveraging shared memory.
• Implementation using both Structure of Arrays (SoA) and Array of Aligned Structures (AoS) data layouts.
• Performance evaluation through comparison with serial algorithms on various GPU hardware (GT730M, M5000, K40c) using single and double precision.

Main Results:

• No significant difference in computational efficiency was observed between different data layouts (SoA vs. AoS).
• The tiled version of the GPU-AIDW consistently outperformed the naive version.
• Substantial speed-ups were achieved: up to 763x on single precision (M5000 GPU) and 197x on double precision (K40c GPU).

Conclusions:

• GPU acceleration provides significant performance improvements for AIDW interpolation.
• The tiled approach and shared memory utilization enhance computational efficiency.
• The publicly available parallel AIDW algorithms can benefit various scientific and engineering applications requiring accurate spatial interpolation.