基于DEM的分布式并行通视分析算法研究_张刚.pdf

《基于DEM的分布式并行通视分析算法研究_张刚.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第２９卷第４期地理与地理信息科学Ｖｏｌ．２９Ｎｏ．４２０１３年７月ＧｅｏｇｒａｐｈｙａｎｄＧｅｏ－ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅＪｕｌｙ２０１３ｄｏｉ：１０．７７０２／ｄｌｙｄｌｘｘｋｘ２０１３０４１８基于ＤＥＭ的分布式并行通视分析算法研究张刚１，汤国安１＊，宋效东１，杨坤２（１．南京师范大学虚拟地理环境教育部重点实验室，江苏南京２１００２３；２．南京师范大学计算机科学与技术学院，江苏南京２１００２３）摘要：从负载均衡的角度详细分析了数据并行的特征，提出一种通用且有效数据可达的ＤＥＭ数据划分策略。基于该方法设计了分布

2、式并行通视分析算法，以全国９０ｍＳＲＴＭ作为数据源，对算法的执行效率进行实验，结果表明：基于海量地形数据进行分布式并行通视分析的计算效率与进程数具有一定的关系。另外，算法的并行性能在一定程度上受到地形数据的影响。该文提出的方法有效地提高了海量数据的通视分析算法的计算效率，动态数据划分方案有望为并行环境下地形分析提供新的思路。关键词：ＤＥＭ；通视分析；分布式并行；加速比中图分类号：Ｐ２０８文献标识码：Ａ文章编号：１６７２－０５０４（２０１３）０４－００８１－０５［５］了一定研究。Ｆｌｏｒｉａｎｉ等在ＭＩＭＤ架构基础上，０引言

3、通过静态和动态两种并行数据划分策略，提出了一地形通视性分析（ＴｅｒｒａｉｎＩｎｔｅｒ－ＶｉｓｉｂｉｌｉｔｙＡｎａｌ－种基于ＴＩＮ数据的并行可视性分析算法，但是由于ｙｓｉｓ）是指基于ＤＥＭ数据判断地形上任意两点之间ＴＩＮ数据存储结构的复杂性，算法执行效率有待进［６］是否可见的技术方法，通视的条件取决于视点与目一步提高，使用范围有一定的局限性。Ｋｉｄｎｅｒ等标点间是否存在妨碍视线的障碍物。通视分析实质提出一种基于数据并行的反向可视性分析算法，各［１］上属于对地形进行最优化处理的范畴。目前，基处理节点同步执行串行通视算法，获取由

4、面到区域于规则格网ＤＥＭ的地形通视性分析已经广泛应用的可视域，该算法有效利用了各计算节点的计算能于通信、军事、房地产、考古、景观设计等多个领域。力并取得了较优的加速比，但是计算精度相对不高。但随着空间数据采集技术的迅速发展，海量、高精度由于高分辨率海量ＤＥＭ数据的点对点通视分析算［７］ＤＥＭ数据的应用越来越广泛，通视分析算法的计算法计算量巨大，Ｍｉｌｌｓ等针对ＬＯＳ视线设计了数量也呈现出指数级增长趋势，传统的计算机处理技据划分策略，对传统点点通视分析算法进行了并行术已经不能有效地提高基于海量ＤＥＭ数据的通视化处理，由于测试

5、环境较为简单，实验结果有待进一［２］分析执行效率。因此，如何利用现有计算资源，提步验证。在此基础上，本文从负载均衡角度，通过分高计算效率，降低算法时间复杂度成为通视分析要析ＤＥＭ数据存储的结构特征，提出了一种面向分布解决的关键问题。并行环境的数据划分策略，构建了并行Ｂｒｅｓｅｎｈａｍ近年来，随着海量空间数据分析的不断增长以地形通视分析算法，并以全国９０ｍＳＲＴＭ为数据及高性能地学应用的不断推动，并行空间分析方法源，分析了并行通视分析的运行效率，为并行环境下［３］成为高性能地学计算的发展趋势。并行空间分析的地形通视分析提供了

6、新的思路。方法是将ＧＩＳ空间分析方法与并行计算技术相融合１并行通视分析算法设计框架的过程，旨在通过多种计算资源解决复杂的空间分析问题，提高空间数据处理的速度和质量。通视分１．１数据划分策略析作为地形分析的重要组成部分，也是空间分析不并行计算是指同时使用多种计算资源解决复杂［４］可或缺的内容。研究并行通视分析算法，成为提问题的过程，其包括共享存储模型、消息传递模型和［８］高海量数据下通视分析效率的有效途径。数据并行模型３类。由于栅格数据空间分析具有［９］针对通视分析的高效计算问题，国内外学者做计算数据密集且数据组织规律性强的

7、特点，大部收稿日期：２０１３－０４－３０基金项目：国家８６３计划项目（２０１１ＡＡ１２０３０３）；江苏省高校自然科学研究重大项目（１３ＫＪＡ１７０００１）；江苏省普通高校研究生科研创新计划项目（ＣＸＺＺ１２＿０３９３）作者简介：张刚（１９８７－），男，硕士研究生，主要研究方向为数字地形分析及高性能计算。＊通讯作者Ｅ－ｍａｉｌ：ｔａｎｇｇｕｏａｎ＠ｎｊｎｕ．ｅｄｕ．ｃｎ第８２页地理与地理信息科学第２９卷分栅格数据空间分析的并行模式均采用数据并行处数据是一个ｍ行×ｎ列的矩阵，一般通过数组的形［１０］理方式。数据并行是将串行任务

8、需要处理的原始式进行组织。因此，规则划分相较于不规则划分更大数据集划分为从节点处理的子数据集，各处理节易实现且有利于并行计算系统的负载平衡。实验表点独立执行串行程序，获取计算结果。数据并行策明，在规则划分中，一维数据划分程序的执行效率优略的基础是数据划分，针对ＤＥＭ数据的矩阵式特于二维划分，而ＤＥＭ数据