hw4.c

#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
#include "mkl.h"
#include <math.h>

#define DEBUG
#define N 500

char**
buildGliderGun(char **mat)
{
	mat[6][2] = 1;
	mat[7][2] = 1;
	mat[6][3] = 1;
	mat[7][3] = 1;
	mat[6][12] = 1;
  	mat[7][12] = 1;
    mat[8][12] = 1;
	mat[5][13] = 1;
	mat[9][13] = 1;
	mat[4][14] = 1;
	mat[10][14] = 1;
	mat[4][15] = 1;
	mat[10][15] = 1;
	mat[7][16] = 1;
	mat[5][17] = 1;
	mat[9][17] = 1;
	mat[6][18] = 1;
	mat[7][18] = 1;
	mat[8][18] = 1;
	mat[7][19] = 1;
	mat[6][22] = 1;
  	mat[5][22] = 1;
    mat[4][22] = 1;
	mat[6][23] = 1;
	mat[5][23] = 1;
	mat[4][23] = 1;
	mat[3][24] = 1;
	mat[7][24] = 1;
	mat[3][26] = 1;
	mat[7][26] = 1;
	mat[2][26] = 1;
	mat[8][26] = 1;
	mat[4][36] = 1;
	mat[5][36] = 1;
	mat[4][37] = 1;
	mat[5][37] = 1;

	return mat;
}

int
length(int *arr)
{
	if(!arr) return 0;
	int i;
	for(i=0;arr[i]!=-1;i++);
	return i;
}

int*
append(int *arr, int arg)
{
	if(!arr)
	{
		arr = malloc(sizeof(int)*2);
		arr[0] = arg;
		arr[1] = -1;
	}
	else
	{
		int len = length(arr);
		arr = (int*) realloc(arr, (len+2) * sizeof(int));
		arr[len] = arg;
		arr[len+1] = -1;
	}
	
	return arr;
}

#ifdef DEBUG
void 
printUpLeft(char **mat, int turn)
{
	int i,j;
	if(!(turn%10))
	{
		printf("================\n");
		for(i=0;i<50;i++)
		{
			for(j=0;j<50;j++)
			{
				if(mat[i][j]) printf("|");
				else printf("_");
				}
			printf("\n");
			}
	}
}
#endif

