A parallel framework for data-intensive geospatial analysis on large-scale vector polygons over hybrid CPUs and GPUs

doi:10.13474/j.cnki.11-2246.2022.0151

Abstract

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

CLC Number:

P208

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.

References

[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.