A Parallel Scheme for Large‐scale Polygon Rasterization on CUDA‐enabled GPUs. Issue 3 (13th May 2016)

• Record Type: Journal Article
• Authors: Zhou, Chen; Chen, Zhenjie; Pian, Yuzhe; Xiao, Ningchuan; Li, Manchun
• Is Part Of: Transactions in GIS. Volume 21:Issue 3(2017)
• Page Start: 608
• Page End: 631
• Publication Date: 2016-05-13
• Subjects: Geographic information systems -- Periodicals; 910.285
• DOI: 10.1111/tgis.12213
• Languages: English
• ISSNs: 1361-1682

Abstract

Abstract: This research develops a parallel scheme to adopt multiple graphics processing units (GPUs) to accelerate large‐scale polygon rasterization. Three new parallel strategies are proposed. First, a decomposition strategy considering the calculation complexity of polygons and limited GPU memory is developed to achieve balanced workloads among multiple GPUs. Second, a parallel CPU/GPU scheduling strategy is proposed to conceal the data read/write times. The CPU is engaged with data reads/writes while the GPU rasterizes the polygons in parallel. This strategy can save considerable time spent in reading and writing, further improving the parallel efficiency. Third, a strategy for utilizing the GPU's internal memory and cache is proposed to reduce the time required to access the data. The parallel boundary algebra filling (BAF) algorithm is implemented using the programming models of compute unified device architecture (CUDA), message passing interface (MPI), and open multi‐processing (OpenMP). Experimental results confirm that the implemented parallel algorithm delivers apparent acceleration when a massive dataset is addressed (50.32 GB with approximately 1.3 × 10 8 polygons), reducing conversion time from 25.43 to 0.69 h, and obtaining a speedup ratio of 36.91. The proposed parallel strategies outperform the conventional method and can be effectively extended to a CPU‐based environment.