CUDA Thrust寻找最近的邻居点

Question

在我的问题中，定义了N个点在该区域内，这些点是随机分布的。对于每个点，我需要找到距离小于给定双精度浮点数DIST的所有相邻点。在Thrust中是否有一种有效的方法来实现这一目标？在串行计算中，我会使用邻居表，希望达到近似O（n）的时间复杂度，而不是O（n ^ 2）的朴素算法。
我已经找到了一个适用于我问题的二维桶排序的Thrust示例。但这还不足够，因为对于每个桶，我需要找到相邻桶中的所有点，然后计算它们的距离并查看是否有任何一个小于DIST。找到邻居和计算距离应该相对容易，但将这些合格的点添加到结果数组中似乎真的很难在Thrust中实现。重新阐述这个特定的问题的方式是这样的——我有两个二维数组A1和A2，列数代表2D桶的索引，每列都有不同数量的元素，这些元素是我的点的索引。 A1的第i列中的每个元素都将与A2的第i列中的每个元素形成潜在对，并且所有符合条件的对都应记录到结果数组中。 我可以使用CUDA内核和分配大量潜在未使用的内存作为解决方法，但那将是我最不想做的事情。 提前致谢。

- Wenzhao Sun

---

你可能会发现这里所讨论的数据结构很有用：https://github.com/jaredhoberock/thrust-workshop/tree/master/more_points - Jared Hoberock

Jared Hoberock 已经几乎为你提供了答案，在链接的 Github 页面中，你将找到你所需要的一切。我只是想知道你是需要一个有多个层级的完整树形结构，还是只需要通过将二维空间分割成大小与你处理的最小元素距离相关的盒子来获得一个层级。对于仅有一个层级的情况，对于每个点，你必须评估该点与同一盒子和相邻盒子中的点之间的距离。也许对于实现多层快速多极算法，需要一个完整的树形结构？ - Vitality

你真是个救命恩人！我看了你给的链接并学习了四叉树。那肯定能解决我的问题。非常感谢你！ - Wenzhao Sun

@JaredHoberock：也许你可以写一个非常简短的答案来概括这个评论，这样它就可以得到赞同/接受，并且这个问题可以从未回答的堆栈中移除。 - talonmies

Answer 1

另一种比创建四叉树更简单的可能性是使用“邻域矩阵”。首先将所有点放入2D正方形矩阵（或3D立方体网格，如果你正在处理三个维度），然后可以运行完整或部分空间排序，使得点在矩阵内有序排列。具有较小Y值的点可以移动到矩阵的顶部行，同样，具有较大Y值的点将移动到底部行。与此类似，具有较小X坐标的点应该移动到左侧的列中，而具有较大X值的点将移动到右侧的列中。在进行空间排序后（有许多方法可以实现这一点，包括串行或并行算法），您可以通过访问邻域矩阵中实际存储点P的相邻单元格来查找给定点P的最近点。如果将此矩阵放置在纹理内存中，则可以使用CUDA的所有空间缓存来快速访问所有邻居！您可以在以下论文中阅读更多关于这个想法的详细信息（您会在网上找到其PDF副本）：基于新兴行为的GPU超大规模人群模拟。

排序步骤会给你带来有趣的选择。你可以仅使用论文中描述的奇偶转置排序，这种方法非常简单易实现（即使在CUDA上也是如此）。如果你仅运行一次这种排序，它将为你提供部分排序，如果你的矩阵接近排序状态，这已经非常有用了。也就是说，如果你的点移动缓慢，它会节省很多计算。

如果你需要完全排序，你可以多次运行这种奇偶转置排序（如下面的维基百科页面所述）：

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

这篇文章来自同一作者，描述了对三维情况的扩展，并使用了三次双调排序（高度并行，但不是空间排序）。他们声称它比单个偶奇换位传递更精确，比完全排序更有效率。该论文名为“用于GPU上大规模3D人群模拟的邻域网格数据结构”。

- mgmalheiros

Answer 2

完整的解决方案超出了单个 Stack Overflow 回答的范围，但是在这个代码库中有一个关于如何使用 Thrust 构建 2D 空间索引的讨论。

https://github.com/jaredhoberock/thrust-workshop

- Jared Hoberock