A strategy for parallelising polygon rasterisation algorithms using multi-core CPUs. Issue 1 (2nd January 2016)

• Record Type: Journal Article
• Authors: Zhou, Chen; Chen, Zhenjie; Liu, Yongxue; Li, Manchun; Wu, Jiexuan; Zhang, Yunqian
• Is Part Of: Journal of spatial science. Volume 61:Issue 1(2016)
• Page Start: 47
• Page End: 68
• Publication Date: 2016-01-02
• Subjects: geographic information science -- vector data -- polygon rasterisation -- parallel computing; Geographic information systems -- Periodicals; Cartography -- Periodicals; Surveying -- Periodicals; Geodesy -- Periodicals; Photogrammetry -- Periodicals; Cartography; Geodesy; Geographic information systems; Photogrammetry; Surveying; Periodicals; 526.05
• DOI: 10.1080/14498596.2015.1087888
• Languages: English
• ISSNs: 1449-8596

Abstract

Abstract : Polygon rasterisation is a fundamental process in geographic information science. Because of recent increases in the quantity of vector data, rapid rasterisation techniques are urgently needed. This study explores methods for combining processes and threads on multi-core CPUs to accelerate large-scale polygon rasterisation. First, a data decomposition method is adopted for effective load balancing between processes and threads. Second, a polygon processing strategy is proposed to manage four types of exceptional polygons. Using these approaches, a hybrid parallel framework is proposed to parallelise sequential rasterisation algorithms while maximising their processing speed. The experimental results show that the implemented parallel algorithm can efficiently reduce rasterisation time (from 40.62 h to 1.97 h) and obtain a satisfactory speed-up of 20.62. The proposed hybrid parallel algorithm outperforms pure process-level or pure thread-level implementations. Moreover, the proposed decomposition methods can provide consistently superior performance compared with conventional techniques and can achieve superior load balancing.