p2p_distr_mpi.hpp 45.4 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef P2P_DISTR_MPI_HPP
#define P2P_DISTR_MPI_HPP

#include <mpi.h>

#include <vector>
#include <memory>
#include <cassert>

#include <type_traits>
#include <omp.h>
#include <algorithm>

#include "scope_timer.hpp"
#include "particles_utils.hpp"
#include "p2p_tree.hpp"
17
#include "lock_free_bool_array.hpp"
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

template <class partsize_t, class real_number>
class p2p_distr_mpi {
protected:
    static const int MaxNbRhs = 100;

    enum MpiTag{
        TAG_NB_PARTICLES,
        TAG_POSITION_PARTICLES,
        TAG_RESULT_PARTICLES,
    };

    struct NeighborDescriptor{
        partsize_t nbParticlesToExchange;
        int destProc;
        int nbLevelsToExchange;
        bool isRecv;
35
        bool positionsReceived;
36
37
38

        std::unique_ptr<real_number[]> toRecvAndMerge;
        std::unique_ptr<real_number[]> toCompute;
39
        std::unique_ptr<real_number[]> toData;
40
41
42
43
44
45
46
        std::unique_ptr<real_number[]> results;
    };

    enum Action{
        NOTHING_TODO,
        RECV_PARTICLES,
        COMPUTE_PARTICLES,
47
        CHECK_PARTICLES,
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
        RELEASE_BUFFER_PARTICLES,
        MERGE_PARTICLES,

        RECV_MOVE_NB_LOW,
        RECV_MOVE_NB_UP,
        RECV_MOVE_LOW,
        RECV_MOVE_UP
    };

    MPI_Comm current_com;

    int my_rank;
    int nb_processes;
    int nb_processes_involved;

    const std::pair<int,int> current_partition_interval;
    const int current_partition_size;
    const std::array<size_t,3> field_grid_dim;

    std::unique_ptr<int[]> partition_interval_size_per_proc;
    std::unique_ptr<int[]> partition_interval_offset_per_proc;

    std::unique_ptr<partsize_t[]> current_offset_particles_for_partition;

    std::vector<std::pair<Action,int>> whatNext;
    std::vector<MPI_Request> mpiRequests;
    std::vector<NeighborDescriptor> neigDescriptors;

    std::array<real_number,3> spatial_box_width;
    std::array<real_number,3> spatial_box_offset;

79
    const real_number cutoff_radius_compute;
80
    const int nb_cells_factor;
81
82
83
    const real_number cutoff_radius;
    std::array<long int,3> nb_cell_levels;

84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
    template <class DataType, int sizeElement>
    static void permute_copy(const partsize_t offsetIdx, const partsize_t nbElements,
                             const std::pair<long int,partsize_t> permutation[],
                             DataType data[], std::vector<unsigned char>* buffer){
        buffer->resize(nbElements*sizeof(DataType)*sizeElement);
        DataType* dataBuffer = reinterpret_cast<DataType*>(buffer->data());

        // Permute
        for(partsize_t idxPart = 0 ; idxPart < nbElements ; ++idxPart){
            const partsize_t srcData = permutation[idxPart].second;
            const partsize_t destData = idxPart;
            for(int idxVal = 0 ; idxVal < sizeElement ; ++idxVal){
                dataBuffer[destData*sizeElement + idxVal]
                        = data[srcData*sizeElement + idxVal];
            }
        }

        // Copy back
        for(partsize_t idxPart = 0 ; idxPart < nbElements ; ++idxPart){
            const partsize_t srcData = idxPart;
            const partsize_t destData = idxPart+offsetIdx;
            for(int idxVal = 0 ; idxVal < sizeElement ; ++idxVal){
                data[destData*sizeElement + idxVal]
                        = dataBuffer[srcData*sizeElement + idxVal];
            }
        }
    }

112
    static int foundGridFactor(const real_number in_cutoff_radius, const std::array<real_number,3>& in_spatial_box_width){
113
114
115
116
        int idx_factor = 1;
        while(in_cutoff_radius <= in_spatial_box_width[IDX_Z]/real_number(idx_factor+1)){
            idx_factor += 1;
        }
117
        return idx_factor;
118
119
    }

120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
public:
    ////////////////////////////////////////////////////////////////////////////

