下面是 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;
}