Assignment 3 (CS427) – Game of Life

1. โปรแกรม Game of Life ที่เป็นการทำงานแบบ Sequential จำเป็นจะต้องมีอาร์เรย์จำนวน 2 ชุดในการเก็บข้อมูลของเวลาที่ต่างกันในการทำงาน และใช้ Pointer ในการสลับอาร์เรย์เพื่อประมวลผล

#include <stdio.h>
#include <time.h>
#define MAX_WIDTH 1000

FILE *f;
char board1[MAX_WIDTH * MAX_WIDTH];
char board2[MAX_WIDTH * MAX_WIDTH];
char *currentBoard;
char *pastBoard;
int maxx, maxy;

void init();                           	        /* initial board */
void rand_init_pop(int rand_size);      	/* initial population */
int in_bound(int i, int j);
int neighbor_num(int i, int j);
void process();
void print_board();
void write_to_file();

int main(){
     int i, t = 10;
     int randnum = 0;

     printf("Enter board width : ");
     scanf("%d", &maxx);
     printf("Enter board height : ");
     scanf("%d", &maxy);
     printf("Enter number of random population : ");
     scanf("%d", &randnum);
     printf("Enter time step : ");
     scanf("%d", &t);

     pastBoard = board1;
     currentBoard = board2;

     init();
     rand_init_pop(randnum);

     f = fopen("sequential_board.txt", "w");

     for(i=0;i<t;i++){
          fprintf(f, "t = %d\n", i);
          write_to_file();
          process();
     }
     fprintf(f, "t = %d\n", i);
     write_to_file();

     fclose(f);

     return 0;
}
void init(){
     int i, j;
     for(i=0;i<maxy;i++) for(j=0;j<maxx;j++)
          board1[i * maxx + j] = board2[i * maxx + j] = 'O';
}
void rand_init_pop(int rand_size){
     int i, x, y;
     srand( time(0));

     for(i=0;i<rand_size;i++){
          y = rand() % maxy;
          x = rand() % maxx;
          if(pastBoard[y * maxx + x] == 'X') i--;
          else pastBoard[y * maxx + x] = 'X';
     }
}
int in_bound(int i, int j){
     if(i<0 || j=maxy || j>=maxy)    return 0;
     else                                    return 1;
}
int neighbor_num(int i, int j){
     int num = 0;
     if( in_bound(i-1,j-1) && pastBoard[(i-1) * maxx + (j-1)]=='X' ) num++;
     if( in_bound(i-1, j ) && pastBoard[(i-1) * maxx + ( j )]=='X' ) num++;
     if( in_bound( i ,j-1) && pastBoard[( i ) * maxx + (j-1)]=='X' ) num++;
     if( in_bound(i+1,j+1) && pastBoard[(i+1) * maxx + (j+1)]=='X' ) num++;
     if( in_bound(i+1, j ) && pastBoard[(i+1) * maxx + ( j )]=='X' ) num++;
     if( in_bound( i ,j+1) && pastBoard[( i ) * maxx + (j+1)]=='X' ) num++;
     if( in_bound(i+1,j-1) && pastBoard[(i+1) * maxx + (j-1)]=='X' ) num++;
     if( in_bound(i-1,j+1) && pastBoard[(i-1) * maxx + (j+1)]=='X' ) num++;
     return num;
}
void process(){
     int i,j;
     char* tmp;

     for(i=0;i<maxy;i++){
          for(j=0;j<maxx;j++){
               //For a space that is 'populated'
               if(pastBoard[i * maxx + j]=='X'){
                    //Each cell with one or no neighbors dies, as if by loneliness.
                    if(neighbor_num(i,j) <= 1) currentBoard[i * maxx + j] = 'O';
                    //Each cell with two or three neighbors survives.
                    else if(neighbor_num(i,j) <= 3) currentBoard[i * maxx + j] = 'X';
                    // Each cell with four or more neighbors dies, as if by overpopulation.
                    else currentBoard[i * maxx + j] = 'O';
               }
               //For a space that is 'empty' or 'unpopulated'
               else{
                    // Each cell with three neighbors becomes populated.
                    if(neighbor_num(i,j) == 3) currentBoard[i * maxx + j] = 'X';
                    else currentBoard[i * maxx + j] = 'O';
               }
          }
     }
     tmp = pastBoard;
     pastBoard = currentBoard;
     currentBoard = tmp;
}
void write_to_file(){
     int i, j;
     for(i=0;i<maxy;i++){
          for(j=0;j<maxx;j++){
               if(pastBoard[i * maxx + j]=='X')    fprintf(f, "1”);
               else                                fprintf(f, "0”);
          }
          fprintf(f, "\n");
     }
     fprintf(f, "\n");
}

เมื่อเริ่มต้นโปรแกรม โปรแกรมจะให้ใส่ข้อมูลขนาดความกว้าง และความสูงของตารางที่จะใช้ จากนั้นจะถามถึงจำนวน Cell ที่มีชีวิตเริ่มต้นที่ต้องการกำหนด โดยจะมีตำแหน่งแบบสุ่ม และสุดท้ายจะถามถึง จำนวนหน่วยเวลาที่ต้องการทำการ Simulation เมื่อใส่ข้อมูลครบแล้วโปรแกรมจะทำงาน และเขียนข้อมูลของตารางในแต่ละช่วงเวลาไปยังไฟล์ที่ชื่อ “sequential_board.txt”

---

2. การทำงานของโปรแกรม Game of Life บนจีพียู ใน 1 time step จะต้องเข้าถึงหน่วยความจำเฉลี่ยประมาณ 8 ครั้งต่อ 1 เทรด ดังนั้นเพื่อให้มีความรวดเร็วในการทำงาน จะต้องทำการคัดลอดข้อมูลจาก Global Memory มายัง Shared Memory ก่อน เพื่อให้เข้าถึงหน่วยความจำได้เร็วขึ้น โดยวิธีที่ใช้คือการแบ่งการทำงานออกเป็นเทรดบล็อคโดยที่ในตอนเริ่มต้นการทำงาน แต่ละเทรดบล็อคจะต้องคัดลอกข้อมูลในส่วนของ cell ที่มีพื้นที่ติดกันกับพื้นที่ที่เทรดบล็อคนั้นรับผิดชอบมาด้วย แต่ในการเขียนข้อมูลจะเขียนข้อมูลลงใน Global Memory ในช่องที่เทรดบล็อคนั้นรับผิดชอบเท่านั้น

#include <stdio.h>
#include <math.h>
#include <time.h>
#define MAX_WIDTH 500
#define TILE_WIDTH 16
#define TY threadIdx.y
#define TX threadIdx.x

void rand_init_pop(int *board, int maxx, int maxy, int rand_size);
void write_to_file(FILE *f, int *board, int maxx, int maxy);

__global__ void process(int *board, int maxx, int maxy);

int main(){
     int *board, *d_board, i, t;
     int maxx, maxy, size, randnum;
     FILE *f;

     printf("Enter board width : ");
     scanf("%d", &maxx);
     printf("Enter board height : ");
     scanf("%d", &maxy);
     printf("Enter number of random population : ");
     scanf("%d", &randnum);
     printf("Enter time step : ");
     scanf("%d", &t);
     size = sizeof(int) * maxx * maxy;

     f = fopen("cuda_board.txt", "w");

     board = (int*)malloc(size);
     cudaMalloc((void**)&d_board, size);
     rand_init_pop(board, maxx, maxy, randnum);

     dim3 blockDim(TILE_WIDTH+2, TILE_WIDTH+2);
     dim3 gridDim(ceil(maxy*1.0/TILE_WIDTH), ceil(maxx*1.0/TILE_WIDTH));

     cudaMemcpy(d_board, board, size, cudaMemcpyHostToDevice);

     for(i=0;i<t;i++){
          fprintf(f, "t = %d\n", i);
          write_to_file(f, board, maxx, maxy);

          process<<>>(d_board, maxx, maxy);
          cudaMemcpy(board, d_board, size, cudaMemcpyDeviceToHost);
     }
     fprintf(f, "t = %d\n", i);
     write_to_file(f, board, maxx, maxy);

     fclose(f);
     free(board);
     cudaFree(d_board);

     return 0;
}

void init(int *board, int maxx, int maxy){
     int i, j;
     for(i=0;i<maxy;i++) for(j=0;j<maxx;j++)
          board[i * maxx + j] = 0;
}
void rand_init_pop(int *board, int maxx, int maxy, int rand_size){
     int i, x, y;
     srand( time(0));
     init(board, maxx, maxy);

     for(i=0;i<rand_size;i++){
          y = rand() % maxy;
          x = rand() % maxx;
          if(board[y * maxx + x] == 1) i--;
          else board[y * maxx + x] = 1;
     }
}
void write_to_file(FILE *f, int *board, int maxx, int maxy){
     for(int i=0;i<maxy;i++){
          for(int j=0;j<maxx;j++)
               fprintf(f, "%d", board[i * maxx + j]);
          fprintf(f, "\n");
     }
     fprintf(f, "\n");
}

__global__ void process(int *board, int maxx, int maxy){
     __shared__ int sboard[TILE_WIDTH+2][TILE_WIDTH+2];

     int i = (blockIdx.x * TILE_WIDTH) + TX - 1;
     int j = (blockIdx.y * TILE_WIDTH) + TY - 1;

     if(i<=maxy && j=0 && j>=0 && i<maxy && j0 && TX0 && TY<TILE_WIDTH){
          int n = 0;
          n += sboard[TY+1][TX+1];
          n += sboard[TY+1][TX-1];
          n += sboard[TY-1][TX-1];
          n += sboard[TY-1][TX+1];
          n += sboard[TY+1][ TX ];
          n += sboard[ TY ][TX+1];
          n += sboard[ TY ][TX-1];
          n += sboard[TY-1][ TX ];

          if(sboard[TY][TX]==1 && n!=2 && n!=3)
               board[boardidx] = 0;
          else if(sboard[TY][TX]==0 && n==3)
               board[boardidx] = 1;
          }
     }
}

เมื่อรันโปรแกรม โปรแกรมจะถามข้อมูลเช่นเดียวกับโปรแกรม Sequential แต่ข้อมูลจะเขียนลงไปที่ไฟล์ที่มีชื่อว่า “cuda_board.txt”

สามารถดาวน์โหลดไฟล์โปรแกรมได้ที่ด้านล่าง
GameOfLife.c
GameOfLifeCUDA.cu