Part 1: Design and implement a multithreaded version of the Game of Life program(developed in Homework-1)using OpenMP. The program must takethe problem size, maximum number of iterations, and number of threads as command-line arguments. Make sure the program checks if there isa change in the board state between iterations. The program must create a parallel regiononly once, i.e.,you should not create a new thread during each iteration.

/* Name: BlazerId: Course Section: Homework #:

Instructions to run the program in terminal (Ubuntu) sudo g++ filename.cpp ./a.out arg1 arg2

*/ #include #include using namespace std; #define FIO \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0)

double gettime(void) { struct timeval tval;

gettimeofday(&tval, NULL);

return ((double)tval.tv_sec + (double)tval.tv_usec / 1000000.0); }

int **allocarray(int P, int Q) { int i; int *p, **a;

p = (int *)malloc(P * Q * sizeof(int)); a = (int **)malloc(P * sizeof(int *));

if (p == NULL || a == NULL) printf("Error allocating memory ");

/* for row major storage */ for (i = 0; i < P; i++) a[i] = &p[i * Q];

return a; }

int **initarray(int **a, int mrows, int ncols, int value) { int i, j;

for (i = 1; i < mrows - 1; i++) { for (j = 1; j < ncols - 1; j++) { // assigning value either 0(dead) or 1(alive) a[i][j] = (rand()) % 2; } }

return a; }

void printarray(int **a, int mrows, int ncols) { int i, j;

for (i = 0; i < mrows; i++) { for (j = 0; j < ncols; j++) printf("%d ", a[i][j]); printf(" "); } } int adj_neighbors(int **board, int i, int j) { int count = 0; int arr[] = {i, i, i + 1, i + 1, i + 1, i - 1, i - 1, i - 1}; int arr1[] = {j - 1, j + 1, j, j + 1, j - 1, j, j + 1, j - 1};

for (int r = 0; r < 8; r++) { if (arr[r] != -1 && arr1[r] != -1) { if (board[arr[r]][arr1[r]] == 1) count++; } }

return count; } void playGame(int **cur_board, int **prev_board, int mrows, int ncols) { /* 1. If a cell is alive in the current generation, then depending on its neighbors state, in the next generation the cell will either live or die based on the following conditions: o Each cell with one or no neighbor dies, as if by loneliness. o Each cell with four or more neighbors dies, as if by overpopulation. o Each cell with two or three neighbors survives. 2. If a cell is dead in the current generation, then if there are exactly three neighbors "alive" then it will change to the "alive" state in the next generation, as if the neighboring cells gave birth to a new organism.

"""In my case I assumed 0 as dead, 1 as alive""" */ int i, j; int adj; for (i = 1; i < mrows - 1; i++) { for (j = 1; j < ncols - 1; j++) { adj = adj_neighbors(prev_board, i, j); if (prev_board[i][j] == 1 && (adj <= 1 || adj >= 4)) cur_board[i][j] = 0; else if (prev_board[i][j] == 1 && (adj == 2 || adj == 3)) cur_board[i][j] = 1;

if (prev_board[i][j] == 0 && adj == 3) cur_board[i][j] = 1; } }

for (i = 1; i < mrows - 1; i++) { for (j = 1; j < ncols - 1; j++) { prev_board[i][j] = cur_board[i][j]; } } } int main(int argc, char **argv) { FIO; int N, generations; double startTime, endTime; int **cur_board = NULL, **prev_board = NULL;

if (argc != 3) { printf("Usage: %s ", argv[0]); exit(-1); }

N = atoi(argv[1]); generations = atoi(argv[2]);

// Memory allocation for arrays cur_board = allocarray(N + 2, N + 2); prev_board = allocarray(N + 2, N + 2);

// Array Initialization cur_board = initarray(cur_board, N + 2, N + 2, 0); prev_board = initarray(prev_board, N + 2, N + 2, 0);

startTime = gettime(); for (int i = 0; i < generations; i++) { printf("%d Generation ", i); printarray(cur_board, N + 2, N + 2); playGame(cur_board, prev_board, N + 2, N + 2); } endTime = gettime(); free(cur_board); free(prev_board); printf("Time taken = %lf seconds ", endTime - startTime); }

Part 2: Write a C++ program to implement a two-dimensional data distribution using OpenMP and measure the performance for the following grid sizes(thread mappings): 1x16, 2X8, 4X4, 8X2, and 16X1. Analyze the performance across different grid sizes (thread mappings) and include this analysis in the report. Note that the grid sizeof16X1 is equivalent to using 16 threads with the one-dimensional data distribution implemented in Part #1.