在我的问题中，域中有 N 个点，它们以某种方式随机分布。对于每个点，我需要找到距离小于给定双精度浮点数 DIST 的所有相邻点。在 Thrust 中是否有有效的方法来做到这一点？在串行中，我会使用邻域表并希望实现大约 O(n) 而不是 O(n^2) 的朴素算法。
我找到了一个用于 2D 桶排序的推力示例，它非常适合我的问题的第一部分。但这还不够，因为对于每个桶，我需要找到相邻桶中的所有点，然后计算它们的距离，看看它们中的任何一个是否小于 DIST。查找邻居和计算距离应该相对容易，但是将这些符合条件的点添加到结果数组对我来说似乎很难在 Thrust 中实现。重新表述这个特定问题的一种方法是——我有两个二维数组 A1 和 A2，列号表示二维存储桶的索引，每列有不同数量的元素，它们是我的点的索引。A1 的第(i) 列中的每个元素将与A2 的第(i) 列中的每个元素形成一个潜在对，并且所有符合条件的对都应记录到结果数组中。我可以使用 CUDA 内核并分配大量可能未使用的内存作为解决方法，但这将是我最不想做的事情。提前致谢。
问问题
1840 次
2 回答
2
另一种比创建四叉树更简单的可能性是使用邻域矩阵。
首先将所有点放入 2D 方阵（或 3D 立方网格，如果您正在处理三个维度）。然后您可以运行完整或部分空间排序，因此点将在矩阵内变得有序。
Y 小的点可以移动到矩阵的顶行，同样，Y 大的点会移动到矩阵的底行。具有较小 X 坐标的点也会发生同样的情况，这些点应该移动到左侧的列。并且对称地，具有大 X 值的点将进入右列。
完成空间排序后（有很多方法可以通过串行或并行算法实现这一点），您可以通过访问点 P 实际存储在邻域矩阵中的相邻单元来查找给定点 P 的最近点。
如果将此矩阵放入纹理内存中，您可以使用 CUDA 中的所有空间缓存来非常快速地访问所有邻居！
您可以在以下论文中阅读有关此想法的更多详细信息（您可以在线找到它的 PDF 副本）：基于紧急行为的 GPU 上的超大规模人群模拟。
排序步骤为您提供了有趣的选择。您可以只使用论文中描述的奇偶转置排序，它实现起来非常简单（即使在 CUDA 中也是如此）。如果你只运行一次，它会给你一个部分排序，如果你的矩阵是接近排序的，这可能已经很有用了。也就是说，如果您的点移动缓慢，它将为您节省大量计算。
如果你需要一个完整的排序，你可以多次运行这样的奇偶转置传递（如下面的维基百科页面所述）：
http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort
还有来自同一作者的第二篇论文，描述了对 3D 的扩展，并使用了三遍双音排序（这是高度并行的，但它不是空间排序）。他们声称它比单个奇偶转置传递更精确，并且比完整排序更有效。这篇论文是A Neighborhood Grid Data Structure for Massive 3D Crowd Simulation on GPU。
于 2014-02-08T21:18:46.797 回答
2
完整的解决方案超出了单个 Stack Overflow 答案的范围，但讨论了如何使用 Thrust 在此存储库中构建 2D 空间索引：
于 2013-11-11T19:49:28.977 回答