Conway's game of Life

Parallel evolve() function for Conway's game of Life

/* "evolve" routine for John Horton Conway's game of Life.
* This version is parallelized using pthreads.
* 2019-11-06
*/
#include <stdio.h>      // needed for debugging
#include <pthread.h>

#define NTHREADS 4  // Arbitrary choice, set equal to the # of Raspberry Pi cores

struct ThreadInfo {
    char *this, *next;
    unsigned xsize;
    unsigned ymin, ymax;
    int ID; // optional
} ;

/*
* This function is executed in each thread;
* it gets its parameters via a pointer to a struct ThreadInfo.
* The Y-rows are divided up between the threads by the parent function, evolve().
*/
void *worker(void *vp)
{
    struct ThreadInfo *tip = vp;

    fprintf(stderr, "  Thread %d starts\n", tip->ID);

    // For each cell:
    for (int y = tip->ymin; y < tip->ymax; y++) {
        for (int x = 1; x < tip->xsize-1; x++) {

            // For all neighbors of the cell:
            unsigned neighbors = 0;
            for (int yl = -1; yl <= +1; yl++)
                for (int xl = -1; xl <= +1; xl++)
                    if (xl != 0 || yl != 0)
                        neighbors += *(tip->this + (x + xl) + tip->xsize * (y + yl));

            /*
            * Update the "next-gen" board
            * This doesn't need to be a critical section, only because
            * each thread is updating a DIFFERENT part of the boardnext array.
            */
            switch (neighbors) {
              case 0: case 1:
                *(tip->next + x + tip->xsize * y) = 0;
                break;
              case 2:
                *(tip->next + x + tip->xsize * y) = *(tip->this + x + tip->xsize * y);
                break;
              case 3:
                *(tip->next + x + tip->xsize * y) = 1;
                break;
              default:
                *(tip->next + x + tip->xsize * y) = 0;
                break;
            }
        }
    }
    return NULL;
}


/*
* This function is called by main to do the work.
* It parallelizes the work by splitting it among multiple threads.
*/
void evolve(char *board, char *boardnext, unsigned xsize, unsigned ysize)
{
    pthread_t threads[NTHREADS];
    struct ThreadInfo info[NTHREADS];

    fprintf(stderr, "evolve() starts\n");

    // Set up the the arguments to be passed to the worker threads:
    for (int i = 0; i < NTHREADS; i++) {
        info[i].ID = i;     // arbitrary ID number

        info[i].this = board;       // shared by all threads (in)
        info[i].next = boardnext;   // shared by all threads (out)
        info[i].xsize = xsize;      // common to all threads

        unsigned yrange = ysize / NTHREADS;
        if (i == 0) {
            info[i].ymin = 1;
            info[i].ymax = (i+1) * yrange;
        } else if (i == (NTHREADS - 1)) {
            info[i].ymin = i * yrange;
            info[i].ymax = ysize - 1;
        } else {
            info[i].ymin = i * yrange;
            info[i].ymax = (i+1) * yrange;
        }
    }

    // Fire off all the threads:
    for (int i = 0; i < NTHREADS; i++)
        pthread_create(&threads[i], NULL, worker, &info[i]);

    // Wait for each of the threads to finish
    for (int i = 0; i < NTHREADS; i++)
        pthread_join(threads[i], NULL);

    // Finished with this generation.
    return;
}

Unchanged: main() for Conway's game of Life

/* Main routine for John Horton Conway's game of Life.
* 2019-10-30
*/
#include <stdio.h>
#include <stdlib.h> // calloc()

void evolve(char *board, char *boardnext, unsigned xsize, unsigned ysize);
void displayboard( char *board, unsigned xsize, unsigned ysize,
                    unsigned gen,
                    char blank )
;

int main(int argc, char **argv)
{
    if (argc < 2) {
        fprintf(stderr, "usage: %s  <config-file>\n", argv[0]);
        return 1;
    }
    char blank = '.';
    if (argc == 3) {
        blank = argv[2][0];
    }

    FILE *handle;
    if (NULL == (handle = fopen(argv[1], "r"))) {
        fprintf(stderr, "Can't open configuration file '%s'\n", argv[1]);
        return 2;
    }

    unsigned xsize, ysize;
    fscanf(handle, " %u %u", &xsize, &ysize);
    char *boardA = calloc(xsize * ysize, sizeof(char)); // initialize board to 0's
    char *boardB = calloc(xsize * ysize, sizeof(char)); // initialize board to 0's

    unsigned xcoord, ycoord;
    while (EOF != fscanf(handle, " %u %u", &xcoord, &ycoord)) {
        *(boardA + xcoord + (ycoord * xsize)) = 1;
    }

    for (int i = 0; i < 64; i+=2) {
        // even-numbered generations...
        evolve(boardA, boardB, xsize, ysize);
        displayboard(boardA, xsize, ysize, i, blank);

        // odd-numbered generations...
        evolve(boardB, boardA, xsize, ysize);
        displayboard(boardB, xsize, ysize, i+1, blank);
    }

    return 0;
}

Unchanged: Board-display function for Conway's game of Life


/* Display routine for John Horton Conway's game of Life.
* 2019-10-30
*/
#include <stdio.h>
#include <unistd.h> // usleep()

char marker[] = { '.', '*' };

void displayboard( char *board, unsigned xsize, unsigned ysize,
                    unsigned gen,
                    char blank )
{
    marker[0] = blank;  // controllable display of blank space

    usleep(500000);                 // Pause 0.5sec ...
    fprintf(stdout, "\x1b[2J;");    // ...Clear display!
    fprintf(stdout, "Generation %u\n", gen);

    // Draw top border:
    fputc('+', stdout);
    for (int x = 0; x < xsize; x++)
        fputc('-', stdout);
    fputc('+', stdout);
    fputc('\n', stdout);

    // draw the "universe", row by row
    for (int y = ysize-1; y >= 0; y--) {
        fputc('|', stdout); // draw left border
        for (int x = 0; x < xsize; x++)
            fputc(marker[ (int)*(board + x + (y*xsize)) ], stdout);
        fputc('|', stdout); // draw right border
        fputc('\n', stdout);
    }

    // Draw bottom border
    fputc('+', stdout);
    for (int x = 0; x < xsize; x++)
        fputc('-', stdout);
    fputc('+', stdout);
    fputc('\n', stdout);

    fputc('\n', stdout);
    return;
}