FMEMultipoleKernel.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/energybased/fast_multipole_embedder/FMEFunc.h>
#include <ogdf/energybased/fast_multipole_embedder/FMEKernel.h>
#include <ogdf/energybased/fast_multipole_embedder/LinearQuadtree.h>
 
#include <cstdint>
#include <list>
 
namespace ogdf::fast_multipole_embedder {
class ArrayGraph;
class FMEThread;
} // namespace ogdf::fast_multipole_embedder
 
namespace ogdf {
namespace fast_multipole_embedder {
 
struct ArrayPartition {
    uint32_t begin;
    uint32_t end;
 
    template<typename Func>
    void for_loop(Func& func) {
        for (uint32_t i = begin; i <= end; i++) {
            func(i);
        }
    }
};
 
class FMEMultipoleKernel : public FMEKernel {
public:
    explicit FMEMultipoleKernel(FMEThread* pThread) : FMEKernel(pThread) { }
 
    static FMEGlobalContext* allocateContext(ArrayGraph* pGraph, FMEGlobalOptions* pOptions,
            uint32_t numThreads);
 
    static void deallocateContext(FMEGlobalContext* globalContext);
 
    void quadtreeConstruction(ArrayPartition& nodePointPartition);
 
    void multipoleApproxSingleThreaded(ArrayPartition& nodePointPartition);
 
    void multipoleApproxSingleWSPD(ArrayPartition& nodePointPartition);
 
    void multipoleApproxNoWSPDStructure(ArrayPartition& nodePointPartition);
 
    void multipoleApproxFinal(ArrayPartition& nodePointPartition);
 
    void operator()(FMEGlobalContext* globalContext);
 
    inline ArrayPartition arrayPartition(uint32_t n) {
        return arrayPartition(n, threadNr(), numThreads(), 16);
    }
 
    inline ArrayPartition arrayPartition(uint32_t n, uint32_t threadNr, uint32_t numThreads,
            uint32_t chunkSize) {
        ArrayPartition result;
        if (!n) {
            result.begin = 1;
            result.end = 0;
            return result;
        }
        if (n >= numThreads * chunkSize) {
            uint32_t s = n / (numThreads * chunkSize);
            uint32_t o = s * chunkSize * threadNr;
            if (threadNr == numThreads - 1) {
                result.begin = o;
                result.end = n - 1;
            } else {
                result.begin = o;
                result.end = o + s * chunkSize - 1;
            }
        } else {
            if (threadNr == 0) {
                result.begin = 0;
                result.end = n - 1;
            } else {
                result.begin = 1;
                result.end = 0;
            }
        }
        return result;
    }
 
    template<typename F>
    inline void for_loop(const ArrayPartition& partition, F func) {
        if (partition.begin > partition.end) {
            return;
        }
        for (uint32_t i = partition.begin; i <= partition.end; i++) {
            func(i);
        }
    }
 
    template<typename F>
    inline void for_tree_partition(F functor) {
        for (LinearQuadtree::NodeID id : m_pLocalContext->treePartition.nodes) {
            functor(id);
        }
    }
 
    template<typename T, typename C>
    inline void sort_single(T* ptr, uint32_t n, C comparer) {
        if (isMainThread()) {
            std::sort(ptr, ptr + n, comparer);
        }
    }
 
    template<typename T, typename C>
    inline void sort_parallel(T* ptr, uint32_t n, C comparer) {
        if (n < numThreads() * 1000 || numThreads() == 1) {
            sort_single(ptr, n, comparer);
        } else {
            sort_parallel(ptr, n, comparer, 0, numThreads());
        }
    }
 
    template<typename T, typename C>
    inline void sort_parallel(T* ptr, uint32_t n, C comparer, uint32_t threadNrBegin,
            uint32_t numThreads) {
        if (n <= 1) {
            return;
        }
        if (numThreads == 1) {
            std::sort(ptr, ptr + n, comparer);
        } else {
            uint32_t half = n >> 1;
            uint32_t halfThreads = numThreads >> 1;
            if (this->threadNr() < threadNrBegin + halfThreads) {
                sort_parallel(ptr, half, comparer, threadNrBegin, halfThreads);
            } else {
                sort_parallel(ptr + half, n - half, comparer, threadNrBegin + halfThreads,
                        halfThreads);
            }
 
            // wait until all threads are ready.
            sync();
            if (this->threadNr() == threadNrBegin) {
                std::inplace_merge(ptr, ptr + half, ptr + n, comparer);
            }
        }
    }
 
private:
    FMEGlobalContext* m_pGlobalContext = nullptr;
    FMELocalContext* m_pLocalContext = nullptr;
};
 
}
}