基于OpenCL的累积汇流并行计算

摘要/Abstract

摘要： 大尺度、高分辨率数字地形数据应用需求的增长，给计算密集型的累积汇流等数字地形分析算法带来了新的挑战。针对CPU/GPU（Graphics Processing Unit）异构计算平台的特点，提出了一种基于OpenCL（Open Computing Language）的多流向累积汇流算法的并行化策略，具有更好的平台独立性和可移植性，简化了CPU/GPU异构平台下的并行应用程序设计。累积汇流并行算法包括时空独立型的流量分配和空间依赖型的累积入流两个过程，均定义为OpenCL内核并交由OpenCL设备并行执行，其中累积入流过程借助流量转移矩阵由递归式转换为迭代式来实现并行计算。与基于流量转移矩阵的并行汇流算法相比，尽管基于单元入度矩阵的并行汇流算法可以降低迭代过程中的计算冗余，但需要采用具有较大延迟的原子操作以及需要更多的迭代次数，在有限的GPU计算资源下，两种算法性能差异不明显。实验结果表明，并行累积汇流算法在NVIDIA GeForce GT 650M GPU上获得了较好的加速比，加速性能随格网尺度增加而有所增加，其中流量分配获得了约50~70倍的加速比，累积入流获得了10~20倍的加速比，展示了利用OpenCL在GPU等并行计算设备上进行大规模数字地形分析的潜在优势。

关键词: 并行计算, 累积汇流, 图形处理器, 开放计算语言

Abstract: The growing demand for the applications of large scale and high resolution digital terrain data has brought new challenges to computationally intensive digital terrain analysis algorithms such as flow accumulation. According to the characteristics of heterogeneous computing platform with CPU/GPU（Graphics Processing Unit）, a parallelization strategy for multiple flow direction flow accumulation algorithm is put forward based on the OpenCL（Open Computing Language）. It has better platform independence and portability, which simplifies the programming for parallel computing under CPU/GPU heterogeneous platform. The parallel flow accumulation algorithm includes outflow allocation process independently with the space and time domain, and the inflow accumulation process depending on the space domain. The two processes are defined as OpenCL kernels and are executed parallelly on the OpenCL devices. The transfer matrix is used to transfer the recursive inflow accumulation process into iterative style for parallel computing. Compared with the parallel flow accumulation algorithm based on flow transfer matrix, the parallel flow accumulation algorithm based on indegree matrix with graph theory can reduce the computation redundancy in the iterative inflow accumulation process, but it requires atomic operations with large delay and more iterations. With limited GPU computing resources, the two parallel flow accumulation algorithms have no obvious differences in speedup performance. Experimental results show that the parallel flow accumulation algorithm obtains a good speedup on NVIDIA GeForce GT 650M GPU and the speedup is increased gradually with the increase of grid scale. The speedups are 50~70 for the outflow allocation process and 10~20 for the inflow accumulation process, which demonstrates the potential advantages of large scale digital terrain analysis on parallel computing devices such as GPU with OpenCL.

Key words: parallel computing, flow accumulation, Graphics Processing Unit（GPU）, Open Computing Language（OpenCL）

龙满生，罗文浪. 基于OpenCL的累积汇流并行计算[J]. 计算机工程与应用, 2014, 50(3): 22-29.

LONG Mansheng, LUO Wenlang. Parallel computing with OpenCL for flow accumulation[J]. Computer Engineering and Applications, 2014, 50(3): 22-29.

[1]	冯凯，李婧. k元n方体网络的子网络可靠性[J]. 计算机工程与应用, 2021, 57(16): 83-89.
[2]	李健，张大伟，姜晓明，向立云. 并行化洪水演进模拟研究综述[J]. 计算机工程与应用, 2021, 57(13): 1-7.
[3]	孙明，陈昕. 面向卷积神经网络的硬件加速器设计方法[J]. 计算机工程与应用, 2021, 57(13): 77-84.
[4]	杨捷，吴素萍. 点云重建的并行算法[J]. 计算机工程与应用, 2020, 56(6): 213-219.
[5]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[6]	杜伟，傅游. 基于GPU的最小二乘蒙特卡罗算法期权定价[J]. 计算机工程与应用, 2020, 56(4): 225-229.
[7]	金之雁，杨磊，林隽民，王哲. 广义共轭余差法的通信避免算法[J]. 计算机工程与应用, 2020, 56(3): 74-79.
[8]	刘家华，陈靖宇. 多核并行脉冲神经网络模拟器的设计[J]. 计算机工程与应用, 2020, 56(22): 244-250.
[9]	朱超，吴素萍. 特征点检测DoG并行算法[J]. 计算机工程与应用, 2020, 56(10): 36-43.
[10]	邬阳阳，汤建国. 大数据背景下粗糙集属性约简研究进展[J]. 计算机工程与应用, 2019, 55(6): 31-38.
[11]	刘军，李威，吴梦婷，陈起凤. Hadoop平台下新型图像并行处理模型设计[J]. 计算机工程与应用, 2019, 55(6): 186-190.
[12]	刘洋，陈经纬，冯勇，吴文渊. 并行LLL算法研究综述[J]. 计算机工程与应用, 2019, 55(16): 36-41.
[13]	曾有灵，陈耿铎，熊威，李喆. 基于Spark的CT图像FBP重建算法程序并行设计[J]. 计算机工程与应用, 2019, 55(10): 218-224.
[14]	姜悦宁1，2，3，贾宏光1，3，厉明1，3. 基于多核并行计算的无人机CFD数值模拟[J]. 计算机工程与应用, 2018, 54(7): 221-225.
[15]	魏子衿1，2，3，肖丽2，3. 基于区域分解的并行动态LOD构建算法[J]. 计算机工程与应用, 2018, 54(6): 168-177.

基于OpenCL的累积汇流并行计算

Parallel computing with OpenCL for flow accumulation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics