t2.c

/*
* The Game of Life
*
* a cell is born, if it has exactly three neighbours
* a cell dies of loneliness, if it has less than two neighbours
* a cell dies of overcrowding, if it has more than three neighbours
* a cell survives to the next generation, if it does not die of loneliness
* or overcrowding
*
* In this version, a 2D array of ints is used.  A 1 cell is on, a 0 cell is off.
* The game plays a number of steps (given by the input), printing to the screen each time.  'x' printed
* means on, space means off.
*
*/
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/sysinfo.h>
#include <unistd.h>
#include <mpi.h>

typedef unsigned char cell_t;

/* ------------------------------------------------------------------------- */

cell_t ** allocate_board (int size) {
  cell_t ** board = (cell_t **) malloc(sizeof(cell_t*)*size);
  int   i;
  for (i=0; i<size; i++)
  board[i] = (cell_t *) malloc(sizeof(cell_t)*size);
  return board;
}

/* ------------------------------------------------------------------------- */

void free_board (cell_t ** board, int size) {
  int     i;
  for (i=0; i<size; i++)
  free(board[i]);
  free(board);
}

/* ------------------------------------------------------------------------- */

/* return the number of on cells adjacent to the i,j cell */
 int adjacent_to (cell_t ** board, int size, int i, int j) {
  int count = 0;
  count+=board[i-1][j-1];
  count+=board[i-1][j];
  count+=board[i-1][j+1];
  count+=board[i][j-1];
  count+=board[i][j+1];
  count+=board[i+1][j-1];
  count+=board[i+1][j];
  count+=board[i+1][j+1];
  return count;
}

/* ------------------------------------------------------------------------- */

/* print the life board */
void print (cell_t ** board, int size) {
  int   i, j;
  /* for each row */
  for (j=1; j<size+1; j++) {
    /* print each column position... */
    for (i=1; i<size+1; i++)
      if(board[i][j]){
          printf ("■ ");
      } else {
        printf ("  ");
      }
    /* followed by a carriage return */
    printf ("\n");
  }
}

/* ------------------------------------------------------------------------- */

/* read a file into the life board */
void read_file (FILE * f, cell_t ** board, int size) {
  int   i, j;
  char  *s = (char *) malloc(size+10);

  /* read the first new line (it will be ignored) */
  fgets (s, size+10,f);

  /* read the life board */
  for (j=0; j<size; j++) {
    /* get a string */
    fgets (s, size+10,f);
    /* copy the string to the life board */
    for (i=0; i<size; i++)
    board[i+1][j+1] = s[i] == 'x';
  }
  for (i=0; j<size+2; i++) {
    board[0][j] = 0;
    board[j][size+1] = 0;
    board[size+1][j] = 0;
    board[j][size+1] = 0;
  }

}

void fill_board(cell_t ** board, int size, int percentage_alive) {
  int   i, j;
  srand(time(NULL));
  for (j=1; j<size+1; j++) {
    for (i=1; i<size+1; i++){
        board[i][j] = ((int)(rand()) %percentage_alive == 0? 1 : 0 );
    }
  }
}


 void get_next_state(cell_t** board, cell_t** newboard, int a, int i, int j){
  if (a == 2) {
    newboard[i][j] = board[i][j];
  } else if (a == 3) {
    newboard[i][j] = 1 ;
  } else {
    newboard[i][j] = 0;
  }
}

/* ------------------------------------------------------------------------- */

int main(int argc, char**argv){
int size, steps;
  cell_t ** board;
  cell_t ** newboard;
  //if (argc<2 || atoi(argv[1])){
    FILE    *f;
    f = stdin;
    fscanf(f,"%d %d", &size, &steps);
    board = allocate_board (size+2);
    read_file (f, board,size);
    fclose(f);
    newboard = allocate_board (size+2);
  /*} else {
    steps = 1000;
    size = 1000;
    board = allocate_board (size+2);
    newboard = allocate_board (size+2);
    fill_board(board, size, 32);
  }
  /**/
  cell_t ** tmp;
  int i;
  #ifdef DEBUG
    printf("Initial:\n");
    //print(board,size);
  #endif
   printf ("You have %d processors.\n", get_nprocs());
  int nthreads = atoi(argv[1]);

  MPI_Init(&argc, &argv);
  //cria os processos
  // for (int j = 0; j<nthreads; j++) {
  //   if (fork() == 0){//se for um processo novo nao cria outros, quem faz isso é o principal
  //     break;
  //   }
  // }

  int rank;
  MPI_Comm_rank( MPI_COMM_WORLD, &rank);
  //como o  rank 0 é o processo principal, os ranks começam do 1 o thread_number é o rank-1
  int thread_number = rank-1;
  //se for o processo inicial, não faz os calculos, apenas aguarda finalizarem
  if (thread_number != 0){
    for (i=0; i<steps; i++) {
      int i, j;
      /* for each cell, apply the rules of Life */
      int maxi = (int)(size/(double)nthreads*(thread_number+1));
      int mini = (int)(size/(double)nthreads*thread_number);
      for (int k=0; k<steps; k++) {
        // calcula a primeira e ultima linhas
        for (j= 1; j<size+1; j++) {
          get_next_state(board, newboard, adjacent_to(board, size, mini+1, j), mini+1, j);
          get_next_state(board, newboard, adjacent_to(board, size, maxi+1, j), maxi+1, j);
        }
        // se não for a primeira seção, manda a primeira linha para o proc anterior
        if (rank > 1){
          MPI_Send(newboard[mini], size, MPI_CHAR, rank - 1, 0, MPI_COMM_WORLD);
        }
        if (rank < nthreads){
          MPI_Send(newboard[maxi], size, MPI_CHAR, rank + 1, 0, MPI_COMM_WORLD);
        }
        //calcula o resto
        for (i = mini+1 + 1; i<maxi+1-1; ++i) {
          for (j= 1; j<size+1; j++) {
            get_next_state(board, newboard, adjacent_to(board, size, i, j), i, j);
          }
        }
        // recebe as novas linhas calculadas pelo outro processo
        if (rank > 1){
          MPI_Recv(newboard[mini], size, MPI_CHAR, rank-1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        }
        if (rank < nthreads){
          MPI_Recv(newboard[maxi+2], size, MPI_CHAR, rank+1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        }
        tmp = newboard;
        newboard = board;
        board = tmp;
      }

      //manda suas linhas para o processo principal
      for (int i = mini+1; i<maxi+1; ++i) {
        //usando i como tag para receber na ordem certa
        MPI_Send(newboard[i], size, MPI_CHAR, 0, i, MPI_COMM_WORLD);
      }
    }
  } else {
    //recebe os valores finais dos processos
    for (int i = 1; i<size+1; ++i) {
      MPI_Recv(newboard[i], size, MPI_CHAR, MPI_ANY_SOURCE, i, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    }
      #ifdef RESULT
        printf("Final:\n");
        //print (board,size);
      #endif
  }
  free_board(newboard,size);
  free_board(board,size);
  MPI_Finalize();
}