多种数据划分方法下D8算法的多核并行化实验对比  

Experimental Comparison and Analysis of Multi-core Parallelization of D8 Algorithm under Different Data Partition Methods

作　　者：高琪[1,2] 范俊甫[1,2] 何惠馨[1] 孔维华[1] 周玉科[3] GAO Qi FAN Jun-fu HE Hui-xin KONG Wei-hua ZHOU Yu -kea(School of Civil and Architectural Engineering, Shandong University of Technology, Zibo 255049 State Key Laboratory of Resources and Environmental Information System, Institute of Geographic and Nature Resources Research ,Chinese Academy of Sciences ,Beijing 100101 Ecology Observing Network and Modeling Laboratory, Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences, Beijing 100101 , China)

机构地区：[1]山东理工大学建筑工程学院,山东淄博255049 [2]中国科学院地理科学与资源研究所/资源与环境信息系统国家重点实验室,北京100101 [3]中国科学院地理科学与资源研究所/生态系统网络观测与模拟院重点实验室,北京100101

出　　处：《地理与地理信息科学》2017年第2期63-68,共6页Geography and Geo-Information Science

基　　金：国家自然科学基金项目(41501425);资源与环境信息系统国家重点实验室开放基金项目;山东理工大学博士科研基金项目(4041-414039);山东理工大学青年教师发展支持计划项目;山东省重点研发计划项目(2016GSF122006);山东省高等学校科技计划项目(J16LH03)

摘　　要：对地观测技术的快速发展使空间数据规模迅速增大,海量高分辨率DEM数据使得GIS数字地形分析算法面临日益严重的效率瓶颈,多核并行计算技术是在PC端解决上述问题的潜在途径,而并行任务调度策略、数据划分方法是影响并行算法计算效率的重要因素。该文以河网提取中流向算法D8算法为例,基于OpenMP多核并行编程模型,在最佳任务调度策略下研究按行、列、块进行任务分解对该算法计算效率的影响。实验结果表明,不同数据划分方法对计算效率的影响存在差异。结合dynamic任务调度策略,对该算法采用行划分方法,并调用计算机最大可用线程个数16时并行加速效果最佳,加速比峰值达到13.88;划分块数为16时,运行加速比最高为13.46;按列划分加速比峰值达到12.829;而划分成9块和4块最高加速比仅为7.97和3.83。With the developing of earth observation technologies, the scale of spatial data is increasing rapidly, digital terrain a- nalysis algorithms are also facing efficiency bottlenecks brought by massive high-resolution DEM data, multi-core parallel com- puting technique is a potential approach to solve the above problems on PC. However, the parallel task scheduling strategies and data partition methods will have an impact on calculation efficiency of parallel algorithms. In this paper, using D8 algorithm which is a flow calculation algorithm in drainage network extraction as an example, we research on task scheduling strategies and data partition methods based on OpenMP which is a parallel programming model. Then task scheduling strategies and data partition rules are summarized through analyzing the influence of muhi-core parallel task scheduling strategies and task decom- posed by rows, columns or data blocks on 138 algorithm efficiency. Finally, the parallel algorithm optimization designing is com- pleted. The experimental results show that different data partitioning methods could result in different calculation efficiency. The speedup of D8 algorithm is highest when divided by rows with dynamic task scheduling, while calling the maximum number of computer available threads,it reaches 13.88, and speedup which dividing into 16 blocks is the second, reaches 13. 46. When divided by columns, speedup reaches 12. 829, and when divided into nine and four blocks, the maximum speedup is 7. 97 and 3.83, respectively.

关 键 词：DEM 数据划分 D8算法 多核并行优化 

分 类 号：P208[天文地球—地图制图学与地理信息工程]