int 
main(int argc, char **argv)
{
	int rank, size, i, j, k, m, n, turn;
	int sqrtSize, portionEdge, localResult=0;
	int globalResult1, globalResult2, globalResult3;
	char **mat;
	const int FIRST_STEP = 400, SECOND_STEP = 800, THIRD_STEP = 1600;
	float t0, t1;

	MPI_Init( &argc, &argv );
	MPI_Comm_size( MPI_COMM_WORLD, &size );
	MPI_Comm_rank( MPI_COMM_WORLD, &rank );

	/* Edge length of matrix, in terms of process count */
	sqrtSize = (int) sqrt(size);

	/* Edge length of one portion */
	portionEdge = (int) N / sqrtSize;
	
	mat = malloc(portionEdge*sizeof(char*));
	for(i=0; i<portionEdge; i++)
	{
		mat[i] = calloc(portionEdge,sizeof(char));
	}
	if(!rank)
	{
		mat = buildGliderGun(mat);
		t0 = MPI_Wtime();
	}

	int rowIndex = (int) rank / sqrtSize;
	int columnIndex = rank % (int) sqrtSize;

	int lol = 0;
	for(i=0;i<portionEdge;i++)for(j=0;j<portionEdge;j++)lol+=mat[i][j];
	
	for(turn=0; turn<THIRD_STEP; turn++)
	{
		int *rowsToFlip=NULL, *columnsToFlip=NULL;

		int aboveProcess = rowIndex != 0 ? rank-sqrtSize : -1;
		int belowProcess = rowIndex != sqrtSize-1 ? rank+sqrtSize : -1;
		int leftProcess = columnIndex != 0 ? rank-1 : -1;
		int rightProcess = columnIndex != sqrtSize-1 ? rank+1 : -1;
		int upLeftProcess = (aboveProcess !=-1) && (leftProcess != -1) ? aboveProcess-1 : -1;
		int upRightProcess = (aboveProcess !=-1) && (rightProcess != -1) ? aboveProcess+1 : -1;
		int downLeftProcess = (belowProcess !=-1) && (leftProcess != -1) ? belowProcess-1 : -1;
		int downRightProcess = (belowProcess !=-1) && (rightProcess != -1) ? belowProcess+1 : -1;

		//printf("rank%d: sending\n",rank);
		if(aboveProcess != -1) MPI_Send(mat[0],portionEdge,MPI_CHAR,aboveProcess,0,MPI_COMM_WORLD);
		if(belowProcess != -1) MPI_Send(mat[portionEdge-1],portionEdge,MPI_CHAR,belowProcess,0,MPI_COMM_WORLD);
		if(leftProcess != -1)
		{
			char *buffer = malloc(portionEdge*sizeof(char));
			for(i=0; i<portionEdge; i++)
			{
				buffer[i] = mat[i][0];
			}
			MPI_Send(buffer,portionEdge,MPI_CHAR,leftProcess,0,MPI_COMM_WORLD);
		}
		if(rightProcess != -1)
		{
			char *buffer = malloc(portionEdge*sizeof(char));
			for(i=0; i<portionEdge; i++)
			{
				buffer[i] = mat[i][portionEdge-1];
			}
			MPI_Send(buffer,portionEdge,MPI_CHAR,rightProcess,0,MPI_COMM_WORLD);
		}
		if(upLeftProcess != -1) MPI_Send(&(mat[0][0]),1,MPI_CHAR,upLeftProcess,0,MPI_COMM_WORLD);
		if(upRightProcess != -1) MPI_Send(&(mat[0][portionEdge-1]),1,MPI_CHAR,upRightProcess,0,MPI_COMM_WORLD);
		if(downLeftProcess != -1) MPI_Send(&(mat[portionEdge-1][0]),1,MPI_CHAR,downLeftProcess,0,MPI_COMM_WORLD);
		if(downRightProcess != -1) MPI_Send(&(mat[portionEdge-1][portionEdge-1]),1,MPI_CHAR,downRightProcess,0,MPI_COMM_WORLD);
		
		
		//printf("rank%d: receiving\n",rank);
		char *aboveRow=NULL, *belowRow=NULL, *leftColumn=NULL, *rightColumn=NULL;
		int upLeftCell, upRightCell, downLeftCell, downRightCell;

		if(aboveProcess != -1)
		{
			aboveRow = malloc(portionEdge*sizeof(char));
			MPI_Recv(aboveRow,portionEdge,MPI_CHAR,aboveProcess,0,MPI_COMM_WORLD, NULL);
		}
		if(belowProcess != -1)
		{
			belowRow = malloc(portionEdge*sizeof(char));
			MPI_Recv(belowRow,portionEdge,MPI_CHAR,belowProcess,0,MPI_COMM_WORLD, NULL);
		}
		if(leftProcess != -1)
		{
			leftColumn = malloc(portionEdge*sizeof(char));
			MPI_Recv(leftColumn,portionEdge,MPI_CHAR,leftProcess,0,MPI_COMM_WORLD, NULL);
		}
		if(rightProcess != -1)
		{
			rightColumn = malloc(portionEdge*sizeof(char));
			MPI_Recv(rightColumn,portionEdge,MPI_CHAR,rightProcess,0,MPI_COMM_WORLD, NULL);
		}
		if(upLeftProcess != -1) MPI_Recv(&upLeftCell,1,MPI_CHAR,upLeftProcess,0,MPI_COMM_WORLD,NULL);
		if(upRightProcess != -1) MPI_Recv(&upRightCell,1,MPI_CHAR,upRightProcess,0,MPI_COMM_WORLD,NULL);
		if(downLeftProcess != -1) MPI_Recv(&downLeftCell,1,MPI_CHAR,downLeftProcess,0,MPI_COMM_WORLD,NULL);
		if(downRightProcess != -1) MPI_Recv(&downRightCell,1,MPI_CHAR,downRightProcess,0,MPI_COMM_WORLD,NULL);

		//printf("rank%d: checking cells\n",rank);
		for(i=0; i<portionEdge; i++)
		{
			for(j=0; j<portionEdge; j++)
			{
				int aliveNeighbors = 0;

				if(!i)
				{
					if(!j)
					{
						if(upLeftProcess != -1) aliveNeighbors += upLeftCell;
						if(aboveProcess != -1) aliveNeighbors += aboveRow[0] + aboveRow[1];
						aliveNeighbors += mat[0][1] + mat[1][0] + mat[1][1];				
					}
					else if(j==portionEdge-1)
					{
						if(upRightProcess != -1) aliveNeighbors += upRightCell;
						if(aboveProcess != -1) aliveNeighbors += aboveRow[portionEdge-1] + aboveRow[portionEdge-2];
						aliveNeighbors += mat[0][portionEdge-2] + mat[1][portionEdge-2] + mat[1][portionEdge-1];
					}
					else
					{
						if(aboveProcess != -1) aliveNeighbors += aboveRow[j-1] + aboveRow[j] + aboveRow[j+1];
						aliveNeighbors += mat[0][j-1] + mat[0][j+1] 
										+ mat[1][j-1] + mat[1][j] + mat[1][j+1];
					}
				}
				else if(i==portionEdge-1)
				{
					if(!j)
					{
						if(downLeftProcess != -1) aliveNeighbors += downLeftCell;
						if(belowProcess != -1) aliveNeighbors += belowRow[0] + belowRow[1];
						aliveNeighbors += mat[portionEdge-2][0] + mat[portionEdge-2][1] + mat[portionEdge-1][1];
					}
					else if(j==portionEdge-1)
					{
						if(downRightProcess != -1) aliveNeighbors += downRightCell;
						if(belowProcess != -1) aliveNeighbors += belowRow[portionEdge-1] + belowRow[portionEdge-2];
						aliveNeighbors += mat[portionEdge-2][portionEdge-1]
										+ mat[portionEdge-2][portionEdge-2] + mat[portionEdge-1][portionEdge-2];
					}
					else
					{
						if(belowProcess != -1) aliveNeighbors += belowRow[j-1] + belowRow[j] + belowRow[j+1]; 
						aliveNeighbors += mat[portionEdge-1][j-1] + mat[portionEdge-1][j+1]
										+ mat[portionEdge-2][j-1] + mat[portionEdge-2][j] + mat[portionEdge-2][j+1];
					}
				}
				else if(!j)
				{
					if(leftProcess != -1) aliveNeighbors += leftColumn[i-1] + leftColumn[i] + leftColumn[i+1];
					aliveNeighbors += mat[i-1][0] + mat[i+1][0]
									+ mat[i-1][1] + mat[i][1] + mat[i+1][1];
				}
				else if(j==portionEdge-1)
				{
					if(rightProcess != -1) aliveNeighbors += rightColumn[i-1] + rightColumn[i] + rightColumn[i+1];
					aliveNeighbors += mat[i-1][portionEdge-1] + mat[i+1][portionEdge-1]
									+ mat[i-1][portionEdge-2] + mat[i][portionEdge-2] + mat[i][portionEdge-2];
				}
				else
				{
					aliveNeighbors +=
					mat[i-1][j-1] + mat[i-1][j] + mat[i-1][j+1] +
					mat[i][j-1] + mat[i][j+1] +
					mat[i+1][j-1] + mat[i+1][j] + mat[i+1][j+1];
				}

				if(mat[i][j])
				{
					if(aliveNeighbors < 2 || aliveNeighbors > 3)
					{
						rowsToFlip = append(rowsToFlip, i);
						columnsToFlip = append(columnsToFlip, j);
					}
				}
				else
				{
					if(aliveNeighbors == 3)
					{
						rowsToFlip = append(rowsToFlip, i);
						columnsToFlip = append(columnsToFlip, j);
					}
				}
			}
		}
		if(rowsToFlip)
		{
			int len = length(rowsToFlip);

			for(i=0; i<len; i++)
			{
				mat[rowsToFlip[i]][columnsToFlip[i]] = !mat[rowsToFlip[i]][columnsToFlip[i]];
			}

			free(rowsToFlip);
			free(columnsToFlip);

		}
		if(turn == FIRST_STEP-1)
		{
			for(i=0; i<portionEdge; i++)
			{
				for(j=0; j<portionEdge; j++)
				{
					localResult += mat[i][j];
				}
			}	
			MPI_Reduce(&localResult,&globalResult1,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
			if(!rank)
			{
				t1 = MPI_Wtime();
				printf("%d %f\n",globalResult1, t1-t0);
			}
		}
		if(turn == SECOND_STEP-1)
		{
			for(i=0; i<portionEdge; i++)
			{
				for(j=0; j<portionEdge; j++)
				{
					localResult += mat[i][j];
				}
			}	
			MPI_Reduce(&localResult,&globalResult2,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
			if(!rank)
			{
				t1 = MPI_Wtime();
				printf("%d %f\n",globalResult2, t1-t0);
			}
		}
		if(turn == THIRD_STEP-1)
		{
			for(i=0; i<portionEdge; i++)
			{
				for(j=0; j<portionEdge; j++)
				{
					localResult += mat[i][j];
				}
			}	
			MPI_Reduce(&localResult,&globalResult3,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
			if(!rank)
			{
				t1 = MPI_Wtime();
				printf("%d %f\n",globalResult3, t1-t0);
			}
		}
	}

	MPI_Finalize();
    return 0;
}