algorithm - 如何使用CUDA减少二分查找的分支发散

Question

应用程序是求两个排序的整数列表的交集(集合交集)，比如 list1 和 list2。

list1的每个元素都会被分配一个GPU线程，进行二分查找是否出现在list2中。很容易看出，在这个应用程序中会有大量的线程分歧。我想知道是否有什么好的方法可以减少线程分歧。我正在使用 CUDA 来实现这个应用程序。

我知道有一种方法叫做 P-ary search，但我的任务是减少二分查找的线程发散。我也知道有一个名为 thrust 的库，但似乎没有尝试减少分歧。

Answer 1

如果两个列表都已排序，则二分查找不是您可以执行的最佳算法。二进制搜索将给出 O(n lg n)，但仅执行类似合并的算法，仅取交集，是 O(n)。

这是一个使用 GPU 的愚蠢算法。我看到的唯一情况是您刚刚在 GPU 中生成了数据。在这种情况下，您希望将问题分解为一堆较小的交集并为每个交集分配一个线程。

为此，选择 list1 的 k 个等距元素，并使用二进制搜索在 list2 中找到它们。类似地，从 list2 中选取 k 个等距元素，并在 list1 中找到它们。您现在在每个列表中有 2k 个范围，其中每个范围最多有 N/k 个元素。现在将这些范围平行相交。 (将 k 设置为您想要的线程数的一半。)