    p2p_distr_mpi(MPI_Comm in_current_com,
                     const std::pair<int,int>& in_current_partitions,
                     const std::array<size_t,3>& in_field_grid_dim,
                     const std::array<real_number,3>& in_spatial_box_width,
                     const std::array<real_number,3>& in_spatial_box_offset,
                     const real_number in_cutoff_radius)
        : current_com(in_current_com),
            my_rank(-1), nb_processes(-1),nb_processes_involved(-1),
            current_partition_interval(in_current_partitions),
            current_partition_size(current_partition_interval.second-current_partition_interval.first),
            field_grid_dim(in_field_grid_dim),
            spatial_box_width(in_spatial_box_width), spatial_box_offset(in_spatial_box_offset),
135
            cutoff_radius_compute(in_cutoff_radius),
136
137
            nb_cells_factor(foundGridFactor(in_cutoff_radius, in_spatial_box_width)),
            cutoff_radius(in_spatial_box_width[IDX_Z]/real_number(nb_cells_factor)){
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

        AssertMpi(MPI_Comm_rank(current_com, &my_rank));
        AssertMpi(MPI_Comm_size(current_com, &nb_processes));

        partition_interval_size_per_proc.reset(new int[nb_processes]);
        AssertMpi( MPI_Allgather( const_cast<int*>(&current_partition_size), 1, MPI_INT,
                                  partition_interval_size_per_proc.get(), 1, MPI_INT,
                                  current_com) );
        assert(partition_interval_size_per_proc[my_rank] == current_partition_size);

        partition_interval_offset_per_proc.reset(new int[nb_processes+1]);
        partition_interval_offset_per_proc[0] = 0;
        for(int idxProc = 0 ; idxProc < nb_processes ; ++idxProc){
            partition_interval_offset_per_proc[idxProc+1] = partition_interval_offset_per_proc[idxProc] + partition_interval_size_per_proc[idxProc];
        }

        current_offset_particles_for_partition.reset(new partsize_t[current_partition_size+1]);

        nb_processes_involved = nb_processes;
        while(nb_processes_involved != 0 && partition_interval_size_per_proc[nb_processes_involved-1] == 0){
            nb_processes_involved -= 1;
        }
        assert(nb_processes_involved != 0);
        for(int idx_proc_involved = 0 ; idx_proc_involved < nb_processes_involved ; ++idx_proc_involved){
            assert(partition_interval_size_per_proc[idx_proc_involved] != 0);
        }

        assert(int(field_grid_dim[IDX_Z]) == partition_interval_offset_per_proc[nb_processes_involved]);

167
168
169
        nb_cell_levels[IDX_X] = nb_cells_factor;
        nb_cell_levels[IDX_Y] = nb_cells_factor;
        nb_cell_levels[IDX_Z] = nb_cells_factor;
170
171
172
173
174
175
    }

    virtual ~p2p_distr_mpi(){}

    ////////////////////////////////////////////////////////////////////////////

176
177
178
179
180
181
182
183
    int getGridFactor() const{
        return nb_cells_factor;
    }

    real_number getGridCutoff() const{
        return cutoff_radius;
    }

184
185
186
187
188
    long int get_cell_coord_x_from_index(const long int index) const{
        return index % nb_cell_levels[IDX_X];
    }

    long int get_cell_coord_y_from_index(const long int index) const{
189
        return (index % (nb_cell_levels[IDX_X]*nb_cell_levels[IDX_Y]))
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
                / nb_cell_levels[IDX_X];
    }

    long int get_cell_coord_z_from_index(const long int index) const{
        return index / (nb_cell_levels[IDX_X]*nb_cell_levels[IDX_Y]);
    }

    long int first_cell_level_proc(const int dest_proc) const{
        const real_number field_section_width_z = spatial_box_width[IDX_Z]/real_number(field_grid_dim[IDX_Z]);
        return static_cast<long int>((field_section_width_z*real_number(partition_interval_offset_per_proc[dest_proc]))/cutoff_radius);
    }

    long int last_cell_level_proc(const int dest_proc) const{
        const real_number field_section_width_z = spatial_box_width[IDX_Z]/real_number(field_grid_dim[IDX_Z]);
        return static_cast<long int>((field_section_width_z*real_number(partition_interval_offset_per_proc[dest_proc+1])
                                     - std::numeric_limits<real_number>::epsilon())/cutoff_radius);
    }

208
209
210
211
212
213
214
215
216
217
    real_number apply_pbc(real_number pos, IDXS_3D dim) const{
        while( pos < spatial_box_offset[dim] ){
            pos += spatial_box_width[dim];
        }
        while( spatial_box_width[dim]+spatial_box_offset[dim] <= pos){
            pos -= spatial_box_width[dim];
        }
        return pos;
    }

218
219
    std::array<long int,3> get_cell_coordinate(const real_number pos_x, const real_number pos_y,
                                               const real_number pos_z) const {
220
221
222
        const real_number diff_x = apply_pbc(pos_x,IDX_X) - spatial_box_offset[IDX_X];
        const real_number diff_y = apply_pbc(pos_y,IDX_Y) - spatial_box_offset[IDX_Y];
        const real_number diff_z = apply_pbc(pos_z,IDX_Z) - spatial_box_offset[IDX_Z];
223
224
225
226
227
228
229
230
231
232
233
234
235
236
        std::array<long int,3> coord;
        coord[IDX_X] = static_cast<long int>(diff_x/cutoff_radius);
        coord[IDX_Y] = static_cast<long int>(diff_y/cutoff_radius);
        coord[IDX_Z] = static_cast<long int>(diff_z/cutoff_radius);
        return coord;
    }

    long int get_cell_idx(const real_number pos_x, const real_number pos_y,
                          const real_number pos_z) const {
        std::array<long int,3> coord = get_cell_coordinate(pos_x, pos_y, pos_z);
        return ((coord[IDX_Z]*nb_cell_levels[IDX_Y])+coord[IDX_Y])*nb_cell_levels[IDX_X]+coord[IDX_X];
    }

