Difference between revisions of "Game of Life in C and MPI"

From dftwiki3
Jump to: navigation, search
m (Thiebaut moved page Game of Life in C to Game of Life in C and MPI)
(→‎Source)
 
(8 intermediate revisions by the same user not shown)
Line 4: Line 4:
 
=Serial Game of Life=
 
=Serial Game of Life=
 
<br />
 
<br />
 +
==Source, Version 1==
 
::<source lang="C">
 
::<source lang="C">
 
/*   
 
/*   
Line 26: Line 27:
 
*/
 
*/
 
#include <stdio.h>
 
#include <stdio.h>
−
#include <strings.h>
+
#include <string.h>
 
#include <stdlib.h>
 
#include <stdlib.h>
 
#include <time.h>
 
#include <time.h>
Line 104: Line 105:
 
   */
 
   */
  
 +
  char ANSI_CLS[] = "\x1b[2J";
 +
  char ANSI_HOME[] = "\x1b[H";
 +
  printf( "%s%s", ANSI_HOME, ANSI_CLS );
 +
 +
}
 +
 +
// --------------------------------------------------------------------------
 +
// print
 +
void print( char* dish[] ) {
 +
  /*
 +
  * just display all the lines of the array of strings.
 +
  */
 +
  int i;
 +
 +
  for (i=0; i<NUMBERROWS; i++ ) {
 +
    pos( i, 0 );
 +
    printf( "%s\n", dish[i] );
 +
  }
 +
 +
}
 +
 +
 +
// --------------------------------------------------------------------------
 +
void  life( char** dish, char** newGen ) {
 +
  /*
 +
  * Given an array of string representing the current population of cells
 +
  * in a petri dish, computes the new generation of cells according to
 +
  * the rules of the game. A new array of strings is returned.
 +
  */
 +
  int i, j, row;
 +
  int rowLength = strlen( dish[0] );
 +
  int dishLength = NUMBERROWS;
 +
 +
  for (row = 0; row < NUMBERROWS; row++) {// each row
 +
 +
    for ( i = 0; i < rowLength; i++) { // each char in the
 +
                                      // row
 +
 +
      int r, j, neighbors = 0;
 +
      char current = dish[row][i];
 +
 +
      // loop in a block that is 3x3 around the current cell
 +
      // and count the number of '#' cells.
 +
      for ( r = row - 1; r <= row + 1; r++) {
 +
 +
        // make sure we wrap around from bottom to top
 +
        int realr = r;
 +
        if (r == -1)
 +
          realr = dishLength - 1;
 +
        if (r == dishLength)
 +
          realr = 0;
 +
 +
        for ( j = i - 1; j <= i + 1; j++) {
 +
 +
          // make sure we wrap around from left to right
 +
          int realj = j;
 +
          if (j == -1)
 +
            realj = rowLength - 1;
 +
          if (j == rowLength)
 +
            realj = 0;
 +
 +
          if (r == row && j == i)
 +
            continue; // current cell is not its
 +
          // neighbor
 +
          if (dish[realr][realj] == '#')
 +
            neighbors++;
 +
        }
 +
      }
 +
 +
      if (current == '#') {
 +
        if (neighbors < 2 || neighbors > 3)
 +
          newGen[row][i] =  ' ';
 +
        else
 +
          newGen[row][i] = '#';
 +
      }
 +
 +
      if (current == ' ') {
 +
        if (neighbors == 3)
 +
          newGen[row][i] = '#';
 +
        else
 +
          newGen[row][i] = ' ';
 +
      }
 +
    }
 +
  }
 +
}
 +
 +
 +
// --------------------------------------------------------------------------
 +
int main( int argc, char* argv[] ) {
 +
  int gens = 3000;      // # of generations
 +
  int i;
 +
  char **dish, **future, **temp;
 +
 +
  //--- clear screen ---
 +
  cls();
 +
 +
  //--- init the global arrays ---
 +
  initDishes();
 +
 +
  //--- set pointers to them ---
 +
  dish  = DISH0;
 +
  future = DISH1;
 +
 +
  //--- print first generation ---
 +
  print( dish );         
 +
 +
 +
  //--- iterate over all generations ---
 +
  for ( i = 0; i < gens; i++) {
 +
   
 +
    //printf( "Generation %d\n", i );
 +
 +
    // apply the rules of life to the current population and
 +
    // generate the next generation.
 +
    life( dish, future );
 +
 +
    // display the new generation (comment this out if you want
 +
    // the last generation, instead)
 +
    print( dish );
 +
 +
    // add a bit of a delay to better see the visualization
 +
    // remove this part to get full timing.
 +
    sleep(1);  // 1 sec
 +
 +
    // copy future to dish
 +
    temp = dish;
 +
    dish = future;
 +
    future = temp;
 +
  }
 +
 +
  // display the last generation
 +
  print(dish);
 +
}
 +
 +
 +
 +
</source>
 +
<br />
 +
 +
==Output==
 +
<br />
 +
