| 引用本文: | 周琛,李满春,陈振杰,等.矢量多边形并行栅格化数据划分方法.[J].国防科技大学学报,2015,37(5):21-28.[点击复制] |
| ZHOU Chen,LI Manchun,CHEN Zhenjie,et al.A novel data decomposition method for rapid parallel processing of vector polygon rasterization[J].Journal of National University of Defense Technology,2015,37(5):21-28[点击复制] |
|
| |
|
|
| 本文已被：浏览 9684次 下载 6797次 |
| 矢量多边形并行栅格化数据划分方法 |
| 周琛, 李满春, 陈振杰, 姜朋辉, 陈东 |
|
(南京大学 地理与海洋科学学院， 江苏 南京 210023)
|
| 摘要: |
| 针对多边形并行栅格化中的负载不均衡问题提出一种新的数据划分方法，主要包括：迭代计算划分线的位置，在每次迭代中保证分块间的计算量大致均衡，完成数据划分、实现负载均衡；提出基于二叉树的划分结果融合策略，以解决跨边界多边形的融合问题。在多核CPU环境下实现并行算法，选用多个典型土地利用现状数据集进行测试。结果表明：针对不同类型多边形数据集，所提方法较传统方法可获得更高的并行加速比和更好的负载均衡；针对大数据量数据集，以多边形节点数为度量标准可更精确地估算分块计算量，从而更好地实现负载均衡。 |
| 关键词: 地理信息系统 并行计算 多边形栅格化 数据划分 负载均衡 |
| DOI：10.11887/j.cn.201505004 |
| 投稿日期：2015-06-16 |
| 基金项目:国家863计划资助项目（2011AA120301） |
|
| A novel data decomposition method for rapid parallel processing of vector polygon rasterization |
| ZHOU Chen, LI Manchun, CHEN Zhenjie, JIANG Penghui, CHEN Dong |
|
(School of Geographic and Oceanographic Sciences, Nanjing University, Nanjing 210023, China)
|
| Abstract: |
| According to the load balance problem of large-scale parallel vector polygon rasterization, a novel data decomposition method was proposed. Firstly, the number of polygon nodes or the number of polygons was employed to evaluate the amount of calculations of a subset. The spatial locations of decomposed lines were computed iteratively and the balanced calculations between decomposed subsets were guaranteed, so as to realize data decomposition and load balancing. Secondly, a binary-tree based fusion strategy was 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 a higher speed-up ratio and 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 the calculation of a subset precisely. |
| Keywords: geographical information system parallel computing vector polygon rasterization data decomposition load balancing |
|
|
|
|
|
