2

我正在阅读有关 CUDA 的内容，并尝试实现一个简单的代码来创建 的所有可能排列array {a,b,c,d}，但我不知道如何实现 CUDA 方式（因为我阅读的所有示例都是形式a[blockIdx.x] = b[blockIdx.x] + c[blockIdx.x]）。

任何帮助将不胜感激。

4

2 回答 2

3

下面是 CUDA 中并行排列生成器的一个有点幼稚的实现。该示例旨在生成 的所有可能排列ABCD。

由于所有可能的排列都可以通过将第一个符号固定为，X然后附加其余符号的所有可能排列，然后将第一个符号更改为，然后Y再次执行上述过程来生成，代码背后的简单想法是指定4线程来完成这项工作，每个线程引用不同的初始符号。

第一个符号之后的排列以规范的方式进行评估，即通过递归。

显然，下面的代码可以变得更通用，甚至可以改进，但它应该给你一个初步的大致思路。

#include <stdio.h>

inline void GPUassert(cudaError_t code, char * file, int line, bool Abort=true)
{
    if (code != 0) {
        fprintf(stderr, "GPUassert: %s %s %d\n", cudaGetErrorString(code),file,line);
        if (Abort) exit(code);
    }       
}

#define GPUerrchk(ans) { GPUassert((ans), __FILE__, __LINE__); }

__host__ __device__ void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

__device__ void permute_device(char *a, int i, int n, int tid, int* count) 
{
    if (i == n) { 
        char b[4]; char* c = a - 1; 
        b[0] = c[0]; b[1] = c[1]; b[2] = c[2]; b[3] = c[3];
        printf("Permutation nr. %i from thread nr. %i is equal to %s\n", count[0], tid, c); count[0] = count[0] + 1; 
    }
    else
    {
        for (int j = i; j <= n; j++)
        {
            swap((a+i), (a+j));
            permute_device(a, i+1, n, tid, count);
            swap((a+i), (a+j)); //backtrack
        }
    }
} 

__global__ void permute_kernel(char* d_A, int size) {

    int tid = threadIdx.x + blockIdx.x * blockDim.x;
    int count[1]; count[0] = 0;

    char local_array[4];

    for (int i=0; i<size; i++) local_array[i] = d_A[i];

    swap(local_array+threadIdx.x,local_array);
    permute_device(local_array+1,0,2,tid,count);

}

int main()
{
    char h_a[] = "ABCD";

    char* d_a; cudaMalloc((void**)&d_a,sizeof(h_a));
    GPUerrchk(cudaMemcpy(d_a, h_a, sizeof(h_a), cudaMemcpyHostToDevice));

    printf("\n\n Permutations on GPU\n");
    permute_kernel<<<1,4>>>(d_a, 4);
    GPUerrchk(cudaPeekAtLastError());
    GPUerrchk(cudaDeviceSynchronize());

    getchar();
    return 0;
}
于 2013-11-14T20:53:43.970 回答
-2

我想知道你的组合是否是成对的。

  1. 考虑数组的长度。（n）
  2. 想想组合复合体。（n^2，成对）
  3. 选择一种并行计算的方法。（使用块 id 作为添加偏移量，线程 id 作为基数。例如，array(threadid) + array(threadid+offset)）

所以你的内核应该这样写：

template<typename T>
__global__ void 
combination(T* in, T* out) {
  int tid = threadId.x;
  int bid = blockId.x+1;
  out[tid+bid*blockDim.x] = in[tid]+in[(tid+bid)%arrlen];     //0+1, 1+2,..., 0+2, 1+3
}

gridDim(arrlen)您可以使用和调用内核blockDim(arrlen)。

于 2013-11-13T06:59:53.737 回答