parallel_automaton_busyw.hpp

Go to the documentation of this file.

 
#ifndef PARALLEL_CELLULAR_AUTOMATA_PARALLEL_AUTOMATON_BW_HPP
#define PARALLEL_CELLULAR_AUTOMATA_PARALLEL_AUTOMATON_BW_HPP
 
#ifndef PARALLEL_CELLULAR_AUTOMATA_CELLULAR_AUTOMATA_HPP
#include "cellular_automata.hpp"
#endif
#include <barrier.hpp>
#include <grid.hpp>
#include <stdexcept>
#include <thread>
#include <threadpool.hpp>
#include <vector>
 
using namespace std;
 
namespace ca
{
namespace par
{
namespace bw
 
{
template <typename T>
class CellularAutomaton
{
  public:
    CellularAutomaton(ca::Grid<T> &grid, std::function<T(T, T, T, T, T, T, T, T, T)> update_function,
                      unsigned workers = 0)
        : grid{grid}, generation(0), update_function(update_function), pool(workers)
    {
 
        this->nw = pool.get_number_workers();
    };
    CellularAutomaton(CellularAutomaton &&other)
    {
        // move what's movable and copying numeric types.
        grid = std::move(other.grid);
        generation = other.generation;
        update_function = other.update_function;
        nw = other.nw;
        pool = std::move(other.pool);
        // set the old object in a valid state
        other.generation = 0;
    }
 
    CellularAutomaton(const CellularAutomaton &other) = delete;
 
    virtual void simulate(unsigned steps = 1)
    {
        if (steps == 0)
            return;
        // allocate new grid
        Grid<T> new_grid = Grid<T>::newWithSameSize(grid);
 
        ca::Barrier sync_point(nw);
 
        auto step_advancement_fun = [&]() {
            grid.swap(new_grid);
            ++generation;
            --steps;
        };
 
        // function to be run by each thread
        auto work = [&, this](unsigned start, unsigned end) {
            while (steps > 0)
            {
                for (unsigned r{start}; r < end; ++r)
                {
                    for (unsigned c{0}; c < grid.columns(); ++c)
                    {
                        auto cell = std::make_tuple(grid(r, c));
                        new_grid(r, c) =
                            std::apply(this->update_function, std::tuple_cat(cell, get_neighborhood(r, c)));
                    }
                }
                sync_point.busy_wait(
                    step_advancement_fun); // this gets executed only by the last thread to reach the barrier
            }
        };
 
        std::vector<std::future<void>> results; // handles for waiting the threads
        unsigned delta{static_cast<unsigned>(grid.rows()) / nw};
 
        for (unsigned i{0}; i < nw; i++) // split the grid
        {
            unsigned start = i * delta;
            unsigned end = (i != (nw - 1) ? (i + 1) * delta : grid.rows());
 
            results.push_back(pool.submit(work, start, end));
        }
 
        for (auto &r : results)
        {
            r.wait();
        }
    }
 
    virtual size_t get_generation() const
    {
        return generation;
    }
    friend std::ostream &operator<<(std::ostream &os, const CellularAutomaton &ca)
    {
 
        return os << ca.grid;
    }
 
  protected:
    Grid<T> &grid;
 
    size_t generation;
    std::function<T(T, T, T, T, T, T, T, T, T)> update_function;
    virtual std::tuple<T, T, T, T, T, T, T, T> get_neighborhood(int row, int col) const
    {
        unsigned rows = grid.rows();
        unsigned columns = grid.columns();
        T top_left, top, top_right, left, right, bottom_left, bottom, bottom_right;
        top_left = grid((row - 1 + rows) % rows, (col - 1 + columns) % columns);
        top = grid((row - 1 + rows) % rows, col);
        top_right = grid((row - 1 + rows) % rows, (col + 1) % columns);
        left = grid(row, (col - 1 + columns) % columns);
        right = grid(row, (col + 1) % columns);
        bottom_left = grid((row + 1) % rows, (col - 1 + columns) % columns);
        bottom = grid((row + 1) % rows, col);
        bottom_right = grid((row + 1) % rows, (col + 1) % columns);
        return std::make_tuple(top_left, top, top_right, left, right, bottom_left, bottom, bottom_right);
    };
    unsigned nw;
 
    Threadpool pool;
};
} // namespace bw
} // namespace par
} // namespace ca
#endif