::<source lang="text">
 +
                                            # #                                 
 +
                                            ##                                 
 +
                                                                #               
 +
                                                              # #               
 +
                                                ##            ##               
 +
                                                #  #                             
 +
                                                ##                             
 +
                                                                                 
 +
                                                                                 
 +
                                            ##                                 
 +
                                            # #                                 
 +
                                            #                                   
 +
                                                                                 
 +
                                                                              # 
 +
                                                                            # # 
 +
                                                                            # # 
 +
                                                                              # 
 +
                                                                                 
 +
##                                                                      ##     
 +
  #                                                                    #  #    #
 +
##                        #                              #              ##     
 +
                          # #                            # #                     
 +
                          ##                            # #  ###            # 
 +
                                                          #                  # # 
 +
                                                      ##                    # # 
 +
                                                      ##                      # 
 +
                                                        ##                       
 +
352b@aurora ~/handout/mpi $
 +
 +
</source>
 +
<br />
 +
==Source, Version 2==
 +
<br />
 +
This version reads the initial dish from a data file whose name is provided on the command line.  This version also reports the execution time of the program without displaying the generations.
 +
<br />
 +
Execution times on a MacBook Pro 2016 for a 3000 generations of a game of life with a 2048-line dish of 80-char long lines: 20.98246 sec, 21.08754 sec, and 20.79234 sec.
 +
::<source lang="C">
 +
/* 
 +
Game of life (V2)
 +
D. Thiebaut
 +
Heavily adapted from code found in java section at this
 +
URL:  https://rosettacode.org/wiki/Conway%27s_Game_of_Life#Java
 +
and ported to C.
 +
 +
This code works in console mode, computing 3000 generations of
 +
a game of life provided in a dish that is originally read from a data
 +
file.
 +
 +
To compile and run:
 +
 +
gcc -o GameOfLife2 GameOfLife2.c
 +
./GameOfLife2  dishFileName
 +
 +
 +
*/
 +
#include <stdio.h>
 +
#include <strings.h>
 +
#include <stdlib.h>
 +
#include <time.h>
 +
#include <unistd.h>
 +
 +
// ------------------------------------- MACROS ----------------------------------------
 +
#define esc 27
 +
#define cls() printf("%c[2J",esc)
 +
#define pos(row,col) printf("%c[%d;%dH",esc,row,col)
 +
 +
// ------------------------------------- GLOBALS ----------------------------------------
 +
int  NUMBERROWS;
 +
char  **DISH0;
 +
char  **DISH1;
 +
 +
// --------------------------------- prototypes -----------------------------
 +
void life( char**, char** );
 +
void initDishes( char* );
 +
void clearScreen();
 +
void print( char ** );
 +
 +
// --------------------------------------------------------------------------
 +
// initDishes
 +
// inits the dishes (current and future)
 +
void initDishes( char* fileName ) {
 +
  int i, n;
 +
  char ch, buffer[1000];
 +
 +
  //--- read # of lines first ---
 +
  FILE *f = fopen( fileName, "r" );
 +
  int noLines = 0;
 +
  while ( !feof( f ) ) {
 +
    ch = fgetc( f );
 +
    if (ch == '\n') noLines++;
 +
  }
 +
  fclose( f );
 +
 +
  //--- set global ---
 +
  NUMBERROWS = noLines;
 +
  //printf( "number of lines = %d\n", noLines );
 +
 +
  //--- initialize DISH arrays ---
 +
  DISH0 = (char **) malloc( noLines * sizeof( char* ) );
 +
  DISH1 = (char **) malloc( noLines * sizeof( char* ) );
 +
 +
  //--- read file again and initialize arrays ---
 +
  f = fopen( fileName, "r" );
 +
  i = 0;
 +
  while ( !feof( f ) ) {
 +
    fgets( buffer, 1000, f );
 +
    if ( feof( f ) )
 +
      break;
 +
    buffer[999] = '\0';
 +
    DISH0[i] = (char *) malloc( (strlen( buffer) + 1 ) * sizeof( char ) );
 +
    strcpy( DISH0[i], buffer );
 +
    DISH1[i] = (char *) malloc( (strlen( DISH0[i] ) + 1 ) * sizeof( char )  );
 +
    strcpy( DISH1[i], DISH0[i] );
 +
    i++;
 +
  }
 +
  fclose( f );
 +
}
 +
 +
 +
// --------------------------------------------------------------------------
 +
// clearscreen:
 +
