Debian Codegraph @

dune/uggrid/parallel/dddif/lbrcb.cc

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 /****************************************************************************/
6 /* File: lbrcb.c */
7 /* Purpose: simple static load balancing scheme for testing initial */
8 /* grid distribution */
9 /****************************************************************************/
10
11 #ifdef ModelP
12
13 #include <config.h>
14
15 #include <algorithm>
16 #include <vector>
17 #include <array>
18 #include <iterator>
19
20 #include <dune/common/exceptions.hh>
21 #include <dune/common/fvector.hh>
22 #include <dune/uggrid/parallel/ppif/ppifcontext.hh>
23
24 #include "parallel.h"
25 #include <dune/uggrid/low/namespace.h>
26 #include <dune/uggrid/ugdevices.h>
27 #include <dune/uggrid/gm/evm.h>
28 #include <dune/uggrid/gm/ugm.h>
29
30 USING_UG_NAMESPACES
31 using namespace PPIF;
32
33 START_UGDIM_NAMESPACE
34
35 // only used in this source file
36 struct LB_INFO {
37 ELEMENT *elem;
38 Dune::FieldVector<DOUBLE, DIM> center;
39 };
40
41 /**
42 * Bisects a 2D processor array along the longest axis
43 *
44 * std::array<int, 4> specifies a part of a 2D processor array
45 * with the entries (x, y, dx, dy), where
46 * (x, y): bottom left position in 2D processor array
47 * (dx, dy): size of the 2D processor array
48 */
49 static std::array<std::array<int, 4>, 2> BisectProcessorArray (const std::array<int, 4>& procs)
50 {
51 const int dx = procs[2];
52 const int dy = procs[3];
53 if (dx >= dy)
54 {
55 const int part0Size = dx/2;
56 const int part1Size = dx-part0Size;
57 return {{{ procs[0], procs[1], part0Size, dy },
58 { procs[0]+part0Size, procs[1], part1Size, dy }}};
59 }
60 else
61 {
62 const int part0Size = dy/2;
63 const int part1Size = dy-part0Size;
64 return {{{ procs[0], procs[1], dx, part0Size },
65 { procs[0], procs[1]+part0Size, dx, part1Size }}};
66 }
67 }
68
69 /**
70 * Compute the number of processor in a processor grid
71 */
72 static int NumProcessorsInPart (const std::array<int, 4>& procs)
73 {
74 return procs[2]*procs[3];
75 }
76
77 /**
78 * Compute the ratio of a processor splitting done by BisectProcessorArray
79 * returns real number between 0 and 1
80 */
81 static DOUBLE ComputeProcessorSplitRatio (const std::array<std::array<int, 4>, 2>& parts)
82 {
83 const int numProcsPart0 = NumProcessorsInPart(parts[0]);
84 const int numProcsPart1 = NumProcessorsInPart(parts[1]);
85 return static_cast<DOUBLE>(numProcsPart0) / static_cast<DOUBLE>(numProcsPart0 + numProcsPart1);
86 }
87
88 /****************************************************************************/
89 /*
90 RecursiveCoordinateBisection - balance all local triangles
91
92 PARAMETERS:
93 . begin - iterator to LB_INFO vector
94 . end - iterator to LB_INFO vector
95 . procs - (px, py, dx, dy) processor grid, where
96 (px, py): bottom left position in 2D processor array
97 (dx, dy): size of the 2D processor array
98 . bisectionAxis - axis along which we sort: 0=x, 1=y, 2=z
99
100 DESCRIPTION:
101 This function, a simple load balancing algorithm, balances all local triangles using a 'recursive coordinate bisection' scheme,
102
103 RETURN VALUE:
104 void
105 */
106 /****************************************************************************/
107
108 static void RecursiveCoordinateBisection (const PPIF::PPIFContext& ppifContext,
109 const std::vector<LB_INFO>::iterator& begin,
110 const std::vector<LB_INFO>::iterator& end,
111 const std::array<int, 4> procs,
112 int bisectionAxis = 0)
113 {
114 // empty element range for these processors: nothing to do
115 if (begin == end)
116 return;
117
118 // we found a single destination rank for this element subrange: end recursion
119 if (NumProcessorsInPart(procs) <= 1)
120 {
121 for (auto it = begin; it != end; ++it)
122 {
123 const int destinationRank = procs[1]*ppifContext.dimX()+procs[0];
124 PARTITION(it->elem) = destinationRank;
125 }
126 return;
127 }
128
129 // bisect processors and bisect element accordingly
130 const auto procPartitions = BisectProcessorArray(procs);
131 const auto splitRatio = ComputeProcessorSplitRatio(procPartitions);
132 const auto numElements = std::distance(begin, end);
133 const auto middle = begin + static_cast<int>(numElements*splitRatio);
134
135 // partial sort such that middle iterator points to the bisection element
136 std::nth_element(begin, middle, end,
137 [bisectionAxis](const auto& a, const auto& b)
138 {
139 auto eps = (b.center-a.center); eps *= 1e-7;
140 for (int dimIdx = 0; dimIdx < DIM; ++dimIdx)
141 {
142 const int i = (dimIdx+bisectionAxis)%DIM;
143 if (a.center[i] < b.center[i] - eps[i]) return true;
144 if (a.center[i] > b.center[i] + eps[i]) return false;
145 }
146 return false;
147 }
148 );
149
150 // we simply alternate between the axis hoping for a decent partition
151 // this could be probably improved by sorting along the longest axis but
152 // computing the longest axis is expensive if we have to compute the grids bounding box every time
153 const int nextBisectionAxis = (bisectionAxis+1)%DIM;
154
155 RecursiveCoordinateBisection(ppifContext, begin, middle, procPartitions[0], nextBisectionAxis);
156 RecursiveCoordinateBisection(ppifContext, middle, end, procPartitions[1], nextBisectionAxis);
157 }
158
159 /**
160 * Compute an element's center of mass
161 */
162 static Dune::FieldVector<DOUBLE, DIM> CenterOfMass (ELEMENT *e)
163 {
164 Dune::FieldVector<DOUBLE, DIM> center(0.0);
165
166 const auto corners = CORNERS_OF_ELEM(e);
167 for(int i=0; i<corners; i++)
168 center += CVECT(MYVERTEX(CORNER(e,i)));
169
170 center /= corners;
171 return center;
172 }
173
174 /****************************************************************************/
175 /*
176 InheritPartition -
177
178 SYNOPSIS:
179 static void InheritPartition (ELEMENT *e);
180
181 PARAMETERS:
182 . e
183
184 DESCRIPTION:
185
186 RETURN VALUE:
187 void
188 */
189 /****************************************************************************/
190
191 static void InheritPartition (ELEMENT *e)
192 {
193 ELEMENT *SonList[MAX_SONS];
194
195 if (GetAllSons(e,SonList)==0)
196 {
197 for(int i=0; i<MAX_SONS && SonList[i]!=NULL; i++)
198 {
199 PARTITION(SonList[i]) = PARTITION(e);
200 InheritPartition(SonList[i]);
201 }
202 }
203 }
204
205
206 /****************************************************************************/
207 /*
208 BalanceGridRCB -
209
210 PARAMETERS:
211 . theMG
212 . level
213
214 DESCRIPTION:
215 Load balance one level of a multigrid hierarchy
216 using recursive coordinate bisection
217
218 RETURN VALUE:
219 void
220 */
221 /****************************************************************************/
222
223 void BalanceGridRCB (MULTIGRID *theMG, int level)
224 {
225 const GRID *theGrid = GRID_ON_LEVEL(theMG,level);
226 DDD::DDDContext& context = theMG->dddContext();
227 const PPIF::PPIFContext& ppifContext = theMG->ppifContext();
228
229 /* distributed grids cannot be redistributed by this function */
230 if (not context.isMaster() && FIRSTELEMENT(theGrid) != NULL)
231 DUNE_THROW(Dune::NotImplemented, "Redistributing distributed grids using recursive coordinate bisection is not implemented!");
232
233 if (context.isMaster())
234 {
235 if (NT(theGrid) == 0)
236 {
237 UserWriteF("WARNING in BalanceGridRCB: no elements in grid\n");
238 return;
239 }
240
241 std::vector<LB_INFO> lbinfo(NT(theGrid));
242 int i = 0;
243 for (auto e=FIRSTELEMENT(theGrid); e!=NULL; e=SUCCE(e))
244 {
245 lbinfo[i].elem = e;
246 lbinfo[i].center = CenterOfMass(e);
247 ++i;
248 }
249
250 RecursiveCoordinateBisection(ppifContext, lbinfo.begin(), lbinfo.end(), {0, 0, ppifContext.dimX(), ppifContext.dimY()});
251
252 IFDEBUG(dddif,1)
253 for (auto e=FIRSTELEMENT(theGrid); e!=NULL; e=SUCCE(e))
254 UserWriteF("elem %08x has dest=%d\n", DDD_InfoGlobalId(PARHDRE(e)), PARTITION(e));
255 ENDDEBUG
256
257 for (auto e=FIRSTELEMENT(theGrid); e!=NULL; e=SUCCE(e))
258 InheritPartition (e);
259
260 }
261 }
262
263 END_UGDIM_NAMESPACE
264
265 #endif /* ModelP */