矢量多边形并行栅格化数据划分方法

针对多边形并行栅格化中的负载不均衡问题提出一种新的数据划分方法,主要包括:迭代计算划分线的位置,在每次迭代中保证分块间的计算量大致均衡,完成数据划分、实现负载均衡;提出基于二叉树的划分结果融合策略,以解决跨边界多边形的融合问题。在多核CPU环境下实现并行算法,选用多个典型土地利用现状数据集进行测试。结果表明:针对不同类型多边形数据集,所提方法较传统方法可获得更高的并行加速比和更好的负载均衡;针对大数据量数据集,以多边形节点数为度量标准可更精确地估算分块计算量,从而更好地实现负载均衡。

A novel data decomposition method for rapid parallel processing of vector polygon rasterization

This paper presents a novel data decomposition method for large-scale parallel vector polygon rasterization. First, the number of polygon nodes or the number of polygons is employed to evaluate the amount of calculations of a subset. The spatial locations of decomposed lines are computed iteratively, guaranteeing the balanced calculations between decomposed subsets. Second, a binary-tree based fusion strategy is put forth to merge the polygons across multiple subsets. The proposed parallel algorithm was implemented under a multi-core CPU-based environment and multiple China land use datasets were employed. Experimental results show that the presented method can outperform conventional methods for different datasets and can achieve good load balancing. Moreover, when dealing with a large-scale vector dataset, the number of polygonal nodes is more appropriate to be the metric to evaluate precisely the calculation of a subset.