mardi 26 février 2019

How to implement the Game of Life in parallel using C++ threads?

I have implemented a sequential version of the Game of Life but now I want to parallelize it. I'm trying to learn how to use C++ threads, thread barriers, and maybe even the future library to speed up this implementation. I'm not sure how to go about this. Advice would be greatly appreciated!

Here is my sequential implementation:

GameOfLife.h:

#include <vector>
#include <tuple>
using namespace std;


class GameOfLife {

    public:

        vector<vector<int> > SimulateLife(vector<vector<int> > &board, int life_cycles);

    private:

        vector<vector<int> > board;

        int CheckNeighbors(vector<vector<int> > &board, int row, int col);
        void UpdateBoard(vector<vector<int> > &board, vector<tuple<int, int> > &liveSpots,
                     vector<tuple<int, int> > &deadSpots);
};


//Checks all 8 neighbors of the current cell to see if they are alive
//If they are alive add one to liveNeighbors

int GameOfLife::CheckNeighbors(vector<vector<int> > &board, int row, int col) {
    int liveNeighbors = 0;

    if(board[(board.size()+row-1)%board.size()][(board.size()+col-1)%board.size()] == 1)
        liveNeighbors++;

    if(board[(board.size()+row-1)%board.size()][col] == 1)
        liveNeighbors++;

    if(board[(board.size()+row-1)%board.size()][(board.size()+col+1)%board.size()] == 1)
        liveNeighbors++;

    if(board[row][(board.size()+col+1)%board.size()] == 1)
        liveNeighbors++;

    if(board[(board.size()+row+1)%board.size()][(board.size()+col+1)%board.size()] == 1)
        liveNeighbors++;

    if(board[(board.size()+row+1)%board.size()][col] == 1)
        liveNeighbors++;

    if(board[(board.size()+row+1)%board.size()][(board.size()+col-1)%board.size()] == 1)
        liveNeighbors++;

    if(board[row][(board.size()+col-1)%board.size()] == 1)
        liveNeighbors++;

    return liveNeighbors;
}


//Using the x,y tuples, updates the board with dead
//and alive cells after a life cycle

void GameOfLife::UpdateBoard(vector<vector<int> > &board, vector<tuple<int, int> > &liveSpots,
                         vector<tuple<int, int> > &deadSpots) {

    for(tuple<int, int> t : liveSpots)
        board[get<0>(t)][get<1>(t)] = 1;

    for(tuple<int, int> t : deadSpots)
        board[get<0>(t)][get<1>(t)] = 0;
}


//Loops over every cell for the number of life cycles
//If the cell's value is 2, it will never die (small change to real game)

//If the cell's value is 1, it is currently alive. 
//Check number of alive neighbors to see if it dies or stays alive

//If the cell's value is 0, it is currently dead.
//Check the number of alive neighbors to see if it becomes alive or stays dead

vector<vector<int> > GameOfLife::SimulateLife(vector<vector<int> > &board, int life_cycles) {

    for(int cycles = life_cycles; life_cycles > 0; life_cycles--) {
        vector<tuple<int, int> > liveSpots;
        vector<tuple<int, int> > deadSpots;

        for(int row = 0; row < board.size(); row++) {
            for(int col = 0; col < board.size(); col++) {
                int aliveNeighbors = 0;

                if(board[row][col] == 2)
                    break;

                if(board[row][col] == 1) {
                    aliveNeighbors = CheckNeighbors(board, row, col);
                    if(aliveNeighbors < 2 || aliveNeighbors > 3)
                        deadSpots.push_back(make_tuple(row, col));
                }

                if(board[row][col] == 0) {
                    aliveNeighbors = CheckNeighbors(board, row, col);
                    if(aliveNeighbors == 3)
                        liveSpots.push_back(make_tuple(row, col));
                }
            }
        }

        UpdateBoard(board, liveSpots, deadSpots);
    }

    return board;
}

Main.cc:

#include <iostream>
#include <vector>
#include "GameOfLife.h"
using namespace std;


void print_board(vector<vector<int> > &board) {
    int n = board.size();

    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}


int main() {
    int n;
    cin >> n;

    vector<vector<int> > board;
    board.resize(n);

    for (int i=0;i<n;i++) {
        board[i].resize(n);
        for (int j=0;j<n;j++) {
            cin >> board[i][j];
        }
    }

    int k;
    cin >> k;

    GameOfLife obj;
    vector<vector<int> > result;
    result = obj.SimulateLife(board,k);
    print_board(result);
}

Aucun commentaire:

Enregistrer un commentaire