基于异构多核架构的点、线与多边形间空间关系查询并行加速研究.docx

基于异构多核架构的点、线与多边形间空间关系查询并行加速研究
基于异构多核架构的点、线与多边形间空间关系查询并行加速研究
摘要：随着计算机性能的提高和大规模空间数据的增长，点、线与多边形间空间关系查询已成为许多应用领域的核心问题。为了加速这些查询过程，本论文提出了一种基于异构多核架构的并行加速方法。该方法利用多核CPU与GPU的并行计算能力，实现了点、线与多边形间空间关系查询的高效处理。通过实验结果验证，该方法能够在减少查询时间的同时保证查询结果的精确性。
1.引言
点、线与多边形间空间关系查询是许多地理信息系统、计算机图形学、计算机辅助设计等应用领域的基础问题。该查询通常用于判断点是否在多边形内部、线与多边形是否相交等。然而随着数据量的增加和查询复杂性的提高，传统的串行算法已经无法满足实时查询的需求。因此，研究基于并行计算的加速方法具有重要的意义。
2.相关工作
传统的点、线与多边形间空间关系查询算法主要基于几何学的原理和计算几何的算法，如射线法、射线扫描法等。这些算法往往需要大量的计算和存储开销，导致查询效率低下。为了加速查询过程，研究者们提出了各种并行计算方法，如基于GPU的并行计算、基于多核CPU的并行计算等。
3.异构多核架构
异构多核架构包括多核CPU和GPU两部分，每个部分都有自己的特点和优势。多核CPU通常具有较强的通用计算能力，适用于复杂算法的计算；而GPU则擅长于并行计算，适用于大规模数据的处理。通过充分利用CPU和GPU的优势，可以实现点、线与多边形间空间关系查询的高效处理。
4.并行加速方法
本论文提出的并行加速方法主要包括以下步骤：
-数据预处理：将输入数据划分为多个子任务，并确定每个子任务的处理范围。
-并行计算：将每个子任务分配给不同的核心进行并行计算，利用CPU和GPU的并行计算能力，同时进行多个查询任务。
-结果合并：将每个子任务的查询结果合并，得到最终的查询结果。
5.实验与评估
为了验证本方法的性能，本论文设计了一组实验，并与传统的串行算法进行比较。实验结果表明，本方法能够显著提高查询的效率，减少查询时间。
同时，本方法在保证查询结果准确性的前提下，能够有效处理大规模数据的查询任务。
6.总结与展望
本论文提出了一种基于异构多核架构的点、线与多边形间空间关系查询并行加速方法。该方法通过充分利用多核CPU和GPU的并行计算能力，实现了高效的查询处理。实验结果表明，该方法在减少查询时间的同时保证了查询结果的精确性。未来的研究可以进一步优化方法的并行计算策略，提高查询的效率和准确性。
参考文献：
[1]ZhangX,WuE,WuH,etal.Aparallelpoint-in-polygonalgorithmanditsGPUimplementation[J].InternationalJournalofDigitalEarth,2017,10(12):1231-1245.
[2]ChenY,WangM,KaoB,etal.GPU-acceleratedspatialqueryprocessing[C]//2017IEEEInternationalConferenceonBigData(BigData).IEEE,2017:177-186.
[3]LiM,CongG,BiswasR,etal.POC:Progressiveoctreeconstructiononlargepointcloudsusingdistributedspatialpartitioning[J].IEEEtransactionsonvisualizationandcomputergraphics,2017,23(1):631-640.