面向D-TIN并行构建的动态条带数据划分方法与实验分析
Dynamic Strip Partitioning Method Oriented Parallel Computing for Construction of Delaunay Triangulation
查看参考文献15篇
|
文摘
|
数据划分是并行算法设计的重要步骤,其结果的均衡性与高效性是提高并行算法性能的重要前提。对于集聚分布的点集数据,传统的D-TIN(Delaunay Triangulation)并行算法尚未给出划分结果均衡、划分效率高效的理想解决方案。针对上述问题,本文在传统D-TIN并行算法规则条带划分方法的基础上,提出采用动态条带实现针对集聚分布点集数据的均衡、高效划分方法。首先,获取点集的最小外接矩形,并使用规则矩形条带按照同一方向进行点集粗分,然后,按顺序进行相邻条带的合并,必要时需动态调整合并区域边界以达到满足负载均衡的要求。为了提高划分效率,尽量减少边界移动次数,采用了对半移动的规则进行边界的动态调整。为了验证动态条带划分方法的适用性,本文使用人工模拟点集数据,进行加速比测试,使用实验区域真实数据进行D-TIN并行构建效率的统计,实验证明,采用该数据划分方法可以获得更高、更稳定的并行加速比,并且数据分布形态和数据规模对加速比的影响较小,进行D-TIN构建可以获得更好的执行效率,并且加速效果更加明显。 |
|
其他语种文摘
|
Data partitioning is an important step of parallel algorithm design.The load balance and efficiency of data partitioning is the precondition for improvement of parallel algorithm efficiency.For aggregated distributed point sets,the traditional Delaunay triangulation parallel algorithm can’t ensure the balance and the execution’s efficiency of the partitioning result.In view of the problems above,this paper we proposed a partitioning method using dynamic strips based on the idea of equally strips partitioning method in traditional Delaunay Triangulation construction and we titled it Dynamic Strip Partitioning Method.The detailed steps of this algorithm are as follows.First,the minimum bounding rectangle of the point data set should be obtained and the point set is roughly split using regular slim strips in the same direction.Then the number of points in every strip would be counted and the neighbor strips are merged into a partition region from the first strip in the sequence following a certain regulation.The boundaries of some strips should be moved dynamically if the total amount of points in these strips reached the load threshold value.In order to promote the efficiency of partitioning and reduce the boundaries movement,a rule of "move half points a time" has been used.We tested the speed-up of the Delaunay Triangulation parallel algorithm using the artificial point sets and tested the performance of the Delaunay triangulation parallel algorithm using the real test area point sets in the multi-kernel parallel computing systems.The results of the experiments showed that the method of dynamic strips partitioning can help to get high and stable speed-up of the Delaunay triangulation parallel algorithm and the data distributional pattern and size has less influence to it.Delaunay triangulation parallel algorithm based on dynamic strips partitioning method can get high efficiency and the speed-up effect is superior to the traditional method. |
|
来源
|
地球信息科学学报
,2012,14(1):55-61 【核心库】
|
|
关键词
|
D-TIN
;
并行计算
;
数据划分
;
负载均衡
;
加速比
|
|
地址
|
南京师范大学地理科学学院, 虚拟地理环境教育部重点实验室;;地理信息科学江苏省重点实验室, 南京, 210046
|
|
语种
|
中文 |
|
ISSN
|
1560-8999 |
|
学科
|
测绘学 |
|
基金
|
江苏研究生创新计划
;
国家自然科学基金
|
|
文献收藏号
|
CSCD:4464950
|
参考文献 共
15
共1页
|
|
1.
汤国安.
数字高程模型及地学分析的原理与方法,2005
|
CSCD被引
152
次
|
|
|
|
|
2.
李水乡. 快速Delaunay逐点插入网格生成算法.
北京大学学报（自然科学版）,2007,43(3):302306
|
CSCD被引
1
次
|
|
|
|
|
3.
艾廷华. 保持空间分布特征的群点化简方法.
测绘学报,2002,31(2):175181
|
CSCD被引
1
次
|
|
|
|
|
4.
Yan H. An algorithm for point cluster generalization based on the Voronoi diagram.
Computers & Geosciences,2008,34(8):939-954
|
CSCD被引
27
次
|
|
|
|
|
5.
Davy J R. A note on improving the performance of Delaunay triangulation.
Proc. of Computer Graphics International '89,1989
|
CSCD被引
1
次
|
|
|
|
|
6.
Jiang J. Study of load balancing algorithms based on multiple resources.
Acta Electronica Sinica,2002,30(8):11481152
|
CSCD被引
1
次
|
|
|
|
|
7.
Cignoni P.
Parallel 3D Delaunay triangulation,1993
|
CSCD被引
1
次
|
|
|
|
|
8.
Chen M B. Efficient parallel implementations of 2D Delaunay triangulation with high performance.
FORTRAN,2000
|
CSCD被引
1
次
|
|
|
|
|
9.
Hardwick J C. Implementation and evaluation of an efficient parallel Delaunay triangulation algorithm.
ACM,1997
|
CSCD被引
1
次
|
|
|
|
|
10.
Wang S. A quadtree approach to domain decomposition for spatial interpolation in grid computing environments.
Parallel Computing,2003,29(10):14811504
|
CSCD被引
16
次
|
|
|
|
|
11.
赵春宇. 一种面向并行空间数据库的数据划分算法研究.
武汉大学学报：信息科学版,2006,31(11):962-965
|
CSCD被引
19
次
|
|
|
|
|
12.
贾婷. 一种面向并行空间查询的数据划分方法.
计算机科学,2010,37(8):198200
|
CSCD被引
1
次
|
|
|
|
|
13.
武晓波. Delaunay三角网的生成算法研究.
测绘学报,1999,28(1):2835
|
CSCD被引
1
次
|
|
|
|
|
14.
周侗. 面向集聚分布空间数据的混合式索引方法研究.
地理与地理信息科学,2010(1):710
|
CSCD被引
1
次
|
|
|
|
|
15.
陈国良.
并行算法的设计与分析,1994
|
CSCD被引
36
次
|
|
|
|
|
了解气象卫星更多信息，请访问