FFmmAlgorithm.hpp 12.3 KB
Newer Older
1
// ===================================================================================
2
3
4
5
6
// Copyright ScalFmm 2011 INRIA, Olivier Coulaud, Bérenger Bramas, Matthias Messner
// olivier.coulaud@inria.fr, berenger.bramas@inria.fr
// This software is a computer program whose purpose is to compute the FMM.
//
// This software is governed by the CeCILL-C and LGPL licenses and
7
8
// abiding by the rules of distribution of free software.
//
9
10
11
12
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public and CeCILL-C Licenses for more details.
13
// "http://www.cecill.info".
14
// "http://www.gnu.org/licenses".
15
// ===================================================================================
16
17
#ifndef FFMMALGORITHM_HPP
#define FFMMALGORITHM_HPP
18

19

20
#include "../Utils/FGlobal.hpp"
BRAMAS Berenger's avatar
BRAMAS Berenger committed
21
#include "../Utils/FAssert.hpp"
BRAMAS Berenger's avatar
BRAMAS Berenger committed
22
#include "../Utils/FLog.hpp"
23

24
25
26
#include "../Utils/FTic.hpp"

#include "../Containers/FOctree.hpp"
27
#include "../Containers/FVector.hpp"
28
#include "../Utils/FAlgorithmTimers.hpp"
29

30
#include "FCoreCommon.hpp"
31
32

/**
33
34
* \author Berenger Bramas (berenger.bramas@inria.fr)
* \brief Implements a basic FMM algorithm.
35
*
36
* Please read the license.
37
*
38
39
40
* This class runs the FMM algorithm on a tree using the kernels that it was given.
*
* This class does not deallocate pointers given to it constructor.
41
*/
42
template<class OctreeClass, class CellClass, class ContainerClass, class KernelClass, class LeafClass>
43
class FFmmAlgorithm :  public FAbstractAlgorithm, public FAlgorithmTimers {
44

45
46
    OctreeClass* const tree;       ///< The octree to work on.
    KernelClass* const kernels;    ///< The kernels.
47

48
    const int OctreeHeight;        ///< The height of the given tree.
49

50
    const int leafLevelSeperationCriteria;
51
public:
52
53
54
55
56
57
58
59
    /** Class constructor
     * 
     * The constructor needs the octree and the kernels used for computation.
     * @param inTree the octree to work on.
     * @param inKernels the kernels to call.
     *
     * \except An exception is thrown if one of the arguments is NULL.
     */
60
61
    FFmmAlgorithm(OctreeClass* const inTree, KernelClass* const inKernels, const int inLeafLevelSeperationCriteria = 1)
        : tree(inTree) , kernels(inKernels), OctreeHeight(tree->getHeight()), leafLevelSeperationCriteria(inLeafLevelSeperationCriteria) {
62

BRAMAS Berenger's avatar
BRAMAS Berenger committed
63
64
        FAssertLF(tree, "tree cannot be null");
        FAssertLF(kernels, "kernels cannot be null");
65

66
67
        FAbstractAlgorithm::setNbLevelsInTree(tree->getHeight());

BRAMAS Berenger's avatar
BRAMAS Berenger committed
68
        FLOG(FLog::Controller << "FFmmAlgorithm\n");
69
70
71
72
73
74
    }

