Massively parallel spatial point pattern analysis: Ripley’s K function accelerated using graphics processing units

Abstract

This study presents a massively parallel spatial computing approach that uses general-purpose graphics processing units (GPUs) to accelerate Ripley’s K function for univariate spatial point pattern analysis. Ripley’s K function is a representative spatial point pattern analysis approach that allows for quantitatively evaluating the spatial dispersion characteristics of point patterns. However, considerable computation is often required when analyzing large spatial data using Ripley’s K function. In this study, we developed a massively parallel approach of Ripley’s K function for accelerating spatial point pattern analysis. GPUs serve as a massively parallel platform that is built on many-core architecture for speeding up Ripley’s K function. Variable-grained domain decomposition and thread-level synchronization based on shared memory are parallel strategies designed to exploit concurrency in the spatial algorithm of Ripley’s K function for efficient parallelization. Experimental results demonstrate that substantial acceleration is obtained for Ripley’s K function parallelized within GPU environments.

Keywords:

• spatial point pattern analysis
• Ripley’s K function
• parallel computing
• graphics processing units

Acknowledgements

The authors would like to acknowledge the support received from US NSF XSEDE Supercomputing Resource Award (TGSES090019) ‘Extending and Sustaining CyberGIS Discovery Environment’ and Faculty Research Grant at the University of North Carolina at Charlotte. Partial computing resources used in this study were from University Research Computing at the University of North Carolina at Charlotte. The authors also thank the NVIDIA CUDA Research Center at the Center for Applied GIScience at the University of North Carolina at Charlotte. Thanks also to Huifang Zuo for assistance on the preparation of figures in this work.