void clearScreen() {
 +
  /*
 +
  * brings the cursor home (top-left), so that the next generation will
 +
  * be printed over the current one.
 +
  */
 +
  return;
 
   char ANSI_CLS[] = "\x1b[2J";
 
   char ANSI_CLS[] = "\x1b[2J";
 
   char ANSI_HOME[] = "\x1b[H";
 
   char ANSI_HOME[] = "\x1b[H";
Line 218: Line 488:
 
   int i;
 
   int i;
 
   char **dish, **future, **temp;
 
   char **dish, **future, **temp;
 +
  char *fileName;
 +
  unsigned long micros = 0;
 +
  clock_t startTime, endTime;
 +
 +
  if ( argc < 2 ) {
 +
    printf( "Syntax: ./GameOfLife2 dishFileName\n\n" );
 +
    return 1;
 +
  }
 +
 +
  //--- get the file name from the command line ---
 +
  fileName = argv[1];
  
 
   //--- clear screen ---
 
   //--- clear screen ---
−
   cls();
+
   //cls();
  
 
   //--- init the global arrays ---
 
   //--- init the global arrays ---
−
   initDishes();
+
   initDishes( fileName );
 +
 
 +
  //--- start measuring time ---
 +
  startTime = clock();
  
 
   //--- set pointers to them ---
 
   //--- set pointers to them ---
Line 229: Line 513:
 
   future = DISH1;
 
   future = DISH1;
  
 +
  //--- for debugging ---
 
   //check( dish, future );
 
   //check( dish, future );
  
 
   //--- print first generation ---
 
   //--- print first generation ---
−
   print( dish );           
+
   //print( dish );           
  
  
Line 246: Line 531:
 
     // display the new generation (comment this out if you want
 
     // display the new generation (comment this out if you want
 
     // the last generation, instead)
 
     // the last generation, instead)
−
     print( dish );
+
     //print( dish );
  
 
     // add a bit of a delay to better see the visualization
 
     // add a bit of a delay to better see the visualization
 
     // remove this part to get full timing.
 
     // remove this part to get full timing.
−
     sleep(1);  // 1 sec
+
     //sleep(1);  // 1 sec
  
 
     // copy future to dish
 
     // copy future to dish
Line 259: Line 544:
  
 
   // display the last generation
 
   // display the last generation
−
   print(dish);
+
   //print(dish);
 +
 
 +
  //--- measure elapsed time ---
 +
  endTime = clock();
 +
  float seconds = (endTime - startTime)/1000000.0;
 +
  printf( "%1.5f\n", seconds );
 
}
 
}
  
Line 266: Line 556:
 
</source>
 
</source>
 
<br />
 
<br />
 +
 
=MPI Version of Game of Life, in C=
 
=MPI Version of Game of Life, in C=
 +
<br />
 +
==Source==
 
<br />
 
<br />
 
::<source lang="C">
 
::<source lang="C">
Line 289: Line 582:
 
  The initial pattern is defined in the array PATTERN.
 
  The initial pattern is defined in the array PATTERN.
  
−
  To compile and run:
+
  To compile and run, several different variants:
 +
 
 +
mpicc.mpich -o GameOfLifeMPI2 GameOfLifeMPI2.c
 +
mpiexec.mpich -n 2 ./GameOfLifeMPI2
 +
 +
or
  
 
  mpicc -o GameOfLifeMPI2 GameOfLifeMPI2.c
 
  mpicc -o GameOfLifeMPI2 GameOfLifeMPI2.c
 
  mpirun -np 2 ./GameOfLifeMPI2
 
  mpirun -np 2 ./GameOfLifeMPI2
−
 
  
 
*/
 
*/
Line 364: Line 661:
 
}
 
}
  
 +
 +
// --------------------------------------------------------------------------
 +
// initDishes2
 +
// inits the dishes (current and future)
 +
// (Buggy: attempts to declare only 1 half of the array, plus boundary
 +
//  rows, depending on rank.  Needs a bit more debugging...)
 
void initDishes2( int rank ) {
 
void initDishes2( int rank ) {
 
   int i;
 
   int i;
Line 618: Line 921:
 
     future = temp;
 
     future = temp;
 
   }
 
   }
−
 
−
  //--- close MPI ---
 
−
    pos( 30+rank, 0 );
 
−
    printf( "Process %d done.  Exiting\n\n", rank );
 
−
    MPI_Finalize();
 
  
 
   //--- display the last generation ---
 
   //--- display the last generation ---
 
   print(dish, rank);
 
   print(dish, rank);
  
 +
  //--- close MPI ---
 +
  pos( 30+rank, 0 );
 +
  printf( "Process %d done.  Exiting\n\n", rank );
 +
  MPI_Finalize();
 +
 +
  return 0;
 
}
 
}
  
Line 633: Line 937:
 
</source>
 
</source>
 
<br />
 
<br />
 +
 +
==Output==
 
<br />
 
<br />
 +
::<source lang="text">
 +
                                            # #                                 
 +
                                            ##                                 
 +
                                                                #               
 +
                                                              # #               
 +
                                                ##            ##               
 +
                                                #  #                             
 +
                                                ##                             
 +
                                                                                 
 +
                                                                                 
 +
                                            ##                                 
 +
                                            # #                                 
 +
                                            #                                   
 +
                                                                                 
 +
                                                                              # 
 +
                                                                            # # 
 +
                                                                            # # 
 +
                                                                              # 
 +
                                                                                 
 +
##                                                                      ##     
 +
  #                                                                    #  #    #
 +
##                        #                              #              ##     
 +
                          # #                            # #                     
 +
                          ##                            # #  ###            # 
 +
                                                          #                  # # 
 +
                                                      ##                    # # 
 +
                                                      ##                      # 
 +
                                                        ##                       
 +
 +
 +
Process 0 done.  Exiting
 +
Process 1 done.  Exiting
 +
 +
352b@aurora ~/handout/mpi $
 +
 +
 +
</source>
 
<br />
 
<br />
 
<br />
 
<br />

Latest revision as of 10:51, 6 April 2017

--D. Thiebaut (talk) 23:25, 8 March 2017 (EST)

Serial Game of Life


Source, Version 1

/*  
 Game of life
 D. Thiebaut
 Heavily adapted from code found in java section at this
 URL:  https://rosettacode.org/wiki/Conway%27s_Game_of_Life#Java
 and ported to C.

 This code works in console mode, displaying successive generations
 of the game of life on the screen, and clearing the screen between
 each one.

 The initial pattern is defined in the array dish (as in petri dish).

 To compile and run:

 gcc -o GameOfLife GameOfLife.c
 ./GameOfLife


*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

// ------------------------------------- MACROS ----------------------------------------
#define NUMBERROWS 28
#define esc 27
#define cls() printf("%c[2J",esc)
#define pos(row,col) printf("%c[%d;%dH",esc,row,col)

// ------------------------------------- GLOBALS ----------------------------------------
char  *DISH0[ NUMBERROWS ];
char  *DISH1[ NUMBERROWS ];
char  *PATTERN[NUMBERROWS] = {
  "                                                                                  ",
  "   #                                                                              ",
  " # #                                            ###                               ",
  "  ##                                                                              ",
  "                                                                                  ",
  "                                                      #                           ",
  "                                                    # #                           ",
  "                                                     ##                           ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "             #                                                                    ",
  "           # #                                                                    ",
  "            ##                                                                    ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  " 
};

// --------------------------------- prototypes -----------------------------
void life( char**, char** );
void initDishes( );
void clearScreen();
void print( char ** );


// --------------------------------------------------------------------------
// initDishes
// inits the dishes (current and future)
void initDishes( ) {
  int i;

  //--- initialize other dish with spaces.  Make it same dimension as DISH0. ---
  for (i = 0; i< NUMBERROWS; i++ )  {
    DISH0[i] = (char *) malloc( (strlen( PATTERN[0] ) + 1 ) * sizeof( char ) );
    strcpy( DISH0[i], PATTERN[i] );

    DISH1[i] = (char *) malloc( (strlen( DISH0[0] )+1) * sizeof( char )  );
    strcpy( DISH1[i], DISH0[i] );
  }

}


// --------------------------------------------------------------------------
// clearscreen:
void clearScreen() {
  /*
   * brings the cursor home (top-left), so that the next generation will
   * be printed over the current one.
   */

  char ANSI_CLS[] = "\x1b[2J";
  char ANSI_HOME[] = "\x1b[H";
  printf( "%s%s", ANSI_HOME, ANSI_CLS );

}

// --------------------------------------------------------------------------
// print
void print( char* dish[] ) {
  /*
   * just display all the lines of the array of strings.
   */
  int i;

  for (i=0; i<NUMBERROWS; i++ ) {
    pos( i, 0 );
    printf( "%s\n", dish[i] );
  }

}


// --------------------------------------------------------------------------
void  life( char** dish, char** newGen ) {
  /*
   * Given an array of string representing the current population of cells
   * in a petri dish, computes the new generation of cells according to
   * the rules of the game. A new array of strings is returned.
   */
  int i, j, row;
  int rowLength = strlen( dish[0] );
  int dishLength = NUMBERROWS;

  for (row = 0; row < NUMBERROWS; row++) {// each row

    for ( i = 0; i < rowLength; i++) { // each char in the
                                       // row

      int r, j, neighbors = 0;
      char current = dish[row][i];

      // loop in a block that is 3x3 around the current cell
      // and count the number of '#' cells.
      for ( r = row - 1; r <= row + 1; r++) {

        // make sure we wrap around from bottom to top
        int realr = r;
        if (r == -1)
          realr = dishLength - 1;
        if (r == dishLength)
          realr = 0;

        for ( j = i - 1; j <= i + 1; j++) {

          // make sure we wrap around from left to right
          int realj = j;
          if (j == -1)
            realj = rowLength - 1;
          if (j == rowLength)
            realj = 0;

          if (r == row && j == i)
            continue; // current cell is not its
          // neighbor
          if (dish[realr][realj] == '#')
            neighbors++;
        }
      }

      if (current == '#') {
        if (neighbors < 2 || neighbors > 3)
          newGen[row][i] =  ' ';
        else
          newGen[row][i] = '#';
      }

      if (current == ' ') {
        if (neighbors == 3)
          newGen[row][i] = '#';
        else
          newGen[row][i] = ' ';
      }
    }
  }
}


// --------------------------------------------------------------------------
int main( int argc, char* argv[] ) {
  int gens = 3000;      // # of generations
  int i;
  char **dish, **future, **temp;

  //--- clear screen ---
  cls();

  //--- init the global arrays ---
  initDishes();

  //--- set pointers to them ---
  dish   = DISH0;
  future = DISH1;

  //--- print first generation ---
  print( dish );          


  //--- iterate over all generations ---
  for ( i = 0; i < gens; i++) {
    
    //printf( "Generation %d\n", i );

    // apply the rules of life to the current population and 
    // generate the next generation.
    life( dish, future );

    // display the new generation (comment this out if you want
    // the last generation, instead)
    print( dish );

    // add a bit of a delay to better see the visualization
    // remove this part to get full timing.
    sleep(1);  // 1 sec

    // copy future to dish
    temp = dish;
    dish = future;
    future = temp;
  }

  // display the last generation
  print(dish);
}


Output


                                            # #                                   
                                             ##                                   
                                                                #                 
                                                               # #                
                                                 ##             ##                
                                                #  #                              
                                                 ##                               
                                                                                  
                                                                                  
                                             ##                                   
                                            # #                                   
                                             #                                    
                                                                                  
                                                                              #   
                                                                             # #  
                                                                             # #  
                                                                              #   
                                                                                  
##                                                                       ##       
  #                                                                     #  #     #
##                         #                              #              ##       
                          # #                            # #                      
                           ##                            # #   ###            #   
                                                          #                  # #  
                                                      ##                     # #  
                                                      ##                      #   
                                                        ##                        
352b@aurora ~/handout/mpi $


Source, Version 2


This version reads the initial dish from a data file whose name is provided on the command line. This version also reports the execution time of the program without displaying the generations.
Execution times on a MacBook Pro 2016 for a 3000 generations of a game of life with a 2048-line dish of 80-char long lines: 20.98246 sec, 21.08754 sec, and 20.79234 sec. 

/*  
 Game of life (V2)
 D. Thiebaut
 Heavily adapted from code found in java section at this
 URL:  https://rosettacode.org/wiki/Conway%27s_Game_of_Life#Java
 and ported to C.

 This code works in console mode, computing 3000 generations of
 a game of life provided in a dish that is originally read from a data 
 file.

 To compile and run:

 gcc -o GameOfLife2 GameOfLife2.c
 ./GameOfLife2  dishFileName


*/
#include <stdio.h>
#include <strings.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

// ------------------------------------- MACROS ----------------------------------------
#define esc 27
#define cls() printf("%c[2J",esc)
#define pos(row,col) printf("%c[%d;%dH",esc,row,col)

// ------------------------------------- GLOBALS ----------------------------------------
int   NUMBERROWS;
char  **DISH0;
char  **DISH1;

// --------------------------------- prototypes -----------------------------
void life( char**, char** );
void initDishes( char* );
void clearScreen();
void print( char ** );

// --------------------------------------------------------------------------
// initDishes
// inits the dishes (current and future)
void initDishes( char* fileName ) {
  int i, n;
  char ch, buffer[1000];

  //--- read # of lines first ---
  FILE *f = fopen( fileName, "r" );
  int noLines = 0;
  while ( !feof( f ) ) {
    ch = fgetc( f );
    if (ch == '\n') noLines++;
  }
  fclose( f );

  //--- set global ---
  NUMBERROWS = noLines;
  //printf( "number of lines = %d\n", noLines );

  //--- initialize DISH arrays ---
  DISH0 = (char **) malloc( noLines * sizeof( char* ) );
  DISH1 = (char **) malloc( noLines * sizeof( char* ) );

  //--- read file again and initialize arrays ---
  f = fopen( fileName, "r" );
  i = 0;
  while ( !feof( f ) ) {
    fgets( buffer, 1000, f );
    if ( feof( f ) )
      break;
    buffer[999] = '\0';
    DISH0[i] = (char *) malloc( (strlen( buffer) + 1 ) * sizeof( char ) );
    strcpy( DISH0[i], buffer );
    DISH1[i] = (char *) malloc( (strlen( DISH0[i] ) + 1 ) * sizeof( char )  );
    strcpy( DISH1[i], DISH0[i] );
    i++;
  }
  fclose( f );
}


// --------------------------------------------------------------------------
// clearscreen:
void clearScreen() {
  /*
   * brings the cursor home (top-left), so that the next generation will
   * be printed over the current one.
   */
  return;
  char ANSI_CLS[] = "\x1b[2J";
  char ANSI_HOME[] = "\x1b[H";
  printf( "%s%s", ANSI_HOME, ANSI_CLS );

}

// --------------------------------------------------------------------------
// print
void print( char* dish[] ) {
  /*
   * just display all the lines of the array of strings.
   */
  int i;

  for (i=0; i<NUMBERROWS; i++ ) {
    pos( i, 0 );
    printf( "%s\n", dish[i] );
  }

}

// --------------------------------------------------------------------------
void check( char** dish, char** future ) {
  int i, j, k, l;
  l = sizeof( dish )/sizeof( dish[0] );
  printf( "length of dish = %d\n", l );

  for ( i=0; i<l; i++ ) {
    k = strlen( dish[i] );
    printf( "%d %s\n", k, dish[i] );
  }
  printf( "\n\n" );

  l = sizeof( future )/sizeof( future[0] );
  printf( "length of future = %d\n", l );

  for ( i=0; i<l; i++ ) {
    k = strlen( future[i] );
    printf( "%d %s\n", k, future[i] );
  }
  printf( "\n\n" );

}

// --------------------------------------------------------------------------
void  life( char** dish, char** newGen ) {
  /*
   * Given an array of string representing the current population of cells
   * in a petri dish, computes the new generation of cells according to
   * the rules of the game. A new array of strings is returned.
   */
  int i, j, row;
  int rowLength = strlen( dish[0] );
  int dishLength = NUMBERROWS;

  for (row = 0; row < NUMBERROWS; row++) {// each row

    for ( i = 0; i < rowLength; i++) { // each char in the
                                       // row

      int r, j, neighbors = 0;
      char current = dish[row][i];

      // loop in a block that is 3x3 around the current cell
      // and count the number of '#' cells.
      for ( r = row - 1; r <= row + 1; r++) {

        // make sure we wrap around from bottom to top
        int realr = r;
        if (r == -1)
          realr = dishLength - 1;
        if (r == dishLength)
          realr = 0;

        for (int j = i - 1; j <= i + 1; j++) {

          // make sure we wrap around from left to right
          int realj = j;
          if (j == -1)
            realj = rowLength - 1;
          if (j == rowLength)
            realj = 0;

          if (r == row && j == i)
            continue; // current cell is not its
          // neighbor
          if (dish[realr][realj] == '#')
            neighbors++;
        }
      }

      if (current == '#') {
        if (neighbors < 2 || neighbors > 3)
          newGen[row][i] =  ' ';
        else
          newGen[row][i] = '#';
      }

      if (current == ' ') {
        if (neighbors == 3)
          newGen[row][i] = '#';
        else
          newGen[row][i] = ' ';
      }
    }
  }
}


// --------------------------------------------------------------------------
int main( int argc, char* argv[] ) {
  int gens = 3000;      // # of generations
  int i;
  char **dish, **future, **temp;
  char *fileName;
  unsigned long micros = 0;
  clock_t startTime, endTime;

  if ( argc < 2 ) {
    printf( "Syntax: ./GameOfLife2 dishFileName\n\n" );
    return 1;
  }

  //--- get the file name from the command line ---
  fileName = argv[1];

  //--- clear screen ---
  //cls();

  //--- init the global arrays ---
  initDishes( fileName );

  //--- start measuring time ---
  startTime = clock();

  //--- set pointers to them ---
  dish   = DISH0;
  future = DISH1;

  //--- for debugging ---
  //check( dish, future );

  //--- print first generation ---
  //print( dish );          


  //--- iterate over all generations ---
  for ( i = 0; i < gens; i++) {
    
    //printf( "Generation %d\n", i );

    // apply the rules of life to the current population and 
    // generate the next generation.
    life( dish, future );

    // display the new generation (comment this out if you want
    // the last generation, instead)
    //print( dish );

    // add a bit of a delay to better see the visualization
    // remove this part to get full timing.
    //sleep(1);  // 1 sec

    // copy future to dish
    temp = dish;
    dish = future;
    future = temp;
  }

  // display the last generation
  //print(dish);

  //--- measure elapsed time ---
  endTime = clock();
  float seconds = (endTime - startTime)/1000000.0;
  printf( "%1.5f\n", seconds );
}


MPI Version of Game of Life, in C


Source


/*  
 Game of life
 D. Thiebaut
 This is the MPI version of GameOfLife.c, for MPI, for 2 Processes,
 or tasks.
 This version works only for 2 tasks.

 It hasn't been optimized.  Each task works on one half of the dish
 arrays where the generations evolve, but actually maintain a full
 array in memory.
 
 The two tasks communicate with each other after each generation 
 and exchange 2 rows, each.  

 This code works in console mode, displaying successive generations
 of the game of life on the screen, and clearing the screen between
 each one.

 The initial pattern is defined in the array PATTERN.

 To compile and run, several different variants:

 mpicc.mpich -o GameOfLifeMPI2 GameOfLifeMPI2.c
 mpiexec.mpich -n 2 ./GameOfLifeMPI2
 
 or 

 mpicc -o GameOfLifeMPI2 GameOfLifeMPI2.c
 mpirun -np 2 ./GameOfLifeMPI2

*/
#include <stdio.h>
#include <strings.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include "mpi.h"

#define NUMBERROWS 28
#define esc 27
#define cls() printf("%c[2J",esc)
#define pos(row,col) printf("%c[%d;%dH",esc,row,col)


char  *DISH0[ NUMBERROWS ];
char  *DISH1[ NUMBERROWS ];
char  *PATTERN[NUMBERROWS] = {
  "                                                                                  ",
  "   #                                                                              ",
  " # #                                            ###                               ",
  "  ##                                                                              ",
  "                                                                                  ",
  "                                                      #                           ",
  "                                                    # #                           ",
  "                                                     ##                           ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "             #                                                                    ",
  "           # #                                                                    ",
  "            ##                                                                    ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  ",
  "                                                                                  " 
};
int ROWSIZE = strlen( "                                                                                  ") + 1;

//------------------------------- prototypes --------------------------------
void life( char**, char**, int );
void initDishes( int  );
void print( char **, int );

// --------------------------------------------------------------------------
// initDishes
// inits the dishes (current and future)
void initDishes( int rank ) {
  int i;

  //--- initialize other dish with spaces.  Make it same dimension as DISH0. ---
  for (i = 0; i< NUMBERROWS; i++ )  {
    DISH0[i] = (char *) malloc( ( strlen( PATTERN[0] ) + 1 ) * sizeof( char ) );
    strcpy( DISH0[i], PATTERN[i] );

    DISH1[i] = (char *) malloc( (strlen( DISH0[0] )+1) * sizeof( char )  );
    strcpy( DISH1[i], PATTERN[i] );
  }
}


