Debian Codegraph @

packages/seacas/applications/nem_slice/fix_column_partitions.C

raw
1 /*
2 * Copyright(C) 1999-2021, 2023, 2024 National Technology & Engineering Solutions
3 * of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with
4 * NTESS, the U.S. Government retains certain rights in this software.
5 *
6 * See packages/seacas/LICENSE for details
7 */
8
9 #include "elb.h" // for LB_Description<INT>, etc
10 #include "elb_elem.h"
11 #include "elb_err.h"
12 #include "fix_column_partitions.h"
13 #include <array>
14 #include <cmath>
15 #include <fmt/core.h>
16 #include <iostream>
17 #include <map>
18 #include <vector>
19
20 namespace {
21 // Opposite side IDs in a hex according to Exodus II convention
22
23 const std::array<int, 6> hex_opp_side{3, 4, 1, 2, 6, 5};
24
25 /*! @brief Given an element and a side, find the adjacent element to that side
26 @param cur_elem Current element under consideration
27 @param etype Element type
28 @param side_id Side across which we want to find an adjacent element
29 @param nadj Number of elements adjacent to cur_elem (from graph description)
30 @param adj Pointer to elements adjacent to cur_elem (from graph description)
31 @param mesh Mesh Description to get connectivity, element types, ...
32 @param adj_elem ID of adjacent element (-1 if not found)
33 @param adj_side Local ID of common side in adjacent element (0 if adj_elem not found)
34 */
35
36 template <typename INT>
37 void find_adjacent_element(INT cur_elem, ElementType etype, int side_id, int nadj, INT const *adj,
38 Mesh_Description<INT> const *const mesh, INT *adj_elem, int *adj_side)
39 {
40 *adj_elem = -1;
41
42 // Get nodes of this side (face) of the element
43
44 int nsnodes = is_hex(etype) ? 4 : 3;
45 std::array<INT, 9> side_nodes{}; // SHELL9 has 9 nodes on a face.
46
47 INT *elnodes = mesh->connect[cur_elem];
48 ss_to_node_list(etype, elnodes, side_id, Data(side_nodes));
49
50 // How would these side's nodes be if they were viewed from the
51 // adjacent element
52
53 std::array<INT, 9> side_nodes_flipped{0}; // Realistically: 4, max possible: 9
54 get_ss_mirror(etype, Data(side_nodes), side_id, Data(side_nodes_flipped));
55
56 for (int i = 0; i < nadj; i++) {
57 INT adj_elem_id = adj[i] - 1; // Adjacency graph entries start from 1
58 ElementType etype2 = mesh->elem_type[adj_elem_id];
59
60 // Does this side occurs in the adjacent element?
61
62 INT *elnodes2 = mesh->connect[adj_elem_id];
63
64 // options to keep 'get_side_id' to not flip out if side nodes are
65 // not found in element
66
67 int skip_check = 2;
68 int partial_adj = 1;
69 *adj_side =
70 get_side_id(etype2, elnodes2, nsnodes, Data(side_nodes_flipped), skip_check, partial_adj);
71
72 if (*adj_side > 0) {
73 *adj_elem = adj_elem_id;
74 return;
75 }
76 }
77 }
78 } // namespace
79
80 /*! @brief If the mesh is columnar, ensure each column is fully in on partition
81 @param lb Load balancing or partitioning information (may be modified)
82 @param mesh Description of the mesh
83 @param graph Description of the adjacency graph
84
85 **** ASSUMES COLUMNS ARE STRICTLY VERTICAL, i.e., NO LATERAL FACE ****
86 **** HAS A Z-COMPONENT IN ITS NORMAL ****
87
88 */
89
90 template int fix_column_partitions(LB_Description<int> *lb, Mesh_Description<int> const *const mesh,
91 Graph_Description<int> const *const graph);
92 template int fix_column_partitions(LB_Description<int64_t> *lb,
93 Mesh_Description<int64_t> const *const mesh,
94 Graph_Description<int64_t> const *const graph);
95
96 template <typename INT>
97 int fix_column_partitions(LB_Description<INT> *lb, Mesh_Description<INT> const *const mesh,
98 Graph_Description<INT> const *const graph)
99 {
100 int nmoved = 0;
101 auto nel = mesh->num_elems;
102 auto nnod = mesh->num_nodes;
103
104 // a flag to indicate if a particular element has been processed
105 std::vector<bool> processed_flag(nel, false);
106
107 // Go through elements and attempt to discover a column of elements
108 // that contain it. Then check if the column is all on one partition
109 // - if not, fix it
110
111 for (size_t i = 0; i < nel; i++) {
112 if (processed_flag[i]) {
113 continue;
114 }
115
116 ElementType etype = mesh->elem_type[i];
117
118 // Only hexes and wedges can be stacked in columns
119 if (!is_hex(etype) && !is_wedge(etype)) {
120 continue;
121 }
122
123 // retrieve the faces of this element - faces are described by the
124 // local numbering of nodes with respect to the element node list
125
126 INT *elnodes = mesh->connect[i];
127 int nelnodes = get_elem_info(ElementInfo::NNODES, etype);
128
129 float elcoord[27][3];
130 for (int j = 0; j < nelnodes; j++) {
131 for (int d = 0; d < 3; d++) {
132 elcoord[j][d] = mesh->coords[elnodes[j] + d * nnod];
133 }
134 }
135
136 int top_side0 = 0;
137 int bot_side0 = 0;
138 int nelfaces = get_elem_info(ElementInfo::NSIDES, etype);
139
140 // Find top and bottom faces by eliminating lateral faces under
141 // the assumption that lateral face normals have no Z component
142
143 int count = 0;
144 for (int j = 0; j < nelfaces; j++) {
145 std::array<INT, 9>
146 fnodes{}; // Should only need 4, but ss_to_node_list can potentially access 9 (SHELL9).
147
148 int nfn = 4;
149 if (is_wedge(etype)) {
150 if (j < 3) {
151 // lateral faces of wedge according to Exodus II - cannot be
152 // up/down faces in a column
153 continue;
154 }
155 nfn = 3;
156 }
157
158 // Nodes of the side/face
159 ss_to_node_list(etype, mesh->connect[i], j + 1, Data(fnodes));
160
161 // Translate global IDs of side nodes to local IDs in element
162 std::array<int, 9> fnodes_loc{0};
163 for (int k = 0; k < nfn; k++) {
164 bool found = false;
165 for (int k2 = 0; k2 < nelnodes; k2++) {
166 if (fnodes[k] == elnodes[k2]) {
167 fnodes_loc[k] = k2;
168 found = true;
169 break;
170 }
171 }
172 if (!found) {
173 Gen_Error(0, "FATAL: side/face node not found in element node list?");
174 }
175 }
176
177 std::array<double, 3> normal{0.0, 0.0, 0.0};
178 if (nfn == 3) {
179 std::array<double, 3> v0;
180 std::array<double, 3> v1;
181 for (int d = 0; d < 3; d++) {
182 v0[d] = elcoord[fnodes_loc[1]][d] - elcoord[fnodes_loc[0]][d];
183 v1[d] = elcoord[fnodes_loc[nfn - 1]][d] - elcoord[fnodes_loc[0]][d];
184 }
185
186 // cross product to get normal corner
187 for (int d = 0; d < 3; d++) {
188 normal[d] = v0[(d + 1) % 3] * v1[(d + 2) % 3] - v0[(d + 2) % 3] * v1[(d + 1) % 3];
189 }
190 }
191 else {
192 for (int k = 0; k < nfn; k++) {
193 std::array<double, 3> v0;
194 std::array<double, 3> v1;
195 for (int d = 0; d < 3; d++) {
196 v0[d] = elcoord[fnodes_loc[(k + 1) % nfn]][d] - elcoord[fnodes_loc[k]][d];
197 v1[d] = elcoord[fnodes_loc[(k - 1 + nfn) % nfn]][d] - elcoord[fnodes_loc[k]][d];
198 }
199
200 // cross product to get normal at corner - add to face normal
201 for (int d = 0; d < 3; d++) {
202 normal[d] += v0[(d + 1) % 3] * v1[(d + 2) % 3] - v0[(d + 2) % 3] * v1[(d + 1) % 3];
203 }
204 }
205 double len = normal[0] * normal[0] + normal[1] * normal[1] + normal[2] * normal[2];
206 if (len > 1.0e-24) { // Don't normalize nearly zero-length vectors
207 for (double &d : normal) {
208 d /= len;
209 }
210 }
211 }
212 if (fabs(normal[2]) > 1.0e-12) { // non-zero
213 if (normal[2] > 0.0) {
214 top_side0 = j + 1; // side id counting starts from 1
215 }
216 else {
217 bot_side0 = j + 1;
218 }
219 count++;
220 }
221 } // for (j = 0; j < nelfaces; j++)
222 if (count > 2) {
223 #ifdef DEBUG
224 Gen_Error(1, "WARNING: more than two faces with non-zero Z-components of normal.");
225 #endif
226 Gen_Error(1, "WARNING: Mesh may not be strictly columnar. Initial partitioning unchanged.");
227 return 0;
228 }
229 if (count < 2) {
230 #ifdef DEBUG
231 Gen_Error(1, "WARNING: could not find up and down faces for element.");
232 #endif
233 Gen_Error(1, "WARNING: Mesh may not be strictly columnar. Initial partitioning unchanged.");
234 return 0;
235 }
236
237 // Found top and bottom sides/faces of current element. Build a
238 // lists of elements stacked above it and below it.
239
240 std::vector<INT> above_list;
241 std::vector<INT> below_list;
242
243 INT cur_elem = i;
244 INT adj_elem = -1;
245 int adj_side = -1;
246 int bot_side = bot_side0;
247 int top_side = top_side0;
248 bool upsearch_done = false;
249 while (!upsearch_done) {
250
251 auto nadj = graph->start[cur_elem + 1] - graph->start[cur_elem];
252 INT const *adj = Data(graph->adj) + graph->start[cur_elem];
253 find_adjacent_element(cur_elem, etype, top_side, nadj, adj, mesh, &adj_elem, &adj_side);
254 if (adj_elem == -1) {
255 upsearch_done = true;
256 }
257 else {
258 above_list.push_back(adj_elem);
259 cur_elem = adj_elem;
260 bot_side = adj_side;
261
262 if (is_hex(etype)) {
263 top_side = hex_opp_side[bot_side - 1];
264 }
265 else { // wedge
266 if (bot_side != 4 && bot_side != 5) {
267 Gen_Error(0, "FATAL: Expected bottom side in wedge to be side 4 or 5");
268 return 0;
269 }
270 top_side = (bot_side == 4) ? 5 : 4;
271 }
272 if (processed_flag[adj_elem]) {
273 Gen_Error(0, "FATAL: repeated column elements");
274 return 0;
275 }
276 processed_flag[adj_elem] = true;
277 }
278 } // while (!upsearch_done)
279 auto nabove = above_list.size();
280
281 cur_elem = i;
282 bot_side = bot_side0;
283 top_side = top_side0;
284 bool downsearch_done = false;
285 while (!downsearch_done) {
286
287 auto nadj = graph->start[cur_elem + 1] - graph->start[cur_elem];
288 INT const *adj = Data(graph->adj) + graph->start[cur_elem];
289 find_adjacent_element(cur_elem, etype, bot_side, nadj, adj, mesh, &adj_elem, &adj_side);
290 if (adj_elem == -1) {
291 downsearch_done = true;
292 }
293 else {
294 below_list.push_back(adj_elem);
295 cur_elem = adj_elem;
296 top_side = adj_side;
297
298 if (is_hex(etype)) {
299 bot_side = hex_opp_side[top_side - 1];
300 }
301 else { // wedge
302 if (top_side != 4 && top_side != 5) {
303 Gen_Error(0, "FATAL: Expected top side in wedge to be side 4 or 5");
304 return 0;
305 }
306 bot_side = (top_side == 4) ? 5 : 4;
307 }
308 if (processed_flag[adj_elem]) {
309 Gen_Error(0, "FATAL: repeated column elements");
310 return 0;
311 }
312 processed_flag[adj_elem] = true;
313 }
314 } // while (!upsearch_done)
315 auto nbelow = below_list.size();
316
317 // Build list of elements in column from top to bottom
318 // Code below assumes we are NOT compiling with C++11 standard enabled
319 // If we do, we can simplify the code quite a bit
320
321 std::vector<INT> colelems;
322 colelems.reserve(nabove + nbelow + 1);
323 auto rit = above_list.rbegin();
324 while (rit != above_list.rend()) {
325 colelems.push_back(*rit);
326 ++rit;
327 }
328 colelems.push_back(i);
329
330 auto it = below_list.begin();
331 while (it != below_list.end()) {
332 colelems.push_back(*it);
333 ++it;
334 }
335
336 // Make all the other elements in the column be on the same
337 // processor as the one that majority of the elements are on.
338 // To do that make a unique list of processors
339 std::map<int, int> procid_elcount;
340
341 it = colelems.begin();
342 while (it != colelems.end()) {
343 INT elem2 = *it;
344 int procid = lb->vertex2proc[elem2];
345
346 // Try to insert 'procid' with element count of 1 as a new entry
347 // If it fails, the processor is already in the map; then just
348 // increment the element count
349
350 std::pair<std::map<int, int>::iterator, bool> status =
351 procid_elcount.insert(std::pair<int, int>(procid, 1));
352 if (!status.second) { // procid already in map; could not insert
353 auto itmap = status.first;
354 (itmap->second)++;
355 }
356 ++it;
357 }
358
359 // Which processor has a dominant presence in this column?
360 int max_procid = -1;
361 int max_elems = 0;
362 auto itmap = procid_elcount.begin();
363 while (itmap != procid_elcount.end()) {
364 if (itmap->second > max_elems) {
365 max_procid = itmap->first;
366 max_elems = itmap->second;
367 }
368 ++itmap;
369 }
370
371 // Switch all elements in the column to the dominant processor
372 it = colelems.begin();
373 while (it != colelems.end()) {
374 INT elem2 = *it;
375 if (lb->vertex2proc[elem2] != max_procid) {
376 #ifdef DEBUG
377 fmt::print(" Reassigning element {} from proc {} to {}\n", elem2, lb->vertex2proc[elem2],
378 max_procid);
379 #endif
380 lb->vertex2proc[elem2] = max_procid;
381 ++nmoved;
382 }
383 ++it;
384 }
385
386 } // for (int i = 0; i < nel; i++)
387
388 return nmoved;
389 } // fix_column_partitions.C