    real_number compute_distance_r2(const real_number x1, const real_number y1, const real_number z1,
Berenger Bramas's avatar
Berenger Bramas committed
237
238
                                    const real_number x2, const real_number y2, const real_number z2,
                                    const real_number xshift_coef, const real_number yshift_coef, const real_number zshift_coef) const {
239
        real_number diff_x = std::abs(apply_pbc(x1,IDX_X)-apply_pbc(x2,IDX_X)+xshift_coef*spatial_box_width[IDX_X]);
Berenger Bramas's avatar
Berenger Bramas committed
240
        assert(diff_x <= 2*cutoff_radius);
241

242
        real_number diff_y = std::abs(apply_pbc(y1,IDX_X)-apply_pbc(y2,IDX_X)+yshift_coef*spatial_box_width[IDX_Y]);
Berenger Bramas's avatar
Berenger Bramas committed
243
        assert(diff_y <= 2*cutoff_radius);
244

245
        real_number diff_z = std::abs(apply_pbc(z1,IDX_X)-apply_pbc(z2,IDX_X)+zshift_coef*spatial_box_width[IDX_Z]);
Berenger Bramas's avatar
Berenger Bramas committed
246
        assert(diff_z <= 2*cutoff_radius);
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
247
248
249

        return (diff_x*diff_x) + (diff_y*diff_y) + (diff_z*diff_z);
    }
250

251
    template <class computer_class, int size_particle_positions, int size_particle_data, int size_particle_rhs>
252
253
254
    void compute_distr(computer_class& in_computer,
                       const partsize_t current_my_nb_particles_per_partition[],
                       real_number particles_positions[],
255
                       real_number particles_data[],
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
                       real_number particles_current_rhs[],
                       partsize_t inout_index_particles[]){
        TIMEZONE("compute_distr");

        // Some processes might not be involved
        if(nb_processes_involved <= my_rank){
            return;
        }

        const long int my_top_z_cell_level = last_cell_level_proc(my_rank);
        const long int my_down_z_cell_level = first_cell_level_proc(my_rank);
        const long int my_nb_cell_levels = 1+my_top_z_cell_level-my_down_z_cell_level;

        current_offset_particles_for_partition[0] = 0;
        partsize_t myTotalNbParticles = 0;
        for(int idxPartition = 0 ; idxPartition < current_partition_size ; ++idxPartition){
            myTotalNbParticles += current_my_nb_particles_per_partition[idxPartition];
            current_offset_particles_for_partition[idxPartition+1] = current_offset_particles_for_partition[idxPartition] + current_my_nb_particles_per_partition[idxPartition];
        }

        // Compute box idx for each particle
        std::unique_ptr<long int[]> particles_coord(new long int[current_offset_particles_for_partition[current_partition_size]]);

        {
            for(int idxPartition = 0 ; idxPartition < current_partition_size ; ++idxPartition){
                #pragma omp parallel for schedule(static)
                for(partsize_t idxPart = current_offset_particles_for_partition[idxPartition] ; idxPart < current_offset_particles_for_partition[idxPartition+1] ; ++idxPart ){
                    particles_coord[idxPart] = get_cell_idx(particles_positions[(idxPart)*size_particle_positions + IDX_X],
                                                                              particles_positions[(idxPart)*size_particle_positions + IDX_Y],
                                                                              particles_positions[(idxPart)*size_particle_positions + IDX_Z]);
                    assert(my_down_z_cell_level <= get_cell_coord_z_from_index(particles_coord[idxPart]));
                    assert(get_cell_coord_z_from_index(particles_coord[idxPart]) <= my_top_z_cell_level);
                }
            }

291
            std::vector<std::pair<long int,partsize_t>> part_to_sort;
292
293
294
295
296
297
298

            // Sort each partition in cells
            for(int idxPartition = 0 ; idxPartition < current_partition_size ; ++idxPartition){
                part_to_sort.clear();

                for(partsize_t idxPart = current_offset_particles_for_partition[idxPartition] ; idxPart < current_offset_particles_for_partition[idxPartition+1] ; ++idxPart ){
                    part_to_sort.emplace_back();
299
300
                    part_to_sort.back().first = particles_coord[idxPart];
                    part_to_sort.back().second = idxPart;
301
302
                }

303
                assert(partsize_t(part_to_sort.size()) == (current_my_nb_particles_per_partition[idxPartition]));
304
305

                std::sort(part_to_sort.begin(), part_to_sort.end(),
306
307
308
                          [](const std::pair<long int,partsize_t>& p1,
                             const std::pair<long int,partsize_t>& p2){
                    return p1.first < p2.first;
309
                });
310
311
312
313
314
315

                // Permute array using buffer
                std::vector<unsigned char> buffer;
                permute_copy<real_number, size_particle_positions>(current_offset_particles_for_partition[idxPartition],
                                                                   current_my_nb_particles_per_partition[idxPartition],
                                                                   part_to_sort.data(), particles_positions, &buffer);
316
317
318
                permute_copy<real_number, size_particle_data>(current_offset_particles_for_partition[idxPartition],
                                                             current_my_nb_particles_per_partition[idxPartition],
                                                             part_to_sort.data(), particles_data, &buffer);
319
320
321
322
323
324
325
326
327
                permute_copy<real_number, size_particle_rhs>(current_offset_particles_for_partition[idxPartition],
                                                             current_my_nb_particles_per_partition[idxPartition],
                                                             part_to_sort.data(), particles_current_rhs, &buffer);
                permute_copy<partsize_t, 1>(current_offset_particles_for_partition[idxPartition],
                                            current_my_nb_particles_per_partition[idxPartition],
                                            part_to_sort.data(), inout_index_particles, &buffer);
                permute_copy<long int, 1>(current_offset_particles_for_partition[idxPartition],
                                            current_my_nb_particles_per_partition[idxPartition],
                                            part_to_sort.data(), particles_coord.get(), &buffer);
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
            }
        }

        // Build the tree
        p2p_tree<std::vector<std::pair<partsize_t,partsize_t>>> my_tree(nb_cell_levels);

        for(int idxPartition = 0 ; idxPartition < current_partition_size ; ++idxPartition){
            long int current_cell_idx = -1;
            partsize_t current_nb_particles_in_cell = 0;
            partsize_t current_cell_offset = 0;

            for(partsize_t idx_part = current_offset_particles_for_partition[idxPartition] ;
                            idx_part != current_offset_particles_for_partition[idxPartition+1]; ++idx_part){
                if(particles_coord[idx_part] != current_cell_idx){
                    if(current_nb_particles_in_cell){
                        my_tree.getCell(current_cell_idx).emplace_back(current_cell_offset,current_nb_particles_in_cell);
                    }
                    current_cell_idx = particles_coord[idx_part];
                    current_nb_particles_in_cell = 1;
                    current_cell_offset = idx_part;
348
349
350
                }
                else{
                    current_nb_particles_in_cell += 1;
351
352
353
354
355
356
357
358
359
                }
            }
            if(current_nb_particles_in_cell){
                my_tree.getCell(current_cell_idx).emplace_back(current_cell_offset,current_nb_particles_in_cell);

            }
        }

        // Offset per cell layers
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
360
        long int previous_index = 0;
361
362
363
364
        std::unique_ptr<partsize_t[]> particles_offset_layers(new partsize_t[my_nb_cell_levels+1]());
        for(int idxPartition = 0 ; idxPartition < current_partition_size ; ++idxPartition){
            for(partsize_t idx_part = current_offset_particles_for_partition[idxPartition] ;
                            idx_part != current_offset_particles_for_partition[idxPartition+1]; ++idx_part){
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
365
366
367
368
369
370
                const long int part_box_z_index = get_cell_coord_z_from_index(particles_coord[idx_part]);
                assert(my_down_z_cell_level <= part_box_z_index);
                assert(part_box_z_index <= my_top_z_cell_level);
                particles_offset_layers[part_box_z_index+1-my_down_z_cell_level] += 1;
                assert(previous_index <= part_box_z_index);
                previous_index = part_box_z_index;
371
372
            }
        }
373
        for(long int idx_layer = 0 ; idx_layer < my_nb_cell_levels ; ++idx_layer){
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
            particles_offset_layers[idx_layer+1] += particles_offset_layers[idx_layer];
        }

        // Reset vectors
        assert(whatNext.size() == 0);
        assert(mpiRequests.size() == 0);
        neigDescriptors.clear();

        // Find process with at least one neighbor
        {
            int dest_proc = (my_rank+1)%nb_processes_involved;
            while(dest_proc != my_rank
                  && (my_top_z_cell_level == first_cell_level_proc(dest_proc)
                      || (my_top_z_cell_level+1)%nb_cell_levels[IDX_Z] == first_cell_level_proc(dest_proc))){
                // Find if we have to send 1 or 2 cell levels
                int nb_levels_to_send = 1;
                if(my_nb_cell_levels > 1 // I have more than one level
                        && (my_top_z_cell_level-1+2)%nb_cell_levels[IDX_Z] <= last_cell_level_proc(dest_proc)){
                    nb_levels_to_send += 1;
                }

                NeighborDescriptor descriptor;
                descriptor.destProc = dest_proc;
                descriptor.nbLevelsToExchange = nb_levels_to_send;
                descriptor.nbParticlesToExchange = particles_offset_layers[my_nb_cell_levels] - particles_offset_layers[my_nb_cell_levels-nb_levels_to_send];
                descriptor.isRecv = false;
400
                descriptor.positionsReceived = false;
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422

                neigDescriptors.emplace_back(std::move(descriptor));

                dest_proc = (dest_proc+1)%nb_processes_involved;
            }

            int src_proc = (my_rank-1+nb_processes_involved)%nb_processes_involved;
            while(src_proc != my_rank
                  && (last_cell_level_proc(src_proc) == my_down_z_cell_level
                      || (last_cell_level_proc(src_proc)+1)%nb_cell_levels[IDX_Z] == my_down_z_cell_level)){
                // Find if we have to send 1 or 2 cell levels
                int nb_levels_to_recv = 1;
                if(my_nb_cell_levels > 1 // I have more than one level
                        && first_cell_level_proc(src_proc) <= (my_down_z_cell_level-1+2)%nb_cell_levels[IDX_Z]){
                    nb_levels_to_recv += 1;
                }

                NeighborDescriptor descriptor;
                descriptor.destProc = src_proc;
                descriptor.nbLevelsToExchange = nb_levels_to_recv;
                descriptor.nbParticlesToExchange = -1;
                descriptor.isRecv = true;
423
                descriptor.positionsReceived = false;
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454

                neigDescriptors.emplace_back(std::move(descriptor));

                src_proc = (src_proc-1+nb_processes_involved)%nb_processes_involved;
            }
        }

        //////////////////////////////////////////////////////////////////////
        /// Exchange the number of particles in each partition
        /// Could involve only here but I do not think it will be a problem
        //////////////////////////////////////////////////////////////////////

        assert(whatNext.size() == 0);
        assert(mpiRequests.size() == 0);


        for(int idxDescr = 0 ; idxDescr < int(neigDescriptors.size()) ; ++idxDescr){
            NeighborDescriptor& descriptor = neigDescriptors[idxDescr];

            if(descriptor.isRecv == false){
                whatNext.emplace_back(std::pair<Action,int>{NOTHING_TODO, -1});
                mpiRequests.emplace_back();
                AssertMpi(MPI_Isend(const_cast<partsize_t*>(&descriptor.nbParticlesToExchange),
                                    1, particles_utils::GetMpiType(partsize_t()),
                                    descriptor.destProc, TAG_NB_PARTICLES,
                                    current_com, &mpiRequests.back()));

                if(descriptor.nbParticlesToExchange){
                    whatNext.emplace_back(std::pair<Action,int>{NOTHING_TODO, -1});
                    mpiRequests.emplace_back();
                    assert(descriptor.nbParticlesToExchange*size_particle_positions < std::numeric_limits<int>::max());
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
455
                    AssertMpi(MPI_Isend(const_cast<real_number*>(&particles_positions[particles_offset_layers[my_nb_cell_levels-descriptor.nbLevelsToExchange]*size_particle_positions]),
456
457
458
459
                              int(descriptor.nbParticlesToExchange*size_particle_positions), particles_utils::GetMpiType(real_number()),
                              descriptor.destProc, TAG_POSITION_PARTICLES,
                              current_com, &mpiRequests.back()));

460
461
462
463
464
465
466
467
                    whatNext.emplace_back(std::pair<Action,int>{NOTHING_TODO, -1});
                    mpiRequests.emplace_back();
                    assert(descriptor.nbParticlesToExchange*size_particle_data < std::numeric_limits<int>::max());
                    AssertMpi(MPI_Isend(const_cast<real_number*>(&particles_data[particles_offset_layers[my_nb_cell_levels-descriptor.nbLevelsToExchange]*size_particle_data]),
                              int(descriptor.nbParticlesToExchange*size_particle_data), particles_utils::GetMpiType(real_number()),
                              descriptor.destProc, TAG_POSITION_PARTICLES,
                              current_com, &mpiRequests.back()));

468
469
                    assert(descriptor.toRecvAndMerge == nullptr);
                    descriptor.toRecvAndMerge.reset(new real_number[descriptor.nbParticlesToExchange*size_particle_rhs]);
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
470
                    whatNext.emplace_back(std::pair<Action,int>{MERGE_PARTICLES, idxDescr});
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
                    mpiRequests.emplace_back();
                    assert(descriptor.nbParticlesToExchange*size_particle_rhs < std::numeric_limits<int>::max());
                    AssertMpi(MPI_Irecv(descriptor.toRecvAndMerge.get(), int(descriptor.nbParticlesToExchange*size_particle_rhs),
                                        particles_utils::GetMpiType(real_number()), descriptor.destProc, TAG_RESULT_PARTICLES,
                                        current_com, &mpiRequests.back()));
                }
            }
            else{
                whatNext.emplace_back(std::pair<Action,int>{RECV_PARTICLES, idxDescr});
                mpiRequests.emplace_back();
                AssertMpi(MPI_Irecv(&descriptor.nbParticlesToExchange,
                      1, particles_utils::GetMpiType(partsize_t()), descriptor.destProc, TAG_NB_PARTICLES,
                      current_com, &mpiRequests.back()));
            }
        }

487
488
        lock_free_bool_array cells_locker(512);

489
490
491
492
493
494
        TIMEZONE_OMP_INIT_PREPARALLEL(omp_get_max_threads())
        #pragma omp parallel default(shared)
        {
            #pragma omp master
            {
                while(mpiRequests.size()){
Berenger Bramas's avatar
Berenger Bramas committed
495
                    TIMEZONE("wait-loop");
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
                    assert(mpiRequests.size() == whatNext.size());

                    int idxDone = int(mpiRequests.size());
                    {
                        TIMEZONE("wait");
                        AssertMpi(MPI_Waitany(int(mpiRequests.size()), mpiRequests.data(), &idxDone, MPI_STATUSES_IGNORE));
                    }
                    const std::pair<Action, int> releasedAction = whatNext[idxDone];
                    std::swap(mpiRequests[idxDone], mpiRequests[mpiRequests.size()-1]);
                    std::swap(whatNext[idxDone], whatNext[mpiRequests.size()-1]);
                    mpiRequests.pop_back();
                    whatNext.pop_back();

                    //////////////////////////////////////////////////////////////////////
                    /// Data to exchange particles
                    //////////////////////////////////////////////////////////////////////
                    if(releasedAction.first == RECV_PARTICLES){
Berenger Bramas's avatar
Berenger Bramas committed
513
                        TIMEZONE("post-recv-particles");
514
                        NeighborDescriptor& descriptor = neigDescriptors[releasedAction.second];
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
515
                        assert(descriptor.isRecv);
516
517
518
519
520
521
522
                        const int destProc = descriptor.destProc;
                        const partsize_t NbParticlesToReceive = descriptor.nbParticlesToExchange;
                        assert(NbParticlesToReceive != -1);
                        assert(descriptor.toCompute == nullptr);

                        if(NbParticlesToReceive){
                            descriptor.toCompute.reset(new real_number[NbParticlesToReceive*size_particle_positions]);
523
                            whatNext.emplace_back(std::pair<Action,int>{CHECK_PARTICLES, releasedAction.second});
524
525
526
527
528
                            mpiRequests.emplace_back();
                            assert(NbParticlesToReceive*size_particle_positions < std::numeric_limits<int>::max());
                            AssertMpi(MPI_Irecv(descriptor.toCompute.get(), int(NbParticlesToReceive*size_particle_positions),
                                                particles_utils::GetMpiType(real_number()), destProc, TAG_POSITION_PARTICLES,
                                                current_com, &mpiRequests.back()));
529
530
531
532
533
534
535
536
537


                            descriptor.toData.reset(new real_number[NbParticlesToReceive*size_particle_data]);
                            whatNext.emplace_back(std::pair<Action,int>{COMPUTE_PARTICLES, releasedAction.second});
                            mpiRequests.emplace_back();
                            assert(NbParticlesToReceive*size_particle_data < std::numeric_limits<int>::max());
                            AssertMpi(MPI_Irecv(descriptor.toData.get(), int(NbParticlesToReceive*size_particle_data),
                                                particles_utils::GetMpiType(real_number()), destProc, TAG_POSITION_PARTICLES,
                                                current_com, &mpiRequests.back()));
538
539
540
541
542
543
544
                        }
                    }

                    //////////////////////////////////////////////////////////////////////
                    /// Computation
                    //////////////////////////////////////////////////////////////////////
                    if(releasedAction.first == COMPUTE_PARTICLES){
Berenger Bramas's avatar
Berenger Bramas committed
545
                        TIMEZONE("compute-particles");
546
                        NeighborDescriptor& descriptor = neigDescriptors[releasedAction.second];
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
547
                        assert(descriptor.isRecv);
548
549
550
                        const partsize_t NbParticlesToReceive = descriptor.nbParticlesToExchange;

                        assert(descriptor.toCompute != nullptr);
551
552
                        assert(descriptor.toData != nullptr);
                        assert(descriptor.positionsReceived == true);
553
                        descriptor.results.reset(new real_number[NbParticlesToReceive*size_particle_rhs]);
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
554
                        in_computer.template init_result_array<size_particle_rhs>(descriptor.results.get(), NbParticlesToReceive);
555
556
557
558
559
560
561

                        // Compute
                        partsize_t idxPart = 0;
                        while(idxPart != NbParticlesToReceive){
                            const long int current_cell_idx = get_cell_idx(descriptor.toCompute[idxPart*size_particle_positions + IDX_X],
                                                                           descriptor.toCompute[idxPart*size_particle_positions + IDX_Y],
                                                                           descriptor.toCompute[idxPart*size_particle_positions + IDX_Z]);
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
562
                            partsize_t nb_parts_in_cell = 1;
563
564
565
566
567
568
569
                            while(idxPart+nb_parts_in_cell != NbParticlesToReceive
                                  && current_cell_idx == get_cell_idx(descriptor.toCompute[(idxPart+nb_parts_in_cell)*size_particle_positions + IDX_X],
                                                                     descriptor.toCompute[(idxPart+nb_parts_in_cell)*size_particle_positions + IDX_Y],
                                                                     descriptor.toCompute[(idxPart+nb_parts_in_cell)*size_particle_positions + IDX_Z])){
                                nb_parts_in_cell += 1;
                            }

570
571
572
573
574
575
                            #pragma omp task default(shared) firstprivate(idxPart, nb_parts_in_cell, current_cell_idx)
                            {
                                const std::vector<std::pair<partsize_t,partsize_t>>* neighbors[27];
                                long int neighbors_indexes[27];
                                std::array<real_number,3> shift[27];
                                const int nbNeighbors = my_tree.getNeighbors(current_cell_idx, neighbors, neighbors_indexes, shift, true);
576

577
                                // with other interval
578
                                for(int idx_neighbor = 0 ; idx_neighbor < nbNeighbors ; ++idx_neighbor){
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
                                    cells_locker.lock(neighbors_indexes[idx_neighbor]);

                                    for(size_t idx_2 = 0 ; idx_2 < (*neighbors[idx_neighbor]).size() ; ++idx_2){
                                        for(partsize_t idx_p1 = 0 ; idx_p1 < nb_parts_in_cell ; ++idx_p1){
                                            for(partsize_t idx_p2 = 0 ; idx_p2 < (*neighbors[idx_neighbor])[idx_2].second ; ++idx_p2){
                                                const real_number dist_r2 = compute_distance_r2(descriptor.toCompute[(idxPart+idx_p1)*size_particle_positions + IDX_X],
                                                                                                descriptor.toCompute[(idxPart+idx_p1)*size_particle_positions + IDX_Y],
                                                                                                descriptor.toCompute[(idxPart+idx_p1)*size_particle_positions + IDX_Z],
                                                                                                particles_positions[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_positions + IDX_X],
                                                                                                particles_positions[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_positions + IDX_Y],
                                                                                                particles_positions[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_positions + IDX_Z],
                                                                                                shift[idx_neighbor][IDX_X], shift[idx_neighbor][IDX_Y], shift[idx_neighbor][IDX_Z]);
                                                if(dist_r2 < cutoff_radius_compute*cutoff_radius_compute){
                                                    in_computer.template compute_interaction<size_particle_positions,size_particle_data, size_particle_rhs>(
                                                                        &descriptor.toCompute[(idxPart+idx_p1)*size_particle_positions],
                                                                        &descriptor.toData[(idxPart+idx_p1)*size_particle_data],
                                                                        &descriptor.results[(idxPart+idx_p1)*size_particle_rhs],
                                                                        &particles_positions[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_positions],
                                                                        &particles_data[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_data],
                                                                        &particles_current_rhs[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_rhs],
                                                                        dist_r2, shift[idx_neighbor][IDX_X], shift[idx_neighbor][IDX_Y], shift[idx_neighbor][IDX_Z]);
                                                }
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
601
                                            }
602
603
                                        }
                                    }
604
605

                                    cells_locker.unlock(neighbors_indexes[idx_neighbor]);
606
607
608
609
610
611
                                }
                            }

                            idxPart += nb_parts_in_cell;
                        }

612
613
                        #pragma omp taskwait

614
615
616
617
618
619
620
621
622
623
624
625
                        // Send back
                        const int destProc = descriptor.destProc;
                        whatNext.emplace_back(std::pair<Action,int>{RELEASE_BUFFER_PARTICLES, releasedAction.second});
                        mpiRequests.emplace_back();
                        assert(NbParticlesToReceive*size_particle_rhs < std::numeric_limits<int>::max());
                        AssertMpi(MPI_Isend(descriptor.results.get(), int(NbParticlesToReceive*size_particle_rhs),
                                            particles_utils::GetMpiType(real_number()), destProc, TAG_RESULT_PARTICLES,
                                            current_com, &mpiRequests.back()));
                    }
                    //////////////////////////////////////////////////////////////////////
                    /// Computation
                    //////////////////////////////////////////////////////////////////////
626
627
628
629
630
631
632
633
634
                    if(releasedAction.first == CHECK_PARTICLES){
                        NeighborDescriptor& descriptor = neigDescriptors[releasedAction.second];
                        assert(descriptor.toCompute != nullptr);
                        assert(descriptor.isRecv);
                        descriptor.positionsReceived = true;
                    }
                    //////////////////////////////////////////////////////////////////////
                    /// Computation
                    //////////////////////////////////////////////////////////////////////
635
636
637
                    if(releasedAction.first == RELEASE_BUFFER_PARTICLES){
                        NeighborDescriptor& descriptor = neigDescriptors[releasedAction.second];
                        assert(descriptor.toCompute != nullptr);
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
638
                        assert(descriptor.isRecv);
639
640
641
642
643
                        descriptor.toCompute.release();
                    }
                    //////////////////////////////////////////////////////////////////////
                    /// Merge
                    //////////////////////////////////////////////////////////////////////
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
644
                    if(releasedAction.first == MERGE_PARTICLES){
Berenger Bramas's avatar
Berenger Bramas committed
645
                        TIMEZONE("merge");
646
                        NeighborDescriptor& descriptor = neigDescriptors[releasedAction.second];
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
647
                        assert(descriptor.isRecv == false);
648
                        assert(descriptor.toRecvAndMerge != nullptr);
Berenger Bramas's avatar
Debug    
Berenger Bramas committed
649
650
                        in_computer.template reduce_particles_rhs<size_particle_rhs>(&particles_current_rhs[particles_offset_layers[my_nb_cell_levels-descriptor.nbLevelsToExchange]*size_particle_rhs],
                                descriptor.toRecvAndMerge.get(), descriptor.nbParticlesToExchange);
651
652
653
654
655
656
657
658
659
660
661
                        descriptor.toRecvAndMerge.release();
                    }
                }
            }
        }

        assert(whatNext.size() == 0);
        assert(mpiRequests.size() == 0);

        // Compute self data
        for(const auto& iter_cell : my_tree){
Berenger Bramas's avatar
Berenger Bramas committed
662
            TIMEZONE("proceed-leaf");
663
664
            const long int currenct_cell_idx = iter_cell.first;
            const std::vector<std::pair<partsize_t,partsize_t>>* intervals_ptr = &iter_cell.second;
665

666
667
668
#pragma omp task default(shared) firstprivate(currenct_cell_idx, intervals_ptr)
            {
                const std::vector<std::pair<partsize_t,partsize_t>>& intervals = (*intervals_ptr);
669

670
                cells_locker.lock(currenct_cell_idx);
671

672
673
                for(size_t idx_1 = 0 ; idx_1 < intervals.size() ; ++idx_1){
                    // self interval
674
                    for(partsize_t idx_p1 = 0 ; idx_p1 < intervals[idx_1].second ; ++idx_p1){
675
                        for(partsize_t idx_p2 = idx_p1+1 ; idx_p2 < intervals[idx_1].second ; ++idx_p2){
676
677
678
                            const real_number dist_r2 = compute_distance_r2(particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_X],
                                                                            particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_Y],
                                                                            particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_Z],
679
680
681
                                                                            particles_positions[(intervals[idx_1].first+idx_p2)*size_particle_positions + IDX_X],
                                                                            particles_positions[(intervals[idx_1].first+idx_p2)*size_particle_positions + IDX_Y],
                                                                            particles_positions[(intervals[idx_1].first+idx_p2)*size_particle_positions + IDX_Z],
Berenger Bramas's avatar
Berenger Bramas committed
682
                                                                            0, 0, 0);
683
                            if(dist_r2 < cutoff_radius_compute*cutoff_radius_compute){
684
                                in_computer.template compute_interaction<size_particle_positions,size_particle_data,size_particle_rhs>(
685
                                                    &particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions],
686
                                                    &particles_data[(intervals[idx_1].first+idx_p1)*size_particle_data],
687
                                                    &particles_current_rhs[(intervals[idx_1].first+idx_p1)*size_particle_rhs],
688
689
690
                                                    &particles_positions[(intervals[idx_1].first+idx_p2)*size_particle_positions],
                                                    &particles_data[(intervals[idx_1].first+idx_p2)*size_particle_data],
                                                    &particles_current_rhs[(intervals[idx_1].first+idx_p2)*size_particle_rhs],
Berenger Bramas's avatar
Berenger Bramas committed
691
                                                    dist_r2, 0, 0, 0);
692
                            }
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
                        }
                    }

