gpu中的平行凸包算法

Question

我正在CUDA中实施凸包的分而治之的方法。这是我的方法： 自上而下：

• 创建列表以存储凸包;

• curSize =输入大小（所有点）;

• 对于i：1至日志N

• 开始
• curSize = curSize/2;
• 以每2个相邻的凸壳中列表的列表，并将它们 合并成更大的船体（使用标准的上部和下部共同切线为鸿沟&治凸包 方法）在curSize线程
• //最初，它合并每2然后在下一次迭代中使用 ，它将大小为2的凸包合并成更大的 凸包等。最后，列表的列表将包含一个 船体上的单点列表
• 结束

但它变得太复杂了，我觉得我没有利用CUDA的并行功能，因为在树的每一层都创建了N/2^i线程，在合并所有相邻的船体时，复杂度为O（N）。因此，网络复杂性仍然是O（N logN）。

你能告诉我如何让它变得更好吗？或者为凸包提供任何替代的整理器并行算法（如果我可以得到graham扫描的并行版本的算法，那将会很棒）？

Answer 1

将你的算法的复杂度仍然是O（N）（相比没有改变一个线程版本），因为你做3两件事：

1. 管理线程：O（N）
2. 删除一些来自列表的顶点：由于只有N个点，所以摊销O（N）。
3. 查看与当前步骤中已移除但未移除的点相邻的点：O（N），因为每次合并的点数不会超过2个。

但是，如果你的点没有排序，你应该更好地并行排序。