Assignment 5 (CS427) – Game of Life
ข้อกำหนดของโปรแกรม
- จำนวนโปรเซสทั้งหมดจะต้องมีจำนวนเท่ากับ (N/K)^2 + 1
- ค่าของความกว้างของบอร์ด(N) และขนาดของTile(K) จะต้องมีค่าอย่างน้อย 1 และ ค่าของ N จะต้องหารด้วย k ลงตัวเสมอ
- ค่าการสุ่มความน่าจะเป็นในการมีชีวิตของแต่ละเซลจะต้องมีค่าอยู่ระหว่าง [0, 100] เท่านั้น
การคอมไพล์โปรแกรมและการใช้งาน
- คอมไพล์โปรแกรมด้วยคำสั่ง mpicc -o Game_of_Life Game_of_Life.c จะได้ไฟล์โปรแกรมชื่อ Game_of_Life
- รันโปรแกรมด้วยคำสั่ง mpirun –np processnum Game_of_Life โดยจะต้องกำหนดจำนวนโปรเซสให้ถูกต้องตามข้อกำหนด
- โปรแกรมจะถามถึงค่าของ ความกว้างของบอร์ด(N) ขนาดของTile(K) จำนวนหน่วยเวลา(t) ต้องการอ่านค่าเริ่มต้นจากไฟล์หรือสุ่มจากโปรแกรม ถ้าเลือกอ่านค่าจากไฟล์จะต้องกำหนดชื่อไฟล์ด้วย หากเลือกสุ่มจากโปรแกรมจะต้องกำหนดค่าความน่าจะเป็นในการที่แต่ละช่องจะมีชีวิตด้วย และ ต้องการเซฟไฟล์ Immediate หรือไม่ ซึ่งจะต้องกรอกให้สอดคล้องกับจำนวนโปรเซสที่กำหนดไว้ หากข้อมูลที่กรอกไม่สอดคล้องหรือไม่ถูกต้องได้แก่
- ค่า N หรือ k ไม่ใช่เลขจำนวนเต็มบวก
- N หาร k ได้ไม่ลงตัว
- จำนวนโปรเซสไม่ถูกต้อง
- ไม่พบไฟล์ที่ต้องการอ่าน
เมื่อพบเงื่อนไขดังกล่าวโปรแกรมจะจบการทันงานโดนทันที ซึ่งจะต้องเริ่มทำการรันโปรแกรมใหม่
การออกแบบโปรแกรมและขั้นตอนการทำงาน
การทำงานของโปรแกรมจะใช้จำนวนโปรเซสเท่ากับจำนวนของ Tile ทั้งหมดบวกด้วย 1 เนื่องจากจะใช้โปรเซส 0 ในการติดต่อกับผู้ใช้ เขียนข้อมูลลงไฟล์ สุ่มค่าเริ่มต้น และใช้โปรเซสที่เหลือทั้งหมดในการคำนวนค่าของแต่ละ Tile ที่ได้รับมอบหมาย
1. โปรเซส 0 จะจองพื้นที่บอร์ดขนาด N x N เพื่อรับข้อมูลจากไฟล์หรือสุ่มขึ้น ส่วนโปรเซสอื่นทั้งหมดจะทำการจองบอร์ดย่อยขนาด (K + 2) x (K + 2) ซึ่งจะสร้างขอบเพิ่มให้กับแต่ละ Tile ในทุกด้านเพื่อใช้ในการคำนวน โดยบอร์ดย่อยที่สร้างขึ้นจะสร้างขึ้นเป็นจำนวน 2 บอร์ดเพื่อใช้ในการคำนวน จากนั้นส่งค่าของ N, k, t ไปยังทุกโปรเซสด้วยคำสั่ง MPI_Bcast()
2. จากนั้นโปรเซส 0 จะแบ่งบอร์ดเป็น Tile และส่งไปให้แต่ละโปรเซสเรียงตามลำดับจากซ้ายไปทางขวาและขึ้นแถวใหม่จนครบดังภาพที่ 1
3. โปรเซสอื่นทั้งหมดจะรับมาเก็บไว้ที่ตรงกลางของบอร์ดย่อยที่มีความยาวมากกว่าขนาดของ Tile อยู่ 2 ดังภาพที่ 2
4. ส่งข้อมูลระหว่างแต่ละโปรเซสเพื่อคำนวนเวลาถัดไปของแต่ละ Tile ด้วยการตรวจสอบว่าแต่ละโปรเซสจะต้องส่งค่าไปยังโปรเซสใดบ้าง และรับค่ามาจากโปรเซสที่ส่งค่าไปหาเสมอ
- โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบบนและไม่ได้อยู่ขอบซ้าย ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านซ้ายบน ดังลูกศรสีแดงในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)%c != 0 && (rank-1)/c > 0 โดยจะส่งเฉพาะข้อมูลที่อยู่ในแถวที่สองและหลักที่สองจำนวน 1 ค่าเท่านั้น ดังภาพที่ 4
- โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบล่างและไม่ได้อยู่ขอบขวา ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านขวาล่าง ดังลูกศรสีเหลืองในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข rank%c != 0 && (rank-1)/c < c-1 โดยจะส่งเฉพาะข้อมูลที่อยู่ในแถวรองสุดท้ายและหลักรองสุดท้ายจำนวน 1 ค่าเท่านั้น ดังภาพที่ 4
- โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบบน ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านบน ดังลูกศรสีส้มในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)/c > 0 โดยจะส่งเฉพาะข้อมูลในแถวที่สอง ตั้งแต่หลักที่สองจนถึงหลักรองสุดท้ายรวมทั้งสิ้น k ค่า ดังภาพที่ 5
- โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบล่าง ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านล่าง ดังลูกศรสีม่วงในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)/c < c-1 โดยจะส่งเฉพาะข้อมูลในแถวรองสุดท้าย ตั้งแต่หลักที่สองจนถึงหลักรองสุดท้ายรวมทั้งสิ้น k ค่า ดังภาพที่ 5
- โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบบนและไม่ได้อยู่ขอบขวา ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านขวาบน ดังลูกศรสีเขียวในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)/c > 0 && rank%c !=0 โดยจะส่งเฉพาะข้อมูลที่อยู่ในแถวที่สองและหลักรองสุดท้ายจำนวน 1 ค่าเท่านั้น ดังภาพที่ 6
- โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบล่างและไม่ได้อยู่ขอบซ้าย ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านซ้ายล่าง ดังลูกศรสีน้ำเงินในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)/c < c-1 && (rank-1)%c != 0 โดยจะส่งเฉพาะข้อมูลที่อยู่ในแถวรองสุดท้ายและหลักที่สองจำนวน 1 ค่าเท่านั้น ดังภาพที่ 6
- โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบขวา ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านขวา ดังลูกศรสีฟ้าในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข rank%c !=0 โดยจะส่งเฉพาะข้อมูลในหลักรองสุดท้าย ตั้งแต่แถวที่สองจนถึงแถวรองสุดท้ายรวมทั้งสิ้น k ค่า ดังภาพที่ 7
- โปรเซสที่มี Tile ที่ไม่ได้อยู่ขอบซ้าย ให้ส่งและรับข้อมูลจากโปรเซสที่มี Tile อยู่ด้านซ้าย ดังลูกศรสีดำในภาพที่ 3 โดยคำนวนจากโปรเซสที่ตรงกับเงื่อนไข (rank-1)%c != 0 โดยจะส่งเฉพาะข้อมูลในหลักที่สอง ตั้งแต่แถวที่สองจนถึงแถวรองสุดท้ายรวมทั้งสิ้น k ค่า ดังภาพที่ 7
หมายเหตุ: rank เป็นหมายเลขของโปรเซส, c เป็นจำนวนเต็มบวกที่ได้มาจาก N/k
ภาพที่ 4 | ภาพที่ 5 |
ภาพที่ 6 | ภาพที่ 7 |
MPI Defined Type ที่ใช้
MPI_Subboard_type : บอร์ดย่อยที่ได้จากการแบ่งเป็น Tile ของบอร์ดใหญ่เพื่อส่งจากโปรเซส 0 ไปยังโปรเซสอื่น
MPI_Type_vector(K, K, N, MPI_INT, &MPI_Subboard_type);
MPI_Subboard_type2 : บอร์ดย่อยที่ใช้ในการประมวลผลของแต่ละโปรเซส และรับส่งบอร์ดย่อยกับโปรเซส 0
MPI_Type_vector(K, K, K+2, MPI_INT, &MPI_Subboard_type2);
MPI_Boardrow_type : แถวของบอร์ดย่อยที่ใช้ในการส่งระหว่าง Tile ที่อยู่ด้านล่างและบน
MPI_Type_contiguous(K, MPI_INT, &MPI_Boardrow_type);
MPI_Boardcol_type : หลักของบอร์ดย่อยที่ใช้ในการส่งข้อมูลระหว่าง Tile ที่อยู่ด้านซ้ายและขวา
MPI_Type_vector(K, 1, K+2, MPI_INT, &MPI_Boardcol_type);
ตัวอย่างการใช้งานแบบอ่านค่าจากไฟล์
$ mpirun –np 5 Game_of_Life
Enter board size (N): 6
Enter tile size (K): 3
Enter time step (t): 2
Do you want to save immediate file (yes/no): yes
Read board from file (yes/no – if no board is initialize by random): yes
Enter input file name : inputboard2.txt
inputboard2.txt | Board.Immediate | Board.output |
XX-XX- —XXX —-XX X-X-X- -X-X-X XXX— |
t = 0 XX-XX- —XXX —-XX X-X-X- -X-X-X XXX—t = 1 –XX-X –X— —— -XX— —XX- XXX—t = 2 –XX– –XX– -XX— –XX– X–X– -XXX– |
–XX– –XX– -XX— –XX– X–X– -XXX– |
ตัวอย่างการใช้งานแบบสุ่มความน่าจะเป็นของการมีชีวิต
$ mpirun –np 5 Game_of_Life
Enter board size (N): 6
Enter tile size (K): 3
Enter time step (t): 8
Do you want to save immediate file (yes/no): no
Read board from file (yes/no – if no board is initialize by random): no
Random life cell probability (0-100): 60
RandomBoard.input | Board.output |
X-XX-X -X–XX -X—X XX-XXX –XXX- XX-X-X |
—— —— —— -XX— X–X– -XX— |
ดาวน์โหลด : ซอร์สโค้ด, ตัวอย่าง input 1, ตัวอย่าง input 2
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