ParGeo: A Library for Parallel Computational Geometry
ParGeo: A Library for Parallel Computational Geometry
复制标题
DOI：
10.48550/arxiv.2207.01834
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Yiqiu Wang;Rahul Yesantharao;Shangdi Yu;Laxman Dhulipala;Yan Gu;Julian Shun
中科院分区：
文献类型：
--
作者：
Yiqiu Wang;Rahul Yesantharao;Shangdi Yu;Laxman Dhulipala;Yan Gu;Julian Shun
本文介绍了ParGeo，一个用于计算几何的多核库。ParGeo包含用于基本任务的模块，包括基于k-d树的空间搜索、空间图生成以及计算几何中的算法。我们重点关注该库中提供的三项新的算法贡献。首先，我们提出了一种基于预留技术的新型并行凸包算法，以实现对凸包的并行修改。我们还提供了随机增量凸包算法以及\(\mathbb{R}^3\)中的分治凸包算法的首个并行实现。其次，对于最小包围球问题，我们提出了一种新的基于采样的算法，以快速减小数据集的大小。我们还提供了用于最小包围球的Welzl经典算法的首个并行实现。第三，我们提出了BDL - 树，一种并行批量动态k - d树，它允许对动态变化的点集进行高效的并行更新和k - 近邻查询。BDL - 树由一组日志结构的k - d树组成，可用于高效地并行插入、删除和查询批量点。在具有双向超线程的36个核心上，我们最快的凸包算法实现了高达44.7倍的自身相对并行加速，相较于现有的最佳顺序实现加速高达559倍。我们使用基于采样的算法的最小包围球算法实现了高达27.1倍的自身相对并行加速，相较于现有的最佳顺序实现加速高达178倍。我们的BDL - 树实现达到了高达46.1倍的自身相对并行加速。在ParGeo中的所有算法中，我们实现了8.1 - 46.61倍的自身相对并行加速。
This paper presents ParGeo, a multicore library for computational geometry. ParGeo contains modules for fundamental tasks including $k$d-tree based spatial search, spatial graph generation, and algorithms in computational geometry. We focus on three new algorithmic contributions provided in the library. First, we present a new parallel convex hull algorithm based on a reservation technique to enable parallel modifications to the hull. We also provide the first parallel implementations of the randomized incremental convex hull algorithm as well as a divide-and-conquer convex hull algorithm in $\mathbb{R}^3$. Second, for the smallest enclosing ball problem, we propose a new sampling-based algorithm to quickly reduce the size of the data set. We also provide the first parallel implementation of Welzl's classic algorithm for smallest enclosing ball. Third, we present the BDL-tree, a parallel batch-dynamic $k$d-tree that allows for efficient parallel updates and $k$-NN queries over dynamically changing point sets. BDL-trees consist of a log-structured set of $k$d-trees which can be used to efficiently insert, delete, and query batches of points in parallel. On 36 cores with two-way hyper-threading, our fastest convex hull algorithm achieves up to 44.7x self-relative parallel speedup and up to 559x speedup against the best existing sequential implementation. Our smallest enclosing ball algorithm using our sampling-based algorithm achieves up to 27.1x self-relative parallel speedup and up to 178x speedup against the best existing sequential implementation. Our implementation of the BDL-tree achieves self-relative parallel speedup of up to 46.1x. Across all of the algorithms in ParGeo, we achieve self-relative parallel speedup of 8.1--46.61x.