    /** Default destructor */
    virtual ~FFmmAlgorithm(){
    }

75
protected:
76
    /**
77
      * Runs the complete algorithm.
78
      */
79
    void executeCore(const unsigned operationsToProceed) override {
80
81

        Timers[P2MTimer].tic();
82
        if(operationsToProceed & FFmmP2M) bottomPass();
83
        Timers[P2MTimer].tac();
berenger-bramas's avatar
berenger-bramas committed
84

85
        Timers[M2MTimer].tic();
86
        if(operationsToProceed & FFmmM2M) upwardPass();
87
        Timers[M2MTimer].tac();
88

89
        Timers[M2LTimer].tic();
90
        if(operationsToProceed & FFmmM2L) transferPass();
91
        Timers[M2LTimer].tac();
92

93
        Timers[L2LTimer].tic();
94
        if(operationsToProceed & FFmmL2L) downardPass();
95
        Timers[L2LTimer].tac();
96

97
        Timers[NearTimer].tic();
98
        if( (operationsToProceed & FFmmP2P) || (operationsToProceed & FFmmL2P) ) directPass((operationsToProceed & FFmmP2P),(operationsToProceed & FFmmL2P));
99
        Timers[NearTimer].tac();
100
101
    }

berenger-bramas's avatar
berenger-bramas committed
102
103
104
105
    /////////////////////////////////////////////////////////////////////////////
    // P2M
    /////////////////////////////////////////////////////////////////////////////

106
    /** Runs the P2M kernel. */
107
    void bottomPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
108
        FLOG( FLog::Controller.write("\tStart Bottom Pass\n").write(FLog::Flush) );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
109
110
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter);
111

berenger-bramas's avatar
berenger-bramas committed
112
        typename OctreeClass::Iterator octreeIterator(tree);
113
114
115
116

        // Iterate on leafs
        octreeIterator.gotoBottomLeft();
        do{
117
            // We need the current cell that represents the leaf
118
            // and the list of particles
BRAMAS Berenger's avatar
BRAMAS Berenger committed
119
            FLOG(computationCounter.tic());
120
            kernels->P2M( octreeIterator.getCurrentCell() , octreeIterator.getCurrentListSrc());
BRAMAS Berenger's avatar
BRAMAS Berenger committed
121
            FLOG(computationCounter.tac());
122
123
        } while(octreeIterator.moveRight());

BRAMAS Berenger's avatar
BRAMAS Berenger committed
124
125
        FLOG( FLog::Controller << "\tFinished (@Bottom Pass (P2M) = "  << counterTime.tacAndElapsed() << "s)\n" );
        FLOG( FLog::Controller << "\t\t Computation : " << computationCounter.cumulated() << " s\n" );
126
127
    }

berenger-bramas's avatar
berenger-bramas committed
128
129
130
131
    /////////////////////////////////////////////////////////////////////////////
    // Upward
    /////////////////////////////////////////////////////////////////////////////

132
    /** Runs the M2M kernel. */
133
    void upwardPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
134
        FLOG( FLog::Controller.write("\tStart Upward Pass\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
135
136
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter);
137
138

        // Start from leal level - 1
berenger-bramas's avatar
berenger-bramas committed
139
        typename OctreeClass::Iterator octreeIterator(tree);
140
141
142
        octreeIterator.gotoBottomLeft();
        octreeIterator.moveUp();

143
        for(int idxLevel = OctreeHeight - 2 ; idxLevel > FAbstractAlgorithm::lowerWorkingLevel-1 ; --idxLevel){
144
145
146
            octreeIterator.moveUp();
        }

berenger-bramas's avatar
berenger-bramas committed
147
        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);
148
149

        // for each levels
150
        for(int idxLevel = FMath::Min(OctreeHeight - 2, FAbstractAlgorithm::lowerWorkingLevel - 1) ; idxLevel >= FAbstractAlgorithm::upperWorkingLevel ; --idxLevel ){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
151
            FLOG(FTic counterTimeLevel);
152

153
154
155
156
            // for each cells
            do{
                // We need the current cell and the child
                // child is an array (of 8 child) that may be null
BRAMAS Berenger's avatar
BRAMAS Berenger committed
157
                FLOG(computationCounter.tic());
158
                kernels->M2M( octreeIterator.getCurrentCell() , octreeIterator.getCurrentChild(), idxLevel);
BRAMAS Berenger's avatar
BRAMAS Berenger committed
159
                FLOG(computationCounter.tac());
160
161
162
            } while(octreeIterator.moveRight());

            avoidGotoLeftIterator.moveUp();
163
164
            octreeIterator = avoidGotoLeftIterator;

BRAMAS Berenger's avatar
BRAMAS Berenger committed
165
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << "s\n" );
166
167
        }

berenger-bramas's avatar
berenger-bramas committed
168

