Advertisement
Guest User

用显卡(cuda)计算扫雷高级局面的3BV

a guest
Sep 23rd, 2022
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.96 KB | Source Code | 0 0
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <cstring>
  5. #include <time.h>
  6. #include "cuda_runtime.h"
  7. #include "device_launch_parameters.h"
  8. #include <curand_kernel.h>
  9. #include <curand.h>
  10. #include <stack>
  11. // #define GRIDSIZE 2048;
  12. // #define BLOCKSIZE 128;
  13. #define GRIDSIZE 1024;
  14. #define BLOCKSIZE 64;
  15. // nvcc -O3 main.cu --run
  16. // -1:雷
  17. // -10:1~8
  18. // 0~60:空及其标记
  19.  
  20. __device__ void print_board(signed short board[][30]) {
  21.     printf("[");
  22.     for(unsigned short i = 0; i < 16; i++) {
  23.         printf("[");
  24.         for(unsigned short j = 0; j < 30; j++) {
  25.             printf("%3d,", board[i][j]);
  26.         }
  27.         printf("],\n");
  28.     }
  29.     printf("]\n");
  30. }
  31.  
  32. __device__ unsigned int curand_int(unsigned int n, curandStateMRG32k3a_t* state) {
  33.     // 0到n-1之间的随机数,闭区间
  34.     if (n == 0) {
  35.         return 0;
  36.     }
  37.     unsigned int t = curand(state);
  38.     while (t > (0xffffffff / n * n)) {
  39.         t = curand(state);
  40.     }
  41.     return t % n;
  42.     return t;
  43. }
  44.  
  45. __device__ void lay_mine_exp(signed short board[][30], curandStateMRG32k3a_t* state) {
  46.     for(unsigned short i = 0; i < 3; i++) {
  47.         for(unsigned short j = 0; j < 30; j++) {
  48.             board[i][j] = -1;
  49.         }
  50.     }
  51.     for(unsigned short j = 0; j < 9; j++) {
  52.         board[3][j] = -1;
  53.     }
  54.  
  55.     for (unsigned short m = 479; m > 0; m--) {
  56.         unsigned int e = curand_int(m + 1, state);
  57.         unsigned int i = e & 0x0000000f;
  58.         unsigned int j = e >> 4;
  59.         unsigned int x = m & 0x0000000f;
  60.         unsigned int y = m >> 4;
  61.         if (board[i][j] != board[x][y]){
  62.             // 交换数字
  63.             if (board[i][j] == 0) {
  64.                 board[i][j] = -1;
  65.                 board[x][y] = 0;
  66.             } else {
  67.                 board[i][j] = 0;
  68.                 board[x][y] = -1;
  69.             }
  70.         }
  71.     } // 至此,埋雷第一步完成
  72.  
  73.     for(signed char i = 0; i < 16; i++) {
  74.         for(signed char j = 0; j < 30; j++) {
  75.             for(signed char m = max(0, i - 1); m < min(16, i + 2); m++) {
  76.                 for(signed char n = max(0, j - 1); n < min(30, j + 2); n++) {
  77.                     if (board[m][n] == -1 && board[i][j] != -1) {
  78.                         board[i][j] = -10;
  79.                         break;
  80.                     }
  81.                 }
  82.             }
  83.         }
  84.     } // 计算数字,只算到1
  85. }
  86.  
  87. __device__ unsigned short cal_bbbv_exp(signed short board[][30]) {
  88.     unsigned short op_num = 0; // op数量
  89.     unsigned short op_head = 0; // 栈顶
  90.     unsigned short bbbv_is_num = 0;
  91.     bool op_id[116]; // 高级最多有58个op,但这里不能这么少,只能试
  92.     memset(op_id,false,sizeof(op_id));
  93.  
  94.     for(signed char i = 0; i < 16; i++) {
  95.         for(signed char j = 0; j < 30; j++) {
  96.             if (board[i][j] == -10) {
  97.                 // 把岛上的3BV数出来
  98.                 bool is_bbbv = true;
  99.                 for(signed char m = max(0, i - 1); m < min(16, i + 2); m++) {
  100.                     for(signed char n = max(0, j - 1); n < min(30, j + 2); n++) {
  101.                         if (board[m][n] >= 0) {
  102.                             is_bbbv = false;
  103.                             break;
  104.                         }
  105.                     }
  106.                 }
  107.                 if (is_bbbv) {
  108.                     bbbv_is_num += 1;
  109.                     // printf("(%2d, %2d), ", i, j);
  110.                 }
  111.             } else if (board[i][j] >= 0) {
  112.                 bool has_neighbour = false;
  113.                 if (i > 0) {
  114.                     for(signed char n = max(0, j - 1); n < min(30, j + 2); n++) {
  115.                         if (board[i - 1][n] > 0) {
  116.                             if (!has_neighbour) {
  117.                                 // 从0变成op的编号
  118.                                 has_neighbour = true;
  119.                                 board[i][j] = board[i - 1][n];
  120.                             } else if(board[i][j] > board[i - 1][n]) {
  121.                                 if (op_id[board[i][j]]) {
  122.                                     op_id[board[i][j]] = false;
  123.                                     op_num -= 1;
  124.                                     board[i][j] = board[i - 1][n];
  125.                                 }
  126.                             } else if(board[i][j] < board[i - 1][n]) {
  127.                                 if (op_id[board[i - 1][n]]) {
  128.                                     op_id[board[i - 1][n]] = false;
  129.                                     op_num -= 1;
  130.                                 }
  131.                             }
  132.                         }
  133.                     }
  134.                    
  135.                 }
  136.                 if (j > 0) {
  137.                     if (board[i][j - 1] > 0) {
  138.                         if (!has_neighbour) {
  139.                             // 从0变成op的编号
  140.                             has_neighbour = true;
  141.                             board[i][j] = board[i][j - 1];
  142.                         } else if(board[i][j] > board[i][j - 1]) {
  143.                             if (op_id[board[i][j]]) {
  144.                                 op_id[board[i][j]] = false;
  145.                                 op_num -= 1;
  146.                                 board[i][j] = board[i][j - 1];
  147.                             }
  148.                         } else if(board[i][j] < board[i][j - 1]) {
  149.                             if (op_id[board[i][j - 1]]) {
  150.                                 op_id[board[i][j - 1]] = false;
  151.                                 op_num -= 1;
  152.                             }
  153.                         }
  154.                     }
  155.                 }
  156.                 if (!has_neighbour) {
  157.                     op_head += 1;
  158.                     op_num += 1;
  159.                     op_id[op_head] = true;
  160.                     board[i][j] = op_head;
  161.                 }
  162.             }
  163.         }
  164.     } // 计算数字,只算到1
  165.     // printf("%3d, ", op_num);
  166.     // print_board(board);
  167.     return op_num + bbbv_is_num;
  168. }
  169.  
  170.  
  171.  
  172.  
  173. __global__ void hello_world_from_gpu(int* bbbv_) {
  174.     // printf("blockDim.x: %d, blockDim.y: %d, blockDim.z: %d\n", blockDim.x, blockDim.y, blockDim.z);
  175.     //printf("threadIdx.x: %d, threadIdx.y: %d, threadIdx.z: %d, blockIdx.x: %d, blockIdx.y: %d, blockIdx.z: %d\n", threadIdx.x, threadIdx.y, threadIdx.z, blockIdx.x, blockIdx.y, blockIdx.z);
  176.     //printf("Hello World from GPU\n");
  177.     unsigned long long tid = threadIdx.x + blockIdx.x * BLOCKSIZE;
  178.     curandStateMRG32k3a_t state;
  179.     unsigned long long subsequence = 0;
  180.     unsigned long long offset = 0;
  181.     curand_init(tid, subsequence, offset, &state);
  182.  
  183.     signed short board[16][30];
  184.  
  185.     for (int t = 0; t < 100; t++){
  186.         memset(board,0,sizeof(board));
  187.         lay_mine_exp(board, &state);
  188.         unsigned short bbbv = cal_bbbv_exp(board);
  189.         // unsigned short bbbv = 1;
  190.         atomicAdd(&bbbv_[bbbv], 1);
  191.     }
  192.  
  193.    
  194.     return;
  195.  
  196. }
  197.  
  198. int main(void) {
  199.  
  200.     printf("Hello World from CPU\n");
  201.     int nx = GRIDSIZE;
  202.     int ny = BLOCKSIZE;
  203.     //dim3 block(3, 2);
  204.     //dim3 grid(nx / block.x, ny / block.y);
  205.    
  206.  
  207.     const int N = 381;
  208.     const int M = sizeof(int) * N;
  209.  
  210.     int bbbv[381] = {0};
  211.     int *cuda_bbbv;
  212.     cudaMalloc(&cuda_bbbv, M);
  213.     cudaMemcpy(cuda_bbbv, bbbv, M, cudaMemcpyHostToDevice);
  214.  
  215.     clock_t start, finish;
  216.     float costtime;
  217.     start = clock();
  218.  
  219.     hello_world_from_gpu <<< nx, ny >>> (cuda_bbbv);
  220.  
  221.  
  222.     int call_back = cudaDeviceSynchronize();
  223.     finish = clock();
  224.     //得到两次记录之间的时间差
  225.     costtime = (float)(finish - start) / CLOCKS_PER_SEC;
  226.  
  227.  
  228.     cudaMemcpy(&bbbv, cuda_bbbv, M, cudaMemcpyDeviceToHost);
  229.  
  230.     //time_t t;
  231.     //srand((unsigned)time(&t));
  232.     //printf(" %d \n", (int)(rand() & 0xff));
  233.  
  234.     int aaa = 0;
  235.     for (int n = 0; n < 381; ++n)
  236.     {
  237.         aaa += bbbv[n];
  238.         printf("%d: %d\n", n, bbbv[n]);
  239.     }
  240.     printf("一共: %d\n", aaa);
  241.     printf("耗时:%f \n", costtime);
  242.     printf("速度:%f \n", aaa/costtime);
  243.  
  244.     cudaDeviceReset();
  245.     cudaFree(cuda_bbbv);
  246.     return 0;
  247. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement