FFmmAlgorithmSectionTask.hpp 12.5 KB
Newer Older
1
// ===================================================================================
2 3 4 5 6 7 8 9 10 11 12 13 14
// 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
// abiding by the rules of distribution of free software.  
// 
// 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.
// "http://www.cecill.info". 
// "http://www.gnu.org/licenses".
15
// ===================================================================================
16 17
#ifndef FFMMALGORITHMSECTIONTASK_HPP
#define FFMMALGORITHMSECTIONTASK_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 27 28
#include "../Utils/FTic.hpp"

#include "../Containers/FOctree.hpp"
#include "../Containers/FVector.hpp"

29
#include "FCoreCommon.hpp"
30 31 32 33 34 35 36 37 38 39 40 41

/**
* @author Berenger Bramas (berenger.bramas@inria.fr)
* @class FFmmAlgorithmSectionTask
* @brief
* Please read the license
*
* This class is a basic FMM algorithm
* It just iterates on a tree and call the kernels with good arguments.
*
* Of course this class does not deallocate pointer given in arguements.
*/
42
template<class OctreeClass, class CellClass, class ContainerClass, class KernelClass, class LeafClass>
BRAMAS Berenger's avatar
BRAMAS Berenger committed
43
class FFmmAlgorithmSectionTask : public FAbstractAlgorithm{
44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

    OctreeClass* const tree;       //< The octree to work on
    KernelClass** kernels;    //< The kernels

    const int MaxThreads;

    const int OctreeHeight;

public:
    /** The constructor need the octree and the kernels used for computation
      * @param inTree the octree to work on
      * @param inKernels the kernels to call
      * An assert is launched if one of the arguments is null
      */
    FFmmAlgorithmSectionTask(OctreeClass* const inTree, KernelClass* const inKernels)
        : tree(inTree) , kernels(0),
          MaxThreads(omp_get_max_threads()), OctreeHeight(tree->getHeight())
    {

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

        this->kernels = new KernelClass*[MaxThreads];
67
        #pragma omp parallel for schedule(static)
68
        for(int idxThread = 0 ; idxThread < MaxThreads ; ++idxThread){
69 70 71 72
            #pragma omp critical
            {
                this->kernels[idxThread] = new KernelClass(*inKernels);
            }
73 74
        }

BRAMAS Berenger's avatar
BRAMAS Berenger committed
75
        FLOG(FLog::Controller << "FFmmAlgorithmSectionTask (Max Thread " << omp_get_max_threads() << ")\n");
76 77 78 79 80 81 82 83 84 85 86 87 88 89
    }

    /** Default destructor */
    virtual ~FFmmAlgorithmSectionTask(){
        for(int idxThread = 0 ; idxThread < MaxThreads ; ++idxThread){
            delete this->kernels[idxThread];
        }
        delete [] this->kernels;
    }

    /**
      * To execute the fmm algorithm
      * Call this function to run the complete algorithm
      */
90
    void execute(const unsigned operationsToProceed = FFmmNearAndFarFields){
91 92 93 94 95 96 97

        #pragma omp parallel
        {
            #pragma omp sections
            {
                #pragma omp section
                {
98
                    if(operationsToProceed & FFmmP2M) bottomPass();
99

100
                    if(operationsToProceed & FFmmM2M) upwardPass();
101

102
                    if(operationsToProceed & FFmmM2L) transferPass();
103

104
                    if(operationsToProceed & FFmmL2L) downardPass();
105 106 107
                }
                #pragma omp section
                {
108
                    if(operationsToProceed & FFmmP2P) directPass();
109 110 111 112
                }
            }
            #pragma omp single
            {
113
                if(operationsToProceed & FFmmL2P) L2PPass();
114 115 116 117 118 119 120 121 122 123 124
            }
        }
    }

private:
    /////////////////////////////////////////////////////////////////////////////
    // P2M
    /////////////////////////////////////////////////////////////////////////////

    /** P2M */
    void bottomPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
125
        FLOG( FLog::Controller.write("\tStart Bottom Pass\n").write(FLog::Flush) );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
126
        FLOG(FTic counterTime);
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143

        typename OctreeClass::Iterator octreeIterator(tree);

        // Iterate on leafs
        octreeIterator.gotoBottomLeft();
        do{
            // We need the current cell that represent the leaf
            // and the list of particles
            #pragma omp task firstprivate(octreeIterator)
            {
                kernels[omp_get_thread_num()]->P2M( octreeIterator.getCurrentCell() , octreeIterator.getCurrentListSrc());
            }
        } while(octreeIterator.moveRight());

