FGroupLinearTree.hpp 12.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#ifndef _FGROUP_LINEAR_TREE_HPP_
#define _FGROUP_LINEAR_TREE_HPP_

#include <vector>
#include "../../Utils/FLog.hpp"
#include "FDistributedGroupTreeBuilder.hpp"

using FReal = double;

template<class node_t>
class FGroupLinearTree {



protected:

    int block_size;
    int nb_block;

20 21
    const inria::mpi_config& mpi_conf;

22
    std::vector<node_t>* linear_tree;
23 24
    std::vector<std::pair<MortonIndex,MortonIndex>> index_particle_distribution;
    bool unknow_index_particle_distribution = true;
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public:

////////////////////////////////////////////////
// constructor
////////////////////////////////////////////////

    /**
     * FBlockedLinearTree  Constructor of blocked linear tree
     * @author benjamin.dufoyer@inria.fr
     * @param  in_block_size    Block size needed
     * @param  in_linear_tree   Linear tree
     * @param  in_box_center    Box Center of particle container
     * @param  in_box_width     Box Width of particle container
     */
40 41
    FGroupLinearTree(const inria::mpi_config& conf):
        mpi_conf(conf),
42
        index_particle_distribution(conf.comm.size())
43 44 45
    {
        linear_tree = new std::vector<node_t>[1];
    }
46 47 48 49 50 51 52 53 54

    /**
     * This function create a blocked linear tree from the current distributed
     * linear tree
     * This function stock the linear tree with his adress
     * @author benjamin.dufoyer@inria.fr
     * @param  in_linear_tree linear tree
     * @param  in_block_size  block size
     */
55
    void create_local_group_linear_tree(
56 57 58 59 60 61 62 63 64 65 66 67 68 69
            std::vector<node_t>* in_linear_tree,
            int in_block_size
    ){
        this->create(in_linear_tree,in_block_size);
    }

    /**
     * this function create a blocked linear tree from the current distributed
     * linear tree and she redistribute block according to the block size
     * the function stock the linear tree with his adress
     * @author benjamin.dufoyer@inria.fr
     * @param  in_linear_tree linear tree
     * @param  in_block_size  blocksize needed
     */
70
    void create_global_group_linear_tree(
71
            std::vector<node_t>* in_linear_tree,
72
            int in_block_size
73 74
    ){
        this->create(in_linear_tree,in_block_size);
75
        this->redistribute_block();
76 77 78 79 80 81
    }

    void create(
        std::vector<node_t>* in_linear_tree,
        int in_block_size
    ){
82

83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
        this->block_size    = in_block_size;
        this->linear_tree   = in_linear_tree;
        this->nb_block      = (int)in_linear_tree->size()/in_block_size;
        if(this->linear_tree->size()%this->block_size != 0)
            this->nb_block += 1;
    }

////////////////////////////////////////////////
// destructor
////////////////////////////////////////////////

    ~FGroupLinearTree(){
        linear_tree = nullptr;
    }

////////////////////////////////////////////////
// Function
////////////////////////////////////////////////

    /**
     * redistribute_block redistribute leaf of the linear_tree with the good
     * block size. For N proc, N-1 proc have the same number of leaf,
     * the rest is for the proc N
     * @author benjamin.dufoyer@inria.fr
     */
108
    void redistribute_block(){
109 110

        dstr_grp_tree_builder::parrallel_build_block(
111
                        this->mpi_conf,
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
                        this->linear_tree,
                        this->block_size);
        //Update nb_block
        if(this->linear_tree->size()%block_size == 0)
            this->nb_block = (int)this->linear_tree->size()/block_size;
        else
            this->nb_block = (int)this->linear_tree->size()/block_size+1;

    }

    size_t get_nb_leaf() const{
        return this->linear_tree->size();
    }

    int get_nb_block() const{
        return this->nb_block;
    }

    int get_block_size() const{
        return this->block_size;
    }

    /**
     * get_block_size_at return the block size of the number of the block
     * placed in parametter,
     * [INFO] first block is 0
     * [INFO] last block is this->nb_block-1
     * @author benjamin.dufoyer@inria.fr
     * @param  num_block number of the block
     * @return size of the block
     */
    int get_block_size_at(int num_block) const{
        FAssertLF(num_block < this->nb_block);
        int size;
        if(num_block == this->nb_block-1){
            size = this->linear_tree->size() - ((this->nb_block-1)*this->block_size);
        } else {
            size = this->block_size;
        }
        return size;
    }

