统一计算设备架构的D8算法并行化研究

Research on parallelization of D8 algorithm based on CUDA

针对空间遥感技术的快速发展导致地理空间数据呈几何级数增长,传统GIS空间分析面临巨大的计算实时性需求的问题,该文为提高GIS数字地形分析算法在处理海量高分辨率DEM数据时的计算效率,基于CUDA众核流处理器并行编程模型,采用不同数据划分方法、纹理内存及异步数据传输机制等技术,对串行D8算法进行了并行化设计及算法优化,探索并分析了D8并行算法的数据拷贝与算法执行等环节的计算效率变化。实验结果表明,CUDA并行编程能够对D8算法实现较为明显的加速,在按5个行子块进行划分、调用1 344个线程时并行加速效果达到最佳,加速比为19.5。并且,在不同行子块划分方式下且调用线程数不超过1 344个时,加速比随调用线程数的增加而增长,计算时间占比随线程数的增加呈递减趋势。

With the rapid developing of space remote sensing technology,the geospatial data grows geometrically,traditional GIS spatial analysis is facing a huge demand for real-time computing.To improve the computational efficiency of the GIS digital terrain analysis algorithm in processing large-scale high-resolution DEM,this article is based on the parallel programming model of CUDA many-core stream processor which uses different data partitioning methods,texture memory and asynchronous transmission mechanism.The serial D8 algorithm is parallelized and optimized,and this paper explores and analyzes the computational efficiency changes of the data copy and the algorithm execution of the D8 parallel algorithm.Finally,the results of experiments show that CUDA parallel programming can achieve the obvious acceleration of the D8 algorithm.Especially,when the DEM image data is divided into 5 rows of sub-blocks and 134 4 threads are called,the parallel acceleration effect is optimal and the acceleration ratio is 19.5.Moreover,in the different row sub-block division manner and the number of calling threads is less than 134 4,speedup of the D8 algorithm increases with the increase in the number of the calling thread,while the share of computing time has a decreasing trend.