c++ - 二分查找是否适合 OpenCL？

Question

我正在编写一个 OpenCL 程序，除其他外，它需要根据白名单检查计算的 (int) 值。我的计划是将白名单存储在常量或共享内存中，然后让每个线程使用此共享白名单运行二分搜索。

然后我读到了诸如存储体冲突之类的内容，其中线程速度减慢，因为它们正在访问同一存储体上的内存，这会导致发生访问序列化。

由于此类问题，二分搜索是否会导致 OpenCL 上的性能损失更大？我使用其他搜索算法(例如哈希)会更好吗？

编辑 让我稍微澄清一下我的程序:

每个线程都会进行并行计算，但使用不同的输入值。因此，每个线程都会得到不同的输出。每个输出都需要根据相同的白名单进行检查。

内核将返回一个 bool 值，指示搜索结果。

我担心的是，由于每个线程都在进行独立的二分搜索，因此多个线程最终将访问白名单的同一组，从而导致串行减速。

Answer 1

如果您在每个线程中搜索不同的项目，那么您不需要担心库冲突，而是需要担心线程分歧，因为二分搜索需要分支。其中一些问题可以使用 select 函数来缓解。

您最好使用其他算法，例如 interpolation search ，它可以以更少的跳数找到该项目(本质上，决定下一步查找的成本比二分搜索更昂贵，但是如果您的搜索数据位于全局内存中，则可以在内存延迟)。

我最近正在解决类似的问题:Binary search with hint .

简化的算法如下所示:

__global const _TyIndex *upper_bound(__global const _TyIndex *begin,
    __global const _TyIndex *end, const _TyIndex elem)
{
    while(begin != end) {
        __global const _TyIndex *mid = begin + (end - begin) / 2;

#if 0
        if(!(elem < *mid))
            begin = mid + 1; // look to the right
        else
            end = mid; // look to the left
#else // 0
        bool b_right = !(elem < *mid);
        begin = (__global const _TyIndex *)select((intptr_t)begin, (intptr_t)(mid + 1), b_right);
        end = (__global const _TyIndex *)select((intptr_t)mid, (intptr_t)end, b_right); // c ? b : a
#endif // 0
    }

    return begin;
}

这是使用 select() 两次而不是分支。您可以通过将#if 0更改为#if 1来比较性能。请注意 e? a : b 确实暗示了一个分支，因此使用它没有帮助。