CPU+GPU异构环境下数据密集型矢量多边形地理大数据并行框架

doi:10.13474/j.cnki.11-2246.2022.0151

摘要/Abstract

摘要： 本文提出了面向CPU+GPU异构环境的数据密集型矢量多边形地理大数据并行计算框架(PFGAP)。PFGAP将数据密集型矢量多边形地理大数据的并行计算分解为算子、数据、粒度、并行环境及任务调度5个模块,分别设计相应的负载均衡并行计算策略;通过封装并行计算实现细节及数据密集型多边形算子的快速并行化。试验采用多边形三角剖分、栅格化及投影变换作为测试算例,采用土地利用数据作为测试数据,在不同类型的并行环境中计算并行效率。结果表明,PFGAP能很好地适用于不同类型的数据集、算子及并行计算环境。利用PFGAP实现的并行算法显著地降低了串行执行时间,取得了40.03的最优并行加速比。试验还分别测试了各个模块涉及的并行策略,结果表明取得的并行效率优于现有并行策略。

关键词: 地理信息系统, 矢量多边形, 空间计算, CPU+GPU异构并行环境, 并行框架

Abstract: In this study, we present a parallel framework for data-intensive geospatial analysis on large-scale vector polygons over hybrid CPUs and GPUs (PFGAP). We consider workload balance in terms of operator, data, granularity, parallel environment, and task scheduling, respectively. These modules constitute the PFGAP and the parallel implementation details are encapsulated. Through applying the PFGAP, the parallel version of a serial algorithm can be easily achieved with a proper degree of workload balance. The typical polygon triangulation, polygon rasterization, and projection transformation algorithms are employed as testing algorithms, and land-use datasets are used as testing datasets. Results show that the implemented parallel algorithms reduce significantly the serial execution time, achieving optimal speedup ratio of 40.03. In addition, the parallel strategies involved in each module are evaluated, showing better effectiveness with conventional ones.

Key words: geographical information system, vector polygons, geospatial analysis, hybrid CPUs and GPUs, parallel framework

中图分类号:

P208

徐云耘, 周琛, 李满春. CPU+GPU异构环境下数据密集型矢量多边形地理大数据并行框架[J]. 测绘通报, 2022, 0(5): 110-119.

XU Yunyun, ZHOU Chen, LI Manchun. A parallel framework for data-intensive geospatial analysis on large-scale vector polygons over hybrid CPUs and GPUs[J]. Bulletin of Surveying and Mapping, 2022, 0(5): 110-119.

参考文献

[1] 黄杏元,马劲松.地理信息系统概论[M]. 3版.北京:高等教育出版社, 2008.
[2] CHANG K T. Introduction togeographic information systems[M]. New York:McGraw-Hill, 2008.
[3] 龚健雅.地理信息系统基础[M].北京:科学出版社, 2001.
[4] 王结臣,王豹,胡玮,等.并行空间分析算法研究进展及评述[J].地理与地理信息科学, 2011, 27(6):1-5.
[5] 吴立新,杨宜舟,秦承志,等.面向新型硬件构架的新一代GIS基础并行算法研究[J].地理与地理信息科学, 2013, 29(4):1-8.
[6] SHEKHAR S, RAVADA S, CHUBB D, et al. Declustering and load-balancing methods for parallelizing geographic information systems[J]. IEEE Transactions on Knowledge and Data Engineering, 1998, 10(4):632-655.
[7] YE Jiuyan, CHEN Bin, CHEN Jian, et al. A spatial data partition algorithm based on statistical cluster[C]//Proceedings of the 19th International Conference on Geoinformatics. Shanghai:IEEE, 2011.
[8] MINETER M J, DOWERS S. Parallel processing for geographical applications:a layered approach[J]. Journal of Geographical Systems, 1999, 1(1):61-74.
[9] WAUGH T C, HOPKINS S. An algorithm for polygon overlay using cooperative parallel processing[J]. International Journal of Geographical Information Systems, 1992, 6(6):457-467.
[10] AGARWAL D,PURI S,HEXi,et al.A system for GIS polygonal overlay computation on linux cluster-an experience and performance report[C]//Proceedings of 2012 IEEE International Parallel and Distributed Processing Symposium Workshops&PhD Forum. Shanghai:IEEE, 2012:1433-1439.
[11] PURI S, PRASAD S K. Aparallel algorithm for clipping polygons with improved bounds and a distributed overlay processing system using MPI[C]//Proceedings of the 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Shenzhen:IEEE, 2015:576-585.
[12] 杨宜舟,吴立新,郭甲腾,等.一种实现拓扑关系高效并行计算的矢量数据划分方法[J].地理与地理信息科学, 2013, 29(4):25-29.
[13] QIN Chengzhi, ZHAN Lijun, ZHU Axing, et al. A strategy for raster-based geocomputation under different parallel computing platforms[J]. International Journal of Geographical Information Science, 2014, 28(11):2127-2144.
[14] FAN Junfu, ZHOU Chenghu, MA Ting, et al. DWSI:an approach to solving the polygon intersection-spreading problem with a parallel union algorithm at the feature layer level[J]. Boletim De Ciências Geodésicas, 2014, 20(1):159-182.
[15] WANG Yong, LIU Zhenling, LIAO Hongyan, et al. Improving the performance of GIS polygon overlay computation with MapReduce for spatial big data processing[J]. Cluster Computing, 2015, 18(2):507-516.
[16] SIMION B, RAY S, BROWN A D. Speeding up spatial database query execution using GPUs[J]. Procedia Computer Science, 2012, 9:1870-1879.
[17] KIM D H, KIM M J. An extension of polygon clipping to resolve degenerate cases[J]. Computer-Aided Design and Applications, 2006, 3(1/2/3/4):447-456.
[18] HE Kejing, ZHENG Li, DONG Shoubin, et al. PGO:a parallel computing platform for global optimization based on genetic algorithm[J]. Computers&Geosciences, 2007, 33(3):357-366.
[19] GUAN Qingfeng, CLARKE K C. A general-purpose parallel raster processing programming library test application using a geographic cellular automata model[J]. International Journal of Geographical Information Science, 2010, 24(5):695-722.
[20] GUAN Qingfeng, ZENG Wen, GONG Junfang, et al. pRPL 2.0:improving the parallel raster processing library[J]. Transactions in GIS, 2014, 18:25-52.
[21] MINETER M J. A software framework to create vector-topology in parallel GIS operations[J]. International Journal of Geographical Information Science, 2003, 17(3):203-222.
[22] GUAN Xuefeng, WU Huayi, LI Lin. A parallel framework for processing massive spatial data with a split-and-merge paradigm[J]. Transactions in GIS, 2012, 16(6):829-843.
[23] HSU C H, CHEN T L, PARK J H. On improving resource utilization and system throughput of master slave job scheduling inheterogeneous systems[J]. The Journal of Supercomputing, 2008, 45(1):129-150.