// --------------------------------------------------------------------------
// initDishes2
// inits the dishes (current and future)
// (Buggy: attempts to declare only 1 half of the array, plus boundary
//  rows, depending on rank.  Needs a bit more debugging...)
void initDishes2( int rank ) {
  int i;

  // init to null all entries.  This way we'll be
  // able to tell if a row belongs to us or not.
  for ( i=0; i<NUMBERROWS; i++ ) {
    DISH0[i] = NULL;
    DISH1[i] = NULL;
  }

  //--- Init RANK 0 rows ---
  if ( rank == 0 ) {
    //--- initialize dishes with lower half of pattern ---
    for (i = 0; i< NUMBERROWS/2+1; i++ )  {
    
      DISH0[i] = (char *) malloc( (strlen( PATTERN[0] ) + 1 ) * sizeof( char ) );
      strcpy( DISH0[i], PATTERN[i] );

      DISH1[i] = (char *) malloc( (strlen( DISH0[0] )+1) * sizeof( char )  );
      strcpy( DISH1[i], DISH0[i] );
    }

    //--- initialize top row of dishes, as they are neighbors of Row 0 ---
    DISH0[NUMBERROWS-1] = (char *) malloc( (strlen( PATTERN[0] ) + 1 ) * sizeof( char ) );
    strcpy( DISH0[NUMBERROWS-1], PATTERN[NUMBERROWS-1] );
    DISH1[NUMBERROWS-1] = (char *) malloc( (strlen( PATTERN[0] ) + 1 ) * sizeof( char ) );
    strcpy( DISH1[NUMBERROWS-1], PATTERN[NUMBERROWS-1] );
  }

  //--- Init RANK 1 rows ---
  if ( rank == 1 ) {
    //--- initialize dishes with upper half of pattern ---                                                                               
    for (i = NUMBERROWS/2-1; i< NUMBERROWS; i++ )  {

      DISH0[i] = (char *) malloc( (strlen( PATTERN[0] ) + 1 ) * sizeof( char ) );
      strcpy( DISH0[i], PATTERN[i] );

      DISH1[i] = (char *) malloc( (strlen( DISH0[0] )+1) * sizeof( char )  );
      strcpy( DISH1[i], DISH0[i] );
    }

    //--- initialize bottom row of dishes, as they are neighbors of top row  ---                                                       
    DISH0[0] = (char *) malloc( (strlen( PATTERN[0] ) + 1 ) * sizeof( char ) );
    strcpy( DISH0[0], PATTERN[0] );
    DISH1[0] = (char *) malloc( (strlen( PATTERN[0] ) + 1 ) * sizeof( char ) );
    strcpy( DISH1[0], PATTERN[01] );
  }
}



// --------------------------------------------------------------------------
// print
void print( char* dish[], int rank ) {
  int i;

  if ( rank == 0 ) {
    //--- display lower half only ---
    for (i=0; i<NUMBERROWS/2; i++ ) {
      if ( dish[i] == NULL ) continue;
      pos( i, 0 );
      printf( "%s\n", dish[i] );
    }
  }

  if ( rank == 1 ) {
    //--- display upper half only ---
    for (i=NUMBERROWS/2; i<NUMBERROWS; i++ ) {
      if ( dish[i] == NULL ) continue;
      pos( i, 0 );
      printf( "%s\n", dish[i] );
    }

  }
}

// --------------------------------------------------------------------------
void check( char** dish, char** future ) {
  int i, j, k, l;
  l = sizeof( dish )/sizeof( dish[0] );
  printf( "length of dish = %d\n", l );

  for ( i=0; i<l; i++ ) {
    k = strlen( dish[i] );
    printf( "%d %s\n", k, dish[i] );
  }
  printf( "\n\n" );

  l = sizeof( future )/sizeof( future[0] );
  printf( "length of future = %d\n", l );

  for ( i=0; i<l; i++ ) {
    k = strlen( future[i] );
    printf( "%d %s\n", k, future[i] );
  }
  printf( "\n\n" );

}

