A strategy for parallelising polygon rasterisation algorithms using multi-core CPUs

作者：Zhou, Chen; Chen, Zhenjie^*; Liu, Yongxue; Li, Manchun; Wu, Jiexuan; Zhang, Yunqian

来源：Journal of Spatial Science, 2016, 61(1): 47-68.

DOI：10.1080/14498596.2015.1087888

• vector data
• polygon rasterisation
• geographic information science
• parallel computing

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.62h to 1.97h) 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.

• 出版日期2016-1-2
• 单位南京大学