A Graph-Theory_Based Mothod for Parallelizing the Multiple-Flow-Direction Algorithm on CUDA Compatible Graphics Processing Units
Flow direction algorithm based on gridded DEM is one kind of the most widely used algorithms in digital terrain analysis. Being a typical recursive algorithm, flow direction algorithm coded traditionally for sequential computation is very time consuming, especially for application on the gridded DEM of large-area with high spatial resolution. Recently, the graphics processing units (GPUs) were applied to speeding up the execution of single flow direction algorithm (SFD) by parallel computing based on compute unified device architecture (CUDA). Although multiple flow direction (MFD) algorithms perform generally better than SFD, parallel MFD algorithm on GPU hasn’t been reported. In this paper, first we designed a CUDA-based parallel implementation on the NVIDIA GPU of a widely-used MFD algorithm (FD8) by using the parallelization strategy of the existing CUDA-based parallel SFD algorithm. Further analysis shows that this parallelization strategy has a problem of computing redundancy. Then, we proposed a graphtheory- based parallel implementation of FD8 algorithm in which the problem of computing redundancy could be released. The application result shows that the proposed graph-theory-based parallel FD8 algorithm gets faster acceleration than the parallel FD8 algorithm using the parallelization strategy of the existing CUDA-based parallel SFD algorithm, and performs much faster than the traditional serial FD8 algorithm.
Digital terrain analysis compute unified device architecture(CUDA) graphics processing unit(GPU) multiple flow direction algorithm(MFD) graph theory Gridded digital lelvation models(DEM)
Lijun Ahan Chengzhi Qin
State Key Laboratory of Resources and Environment Information System, Chinese Academy of Sciences,Beijing 100101,China
国际会议
福州
英文
137-141
2011-06-29（万方平台首次上网日期，不代表论文的发表时间）