        #pragma omp taskwait


BRAMAS Berenger's avatar
BRAMAS Berenger committed
144
        FLOG( FLog::Controller << "\tFinished (@Bottom Pass (P2M) = "  << counterTime.tacAndElapsed() << "s)\n" );
145 146 147 148 149 150 151 152
    }

    /////////////////////////////////////////////////////////////////////////////
    // Upward
    /////////////////////////////////////////////////////////////////////////////

    /** M2M */
    void upwardPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
153
        FLOG( FLog::Controller.write("\tStart Upward Pass\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
154
        FLOG(FTic counterTime);
155 156 157 158 159 160 161 162 163 164

        // Start from leal level - 1
        typename OctreeClass::Iterator octreeIterator(tree);
        octreeIterator.gotoBottomLeft();
        octreeIterator.moveUp();

        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);

        // for each levels
        for(int idxLevel = OctreeHeight - 2 ; idxLevel > 1 ; --idxLevel ){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
165
            FLOG(FTic counterTimeLevel);
166 167 168 169 170 171 172 173 174 175 176 177 178 179
            // for each cells
            do{
                // We need the current cell and the child
                // child is an array (of 8 child) that may be null
                #pragma omp task firstprivate(octreeIterator) shared(idxLevel)
                {
                    kernels[omp_get_thread_num()]->M2M( octreeIterator.getCurrentCell() , octreeIterator.getCurrentChild(), idxLevel);
                }
            } while(octreeIterator.moveRight());

            avoidGotoLeftIterator.moveUp();
            octreeIterator = avoidGotoLeftIterator;// equal octreeIterator.moveUp(); octreeIterator.gotoLeft();

            #pragma omp taskwait
BRAMAS Berenger's avatar
BRAMAS Berenger committed
180
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << "s\n" );
181 182 183
        }


BRAMAS Berenger's avatar
BRAMAS Berenger committed
184
        FLOG( FLog::Controller << "\tFinished (@Upward Pass (M2M) = "  << counterTime.tacAndElapsed() << "s)\n" );
185 186 187 188 189 190 191 192
    }

    /////////////////////////////////////////////////////////////////////////////
    // Transfer
    /////////////////////////////////////////////////////////////////////////////

    /** M2L L2L */
    void transferPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
193
        FLOG( FLog::Controller.write("\tStart Downward Pass (M2L)\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
194
        FLOG(FTic counterTime);
195 196 197 198 199 200 201 202 203 204 205

        const CellClass* neighbors[343];

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

        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);


        // for each levels
        for(int idxLevel = 2 ; idxLevel < OctreeHeight ; ++idxLevel ){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
206
            FLOG(FTic counterTimeLevel);
207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231
            // for each cells
            do{
                int counter = tree->getInteractionNeighbors(neighbors, octreeIterator.getCurrentGlobalCoordinate(), idxLevel);
                if(counter){
                    #pragma omp task firstprivate(octreeIterator, neighbors, counter) shared(idxLevel)
                    {
                        kernels[omp_get_thread_num()]->M2L( octreeIterator.getCurrentCell() , neighbors, counter, idxLevel);
                    }
                }

            } while(octreeIterator.moveRight());

            avoidGotoLeftIterator.moveDown();
            octreeIterator = avoidGotoLeftIterator;

            #pragma omp taskwait

            for( int idxThread = 0 ; idxThread < omp_get_num_threads() ; ++idxThread){
                #pragma omp task
                {
                    kernels[idxThread]->finishedLevelM2L(idxLevel);
                }
            }

            #pragma omp taskwait
BRAMAS Berenger's avatar
BRAMAS Berenger committed
232
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << "s\n" );
233 234
        }

BRAMAS Berenger's avatar
BRAMAS Berenger committed
235
        FLOG( FLog::Controller << "\tFinished (@Downward Pass (M2L) = "  << counterTime.tacAndElapsed() << "s)\n" );
