统一计算设备架构的D8算法并行化研究
发布时间：2021-07-25 01:24
针对空间遥感技术的快速发展导致地理空间数据呈几何级数增长,传统GIS空间分析面临巨大的计算实时性需求的问题,该文为提高GIS数字地形分析算法在处理海量高分辨率DEM数据时的计算效率,基于CUDA众核流处理器并行编程模型,采用不同数据划分方法、纹理内存及异步数据传输机制等技术,对串行D8算法进行了并行化设计及算法优化,探索并分析了D8并行算法的数据拷贝与算法执行等环节的计算效率变化。实验结果表明,CUDA并行编程能够对D8算法实现较为明显的加速,在按5个行子块进行划分、调用1 344个线程时并行加速效果达到最佳,加速比为19.5。并且,在不同行子块划分方式下且调用线程数不超过1 344个时,加速比随调用线程数的增加而增长,计算时间占比随线程数的增加呈递减趋势。
【文章来源】：测绘科学. 2020,45(03)北大核心CSCD
【文章页数】：7 页
【部分图文】：
部分DEM高程值与方向编码值
1)数据并行。数据并行的关键是数据划分,优秀的数据划分方法能够有效提升算法的计算效率,在串行算法并行化中极为重要。本文所用DEM数据为m行、m列的规则矩阵形式,在设备端使用二维CUDA数组进行存储。一般说来,数据划分有规则划分和不规则划分两类方法[22]。规则划分包括按行、按列以及二维块划分,不规则划分是根据DEM中地貌地形特征来划分的,本文根据D8算法的特点采用规则格网划分方法,运用基于行模式的GDAL库对数据进行读写,由于其在行方向上读写效率高,研究选取行为单位的条带式划分方法,如图2所示。2)异步传输。GPU拥有大量的流处理器单元,使其在密集型计算方面有着显著的优势,计算效率较高。然而GPU本身无法直接获取数据,需要从主机端接收,受主机内存与GPU显存之间的带宽的限制,两者之间数据拷贝速度远低于GPU的计算速度,这在一定程度上限制了D8算法计算的加速比的上升。因此,为了进一步提升D8算法的整体效率,引入了异步传输模式[23],以降低数据复制与核函数执行之间的相互等待时间。
3)纹理内存。纹理内存是CUDA编程模型独有的一种只读内存,针对二维空间的局部性访问会获得加速,且适用于大量数据的随机和非对齐访问。DEM栅格数据由CUDA数组进行存储,使用纹理参考实现纹理坐标与格网栅格数据数组的映射绑定。流向计算过程中只需通过纹理拾取访问不同纹理坐标值,即可读取到对应不同栅格单元及其邻接栅格数据,无需进行多个存储器之间的数据交换,降低额外时间开销,提高计算效率。如图4所示,数据已进行纹理绑定,右侧中间4个地址不连续,但通过纹理拾取进行访问会获得一定的加速效果。在为核函数分配线程数目时,根据DEM数据的数据量大小及GPU流处理器核心的数目来确定。并行算法的流程设计如图5所示。
【参考文献】：
期刊论文
[1]CUDA环境下地形因子的并行计算[J]. 陈亮,赵磊,李珂. 北京测绘. 2017(04)
[2]多种数据划分方法下D8算法的多核并行化实验对比[J]. 高琪,范俊甫,何惠馨,孔维华,周玉科. 地理与地理信息科学. 2017(02)
[3]基于GPU的RFT算法并行化[J]. 商哲然,谭贤四,曲智国,王红,丰骁. 雷达科学与技术. 2016(05)
[4]CPU/GPU异构混合并行的栅格数据空间分析研究——以地形因子计算为例[J]. 卢敏,王金茵,卢刚,陶伟东,王结臣. 计算机工程与应用. 2017(01)
[5]基于GPU的二维矢量场LIC算法研究[J]. 陈丁,万刚,王龙,赵宸立. 测绘工程. 2015(03)
[6]格网DEM水系提取并行算法研究[J]. 江岭,刘学军,阳建逸,刘凯,宋效东. 地理与地理信息科学. 2013(04)
[7]地形分析中坡度坡向算法并行化方法研究[J]. 江岭,刘学军,汤国安,宋效东. 计算机工程与科学. 2013(04)
[8]DEM与地形分析的并行计算[J]. 宋效东,刘学军,汤国安,王永君,田剑,窦万峰. 地理与地理信息科学. 2012(04)
[9]一个基于DEM的数字河网体系提取算法的应用[J]. 崔青春,吴孟泉,孔祥生,张丽. 计算机技术与发展. 2011(06)
[10]利用CUDA的地图代数局部算子优化[J]. 张剑波,杨文鑫,周斯波,张帅. 测绘科学. 2012(02)
博士论文
[1]基于DEM的流域地形分析并行算法关键技术研究[D]. 江岭.南京师范大学 2014
硕士论文
[1]并行数字地形分析数据划分方法研究[D]. 张刚.南京师范大学 2014
本文编号：3301821
【文章来源】：测绘科学. 2020,45(03)北大核心CSCD
【文章页数】：7 页
【部分图文】：
部分DEM高程值与方向编码值
1)数据并行。数据并行的关键是数据划分,优秀的数据划分方法能够有效提升算法的计算效率,在串行算法并行化中极为重要。本文所用DEM数据为m行、m列的规则矩阵形式,在设备端使用二维CUDA数组进行存储。一般说来,数据划分有规则划分和不规则划分两类方法[22]。规则划分包括按行、按列以及二维块划分,不规则划分是根据DEM中地貌地形特征来划分的,本文根据D8算法的特点采用规则格网划分方法,运用基于行模式的GDAL库对数据进行读写,由于其在行方向上读写效率高,研究选取行为单位的条带式划分方法,如图2所示。2)异步传输。GPU拥有大量的流处理器单元,使其在密集型计算方面有着显著的优势,计算效率较高。然而GPU本身无法直接获取数据,需要从主机端接收,受主机内存与GPU显存之间的带宽的限制,两者之间数据拷贝速度远低于GPU的计算速度,这在一定程度上限制了D8算法计算的加速比的上升。因此,为了进一步提升D8算法的整体效率,引入了异步传输模式[23],以降低数据复制与核函数执行之间的相互等待时间。
3)纹理内存。纹理内存是CUDA编程模型独有的一种只读内存,针对二维空间的局部性访问会获得加速,且适用于大量数据的随机和非对齐访问。DEM栅格数据由CUDA数组进行存储,使用纹理参考实现纹理坐标与格网栅格数据数组的映射绑定。流向计算过程中只需通过纹理拾取访问不同纹理坐标值,即可读取到对应不同栅格单元及其邻接栅格数据,无需进行多个存储器之间的数据交换,降低额外时间开销,提高计算效率。如图4所示,数据已进行纹理绑定,右侧中间4个地址不连续,但通过纹理拾取进行访问会获得一定的加速效果。在为核函数分配线程数目时,根据DEM数据的数据量大小及GPU流处理器核心的数目来确定。并行算法的流程设计如图5所示。
【参考文献】：
期刊论文
[1]CUDA环境下地形因子的并行计算[J]. 陈亮,赵磊,李珂. 北京测绘. 2017(04)
[2]多种数据划分方法下D8算法的多核并行化实验对比[J]. 高琪,范俊甫,何惠馨,孔维华,周玉科. 地理与地理信息科学. 2017(02)
[3]基于GPU的RFT算法并行化[J]. 商哲然,谭贤四,曲智国,王红,丰骁. 雷达科学与技术. 2016(05)
[4]CPU/GPU异构混合并行的栅格数据空间分析研究——以地形因子计算为例[J]. 卢敏,王金茵,卢刚,陶伟东,王结臣. 计算机工程与应用. 2017(01)
[5]基于GPU的二维矢量场LIC算法研究[J]. 陈丁,万刚,王龙,赵宸立. 测绘工程. 2015(03)
[6]格网DEM水系提取并行算法研究[J]. 江岭,刘学军,阳建逸,刘凯,宋效东. 地理与地理信息科学. 2013(04)
[7]地形分析中坡度坡向算法并行化方法研究[J]. 江岭,刘学军,汤国安,宋效东. 计算机工程与科学. 2013(04)
[8]DEM与地形分析的并行计算[J]. 宋效东,刘学军,汤国安,王永君,田剑,窦万峰. 地理与地理信息科学. 2012(04)
[9]一个基于DEM的数字河网体系提取算法的应用[J]. 崔青春,吴孟泉,孔祥生,张丽. 计算机技术与发展. 2011(06)
[10]利用CUDA的地图代数局部算子优化[J]. 张剑波,杨文鑫,周斯波,张帅. 测绘科学. 2012(02)
博士论文
[1]基于DEM的流域地形分析并行算法关键技术研究[D]. 江岭.南京师范大学 2014
硕士论文
[1]并行数字地形分析数据划分方法研究[D]. 张刚.南京师范大学 2014
本文编号：3301821
本文链接：https://www.wllwen.com/kejilunwen/dizhicehuilunwen/3301821.html
