关键词:
叠加分析
矢量多边形裁剪
混合并行
奇偶排序
OpenMP
算法优化
高性能计算
GIS
摘要:
矢量多边形裁剪是GIS领域中重要且常用的基础功能之一,地理空间数据规模的爆炸式增长给传统裁剪算法的计算效率提出了更高的要求,当前矢量多边形裁剪算法日益呈现计算密集和数据密集的特点。针对这一现象,本文基于矢量多边形裁剪Vatti算法,优化其数据结构,将GPU众核并行技术应用到构建局部最小点表和有序扫描束的环节中,当Block大小为128,裁剪多边形顶点数达到3276800时,在求交算子操作下,对多边形裁剪Vatti算法的加速比达到2.55倍。在此基础上,本文基于CPU多线程并行技术进一步利用计算资源,提出了通过顶点数量对数据集进行分割并实现混合并行加速的优化方法(VSHP)。针对一个大规模数据集,由主线程读取数据后根据顶点数和线程数对原始数据进行划分,之后交由各线程进行计算,期间依次调用GPU对最小外包矩形过滤、构建局部最小点表和有序扫描束环节进行加速,最后当所有数据任务计算完成后,由主线程完成结果的归并和输出。试验表明,当调用4个线程时可获得理想的加速效果,在动态调度策略下启用16个线程时可获得最高19.15倍的加速比。本文通过CPU-GPU的混合并行优化技术,尝试在较低的能耗下实现桌面上的高性能计算,旨在为传统矢量多边形裁剪算法在廉价消费级硬件平台上获得高性能加速优化提供一定的参考价值,降低地理信息数据规模化应用的成本。