    /**
     * get_leaf_at return the leaf at the position placed in parameter
     * @author benjamin.dufoyer@inria.fr
     * @param  position position of the leaf
     * @return the leaf
     */
    node_t get_leaf_at(int position){
        return this->linear_tree->at(position);
    }

    /**
     * get_leaf_at return the leaf at the position placed in parameter
     * @author benjamin.dufoyer@inria.fr
     * @param  position position of the leaf
     * @return the leaf
     */
    node_t at(int position){
        return this->get_leaf_at(position);
    }

    size_t get_leaf_level() const{
        return this->linear_tree->back().level;
    }

    size_t get_tree_height() const{
        return this->get_leaf_level();
    }

DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
182
    size_t get_first_morton_index() const{
183 184 185
        return this->linear_tree->front().morton_index;
    }

DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
186
    size_t get_last_morton_index() const{
187 188 189
        return this->linear_tree->back().morton_index;
    }

DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
190 191 192 193
    /**
     * This function print the information of this current class
     * @author benjamin.dufoyer@inria.fr
     */
194 195 196 197
    void print_info_tree(){
        std::cout << " nb_leaf : " << this->linear_tree->size() << std::endl;
        std::cout << " nb_block : " << nb_block << std::endl;
        std::cout << " block_size : " << block_size << std::endl;
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
198 199
        for(unsigned i = 0 ; i < this->linear_tree->size() ; i++){
            std::cout << linear_tree->data()[i] << std::endl;
200 201 202
        }
    }

DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
203 204 205 206
    /**
     * This function return the linear tree associated with this calss
     * @author benjamin.dufoyer@inria.fr
     */
207 208 209 210 211
    std::vector<node_t>* get_tree(){
        return this->linear_tree;
    }

    /**
212
     * This function fill the index_particle_distribution with a call of the function
213 214 215 216 217
     * from FDistributedGroupTreeBuilder
     * @author benjamin.dufoyer@inria.fr
     * @param  particle_container [description]
     */
    template<class particle_t>
218
    void set_index_particle_distribution(
219
        std::vector<particle_t> particle_container)
220
    {
221 222
       unknow_index_particle_distribution = false;
       dstr_grp_tree_builder::share_particle_division(
223
           this->mpi_conf,
224
           particle_container,
225
           index_particle_distribution);
226 227
    }

DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
228 229 230 231 232 233 234
    void update_index_particle_distribution(std::pair<MortonIndex,MortonIndex> new_distrib){
        dstr_grp_tree_builder::share_particle_division(
            this->mpi_conf,
            new_distrib,
            index_particle_distribution);
    }

235 236
    std::vector<std::pair<MortonIndex,MortonIndex>>*
    get_index_particle_distribution(){
237
        // TO get the particle repartition, you will compute it before
238 239
        FAssert(!unknow_index_particle_distribution);
        return &this->index_particle_distribution;
240 241
    }

242
    std::pair<MortonIndex,MortonIndex> get_index_particle_distribution_at(unsigned i){
243
        // TO get the particle repartition, you will compute it before
244 245 246
        FAssert(!unknow_index_particle_distribution);
        FAssert(i < this->index_particle_distribution.size());
        return this->index_particle_distribution.data()[i];
247 248 249
    }

    /**
250 251
     * return the max morton index of the left proc
     * it's needed for the distributed construction of the groupTree
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
252
     * [RESTRICTION] you will compute the repartition before calling this function
253
     * @author benjamin.dufoyer@inria.fr
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
254
     * @return max left morton index, -1 if he doesn't exist
255
     */
256
    MortonIndex get_left_limit(){
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
257
        // Check if the repartition have been compute
258
        FAssert(!unknow_index_particle_distribution);
259
        int my_rank = this->mpi_conf.comm.rank();
260
        MortonIndex left_limit = -1;
261
        if(my_rank != 0){
262
            left_limit = (MortonIndex )this->index_particle_distribution[my_rank-1].second;
263 264 265 266 267 268 269 270 271 272 273 274
        }
        return left_limit;
    }

