0

该应用程序是相交两个排序的整数列表（设置交集），比如 list1 和 list2。

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

我知道有一种叫做 P-ary 搜索的方法，但我的任务是减少二分搜索的线程发散。我也知道有一个叫做推力的图书馆，但似乎没有尝试减少分歧。

4

2 回答 2

2

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

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

为此，请选择klist1 的等距元素并使用二分搜索在 list2 中找到它们。同样，选择klist2 的等距元素并在 list1 中找到它们。您现在2k在每个列表中都有范围，其中每个范围最多N/k包含元素。现在平行地与这些范围相交。（设置k为所需线程数的一半。）

于 2012-05-01T05:11:43.673 回答
2

可能的代码：

    bool end = false;
    bool found = false;

    while(!end && !found)
    {
            int diff        = max-min;
            int middle      = min + (diff / 2);

            end             = diff < 1;
            found           = element[middle] == element;
            if (index < elements[middle])
                    max = middle-1;
            else //(index > elements[middle+1])
                    min = middle + 2;
    }
    return found;

警告：此代码可能会因访问超出范围的内存而产生异常

于 2012-09-29T17:48:19.800 回答