grid_builder.h

Go to the documentation of this file.

#ifndef FPMAS_GRID_BUILDER_H
#define FPMAS_GRID_BUILDER_H
 
#include "grid.h"
#include "fpmas/random/random.h"
#include "grid_load_balancing.h"
 
namespace fpmas { namespace model { namespace detail {
 
    typedef random::Index<DiscretePoint> GridCellIndex;
 
    template<typename CellType>
        class GridBuilder : public api::model::CellNetworkBuilder<CellType> {
            protected:
                typedef std::vector<std::vector<CellType*>> CellMatrix;
 
            private:
                api::model::GridCellFactory<CellType>& cell_factory;
                DiscreteCoordinate _width;
                DiscreteCoordinate _height;
 
                mutable std::map<DiscretePoint, std::size_t> built_cells;
                mutable GridCellIndex cell_begin {&built_cells};
                mutable GridCellIndex cell_end {&built_cells};
                mutable std::map<GridCellIndex, CellType*> cell_index;
 
                CellMatrix buildLocalCells(
                        api::model::SpatialModel<CellType>& model,
                        GridDimensions local_dimensions,
                        api::model::GroupList groups) const;
 
                void allocate(
                        CellMatrix& matrix,
                        DiscreteCoordinate width,
                        DiscreteCoordinate height) const;
 
                std::vector<CellType*> _build(
                        api::model::SpatialModel<CellType>& model,
                        api::model::GroupList groups) const;
 
            protected:
                virtual void buildLocalGrid(
                        api::model::SpatialModel<CellType>& model,
                        GridDimensions local_dimensions,
                        CellMatrix& cells
                        ) const = 0;
 
                virtual void linkFrontiers(
                        api::model::SpatialModel<CellType>& model,
                        GridDimensions local_dimensions,
                        CellMatrix& local_cells,
                        std::vector<CellType*>& frontier
                        ) const = 0;
 
            public:
 
                static GridCellFactory<CellType> default_cell_factory;
 
                GridBuilder(
                    api::model::GridCellFactory<CellType>& cell_factory,
                    DiscreteCoordinate width,
                    DiscreteCoordinate height)
                : cell_factory(cell_factory), _width(width), _height(height) {
 
                }
 
                GridBuilder(
                        DiscreteCoordinate width,
                        DiscreteCoordinate height)
                    : GridBuilder(default_cell_factory, width, height) {
 
                    }
 
                DiscreteCoordinate width() const {
                    return _width;
                }
                DiscreteCoordinate height() const {
                    return _height;
                }
 
                std::vector<CellType*> build(
                        api::model::SpatialModel<CellType>& spatial_model) const override {
                    return this->_build(spatial_model, {});
                }
 
                std::vector<CellType*> build(
                        api::model::SpatialModel<CellType>& spatial_model,
                        api::model::GroupList groups) const override {
                    return this->_build(spatial_model, groups);
                }
 
                void initSample(
                        std::size_t n,
                        std::function<void(CellType*)> init_function
                        ) const;
 
                template<typename T>
                    void initSequence(
                            const std::vector<T>& items,
                            std::function<void(
                                CellType*,
                                typename std::vector<T>::const_reference
                                )> init_function
                            ) const;
 
        };
 
    template<typename CellType>
        GridCellFactory<CellType> GridBuilder<CellType>::default_cell_factory;
 
    template<typename CellType>
        void GridBuilder<CellType>::allocate(
                CellMatrix& matrix,
                DiscreteCoordinate width,
                DiscreteCoordinate height) const {
            matrix.resize(height);
            for(auto& row : matrix)
                row.resize(width);
        }
 