    /**
     * This function compute the leaf needed to build the LET part of the Group
     * Tree.
     * After she send block needed by other proc and she recev block needed
     * @author benjamin.dufoyer@inria.fr
     * @param tree      local group tree
     * [Optionial]
     * @param dim       Dimension of coordinate of particle
275 276
     */
    template<class GroupTreeClass>
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
277 278 279 280
    void create_let_group_tree_at_level(
        GroupTreeClass& tree,
        int level,
        int dim = 3
281
    ){
282
        FAssert(index_particle_distribution.size() != 0 );
283
        FAssert(dim > 0);
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
284 285 286 287 288 289 290 291 292 293 294 295
        bool leaf_level = (tree.getHeight()-1 == level);
        // Compute min and max global morton index at the level needed
        // This variable is used to put value in const
        MortonIndex gmin =  this->index_particle_distribution.front().first;
        MortonIndex gmax =  this->index_particle_distribution.back().second;
        // update the morton index
        if(!leaf_level){
            gmin = gmin >> 3;
            gmax = gmax >> 3;
        }
        const MortonIndex global_min_m_idx = gmin;
        const MortonIndex global_max_m_idx = gmax;
296 297

        // Compute min and max local morton index
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315
        const MortonIndex local_min_m_idx =
            tree.getParticleGroup(0)->getStartingIndex() >>( (tree.getHeight()-1-level)*dim);
        const MortonIndex local_max_m_idx = tree.getParticleGroup(
            (tree.getNbParticleGroup()-1) )->getEndingIndex() >>( (tree.getHeight()-1-level)*dim);

        std::vector<MortonIndex> leaf_P2P;
        if(leaf_level){
            // IDEA : can be a task
            // This function compute the leaf needed by the P2P operation
            // This function return a vector with all leaf needed
            // get leaf P2P
            leaf_P2P = dstr_grp_tree_builder::get_leaf_P2P_interaction(
                tree,
                global_min_m_idx,
                global_max_m_idx,
                local_min_m_idx,
                local_max_m_idx);
        }
316

317 318 319
        // IDEA can be a task
        // This function compute the leaf needed by the M2L operation
        // This function return a vector with all leaf needed
320
        // get leaf M2L
321 322
        std::vector<MortonIndex> leaf_M2L =
        dstr_grp_tree_builder::get_leaf_M2L_interaction_at_level(
323 324 325 326
            global_min_m_idx,
            global_max_m_idx,
            local_min_m_idx,
            local_max_m_idx,
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
327
            level,
328 329 330
            tree,
            dim);

DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
331 332 333 334 335 336 337 338 339 340 341 342 343
        std::vector<MortonIndex> needed_leaf;
        if(leaf_level){
            // this function return the concatenation of the leaf for the P2P and
            // the leaf for the M2L
            needed_leaf = dstr_grp_tree_builder::concat_M2L_P2P(leaf_P2P,leaf_M2L);
        } else {
            needed_leaf = leaf_M2L;
            this->update_index_particle_distribution(
                std::pair<MortonIndex,MortonIndex>(local_min_m_idx
                                                ,local_max_m_idx)
            );
        }

344
        std::vector<std::vector<size_t>> global_matrix_interaction = dstr_grp_tree_builder::get_matrix_interaction(
345
            needed_leaf,
346
            index_particle_distribution,
347
            this->mpi_conf);
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
348

349
        // Send and get leaf
350 351 352
        // Auto is used to get the block more easly
        // it's a vector<vector<block_t>>
        // block_t is a struct define on FDistributedGroupTreeBuilder.hpp
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
353 354
        auto let_block =
        dstr_grp_tree_builder::send_get_symbolic_block_at_level(
355 356 357
            needed_leaf,
            global_matrix_interaction,
            tree,
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
358
            level,
359
            this->mpi_conf);
360

361
        // Add the block recev to the local group tree
362
        dstr_grp_tree_builder::add_let_leaf_block_to_tree(
363 364
                tree,
                let_block,
DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
365 366
                local_min_m_idx,
                level);
367

DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
368
    }
369

DUFOYER Benjamin's avatar
DUFOYER Benjamin committed
370 371 372 373 374 375 376 377 378 379 380 381 382
        /**
         * This function is used to show the FGroupLinearTee more easly
         * @author benjamin.dufoyer@inria.fr
         */
        friend
        std::ostream& operator<<(std::ostream& os, const FGroupLinearTree& n) {
        return os << "--> Number of leaf : " << n.get_nb_leaf()
                  << "\n first leaf : "      << n.get_first_morton_index()
                  << "\n last  leaf : "      << n.get_last_morton_index()
                  << "\n block_size "          << n.get_block_size()
                  << "\n number of block : "   << n.get_nb_block();
        }

383

384 385 386
};

#endif //_FGROUP_LINEAR_TREE_HPP_