面向D-TIN并行构建的动态条带数据划分方法与实验分析

作     者：齐琳 沈婕 郭立帅 周侗 QI Lin;SHEN Jie;GUO Lishuai;ZHOU Tong

作者机构：南京师范大学地理科学学院南京210046 南京师范大学虚拟地理环境教育部重点实验室南京210046 地理信息科学江苏省重点实验室南京210046 

基　　金：国家自然科学基金项目(41071288 41171350) 江苏研究生创新计划(CXZZ1_0876) 

出 版 物：《地球信息科学学报》 (Journal of Geo-information Science)

年 卷 期：2012年第14卷第1期

页      码：55-61页

摘      要：数据划分是并行算法设计的重要步骤,其结果的均衡性与高效性是提高并行算法性能的重要前提。对于集聚分布的点集数据,传统的D-TIN(Delaunay Triangulation)并行算法尚未给出划分结果均衡、划分效率高效的理想解决方案。针对上述问题,本文在传统D-TIN并行算法规则条带划分方法的基础上,提出采用动态条带实现针对集聚分布点集数据的均衡、高效划分方法。首先,获取点集的最小外接矩形,并使用规则矩形条带按照同一方向进行点集粗分,然后,按顺序进行相邻条带的合并,必要时需动态调整合并区域边界以达到满足负载均衡的要求。为了提高划分效率,尽量减少边界移动次数,采用了对半移动的规则进行边界的动态调整。为了验证动态条带划分方法的适用性,本文使用人工模拟点集数据,进行加速比测试,使用实验区域真实数据进行D-TIN并行构建效率的统计,实验证明,采用该数据划分方法可以获得更高、更稳定的并行加速比,并且数据分布形态和数据规模对加速比的影响较小,进行D-TIN构建可以获得更好的执行效率,并且加速效果更加明显。

主 题 词：D-TIN 并行计算 数据划分 负载均衡 加速比 

学科分类：081603[081603] 07[理学] 08[工学] 070503[070503] 0705[理学-地理科学类] 0816[工学-纺织类] 

核心收录：

D　O　I：10.3724/SP.J.1047.2012.00055

馆 藏 号：203171041...