数据划分是并行算法设计的重要步骤,其结果的均衡性与高效性是提高并行算法性能的重要前提。对于集聚分布的点集数据,传统的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.