BRAMAS Berenger's avatar
BRAMAS Berenger committed
169
170
        FLOG( FLog::Controller << "\tFinished (@Upward Pass (M2M) = "  << counterTime.tacAndElapsed() << "s)\n" );
        FLOG( FLog::Controller << "\t\t Computation : " << computationCounter.cumulated() << " s\n" );
171
172
    }

berenger-bramas's avatar
berenger-bramas committed
173
    /////////////////////////////////////////////////////////////////////////////
174
    // Transfer
berenger-bramas's avatar
berenger-bramas committed
175
176
    /////////////////////////////////////////////////////////////////////////////

177
    /** Runs the M2L kernel. */
178
    void transferPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
179
        FLOG( FLog::Controller.write("\tStart Downward Pass (M2L)\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
180
181
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter);
182
183
184
185

        typename OctreeClass::Iterator octreeIterator(tree);
        octreeIterator.moveDown();

186
        for(int idxLevel = 2 ; idxLevel < FAbstractAlgorithm::upperWorkingLevel ; ++idxLevel){
187
188
189
            octreeIterator.moveDown();
        }

190
191
        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);

192
        const CellClass* neighbors[343];
193

194

195
        // for each levels
196
        for(int idxLevel = FAbstractAlgorithm::upperWorkingLevel ; idxLevel < FAbstractAlgorithm::lowerWorkingLevel ; ++idxLevel ){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
197
            FLOG(FTic counterTimeLevel);
198

199
200
            const int separationCriteria = (idxLevel != FAbstractAlgorithm::lowerWorkingLevel-1 ? 1 : leafLevelSeperationCriteria);

201
202
            // for each cells
            do{
203
                const int counter = tree->getInteractionNeighbors(neighbors, octreeIterator.getCurrentGlobalCoordinate(), idxLevel, separationCriteria);
BRAMAS Berenger's avatar
BRAMAS Berenger committed
204
                FLOG(computationCounter.tic());
205
                if(counter) kernels->M2L( octreeIterator.getCurrentCell() , neighbors, counter, idxLevel);
BRAMAS Berenger's avatar
BRAMAS Berenger committed
206
                FLOG(computationCounter.tac());
207
208
            } while(octreeIterator.moveRight());

BRAMAS Berenger's avatar
BRAMAS Berenger committed
209
            FLOG(computationCounter.tic());
berenger-bramas's avatar
berenger-bramas committed
210
            kernels->finishedLevelM2L(idxLevel);
BRAMAS Berenger's avatar
BRAMAS Berenger committed
211
            FLOG(computationCounter.tac());
berenger-bramas's avatar
berenger-bramas committed
212

213
214
            avoidGotoLeftIterator.moveDown();
            octreeIterator = avoidGotoLeftIterator;
215

BRAMAS Berenger's avatar
BRAMAS Berenger committed
216
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << "s\n" );
217
        }
BRAMAS Berenger's avatar
BRAMAS Berenger committed
218
219
        FLOG( FLog::Controller << "\tFinished (@Downward Pass (M2L) = "  << counterTime.tacAndElapsed() << "s)\n" );
        FLOG( FLog::Controller << "\t\t Computation : " << computationCounter.cumulated() << " s\n" );
220
    }
berenger-bramas's avatar
berenger-bramas committed
221

222
223
224
    /////////////////////////////////////////////////////////////////////////////
    // Downward
    /////////////////////////////////////////////////////////////////////////////
berenger-bramas's avatar
berenger-bramas committed
225

226
    /** Runs the L2L kernel .*/
227
    void downardPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
228
        FLOG( FLog::Controller.write("\tStart Downward Pass (L2L)\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
229
230
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter );
231

232
233
        typename OctreeClass::Iterator octreeIterator(tree);
        octreeIterator.moveDown();
234

235
        for(int idxLevel = 2 ; idxLevel < FAbstractAlgorithm::upperWorkingLevel ; ++idxLevel){
236
237
238
            octreeIterator.moveDown();
        }

239
        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);
240

241
        const int heightMinusOne = FAbstractAlgorithm::lowerWorkingLevel - 1;
