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 に答える