FFmmAlgorithm.hpp 11.8 KB
Newer Older
1
// See LICENCE file at project root
2 3
#ifndef FFMMALGORITHM_HPP
#define FFMMALGORITHM_HPP
4

5

6
#include "../Utils/FGlobal.hpp"
7
#include "../Utils/FAssert.hpp"
8
#include "../Utils/FLog.hpp"
9

10 11 12
#include "../Utils/FTic.hpp"

#include "../Containers/FOctree.hpp"
13
#include "../Containers/FVector.hpp"
14
#include "../Utils/FAlgorithmTimers.hpp"
15

16
#include "FCoreCommon.hpp"
17 18

/**
19 20
* \author Berenger Bramas (berenger.bramas@inria.fr)
* \brief Implements a basic FMM algorithm.
21
*
22
* Please read the license.
23
*
24 25 26
* 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.
27
*/
28
template<class OctreeClass, class CellClass, class ContainerClass, class KernelClass, class LeafClass>
29
class FFmmAlgorithm :  public FAbstractAlgorithm, public FAlgorithmTimers {
30

31 32
    OctreeClass* const tree;       ///< The octree to work on.
    KernelClass* const kernels;    ///< The kernels.
33

34
    const int OctreeHeight;        ///< The height of the given tree.
35

36
    const int leafLevelSeparationCriteria;
37
public:
38 39 40 41 42 43 44 45
    /** 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.
     */
46 47
    FFmmAlgorithm(OctreeClass* const inTree, KernelClass* const inKernels, const int inLeafLevelSeparationCriteria = 1)
        : tree(inTree) , kernels(inKernels), OctreeHeight(tree->getHeight()), leafLevelSeparationCriteria(inLeafLevelSeparationCriteria) {
48

49 50
        FAssertLF(tree, "tree cannot be null");
        FAssertLF(kernels, "kernels cannot be null");
51
        FAssertLF(leafLevelSeparationCriteria < 3, "Separation criteria should be < 3");
52

53 54
        FAbstractAlgorithm::setNbLevelsInTree(tree->getHeight());

55
        FLOG(FLog::Controller << "FFmmAlgorithm\n");
56 57 58 59 60 61
    }

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

62
protected:
63
    /**
64
      * Runs the complete algorithm.
65
      */
66
    void executeCore(const unsigned operationsToProceed) override {
67 68

        Timers[P2MTimer].tic();
69
        if(operationsToProceed & FFmmP2M) bottomPass();
70
        Timers[P2MTimer].tac();
berenger-bramas's avatar
berenger-bramas committed
71

72
        Timers[M2MTimer].tic();
73
        if(operationsToProceed & FFmmM2M) upwardPass();
74
        Timers[M2MTimer].tac();
75

76
        Timers[M2LTimer].tic();
77
        if(operationsToProceed & FFmmM2L) transferPass();
78
        Timers[M2LTimer].tac();
79

80
        Timers[L2LTimer].tic();
81
        if(operationsToProceed & FFmmL2L) downardPass();
82
        Timers[L2LTimer].tac();
83

84
        Timers[NearTimer].tic();
85
        if( (operationsToProceed & FFmmP2P) || (operationsToProceed & FFmmL2P) ) directPass((operationsToProceed & FFmmP2P),(operationsToProceed & FFmmL2P));
86
        Timers[NearTimer].tac();
87 88
    }

berenger-bramas's avatar
berenger-bramas committed
89 90 91 92
    /////////////////////////////////////////////////////////////////////////////
    // P2M
    /////////////////////////////////////////////////////////////////////////////

93
    /** Runs the P2M kernel. */
94
    void bottomPass(){
95
        FLOG( FLog::Controller.write("\tStart Bottom Pass\n").write(FLog::Flush) );
96 97
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter);
98

berenger-bramas's avatar
berenger-bramas committed
99
        typename OctreeClass::Iterator octreeIterator(tree);
100 101 102 103

        // Iterate on leafs
        octreeIterator.gotoBottomLeft();
        do{
104
            // We need the current cell that represents the leaf
105
            // and the list of particles
106
            FLOG(computationCounter.tic());
107
            kernels->P2M( octreeIterator.getCurrentCell() , octreeIterator.getCurrentListSrc());
108
            FLOG(computationCounter.tac());
109 110
        } while(octreeIterator.moveRight());

111
        FLOG( FLog::Controller << "\tFinished (@Bottom Pass (P2M) = "  << counterTime.tacAndElapsed() << " s)\n" );
112
        FLOG( FLog::Controller << "\t\t Computation : " << computationCounter.cumulated() << " s\n" );
113 114
    }