                    // with other interval
                    for(size_t idx_2 = idx_1+1 ; idx_2 < intervals.size() ; ++idx_2){
                        for(partsize_t idx_p1 = 0 ; idx_p1 < intervals[idx_1].second ; ++idx_p1){
                            for(partsize_t idx_p2 = 0 ; idx_p2 < intervals[idx_2].second ; ++idx_p2){
                                const real_number dist_r2 = compute_distance_r2(particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_X],
                                                                                particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_Y],
                                                                                particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_Z],
                                                                                particles_positions[(intervals[idx_2].first+idx_p2)*size_particle_positions + IDX_X],
                                                                                particles_positions[(intervals[idx_2].first+idx_p2)*size_particle_positions + IDX_Y],
                                                                                particles_positions[(intervals[idx_2].first+idx_p2)*size_particle_positions + IDX_Z],
                                                                                0, 0, 0);
                                if(dist_r2 < cutoff_radius_compute*cutoff_radius_compute){
                                    in_computer.template compute_interaction<size_particle_positions,size_particle_data,size_particle_rhs>(
                                                        &particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions],
                                                        &particles_data[(intervals[idx_1].first+idx_p1)*size_particle_data],
                                                        &particles_current_rhs[(intervals[idx_1].first+idx_p1)*size_particle_rhs],
                                                        &particles_positions[(intervals[idx_2].first+idx_p2)*size_particle_positions],
                                                        &particles_data[(intervals[idx_2].first+idx_p2)*size_particle_data],
                                                        &particles_current_rhs[(intervals[idx_2].first+idx_p2)*size_particle_rhs],
                                                        dist_r2, 0, 0, 0);
                                }
                            }