    template<typename CellType>
    typename GridBuilder<CellType>::CellMatrix GridBuilder<CellType>::buildLocalCells(
            api::model::SpatialModel<CellType>& model,
            GridDimensions local_dimensions,
            api::model::GroupList groups) const {
 
        DiscretePoint origin = local_dimensions.getOrigin();
        DiscretePoint extents = local_dimensions.getExtent();
 
        CellMatrix cells;
        allocate(cells, local_dimensions.width(), local_dimensions.height());
 
        for(DiscreteCoordinate y = origin.y; y < extents.y; y++) {
            for(DiscreteCoordinate x = origin.x; x < extents.x; x++) {
                auto cell = cell_factory.build({x, y});
                cells[y-origin.y][x-origin.x] = cell;
                model.add(cell);
                for(auto group : groups)
                    group.get().add(cell);
            }
        }
 
        for(DiscreteCoordinate y = 0; y < this->height(); y++)
            for(DiscreteCoordinate x = 0; x < this->width(); x++)
                built_cells.insert(std::pair<api::model::DiscretePoint, std::size_t>(
                            {x, y}, 1ul
                            ));
        
        cell_begin = GridCellIndex::begin(&built_cells);
        cell_end = GridCellIndex::end(&built_cells);
 
        for(auto row : cells) {
            for(auto cell : row) {
                // GridCellIndex offset is always 0 in this case (at most one
                // cell per coordinate)
                GridCellIndex index(&built_cells, cell->location(), 0);
                cell_index.insert({index, cell});
            }
        }
 
        // Random cell seed initialization
        std::vector<std::mt19937_64::result_type> local_seeds(
                    GridCellIndex::distance(cell_begin, cell_end)
                    );
 
        for(std::size_t i = 0; i < local_seeds.size(); i++)
            // Generates a unique integer for each, independently from the
            // current distribution
            local_seeds[i] = i;
        // Genererates a better seed distribution. The same seeds are
        // generated on all processes.
        std::seed_seq seed_generator(local_seeds.begin(), local_seeds.end());
        seed_generator.generate(local_seeds.begin(), local_seeds.end());
 
        initSequence(local_seeds, [] (
                    CellType* cell,
                    const std::mt19937_64::result_type& seed) {
                cell->seed(seed);
                });
 
        return cells;
    }
 