236 237 238 239 240 241 242
    }

    /////////////////////////////////////////////////////////////////////////////
    // Downward
    /////////////////////////////////////////////////////////////////////////////

    void downardPass(){ // second L2L
BRAMAS Berenger's avatar
BRAMAS Berenger committed
243
        FLOG( FLog::Controller.write("\tStart Downward Pass (L2L)\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
244
        FLOG(FTic counterTime);
245 246 247 248 249 250 251 252 253

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

        typename OctreeClass::Iterator avoidGotoLeftIterator(octreeIterator);

        const int heightMinusOne = OctreeHeight - 1;
        // for each levels exepted leaf level
        for(int idxLevel = 2 ; idxLevel < heightMinusOne ; ++idxLevel ){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
254
            FLOG(FTic counterTimeLevel);
255 256 257 258 259 260 261 262 263 264 265 266 267
            // for each cells
            do{
                #pragma omp task firstprivate(octreeIterator) shared(idxLevel)
                {
                    kernels[omp_get_thread_num()]->L2L( octreeIterator.getCurrentCell() , octreeIterator.getCurrentChild(), idxLevel);
                }

            } while(octreeIterator.moveRight());

            avoidGotoLeftIterator.moveDown();
            octreeIterator = avoidGotoLeftIterator;

            #pragma omp taskwait
BRAMAS Berenger's avatar
BRAMAS Berenger committed
268
            FLOG( FLog::Controller << "\t\t>> Level " << idxLevel << " = "  << counterTimeLevel.tacAndElapsed() << "s\n" );
269 270
        }

BRAMAS Berenger's avatar
BRAMAS Berenger committed
271
        FLOG( FLog::Controller << "\tFinished (@Downward Pass (L2L) = "  << counterTime.tacAndElapsed() << "s)\n" );
272 273 274 275 276 277 278 279 280
    }


    /////////////////////////////////////////////////////////////////////////////
    // Direct
    /////////////////////////////////////////////////////////////////////////////

    /** P2P */
    void directPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
281
        FLOG( FLog::Controller.write("\tStart Direct Pass\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
282 283
        FLOG(FTic counterTime);
        FLOG(FTic computationCounter);
284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304

        const int heightMinusOne = OctreeHeight - 1;

        // There is a maximum of 26 neighbors
        ContainerClass* neighbors[27];

        const int SizeShape = 3*3*3;
        FVector<typename OctreeClass::Iterator> shapes[SizeShape];

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

        // for each leafs
        do{
            const FTreeCoordinate& coord = octreeIterator.getCurrentGlobalCoordinate();
            const int shapePosition = (coord.getX()%3)*9 + (coord.getY()%3)*3 + (coord.getZ()%3);

            shapes[shapePosition].push(octreeIterator);

        } while(octreeIterator.moveRight());

BRAMAS Berenger's avatar
BRAMAS Berenger committed
305
        FLOG( computationCounter.tic() );
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321

        for( int idxShape = 0 ; idxShape < SizeShape ; ++idxShape){
            const int nbLeaf = shapes[idxShape].getSize();
            for(int iterLeaf = 0 ; iterLeaf < nbLeaf ; ++iterLeaf ){
                typename OctreeClass::Iterator toWork = shapes[idxShape][iterLeaf];
                #pragma omp task firstprivate(neighbors, toWork)
                {
                    const int counter = tree->getLeafsNeighbors(neighbors, toWork.getCurrentGlobalCoordinate(),heightMinusOne);
                    kernels[omp_get_thread_num()]->P2P(toWork.getCurrentGlobalCoordinate(), toWork.getCurrentListTargets(),
                                         toWork.getCurrentListSrc(), neighbors, counter);
                }
            }

            #pragma omp taskwait
        }

BRAMAS Berenger's avatar
BRAMAS Berenger committed
322
        FLOG( computationCounter.tac() );
323 324


BRAMAS Berenger's avatar
BRAMAS Berenger committed
325 326
        FLOG( FLog::Controller << "\tFinished (@Direct Pass (P2P) = "  << counterTime.tacAndElapsed() << "s)\n" );
        FLOG( FLog::Controller << "\t\t Computation P2P : " << computationCounter.cumulated() << " s\n" );
327 328 329
    }

    void L2PPass(){
BRAMAS Berenger's avatar
BRAMAS Berenger committed
330
        FLOG( FLog::Controller.write("\tStart L2P Pass\n").write(FLog::Flush); );
BRAMAS Berenger's avatar
BRAMAS Berenger committed
331
        FLOG(FTic counterTime);
332 333 334 335 336 337 338 339 340 341 342 343 344 345

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

        // for each leafs
        do{
            #pragma omp task firstprivate(octreeIterator)
            {
                kernels[omp_get_thread_num()]->L2P(octreeIterator.getCurrentCell(), octreeIterator.getCurrentListTargets());
            }
        } while(octreeIterator.moveRight());

        #pragma omp taskwait

BRAMAS Berenger's avatar
BRAMAS Berenger committed
346
        FLOG( FLog::Controller << "\tFinished (@Direct Pass (L2P) = "  << counterTime.tacAndElapsed() << "s)\n" );
347 348 349 350 351 352 353 354
    }

};


#endif //FFMMALGORITHMTASK_HPP