718
719
720
721
                        }
                    }
                }

722
723
724
725
726
727
728
                const std::vector<std::pair<partsize_t,partsize_t>>* neighbors[27];
                long int neighbors_indexes[27];
                std::array<real_number,3> shift[27];
                const int nbNeighbors = my_tree.getNeighbors(currenct_cell_idx, neighbors, neighbors_indexes, shift, false);

                for(size_t idx_1 = 0 ; idx_1 < intervals.size() ; ++idx_1){
                    // with other interval
729
                    for(int idx_neighbor = 0 ; idx_neighbor < nbNeighbors ; ++idx_neighbor){
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
                        if(currenct_cell_idx < neighbors_indexes[idx_neighbor]){
                            cells_locker.lock(neighbors_indexes[idx_neighbor]);

                            for(size_t idx_2 = 0 ; idx_2 < (*neighbors[idx_neighbor]).size() ; ++idx_2){
                                for(partsize_t idx_p1 = 0 ; idx_p1 < intervals[idx_1].second ; ++idx_p1){
                                    for(partsize_t idx_p2 = 0 ; idx_p2 < (*neighbors[idx_neighbor])[idx_2].second ; ++idx_p2){
                                        const real_number dist_r2 = compute_distance_r2(particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_X],
                                                                                        particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_Y],
                                                                                        particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions + IDX_Z],
                                                                                        particles_positions[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_positions + IDX_X],
                                                                                        particles_positions[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_positions + IDX_Y],
                                                                                        particles_positions[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_positions + IDX_Z],
                                                                                        shift[idx_neighbor][IDX_X], shift[idx_neighbor][IDX_Y], shift[idx_neighbor][IDX_Z]);
                                        if(dist_r2 < cutoff_radius_compute*cutoff_radius_compute){
                                            in_computer.template compute_interaction<size_particle_positions,size_particle_data,size_particle_rhs>(
                                                                &particles_positions[(intervals[idx_1].first+idx_p1)*size_particle_positions],
                                                                &particles_data[(intervals[idx_1].first+idx_p1)*size_particle_data],
                                                                &particles_current_rhs[(intervals[idx_1].first+idx_p1)*size_particle_rhs],
                                                                &particles_positions[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_positions],
                                                                &particles_data[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_data],
                                                                &particles_current_rhs[((*neighbors[idx_neighbor])[idx_2].first+idx_p2)*size_particle_rhs],
                                                                dist_r2, shift[idx_neighbor][IDX_X], shift[idx_neighbor][IDX_Y], shift[idx_neighbor][IDX_Z]);
                                        }
753
                                    }
754
755
                                }
                            }
756
                            cells_locker.unlock(neighbors_indexes[idx_neighbor]);
757
758
759
                        }
                    }
                }
760
761

                cells_locker.unlock(currenct_cell_idx);
762
763
764
765
766
767
            }
        }
    }
};

#endif