Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
FMEMultipoleKernel.h
Go to the documentation of this file.
1
32#pragma once
33
36
37namespace ogdf {
38namespace fast_multipole_embedder {
39
43
44 template<typename Func>
45 void for_loop(Func& func) {
46 for (uint32_t i = begin; i <= end; i++) {
47 func(i);
48 }
49 }
50};
51
53public:
55
59
61 static void deallocateContext(FMEGlobalContext* globalContext);
62
65
68
71
74
77
79 void operator()(FMEGlobalContext* globalContext);
80
83 return arrayPartition(n, threadNr(), numThreads(), 16);
84 }
85
88 uint32_t chunkSize) {
89 ArrayPartition result;
90 if (!n) {
91 result.begin = 1;
92 result.end = 0;
93 return result;
94 }
95 if (n >= numThreads * chunkSize) {
96 uint32_t s = n / (numThreads * chunkSize);
97 uint32_t o = s * chunkSize * threadNr;
98 if (threadNr == numThreads - 1) {
99 result.begin = o;
100 result.end = n - 1;
101 } else {
102 result.begin = o;
103 result.end = o + s * chunkSize - 1;
104 }
105 } else {
106 if (threadNr == 0) {
107 result.begin = 0;
108 result.end = n - 1;
109 } else {
110 result.begin = 1;
111 result.end = 0;
112 }
113 }
114 return result;
115 }
116
118 template<typename F>
119 inline void for_loop(const ArrayPartition& partition, F func) {
120 if (partition.begin > partition.end) {
121 return;
122 }
123 for (uint32_t i = partition.begin; i <= partition.end; i++) {
124 func(i);
125 }
126 }
127
129 template<typename F>
132 functor(id);
133 }
134 }
135
137 template<typename T, typename C>
138 inline void sort_single(T* ptr, uint32_t n, C comparer) {
139 if (isMainThread()) {
140 std::sort(ptr, ptr + n, comparer);
141 }
142 }
143
145 template<typename T, typename C>
146 inline void sort_parallel(T* ptr, uint32_t n, C comparer) {
147 if (n < numThreads() * 1000 || numThreads() == 1) {
148 sort_single(ptr, n, comparer);
149 } else {
150 sort_parallel(ptr, n, comparer, 0, numThreads());
151 }
152 }
153
155 template<typename T, typename C>
156 inline void sort_parallel(T* ptr, uint32_t n, C comparer, uint32_t threadNrBegin,
158 if (n <= 1) {
159 return;
160 }
161 if (numThreads == 1) {
162 std::sort(ptr, ptr + n, comparer);
163 } else {
164 uint32_t half = n >> 1;
166 if (this->threadNr() < threadNrBegin + halfThreads) {
168 } else {
171 }
172
173 // wait until all threads are ready.
174 sync();
175 if (this->threadNr() == threadNrBegin) {
176 std::inplace_merge(ptr, ptr + half, ptr + n, comparer);
177 }
178 }
179 }
180
181private:
184};
185
186}
187}
Definitions of various auxiliary classes for FME layout.
Declaration of FME kernel.
bool isMainThread() const
returns true if this is the main thread ( the main thread is always the first thread )
Definition FMEKernel.h:57
uint32_t threadNr() const
returns the index of the thread ( 0.. numThreads()-1 )
Definition FMEKernel.h:51
uint32_t numThreads() const
returns the total number of threads in the pool
Definition FMEKernel.h:54
ArrayPartition arrayPartition(uint32_t n, uint32_t threadNr, uint32_t numThreads, uint32_t chunkSize)
returns an array partition for the given threadNr and thread count
void multipoleApproxSingleThreaded(ArrayPartition &nodePointPartition)
the single threaded version without fences
static FMEGlobalContext * allocateContext(ArrayGraph *pGraph, FMEGlobalOptions *pOptions, uint32_t numThreads)
allocate the global and local contexts used by an instance of this kernel
void sort_parallel(T *ptr, uint32_t n, C comparer)
lazy parallel sorting for num_threads = power of two
void sort_single(T *ptr, uint32_t n, C comparer)
sorting single threaded
void quadtreeConstruction(ArrayPartition &nodePointPartition)
sub procedure for quadtree construction
void multipoleApproxNoWSPDStructure(ArrayPartition &nodePointPartition)
new but slower method, parallel wspd computation without using the wspd structure
ArrayPartition arrayPartition(uint32_t n)
creates an array partition with a default chunksize of 16
static void deallocateContext(FMEGlobalContext *globalContext)
free the global and local context
void sort_parallel(T *ptr, uint32_t n, C comparer, uint32_t threadNrBegin, uint32_t numThreads)
lazy parallel sorting for num_threads = power of two
void multipoleApproxFinal(ArrayPartition &nodePointPartition)
the final version, the wspd structure is only used for the top of the tree
void multipoleApproxSingleWSPD(ArrayPartition &nodePointPartition)
the original algorithm which runs the WSPD completely single threaded
void for_loop(const ArrayPartition &partition, F func)
for loop on a partition
void for_tree_partition(F functor)
for loop on the tree partition
void operator()(FMEGlobalContext *globalContext)
main function of the kernel
The fast multipole embedder work thread class.
Definition FMEThread.h:77
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
the main global options for a run
Definition FMEFunc.h:66
FMETreePartition treePartition
tree partition assigned to the thread
Definition FMEFunc.h:126
std::list< LinearQuadtree::NodeID > nodes
Definition FMEFunc.h:49