2

我想知道如何避免在使用 CUDA 进行字符串搜索时出现分支分歧，以及是否有一个好的方法来做到这一点。

目前，我尝试将 Knuth Morris Pratt 应用于 GPU，但我相信存在很多分歧，因为每个线程都在寻找 N 个字母，并且每次都比较这些字母是否对应于我正在搜索的单词的第一个字母。

int tid = blockDim.x * blockIdx.x + threadIdx.x;
int startId = tid * 64;
int x = 0;
for(int i = 0; i < 64; i++){
    if(array[startId + i] == 'C'){
        x++;
    }
}

如果我使用这个虚拟代码来查找字母“C”，但我也可以再次查看以搜索更多字母。

4

1 回答 1

1

您可以尝试将比较结果直接添加到值中，如下所示：

x+= (array[startId + i] == 'C');

但我相信这可能仍然存在分支。我的解决方案是将一个块中的数组值存储到共享内存中，然后为块中的每个线程分配一个所需的字符，并将结果放入它们自己的共享内存空间中，然后减少。

__shared__ char l_array[BLOCK_SIZE];
__shared__ char l_results[BLOCK_SIZE];

int bid = blockDim.x * blockIdx.x;
int lid = threadIdx.x;
int tid = bid + lid;
int x=0;

char desired_char = get_character(lid);


l_array[lid] = -1;


//Store global values in shared memory
if(tid < array_size){
    l_array[lid] = array[tid];       
}

__syncthreads();

//Check local memory for desired character
for(int i = 0; i < BLOCK_SIZE; i++)
   x+=(l_array[i] == desired_char);

//Store results into shared memory
l_results[lid] = x;

__syncthreads();
//Then reduce (poorly)
if(lid==0){
    for(int i = 0; i < BLOCK_SIZE; i++)
        x+= l_results[i];
}

虽然我不知道算法本身，但我只是猜测，但这里的一些东西可能会帮助你弄清楚这一点。

于 2015-09-30T16:52:55.537 回答