berenger-bramas's avatar
berenger-bramas committed
115 116 117 118
    /////////////////////////////////////////////////////////////////////////////
    // Upward
    /////////////////////////////////////////////////////////////////////////////

119
    /** Runs the M2M kernel. */
120
    void upwardPass(){
121
        FLOG( FLog::Controller.write("\tStart Upward Pass\n").write(FLog::Flush); );
122 123
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter);
124 125

        // Start from leal level - 1
berenger-bramas's avatar
berenger-bramas committed
126
        typename OctreeClass::Iterator octreeIterator(tree);
127 128 129
        octreeIterator.gotoBottomLeft();
        octreeIterator.moveUp();

130
        for(int idxLevel = OctreeHeight - 2 ; idxLevel > FAbstractAlgorithm::lowerWorkingLevel-1 ; --idxLevel){
131 132 133
            octreeIterator.moveUp();
        }

berenger-bramas's avatar
berenger-bramas committed
134
        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);
135 136

        // for each levels
137
        for(int idxLevel = FMath::Min(OctreeHeight - 2, FAbstractAlgorithm::lowerWorkingLevel - 1) ; idxLevel >= FAbstractAlgorithm::upperWorkingLevel ; --idxLevel ){
138
            FLOG(FTic counterTimeLevel);
139

140 141 142 143
            // for each cells
            do{
                // We need the current cell and the child
                // child is an array (of 8 child) that may be null
144
                FLOG(computationCounter.tic());
145
                kernels->M2M( octreeIterator.getCurrentCell() , octreeIterator.getCurrentChild(), idxLevel);
146
                FLOG(computationCounter.tac());
147 148 149
            } while(octreeIterator.moveRight());

            avoidGotoLeftIterator.moveUp();
150 151
            octreeIterator = avoidGotoLeftIterator;

152
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << " s\n" );
153 154
        }

berenger-bramas's avatar
berenger-bramas committed
155

156
        FLOG( FLog::Controller << "\tFinished (@Upward Pass (M2M) = "  << counterTime.tacAndElapsed() << " s)\n" );
157
        FLOG( FLog::Controller << "\t\t Computation : " << computationCounter.cumulated() << " s\n" );
158 159
    }

berenger-bramas's avatar
berenger-bramas committed
160
    /////////////////////////////////////////////////////////////////////////////
161
    // Transfer
berenger-bramas's avatar
berenger-bramas committed
162 163
    /////////////////////////////////////////////////////////////////////////////

164
    /** Runs the M2L kernel. */
165
    void transferPass(){
166
        FLOG( FLog::Controller.write("\tStart Downward Pass (M2L)\n").write(FLog::Flush); );
167 168
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter);
169 170 171 172

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

173
        for(int idxLevel = 2 ; idxLevel < FAbstractAlgorithm::upperWorkingLevel ; ++idxLevel){
174 175 176
            octreeIterator.moveDown();
        }

177 178
        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);

179 180
        const CellClass* neighbors[342];
        int neighborPositions[342];
181 182

        // for each levels
183
        for(int idxLevel = FAbstractAlgorithm::upperWorkingLevel ; idxLevel < FAbstractAlgorithm::lowerWorkingLevel ; ++idxLevel ){
184
            FLOG(FTic counterTimeLevel);
185

186
            const int separationCriteria = (idxLevel != FAbstractAlgorithm::lowerWorkingLevel-1 ? 1 : leafLevelSeparationCriteria);
187

188 189
            // for each cells
            do{
190
                const int counter = tree->getInteractionNeighbors(neighbors, neighborPositions, octreeIterator.getCurrentGlobalCoordinate(), idxLevel, separationCriteria);
191
                FLOG(computationCounter.tic());
192
                if(counter) kernels->M2L( octreeIterator.getCurrentCell() , neighbors, neighborPositions, counter, idxLevel);
193
                FLOG(computationCounter.tac());
194 195
            } while(octreeIterator.moveRight());

196
            FLOG(computationCounter.tic());
berenger-bramas's avatar
berenger-bramas committed
197
            kernels->finishedLevelM2L(idxLevel);
198
            FLOG(computationCounter.tac());
berenger-bramas's avatar
berenger-bramas committed
199

200 201
            avoidGotoLeftIterator.moveDown();
            octreeIterator = avoidGotoLeftIterator;
202

203
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << " s\n" );
204
        }
205
        FLOG( FLog::Controller << "\tFinished (@Downward Pass (M2L) = "  << counterTime.tacAndElapsed() << " s)\n" );
206
        FLOG( FLog::Controller << "\t\t Computation : " << computationCounter.cumulated() << " s\n" );
207
    }