242
        // for each levels exepted leaf level
243
        for(int idxLevel = FAbstractAlgorithm::upperWorkingLevel ; idxLevel < heightMinusOne ; ++idxLevel ){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
244
            FLOG(FTic counterTimeLevel);
245

246
247
            // for each cells
            do{
BRAMAS Berenger's avatar
BRAMAS Berenger committed
248
                FLOG(computationCounter.tic());
249
                kernels->L2L( octreeIterator.getCurrentCell() , octreeIterator.getCurrentChild(), idxLevel);
BRAMAS Berenger's avatar
BRAMAS Berenger committed
250
                FLOG(computationCounter.tac());
251
            } while(octreeIterator.moveRight());
berenger-bramas's avatar
berenger-bramas committed
252

253
254
            avoidGotoLeftIterator.moveDown();
            octreeIterator = avoidGotoLeftIterator;
255

BRAMAS Berenger's avatar
BRAMAS Berenger committed
256
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << "s\n" );
257
258
        }

BRAMAS Berenger's avatar
BRAMAS Berenger committed
259
260
        FLOG( FLog::Controller << "\tFinished (@Downward Pass (L2L) = "  << counterTime.tacAndElapsed() << "s)\n" );
        FLOG( FLog::Controller << "\t\t Computation : " << computationCounter.cumulated() << " s\n" );
261

262

263
264
    }

berenger-bramas's avatar
berenger-bramas committed
265
266
267
268
    /////////////////////////////////////////////////////////////////////////////
    // Direct
    /////////////////////////////////////////////////////////////////////////////

269
270
271
272
273
    /** Runs the P2P & L2P kernels.
     *
     * \param p2pEnabled If true, run the P2P kernel.
     * \param l2pEnabled If true, run the L2P kernel.
     */
274
    void directPass(const bool p2pEnabled, const bool l2pEnabled){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
275
        FLOG( FLog::Controller.write("\tStart Direct Pass\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
276
277
278
        FLOG(FTic counterTime);
        FLOG(FTic computationCounterL2P);
        FLOG(FTic computationCounterP2P);
279
280
281

        const int heightMinusOne = OctreeHeight - 1;

berenger-bramas's avatar
berenger-bramas committed
282
        typename OctreeClass::Iterator octreeIterator(tree);
283
284
        octreeIterator.gotoBottomLeft();
        // There is a maximum of 26 neighbors
berenger-bramas's avatar
berenger-bramas committed
285
        ContainerClass* neighbors[27];
286
287
        // for each leafs
        do{
288
289
290
291
292
293
294
295
296
297
298
299
300
            if(l2pEnabled){
                FLOG(computationCounterL2P.tic());
                kernels->L2P(octreeIterator.getCurrentCell(), octreeIterator.getCurrentListTargets());
                FLOG(computationCounterL2P.tac());
            }
            if(p2pEnabled){
                // need the current particles and neighbors particles
                const int counter = tree->getLeafsNeighbors(neighbors, octreeIterator.getCurrentGlobalCoordinate(),heightMinusOne);
                FLOG(computationCounterP2P.tic());
                kernels->P2P(octreeIterator.getCurrentGlobalCoordinate(),octreeIterator.getCurrentListTargets(),
                             octreeIterator.getCurrentListSrc(), neighbors, counter);
                FLOG(computationCounterP2P.tac());
            }
301
302
        } while(octreeIterator.moveRight());

berenger-bramas's avatar
berenger-bramas committed
303

BRAMAS Berenger's avatar
BRAMAS Berenger committed
304
305
306
        FLOG( FLog::Controller << "\tFinished (@Direct Pass (L2P + P2P) = "  << counterTime.tacAndElapsed() << "s)\n" );
        FLOG( FLog::Controller << "\t\t Computation L2P : " << computationCounterL2P.cumulated() << " s\n" );
        FLOG( FLog::Controller << "\t\t Computation P2P : " << computationCounterP2P.cumulated() << " s\n" );
307

308
309
310
311
312
313
    }

};


#endif //FFMMALGORITHM_HPP