Digital terrain analysis (DTA) on a gridded digital elevation models (DEM) is often computationally intensive. The traditional algorithms in DTA are coded as sequential program executed on a single computer processor. Therefore, the execution is often very time-consuming, especially for DEMs of large area and finer scale. Quick calculation of DTA presents a practical challenge to personal computer (PC) users. In recent years, rapid increases in hardware capacity of the graphics processing unit (GPU) provided in modern PCs have made it possible to meet this challenge in a PC environment.

In a new study published in the journal Computers & Geosciences, Dr. QIN Cheng-Zhi, an associate professor of geographical information science at the State Key Laboratory of Resources & Environmental Information System, Institute of Geographic Sciences & Natural Resources Research, Chinese Academy of Sciences (LREIS, IGSNRR, CAS), and one of his master students, ZHAN Li-Jun, parallelize two types of computationally intensive DTAalgorithms (i.e., iterative processing and recursive algorithm) on a GPU.

In the new study Dr. QIN and Zhan take the calculation of flow accumulation from gridded DEMs, one of the important DTA tasks, as example for parallelization on GPU.

This DTA task usually involves two steps in a real application: 1) using an iterative DEM preprocessing algorithm to removing the depressions and flat areas commonly contained in real DEMs, and 2) using a recursive flow-direction algorithm to calculate the flow accumulation for every cell in the DEM.

Parallel computing on GPU using a compute-unified-device-architecture (CUDA) programming model has been recently explored to speed up the execution of the single-flow-direction algorithm (SFD). However, the parallel implementation on a GPU of the multiple-flow-direction (MFD) algorithm, which generally performs better than the SFD algorithm, has not been reported.

Moreover, GPU-based parallelization of the DEM preprocessing step in the flow-accumulation calculations has not been addressed. The new study firstly designed the parallelization strategy using a GPU for the parallelization of iterative neighborhood operation in DEM preprocessing.

Then two different parallelization strategies using a GPU were explored. The first parallelization strategy, which has been used in the existing parallel SFD algorithm on GPU, was found to have the problem of computing redundancy. Therefore, Dr. QIN and Zhan designed a parallelization strategy based on graph theory.

The application results show that the proposed parallel approach to calculating flow accumulations on a GPU performs much faster than either sequential algorithms or other parallel GPU-based algorithms based on existing parallelization strategies. The parallel DEM preprocessing algorithm shows the speedup ranging from 15.9 to 22.3 times. The speedup of the proposed parallel MFD algorithm ranges from 5.8 to 10.9 times with different datasets in the test.

The method proposed in the new study, which is to change the recursive algorithm into an iterative process for better parallelizability, is also potentially useful for the parallelization of other recursive algorithms in DTA.

Qin C-Z, Zhan L-J. Parallelizing flow-accumulation calculations on Graphics Processing Units—from iterative DEM preprocessing algorithm to recursive multiple-flow-direction algorithm. Computers & Geosciences, 2012, 43: 7-16. doi: 10.1016/j.cageo.2012.02.022.