    template<typename CellType>
    std::vector<CellType*> GridBuilder<CellType>::_build(
            api::model::SpatialModel<CellType>& model,
            api::model::GroupList groups) const {
        typedef std::pair<std::pair<DistributedId, DiscretePoint>, std::vector<api::model::GroupId>>
            GridCellPack;
 
        CellMatrix cells;
        auto& mpi_comm = model.graph().getMpiCommunicator();
        fpmas::communication::TypedMpi<std::vector<GridCellPack>> mpi(mpi_comm);
 
        TreeProcessMapping tree_process_mapping(
                this->width(), this->height(), mpi_comm
                );
        // Represents the local grid shape built on this process
        GridDimensions local_dimensions
            = tree_process_mapping.gridDimensions(mpi_comm.getRank());
 
        // Build cells
        cells = buildLocalCells(
                model, local_dimensions, groups
                );
 
        // Build local links
        buildLocalGrid(model, local_dimensions, cells);
 
        std::unordered_map<int, std::vector<GridCellPack>> mpi_frontiers;
 
        /* exchange frontiers */
        /*
         * Exchange process:
         * When the TreeProcessMapping is used, the intuitive distribution on 4
         * processes looks as follows:
         * +------+------+
         * |  1   |  2   |
         * +------+------+
         * |  0   |  3   |
         * +------+------+
         *
         * In this case, the right frontier of 0 is sent to 3, the top frontier
         * of 0 is sent to 1, and the top right corner of 0 is sent to 2.
         *
         * There are however specific cases about corners, see below.
         */
         
        DiscreteCoordinate left_x = local_dimensions.getOrigin().x-1;
        if(left_x >= 0) {
            // left frontier
            for(DiscreteCoordinate y = 1; y < local_dimensions.height()-1; y++) {
                auto cell = cells[y][0];
                std::set<int> processes = {
                    tree_process_mapping.process({left_x, cell->location().y})
                };
                if(cell->location().y+1 < this->height())
                    processes.insert(
                            tree_process_mapping.process({left_x, cell->location().y+1})
                            );
                if(cell->location().y-1 >= 0)
                    processes.insert(
                            tree_process_mapping.process({left_x, cell->location().y-1})
                            );
 
                for(int process : processes) {
                    mpi_frontiers[process].push_back(
                            {{cell->node()->getId(), cell->location()}, cell->groupIds()});
                }
            }
        }
        DiscreteCoordinate bottom_y = local_dimensions.getOrigin().y-1;
        if(bottom_y >= 0) {
            // bottom frontier
            for(DiscreteCoordinate x = 1; x < local_dimensions.width()-1; x++) {
                auto cell = cells[0][x];
                std::set<int> processes = {
                    tree_process_mapping.process({cell->location().x, bottom_y})
                };
                if(cell->location().x+1 < this->width())
                    processes.insert(
                            tree_process_mapping.process({cell->location().x+1, bottom_y})
                    );
                if(cell->location().x-1 >= 0)
                    processes.insert(
                            tree_process_mapping.process({cell->location().x-1, bottom_y})
                    );
                for(int process : processes) {
                    mpi_frontiers[process].push_back(
                            {{cell->node()->getId(), cell->location()}, cell->groupIds()});
                }
            }
 
        }
        DiscreteCoordinate right_x = local_dimensions.getExtent().x;
        if(right_x < this->width()) {
            // right frontier
            for(DiscreteCoordinate y = 1; y < local_dimensions.height()-1; y++) {
                auto cell = cells[y][local_dimensions.width()-1];
                std::set<int> processes = {
                    tree_process_mapping.process({right_x, cell->location().y})
                };
                if(cell->location().y+1 < this->height())
                    processes.insert(
                            tree_process_mapping.process({right_x, cell->location().y+1})
                    );
                // if y == 0, this corner is checked at bottom frontier
                if(cell->location().y-1 >= 0)
                    processes.insert(
                            tree_process_mapping.process({right_x, cell->location().y-1})
                    );
                for(int process : processes) {
                    mpi_frontiers[process].push_back(
                            {{cell->node()->getId(), cell->location()}, cell->groupIds()});
                }
            }
        }
        
        DiscreteCoordinate top_y = local_dimensions.getExtent().y;
        if(top_y < this->height()) {
            // top frontier
            for(DiscreteCoordinate x = 1; x < local_dimensions.width()-1; x++) {
                auto cell = cells[local_dimensions.height()-1][x];
                std::set<int> processes = {
                    tree_process_mapping.process({cell->location().x, top_y})
                };
                
                // if x == local_dimensions.width()-1, this corner is checked
                // by the right frontier
                if(cell->location().x+1 < this->width())
                    processes.insert(
                            tree_process_mapping.process({cell->location().x+1, top_y})
                            );
                if(cell->location().x-1 >= 0)
                    processes.insert(
                            tree_process_mapping.process({cell->location().x-1, top_y})
                            );
 
                for(int process : processes) {
                    mpi_frontiers[process].push_back(
                            {{cell->node()->getId(), cell->location()}, cell->groupIds()});
                }
            }
        }
 
        /* corners */
 
        /*
         * Note about corners:
         *
         * When the TreeProcessMapping is used, the distributed grid might have
         * the following shape on 4 processes (where 3's width is greater than
         * 2's width):
         * +------+---+----+
         * |  1   |   |    |
         * +------| 2 |  3 |
         * |  0   |   |    |
         * +------+---+----+
         *
         * In that case, for example, the top right corner of the process 0
         * should **not** be sent again to 2, since it has already been sent as
         * the right frontier of process 0.
         *
         * The following cases prevent all those issues.
         */
        if(local_dimensions.height() > 0 && local_dimensions.width() > 0) {
            std::set<int> corners_processes;
            // Bottom left corner
            {
                auto cell = cells[0][0];
                std::set<int> processes;
                auto x = cell->location().x;
                auto y = cell->location().y;
                if(y-1 >= 0) {
                    processes.insert(
                            tree_process_mapping.process({x, y-1})
                            );
                    if(x-1 >= 0)
                        processes.insert(
                                tree_process_mapping.process({x-1, y-1})
                                );
                    if(x+1 < this->width())
                        processes.insert(
                                tree_process_mapping.process({x+1, y-1})
                                );
                }
                if(x-1 >= 0) {
                    processes.insert(
                            tree_process_mapping.process({x-1, y})
                            );
                    if(y+1 < this->height())
                        processes.insert(
                                tree_process_mapping.process({x-1, y+1})
                                );
                }
                for(int process : processes) {
                    mpi_frontiers[process].push_back(
                            {{cell->node()->getId(), cell->location()}, cell->groupIds()});
                    corners_processes.insert(processes.begin(), processes.end());
                }
            }
 
            {
                // Bottom right corner
                auto cell = cells[0][local_dimensions.width()-1];
                std::set<int> processes;
                auto x = cell->location().x;
                auto y = cell->location().y;
                if(y-1 >= 0) {
                    processes.insert(
                            tree_process_mapping.process({x, y-1})
                            );
                    if(x-1 >= 0)
                        processes.insert(
                                tree_process_mapping.process({x-1, y-1})
                                );
                    if(x+1 < this->width())
                        processes.insert(
                                tree_process_mapping.process({x+1, y-1})
                                );
                }
                if(x+1 < this->width()) {
                    processes.insert(
                            tree_process_mapping.process({x+1, y})
                            );
                    if(y+1 < this->height())
                        processes.insert(
                                tree_process_mapping.process({x+1, y+1})
                                );
                }
                for(int process : processes) {
                    mpi_frontiers[process].push_back(
                            {{cell->node()->getId(), cell->location()}, cell->groupIds()});
                    corners_processes.insert(processes.begin(), processes.end());
                }
            }
 
            // Top left corner
            {
                auto cell = cells[local_dimensions.height()-1][0];
                std::set<int> processes;
                auto x = cell->location().x;
                auto y = cell->location().y;
                if(y+1 < this->height()) {
                    processes.insert(
                            tree_process_mapping.process({x, y+1})
                            );
                    if(x-1 >= 0)
                        processes.insert(
                                tree_process_mapping.process({x-1, y+1})
                                );
                    if(x+1 < this->width())
                        processes.insert(
                                tree_process_mapping.process({x+1, y+1})
                                );
                }
                if(x-1 >= 0) {
                    processes.insert(
                            tree_process_mapping.process({x-1, y})
                            );
                    if(y-1 >= 0)
                        processes.insert(
                                tree_process_mapping.process({x-1, y+1})
                                );
                }
                for(int process : processes) {
                    mpi_frontiers[process].push_back(
                            {{cell->node()->getId(), cell->location()}, cell->groupIds()});
                    corners_processes.insert(processes.begin(), processes.end());
                }
            }
 
            // Top right corner
            {
                auto cell = cells[local_dimensions.height()-1][local_dimensions.width()-1];
                std::set<int> processes;
                auto x = cell->location().x;
                auto y = cell->location().y;
                if(y+1 < this->height()) {
                    processes.insert(
                            tree_process_mapping.process({x, y+1})
                            );
                    if(x-1 >= 0)
                        processes.insert(
                                tree_process_mapping.process({x-1, y+1})
                                );
                    if(x+1 < this->width())
                        processes.insert(
                                tree_process_mapping.process({x+1, y+1})
                                );
                }
                if(x+1 < this->width()) {
                    processes.insert(
                            tree_process_mapping.process({x+1, y})
                            );
                    if(y-1 >= 0)
                        processes.insert(
                                tree_process_mapping.process({x+1, y-1})
                                );
                }
                for(int process : processes) {
                    mpi_frontiers[process].push_back(
                            {{cell->node()->getId(), cell->location()}, cell->groupIds()});
                    corners_processes.insert(processes.begin(), processes.end());
                }
            }
            if(local_dimensions.width() <= 2 || local_dimensions.height() <=2) {
                // Edge case, some corner cells are added several times to some
                // frontiers
 
                auto less_grid_cell_pack = [](const GridCellPack& p1, const GridCellPack& p2) {
                    return p1.first.first < p2.first.first;
                };
                for(int process : corners_processes) {
                    std::set<GridCellPack, decltype(less_grid_cell_pack)> packs(less_grid_cell_pack);
                    for(auto pack : mpi_frontiers[process])
                        packs.insert(pack);
                    mpi_frontiers[process].clear();
                    for(auto pack : packs)
                        mpi_frontiers[process].push_back(pack);
                }
            }
        }
 
        
 
        mpi_frontiers = mpi.allToAll(mpi_frontiers);
 
        std::vector<CellType*> cell_frontiers;
        for(auto frontier : mpi_frontiers) {
            for(auto cell_pack : frontier.second) {
                // Builds a temporary cell
                auto cell = cell_factory.build(cell_pack.first.second);
                // Cells group ids must be updated before it is
                // inserted in the graph
                for(auto gid : cell_pack.second)
                    cell->addGroupId(gid);
 
                // Builds a temporary node representing the node on the
                // frontier (that is located on an other process)
                api::graph::DistributedNode<AgentPtr>* tmp_node
                    = new graph::DistributedNode<AgentPtr>(cell_pack.first.first, cell);
                tmp_node->setLocation(frontier.first);
                model.graph().insertDistant(tmp_node);
                cell_frontiers.push_back(cell);
            }
        }
 
        linkFrontiers(model, local_dimensions, cells, cell_frontiers);
 
        model.graph().synchronize();
        std::vector<CellType*> built_cells;
        for(auto row : cells)
            for(auto cell : row)
                built_cells.push_back(cell);
        return built_cells;
    }
 
    template<typename CellType>
        void GridBuilder<CellType>::initSample(
                std::size_t n,
                std::function<void(CellType*)> init_function) const {
            std::vector<GridCellIndex> indexes = random::sample_indexes(
                    cell_begin, cell_end, n, RandomGridAgentBuilder::rd);
            for(auto index : indexes) {
                auto it = cell_index.find(index);
                if(it != cell_index.end())
                    init_function(it->second);
            }
        }
 
    template<typename CellType>
        template<typename T>
        void GridBuilder<CellType>::initSequence(
                const std::vector<T> &items,
                std::function<void (
                    CellType*,
                    typename std::vector<T>::const_reference
                    )> init_function) const {
            GridCellIndex grid_index = cell_begin;
            auto map_index = cell_index.begin();
            std::size_t i = 0;
            while(map_index != cell_index.end()) {
                if(map_index->first == grid_index) {
                    init_function(
                            map_index->second,
                            items[i]
                            );
                    ++map_index;
                }
                ++grid_index;
                ++i;
            }
        }
 
}}}
#endif