Générer des permutations avec CUDA

J’étais en train de lire sur CUDA, et j’ai essayé d’implémenter un code simple pour créer toutes les permutations possibles du array {a,b,c,d} , mais je ne sais pas comment implémenter la méthode CUDA (car tous les exemples que j’ai read étaient de la forme a[blockIdx.x] = b[blockIdx.x] + c[blockIdx.x] ).

Toute aide serait appréciée.

    Vous trouverez ci-dessous une implémentation quelque peu naïve d’un générateur de permutation parallèle dans CUDA. L’exemple vise à générer toutes les permutations possibles de ABCD .

    Puisque toutes les permutations possibles peuvent être générées en fixant le premier symbole à, disons, X et en ajoutant toutes les permutations possibles des symboles restants, puis en changeant le premier symbole en, par exemple Y et en refaisant le processus ci-dessus, l’idée simple derrière le code est de nommer 4 threads pour faire le travail, chaque thread se référant à un symbole initial différent.

    Les permutations suivant le premier symbole sont évaluées de manière canonique, notamment par récursion.

    Évidemment, le code ci-dessous peut être plus général et peut-être amélioré, mais il devrait vous donner une première idée approximative.

     #include  inline void GPUassert(cudaError_t code, char * file, int line, bool Abort=true) { if (code != 0) { fprintf(stderr, "GPUassert: %s %s %d\n", cudaGetErrorSsortingng(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>>(d_a, 4); GPUerrchk(cudaPeekAtLastError()); GPUerrchk(cudaDeviceSynchronize()); getchar(); return 0; } 

    Je me demande si votre combinaison est paire.

    1. Pensez à la longueur du tableau. (N)
    2. Pensez au complexe de combinaison. (n ^ 2, paire)
    3. choisissez une méthode pour calculer de manière parallèle. (utilisez id de bloc comme add offset et id de thread comme base 1. array (threadid) + array (threadid + offset) par exemple)

    donc votre kernel devrait être écrit comme ceci:

     template __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 } 

    vous pouvez appeler le kernel avec gridDim(arrlen) et blockDim(arrlen) .