// --------------------------------------------------------------------------
void  life( char** dish, char** newGen, int rank ) {
  /*
   * Given an array of string representing the current population of cells
   * in a petri dish, computes the new generation of cells according to
   * the rules of the game. A new array of strings is returned.
   */
  int i, j, row;
  int rowLength = strlen( dish[0] );
  int dishLength = NUMBERROWS;
  
  int lowerRow, upperRow;

  //--- slice the array into two halves.  Rank 0 is lower half, ---
  //--  Rank 1 is upper half.                                   ---
  if ( rank == 0 ) {
    lowerRow = 0;
    upperRow = NUMBERROWS/2;
  }
  if ( rank == 1 ) {
    lowerRow = NUMBERROWS/2;
    upperRow = NUMBERROWS;
  }
  
  for (row = lowerRow; row < upperRow; row++) {// each row
    
    if ( dish[row] == NULL )
      continue;

    for ( i = 0; i < rowLength; i++) { // each char in the
                                       // row

      int r, j, neighbors = 0;
      char current = dish[row][i];

      // loop in a block that is 3x3 around the current cell
      // and count the number of '#' cells.
      for ( r = row - 1; r <= row + 1; r++) {

        // make sure we wrap around from bottom to top
        int realr = r;
        if (r == -1)
          realr = dishLength - 1;
        if (r == dishLength)
          realr = 0;

        for (int j = i - 1; j <= i + 1; j++) {

          // make sure we wrap around from left to right
          int realj = j;
          if (j == -1)
            realj = rowLength - 1;
          if (j == rowLength)
            realj = 0;

          if (r == row && j == i)
            continue; // current cell is not its
          // neighbor
          if (dish[realr][realj] == '#')
            neighbors++;
        }
      }

      if (current == '#') {
        if (neighbors < 2 || neighbors > 3)
          newGen[row][i] =  ' ';
        else
          newGen[row][i] = '#';
      }

      if (current == ' ') {
        if (neighbors == 3)
          newGen[row][i] = '#';
        else
          newGen[row][i] = ' ';
      }
    }
  }
}


// --------------------------------------------------------------------------
int main( int argc, char* argv[] ) {
  int gens = 3000;      // # of generations
  int i;
  char **dish, **future, **temp;

  //--- MPI Variables ---
  int noTasks = 0;
  int rank = 0;
  MPI_Status status;   // required variable for receive routines

  //--- initialize MPI ---
  MPI_Init( &argc, &argv );

  //--- get number of tasks, and make sure it's 2 ---
  MPI_Comm_size( MPI_COMM_WORLD, &noTasks );
  if ( noTasks != 2 ) {
    printf( "Number of Processes/Tasks must be 2.  Number = %d\n\n", noTasks );
    MPI_Finalize();
    return 1;
  }

  //--- get rank ---
  MPI_Comm_rank( MPI_COMM_WORLD, &rank );

  //--- init the dishes as half of the original problem ---
  initDishes( rank );

  dish   = DISH0;
  future = DISH1;

  //check( dish, future );

  //--- clear screen ---
  cls();

  print( dish, rank );          // # first generation, in petri dish


  // iterate over all generations
  for ( i = 0; i < gens; i++) {
    
    pos( 33+rank, 0 );
    printf( "Rank %d: Generation %d\n", rank, i );

    // apply the rules of life to the current population and 
    // generate the next generation.
    life( dish, future, rank );

    // display the new generation
    //print( dish, rank );

    // add a bit of a delay to better see the visualization
    // remove this part to get full timing.
    //if (rank == 0 ) sleep( 1 );

    if (rank==0 ) {
      //          buffer                #items   item-size src/dest tag   world  
      MPI_Send( future[    0         ], ROWSIZE, MPI_CHAR,    1,     0,  MPI_COMM_WORLD );
      MPI_Send( future[NUMBERROWS/2-1], ROWSIZE, MPI_CHAR,    1,     0,  MPI_COMM_WORLD );
      MPI_Recv( future[NUMBERROWS-1],   ROWSIZE, MPI_CHAR,    1,     0,  MPI_COMM_WORLD, &status );
      MPI_Recv( future[NUMBERROWS/2],   ROWSIZE, MPI_CHAR,    1,     0,  MPI_COMM_WORLD, &status );
    }
    if (rank==1 ) {
      MPI_Recv( future[    0         ], ROWSIZE, MPI_CHAR,    0,     0,  MPI_COMM_WORLD, &status );
      MPI_Recv( future[NUMBERROWS/2-1], ROWSIZE, MPI_CHAR,    0,     0,  MPI_COMM_WORLD, &status );
      MPI_Send( future[NUMBERROWS-1],   ROWSIZE, MPI_CHAR,    0,     0,  MPI_COMM_WORLD );
      MPI_Send( future[NUMBERROWS/2],   ROWSIZE, MPI_CHAR,    0,     0,  MPI_COMM_WORLD );
    }
    // copy future to dish
    temp = dish;
    dish = future;
    future = temp;
  }

  //--- display the last generation ---
  print(dish, rank);

  //--- close MPI ---
  pos( 30+rank, 0 );
  printf( "Process %d done.  Exiting\n\n", rank );
  MPI_Finalize();

  return 0;
}


Output


                                            # #                                   
                                             ##                                   
                                                                #                 
                                                               # #                
                                                 ##             ##                
                                                #  #                              
                                                 ##                               
                                                                                  
                                                                                  
                                             ##                                   
                                            # #                                   
                                             #                                    
                                                                                  
                                                                              #   
                                                                             # #  
                                                                             # #  
                                                                              #   
                                                                                  
##                                                                       ##       
  #                                                                     #  #     #
##                         #                              #              ##       
                          # #                            # #                      
                           ##                            # #   ###            #   
                                                          #                  # #  
                                                      ##                     # #  
                                                      ##                      #   
                                                        ##                        


Process 0 done.  Exiting
Process 1 done.  Exiting

352b@aurora ~/handout/mpi $

















Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=Game_of_Life_in_C_and_MPI&oldid=30670"