berenger-bramas's avatar
berenger-bramas committed
208

209 210 211
    /////////////////////////////////////////////////////////////////////////////
    // Downward
    /////////////////////////////////////////////////////////////////////////////
berenger-bramas's avatar
berenger-bramas committed
212

213
    /** Runs the L2L kernel .*/
214
    void downardPass(){
215
        FLOG( FLog::Controller.write("\tStart Downward Pass (L2L)\n").write(FLog::Flush); );
216 217
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter );
218

219 220
        typename OctreeClass::Iterator octreeIterator(tree);
        octreeIterator.moveDown();
221

222
        for(int idxLevel = 2 ; idxLevel < FAbstractAlgorithm::upperWorkingLevel ; ++idxLevel){
223 224 225
            octreeIterator.moveDown();
        }

226
        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);
227

228
        const int heightMinusOne = FAbstractAlgorithm::lowerWorkingLevel - 1;
229
        // for each levels exepted leaf level
230
        for(int idxLevel = FAbstractAlgorithm::upperWorkingLevel ; idxLevel < heightMinusOne ; ++idxLevel ){
231
            FLOG(FTic counterTimeLevel);
232

233 234
            // for each cells
            do{
235
                FLOG(computationCounter.tic());
236
                kernels->L2L( octreeIterator.getCurrentCell() , octreeIterator.getCurrentChild(), idxLevel);
237
                FLOG(computationCounter.tac());
238
            } while(octreeIterator.moveRight());
berenger-bramas's avatar
berenger-bramas committed
239

240 241
            avoidGotoLeftIterator.moveDown();
            octreeIterator = avoidGotoLeftIterator;
242

243
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << " s\n" );
244 245
        }

246
        FLOG( FLog::Controller << "\tFinished (@Downward Pass (L2L) = "  << counterTime.tacAndElapsed() << " s)\n" );
247
        FLOG( FLog::Controller << "\t\t Computation : " << computationCounter.cumulated() << " s\n" );
248

249

250 251
    }

berenger-bramas's avatar
berenger-bramas committed
252 253 254 255
    /////////////////////////////////////////////////////////////////////////////
    // Direct
    /////////////////////////////////////////////////////////////////////////////

256 257 258 259 260
    /** Runs the P2P & L2P kernels.
     *
     * \param p2pEnabled If true, run the P2P kernel.
     * \param l2pEnabled If true, run the L2P kernel.
     */
261
    void directPass(const bool p2pEnabled, const bool l2pEnabled){
262
        FLOG( FLog::Controller.write("\tStart Direct Pass\n").write(FLog::Flush); );
263 264 265
        FLOG(FTic counterTime);
        FLOG(FTic computationCounterL2P);
        FLOG(FTic computationCounterP2P);
266 267 268

        const int heightMinusOne = OctreeHeight - 1;

berenger-bramas's avatar
berenger-bramas committed
269
        typename OctreeClass::Iterator octreeIterator(tree);
270 271
        octreeIterator.gotoBottomLeft();
        // There is a maximum of 26 neighbors
272 273
        ContainerClass* neighbors[26];
        int neighborPositions[26];
274 275
        // for each leafs
        do{
276 277 278 279 280 281 282
            if(l2pEnabled){
                FLOG(computationCounterL2P.tic());
                kernels->L2P(octreeIterator.getCurrentCell(), octreeIterator.getCurrentListTargets());
                FLOG(computationCounterL2P.tac());
            }
            if(p2pEnabled){
                // need the current particles and neighbors particles
283
                const int counter = tree->getLeafsNeighbors(neighbors, neighborPositions, octreeIterator.getCurrentGlobalCoordinate(),heightMinusOne);
284 285
                FLOG(computationCounterP2P.tic());
                kernels->P2P(octreeIterator.getCurrentGlobalCoordinate(),octreeIterator.getCurrentListTargets(),
286
                             octreeIterator.getCurrentListSrc(), neighbors, neighborPositions, counter);
287 288
                FLOG(computationCounterP2P.tac());
            }
289 290
        } while(octreeIterator.moveRight());

berenger-bramas's avatar
berenger-bramas committed
291

292
        FLOG( FLog::Controller << "\tFinished (@Direct Pass (L2P + P2P) = "  << counterTime.tacAndElapsed() << " s)\n" );
293 294
        FLOG( FLog::Controller << "\t\t Computation L2P : " << computationCounterL2P.cumulated() << " s\n" );
        FLOG( FLog::Controller << "\t\t Computation P2P : " << computationCounterP2P.cumulated() << " s\n" );
295

296 297 298 299 300 301
    }

};


#endif //FFMMALGORITHM_HPP