Debian Codegraph @

packages/seacas/applications/nem_slice/elb_loadbal.C

raw
1 /*
2 * Copyright(C) 1999-2021, 2023, 2024, 2025 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 /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
10 * Functions contained in this file:
11 * generate_loadbal()
12 * generate_maps()
13 * nodal_dist()
14 * elemental_dist()
15 * ilog2i()
16 *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
17 #include <cassert> // for assert
18 #include <cfloat> // for FLT_MAX
19 #include <climits> // for INT_MAX
20 #include <cmath> /* Needed for ZPINCH_assign */
21 #include <copy_string_cpp.h>
22 #include <cstdlib> // for malloc, free, realloc, exit, etc
23 #include <cstring> // for strcat
24 #include <fmt/ostream.h>
25
26 #include "chaco.h" // for input_assign, interface
27 #include "elb.h" // for LB_Description<INT>, etc
28 #include "elb_elem.h" // for ElementType, get_elem_info, etc
29 #include "elb_err.h" // for Gen_Error
30 #include "elb_graph.h" // for generate_graph
31 #include "elb_groups.h" // for get_group_info
32 #include "elb_loadbal.h"
33 #include "elb_util.h" // for find_inter, etc
34 #include "fix_column_partitions.h"
35 #include "vector_data.h"
36
37 #ifndef M_PI
38 #define M_PI 3.14159265358979323846264338327
39 #define M_PI_2 (M_PI / 2.0)
40 #endif
41
42 #ifdef USE_ZOLTAN
43 #include "zoltan.h" // for Zoltan_Set_Param, etc
44 #include "zoltan_types.h" // for ZOLTAN_ID_PTR*, ZOLTAN_OK, etc
45 #include <mpi.h> // for MPI_Finalize, etc
46 #endif
47
48 int ilog2i(size_t n)
49 {
50 size_t i = 0;
51 size_t n1 = n;
52 while ((n1 >>= 1) != 0U) {
53 ++i;
54 }
55
56 if (static_cast<size_t>(1) << i != n) {
57 return (-1);
58 }
59 return (i);
60 }
61
62 namespace {
63 template <typename INT>
64 int nodal_dist(LB_Description<INT> * /*lb*/, Machine_Description * /*machine*/,
65 Mesh_Description<INT> * /*mesh*/, Graph_Description<INT> * /*graph*/);
66
67 template <typename INT>
68 int elemental_dist(LB_Description<INT> * /*lb*/, Machine_Description * /*machine*/,
69 Mesh_Description<INT> * /*mesh*/, Graph_Description<INT> * /*graph*/,
70 Problem_Description * /*problem*/);
71
72 /* ZPINCH partitioning interface */
73 int ZPINCH_assign(Machine_Description * /*machine*/, int /*ndot*/, const float * /*x*/,
74 const float * /*y*/, const float * /*z*/, int * /*part*/);
75
76 /* BRICK partitioning interface */
77 int BRICK_assign(Machine_Description * /*machine*/, int /*ndot*/, const float * /*x*/,
78 const float * /*y*/, const float * /*z*/, int * /*part*/);
79
80 #ifdef USE_ZOLTAN
81 /* ZOLTAN_RCB partitioning interface */
82 int ZOLTAN_assign(const char * /*method*/, int /*totalproc*/, size_t /*ndot*/, int * /*vwgt*/,
83 float * /*x*/, float * /*y*/, float * /*z*/, int /*ignore_z*/, int * /*part*/,
84 int /*argc*/, char ** /*argv*/);
85 #endif
86 void BALANCE_STATS(Machine_Description * /*machine*/, const int * /*wgt*/, size_t /*ndot*/,
87 int * /*part*/);
88
89 template <typename INT>
90 int identify_mechanisms(Machine_Description *machine, Problem_Description *problem,
91 Mesh_Description<INT> *mesh, LB_Description<INT> *lb,
92 Graph_Description<INT> *graph, Issues check_type);
93
94 int extract_connected_lists(int nrow, const int *columns, const int *rows, int *list,
95 std::vector<int> &list_ptr);
96 } // namespace
97
98 /*****************************************************************************/
99 /*****************************************************************************/
100 /*****************************************************************************/
101 /* Function generate_loadbal() begins
102 *----------------------------------------------------------------------------
103 * This function calls Chaco to load balance the given problem.
104 *****************************************************************************/
105 template int generate_loadbal(Machine_Description *machine, Problem_Description *problem,
106 Mesh_Description<int> *mesh, LB_Description<int> *lb,
107 Solver_Description *solve, Graph_Description<int> *graph,
108 Weight_Description *weight, Sphere_Info *sphere, int argc,
109 char *argv[]);
110 template int generate_loadbal(Machine_Description *machine, Problem_Description *problem,
111 Mesh_Description<int64_t> *mesh, LB_Description<int64_t> *lb,
112 Solver_Description *solve, Graph_Description<int64_t> *graph,
113 Weight_Description *weight, Sphere_Info *sphere, int argc,
114 char *argv[]);
115
116 /* Variables used in Chaco */
117 extern "C" {
118 extern int FREE_GRAPH;
119 extern int CONNECTED_DOMAINS;
120 extern int OUTPUT_ASSIGN;
121 }
122
123 template <typename INT>
124 int generate_loadbal(Machine_Description *machine, Problem_Description *problem,
125 Mesh_Description<INT> *mesh, LB_Description<INT> *lb,
126 Solver_Description *solve, Graph_Description<INT> *graph,
127 Weight_Description *weight, Sphere_Info *sphere, int argc, char *argv[])
128 {
129 const char *assignfile = nullptr;
130
131 int flag = 0;
132 int arch = 0;
133 int refine = 0;
134 int num_level = 0;
135 int totalproc = 0;
136 int glob_method = 0;
137 int start_proc = 0;
138
139 INT *tmp_start = nullptr;
140 INT *tmp_adj = nullptr;
141 int *tmp_vwgts = nullptr;
142 size_t tmp_nv;
143 std::vector<int> nprocg;
144 std::vector<int> nelemg;
145 std::vector<int> nadjg;
146 size_t max_vtx;
147 size_t max_adj;
148 int group;
149 std::vector<INT> elem_map;
150 int dim[1];
151 int tmpdim[3];
152 int tmp_arch;
153 int tmp_lev;
154 int *tmp_v2p = nullptr;
155
156 float *x_node_ptr = nullptr;
157 float *y_node_ptr = nullptr;
158 float *z_node_ptr = nullptr;
159 std::vector<float> x_elem_ptr;
160 std::vector<float> y_elem_ptr;
161 std::vector<float> z_elem_ptr;
162 float *tmp_x = nullptr;
163 float *tmp_y = nullptr;
164 float *tmp_z = nullptr;
165 float *tmp_ewgts = nullptr;
166
167 long seed = 1;
168 double *goal = nullptr;
169 double time1;
170 double time2;
171 FILE *fp = nullptr;
172
173 /*-----------------------------Execution Begins------------------------------*/
174
175 tmpdim[0] = 0;
176 tmpdim[1] = 0;
177 tmpdim[2] = 0;
178
179 /* if user requests, check for mechanisms in the original mesh before
180 working on the loadbalance
181 */
182
183 if (problem->type == DecompType::ELEMENTAL && problem->global_mech == 1 &&
184 problem->alloc_graph == ELB_TRUE) {
185 fmt::print("\n==============Looking For Global Issues=================\n");
186 identify_mechanisms(machine, problem, mesh, lb, graph, Issues::GLOBAL_ISSUES);
187 fmt::print("============================================================\n");
188 fmt::print("\n");
189 }
190
191 /* Allocate the graph structure as Chaco expects it */
192 if (problem->alloc_graph == ELB_TRUE) {
193 /*
194 * Increment the graph vertices to start a "1" instead of "0",
195 * as expected by Chaco.
196 */
197 for (size_t cnt = 0; cnt < graph->nadj; cnt++) {
198 graph->adj[cnt]++;
199 }
200 }
201
202 if (((problem->type == DecompType::NODAL) && (lb->type == Balance::INERTIAL)) ||
203 ((problem->type == DecompType::ELEMENTAL) &&
204 (lb->type == Balance::INERTIAL || lb->type == Balance::ZPINCH ||
205 lb->type == Balance::BRICK || lb->type == Balance::ZOLTAN_RCB ||
206 lb->type == Balance::ZOLTAN_RIB || lb->type == Balance::ZOLTAN_HSFC))) {
207 if (problem->read_coords != ELB_TRUE) {
208 Gen_Error(0, "FATAL: internal logic error. Reading coordinates, but read_coords not set");
209 return 0;
210 }
211
212 switch (mesh->num_dims) {
213 case 3:
214 x_node_ptr = Data(mesh->coords);
215 y_node_ptr = Data(mesh->coords) + (mesh->num_nodes);
216 z_node_ptr = Data(mesh->coords) + 2 * (mesh->num_nodes);
217 break;
218
219 case 2:
220 x_node_ptr = Data(mesh->coords);
221 y_node_ptr = Data(mesh->coords) + (mesh->num_nodes);
222 z_node_ptr = (float *)calloc(mesh->num_nodes, sizeof(float));
223 break;
224
225 case 1:
226 x_node_ptr = Data(mesh->coords);
227 y_node_ptr = (float *)calloc(mesh->num_nodes, sizeof(float));
228 z_node_ptr = (float *)calloc(mesh->num_nodes, sizeof(float));
229 break;
230
231 default: Gen_Error(0, "FATAL: Invalid mesh dimension. Must be 1, 2, or 3."); return 0;
232 }
233 }
234
235 /* now set the pointers that are being sent to Chaco */
236 float *x_ptr = x_node_ptr;
237 float *y_ptr = y_node_ptr;
238 float *z_ptr = z_node_ptr;
239
240 /*
241 * For an elemental decomposition using inertial, ZPINCH, BRICK
242 * or ZOLTAN geometric load balancing,
243 * I need to come up with coordinates for the elements.
244 */
245 if ((problem->type == DecompType::ELEMENTAL) &&
246 (lb->type == Balance::INERTIAL || lb->type == Balance::ZPINCH || lb->type == Balance::BRICK ||
247 lb->type == Balance::ZOLTAN_RCB || lb->type == Balance::ZOLTAN_RIB ||
248 lb->type == Balance::ZOLTAN_HSFC)) {
249 if (problem->read_coords != ELB_TRUE) {
250 Gen_Error(0, "FATAL: internal logic error. Reading coordinates, but read_coords not set");
251 return 0;
252 }
253 /* just check to make sure that there are vertices to get coords for */
254 if (problem->num_vertices > 0) {
255 /* allocate memory for element coordinates */
256 x_elem_ptr.resize(problem->num_vertices);
257 y_elem_ptr.resize(problem->num_vertices);
258 z_elem_ptr.resize(problem->num_vertices);
259
260 size_t cnt = 0;
261 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
262
263 if (mesh->elem_type[ecnt] != ElementType::SPHERE || problem->no_sph == 1) {
264 /*
265 * for our purposes, the coordinate of the element will
266 * be the average of the coordinates of the nodes that make
267 * up that element
268 */
269 size_t nnodes = get_elem_info(ElementInfo::NNODES, mesh->elem_type[cnt]);
270 for (size_t ncnt = 0; ncnt < nnodes; ncnt++) {
271 x_elem_ptr[cnt] += x_ptr[(mesh->connect[ecnt][ncnt])];
272 y_elem_ptr[cnt] += y_ptr[(mesh->connect[ecnt][ncnt])];
273 z_elem_ptr[cnt] += z_ptr[(mesh->connect[ecnt][ncnt])];
274 }
275 x_elem_ptr[cnt] /= nnodes;
276 y_elem_ptr[cnt] /= nnodes;
277 z_elem_ptr[cnt] /= nnodes;
278 cnt++;
279 }
280
281 } /* End "for (cnt=0; cnt < mesh->num_elem; cnt++)" */
282
283 /* and use different pointers for Chaco */
284 x_ptr = Data(x_elem_ptr);
285 y_ptr = Data(y_elem_ptr);
286 z_ptr = Data(z_elem_ptr);
287
288 } /* End "if (problem->num_vertices > 0)" */
289 } /* End "if ((problem->type == ELEMENTAL) &&
290 (lb->type==INERTIAL||ZPINCH||BRICK||ZOLTAN))"*/
291
292 /* Allocate memory for the vertex to processor vector */
293 if (problem->type == DecompType::ELEMENTAL) {
294 lb->vertex2proc =
295 reinterpret_cast<int *>(malloc(((problem->num_vertices) + sphere->num) * sizeof(int)));
296 }
297 else {
298 lb->vertex2proc = reinterpret_cast<int *>(malloc(problem->num_vertices * sizeof(int)));
299 }
300
301 if (!(lb->vertex2proc)) {
302 Gen_Error(0, "fatal: insufficient memory");
303 return 0;
304 }
305
306 if (machine->type == MachineType::HCUBE) {
307 arch = 0;
308 num_level = ilog2i(static_cast<unsigned int>(machine->procs_per_box));
309 }
310 if (machine->type == MachineType::MESH) {
311 arch = machine->num_dims;
312 num_level = 0;
313 }
314
315 if (lb->refine == Balance::KL_REFINE) {
316 refine = 1;
317 }
318 else {
319 refine = 2;
320 }
321
322 if (lb->type == Balance::INFILE) {
323 assignfile = lb->file.c_str();
324 fp = fopen(assignfile, "r");
325 if (fp == nullptr) {
326 Gen_Error(0, "fatal: could not open assignment file");
327 return 0;
328 }
329 }
330
331 if (lb->outfile) {
332 assignfile = lb->file.c_str();
333 OUTPUT_ASSIGN = 1;
334 }
335
336 switch (lb->type) {
337 case Balance::MULTIKL: glob_method = 1; break;
338 case Balance::SPECTRAL: glob_method = 2; break;
339 case Balance::INERTIAL: glob_method = 3; break;
340 case Balance::ZPINCH:
341 case Balance::BRICK:
342 case Balance::ZOLTAN_RCB:
343 case Balance::ZOLTAN_RIB:
344 case Balance::ZOLTAN_HSFC:
345 glob_method = 999; /* Chaco methods don't apply to ZPINCH, BRICK
346 ZOLTAN_RCB, ZOLTAN_RIB, ZOLTAN_HSFC */
347 break;
348 case Balance::LINEAR: glob_method = 4; break;
349 case Balance::RANDOM: glob_method = 5; break;
350 case Balance::SCATTERED: glob_method = 6; break;
351 case Balance::INFILE: glob_method = 7; break;
352 default:; // do nothing
353 }
354
355 /* check if Chaco is supposed to make sure that the domains are connected */
356 if (lb->cnctd_dom) {
357 CONNECTED_DOMAINS = 1;
358 }
359
360 /*
361 * check if the data needs to be sent to Chaco in groups, and
362 * do some preliminary calculations and memory allocation
363 *
364 * Group or box designations for elements are stored in the
365 * vertex2proc array as negative numbers. So, group 1 will
366 * be designated as -1, etc.
367 *
368 * by default nloops = 1
369 */
370 size_t nloops = 1;
371 if (problem->num_groups > 1) {
372 /* allocate space to hold number of procs and elem per group */
373 nprocg.resize(problem->num_groups);
374 nelemg.resize(problem->num_groups);
375
376 if (!get_group_info(machine, problem, mesh, graph, lb->vertex2proc, Data(nprocg), Data(nelemg),
377 &max_vtx, &max_adj)) {
378 Gen_Error(0, "fatal: Error obtaining group information.");
379 goto cleanup;
380 }
381
382 nloops = problem->num_groups;
383 }
384
385 if (machine->num_boxes > 1) {
386 /* allocate space to hold number of procs and elem per box */
387 nprocg.resize(machine->num_boxes);
388 nelemg.resize(machine->num_boxes);
389 nadjg.resize(machine->num_boxes);
390
391 /*
392 * Call Chaco to get the initial breakdown of the vertices
393 * onto the boxes. The vertex2proc array can then be used
394 * to assign elements to groups that can be used in the
395 * Chaco calls below.
396 */
397 tmp_arch = 1;
398 tmp_lev = 0;
399 dim[0] = machine->num_boxes;
400 FREE_GRAPH = 0; /* Don't have Chaco to free the adjacency */
401
402 fmt::print("=======================Call Chaco===========================\n");
403 time1 = get_time();
404 if (lb->type == Balance::INFILE) {
405 flag =
406 input_assign(fp, const_cast<char *>(assignfile), problem->num_vertices, lb->vertex2proc);
407 }
408 if (lb->type == Balance::ZPINCH || lb->type == Balance::BRICK ||
409 lb->type == Balance::ZOLTAN_RCB || lb->type == Balance::ZOLTAN_RIB ||
410 lb->type == Balance::ZOLTAN_HSFC) {
411 fmt::print(stderr, "KDD -- ZPINCH, BRICK, ZOLTAN_RCB, ZOLTAN_RIB, and "
412 "ZOLTAN_HSFC not supported with num_boxes > 1.\n");
413 fmt::print(stderr, "KDD -- Contact Karen Devine, [email protected].\n");
414 exit(-1);
415 }
416 else {
417 flag = INTER_FACE(problem->num_vertices, (int *)Data(graph->start), (int *)Data(graph->adj),
418 Data(weight->vertices), Data(weight->edges), x_ptr, y_ptr, z_ptr,
419 const_cast<char *>(assignfile), (char *)nullptr, lb->vertex2proc, tmp_arch,
420 tmp_lev, dim, goal, glob_method, refine, (int)solve->rqi_flag, solve->vmax,
421 lb->num_sects, solve->tolerance, seed);
422 }
423
424 time2 = get_time();
425 fmt::print("============================================================\n");
426 fmt::print("Time in Chaco: {}s\n", time2 - time1);
427
428 if (flag != 0) {
429 Gen_Error(0, "fatal: Chaco returned an error");
430 goto cleanup;
431 }
432
433 nloops = machine->num_boxes;
434 for (size_t iloop = 0; iloop < nloops; iloop++) {
435 nelemg[iloop] = nadjg[iloop] = 0;
436 nprocg[iloop] = machine->procs_per_box;
437 }
438
439 for (size_t ecnt = 0; ecnt < problem->num_vertices; ecnt++) {
440 nelemg[lb->vertex2proc[ecnt]]++;
441 if (problem->alloc_graph == ELB_TRUE) {
442 nadjg[lb->vertex2proc[ecnt]] += graph->start[ecnt + 1] - graph->start[ecnt];
443 }
444
445 /*
446 * use negative numbers to specify the groups, in order to
447 * avoid having a problem with group 0, add 1 to the group
448 * number
449 */
450 lb->vertex2proc[ecnt] = -(lb->vertex2proc[ecnt] + 1);
451 }
452
453 max_vtx = 0;
454 max_adj = 0;
455 for (size_t iloop = 0; iloop < nloops; iloop++) {
456 if (nelemg[iloop] > static_cast<int>(max_vtx)) {
457 max_vtx = nelemg[iloop];
458 }
459 if (problem->alloc_graph == ELB_TRUE) {
460 if (nadjg[iloop] > static_cast<int>(max_adj)) {
461 max_adj = nadjg[iloop];
462 }
463 }
464 }
465 }
466
467 if (nloops > 1) {
468
469 /*
470 * now allocate temporary arrays to hold information
471 * to pass into Chaco
472 */
473 if (problem->alloc_graph == ELB_TRUE) {
474 tmp_start = (INT *)malloc((max_vtx + 1) * sizeof(INT));
475 tmp_adj = (INT *)malloc(max_adj * sizeof(INT));
476 if (!tmp_start || !tmp_adj) {
477 Gen_Error(0, "fatal: insufficient memory");
478 goto cleanup;
479 }
480 /* and need a group map for the elements */
481 elem_map.resize(problem->num_vertices);
482 }
483 if (!weight->vertices.empty()) {
484 tmp_vwgts = reinterpret_cast<int *>(malloc(max_adj * sizeof(int)));
485 if (!tmp_vwgts) {
486 Gen_Error(0, "fatal: insufficient memory");
487 goto cleanup;
488 }
489 }
490 if (!weight->edges.empty()) {
491 tmp_ewgts = reinterpret_cast<float *>(malloc(max_adj * sizeof(float)));
492 if (!tmp_ewgts) {
493 Gen_Error(0, "fatal: insufficient memory");
494 goto cleanup;
495 }
496 }
497 if (x_ptr != nullptr) {
498 tmp_x = reinterpret_cast<float *>(malloc(max_vtx * sizeof(float)));
499 if (!tmp_x) {
500 Gen_Error(0, "fatal: insufficient memory");
501 goto cleanup;
502 }
503 }
504 if (y_ptr != nullptr) {
505 tmp_y = reinterpret_cast<float *>(malloc(max_vtx * sizeof(float)));
506 if (!tmp_y) {
507 Gen_Error(0, "fatal: insufficient memory");
508 goto cleanup;
509 }
510 }
511 if (z_ptr != nullptr) {
512 tmp_z = reinterpret_cast<float *>(malloc(max_vtx * sizeof(float)));
513 if (!tmp_z) {
514 Gen_Error(0, "fatal: insufficient memory");
515 goto cleanup;
516 }
517 }
518 tmp_v2p = reinterpret_cast<int *>(malloc(max_vtx * sizeof(int)));
519 if (!tmp_v2p) {
520 Gen_Error(0, "fatal: insufficient memory");
521 goto cleanup;
522 }
523 start_proc = 0; /* counter to keep track of processors for each group */
524 }
525
526 /*
527 * need to check to make sure that the mesh is not made up
528 * entirely of SPHERE elements. If it is, don't call Chaco.
529 * The spheres are linearly distributed after chaco is called.
530 */
531
532 if (sphere->num < mesh->num_elems) {
533
534 FREE_GRAPH = 0; /* Don't have Chaco to free the adjacency */
535 /* now loop over the number of groups */
536 for (size_t iloop = 0; iloop < nloops; iloop++) {
537
538 /* group #'s 1 based */
539 group = iloop + 1;
540
541 /* Call chaco to generate the load balance */
542
543 if (nloops > 1) {
544 if (nelemg[iloop] <= 0) {
545 continue;
546 }
547
548 tmp_nv = nelemg[iloop];
549
550 if (problem->alloc_graph == ELB_TRUE) {
551 /*
552 * Build an element map that is local to this group. This
553 * is necessary so that the adjacency list for each element in
554 * this group can is correctly mapped. Elements that are in this
555 * group are mapped 1:n and elements that are not in the group
556 * are assigned -1.
557 */
558 INT elemp = 1;
559 for (size_t cnt = 0; cnt < problem->num_vertices; cnt++) {
560 if (group == -lb->vertex2proc[cnt]) {
561 elem_map[cnt] = elemp++;
562 }
563 else {
564 elem_map[cnt] = -1;
565 }
566 }
567
568 tmp_start[0] = 0;
569 }
570
571 size_t adjp = 0;
572 size_t elemp = 0;
573
574 /* fill the temporary vectors */
575 for (size_t ecnt = 0; ecnt < problem->num_vertices; ecnt++) {
576 if (group == -lb->vertex2proc[ecnt]) {
577 if (problem->alloc_graph == ELB_TRUE) {
578 for (int cnt = graph->start[ecnt]; cnt < graph->start[ecnt + 1]; cnt++) {
579 if (elem_map[graph->adj[cnt] - 1] > 0) {
580 tmp_adj[adjp] = elem_map[graph->adj[cnt] - 1];
581 if (!weight->edges.empty() && tmp_ewgts != nullptr) {
582 tmp_ewgts[adjp] = weight->edges[cnt];
583 }
584 adjp++;
585 }
586 }
587 tmp_start[elemp + 1] = adjp;
588 }
589 if (!weight->vertices.empty() && tmp_vwgts != nullptr) {
590 tmp_vwgts[elemp] = weight->vertices[ecnt];
591 }
592
593 if (x_ptr) {
594 tmp_x[elemp] = x_ptr[ecnt];
595 }
596 if (y_ptr) {
597 tmp_y[elemp] = y_ptr[ecnt];
598 }
599 if (z_ptr) {
600 tmp_z[elemp] = z_ptr[ecnt];
601 }
602
603 elemp++; /* now increment the element # for the group */
604 }
605 }
606
607 /*
608 * set number of procs for this group
609 * If this is a cluster machine, then machine-dim, arch, and
610 * num_level are already set for each box.
611 */
612 if (problem->num_groups > 1) {
613 if (machine->type == MachineType::MESH) {
614
615 /*
616 * mesh and groups are in conflict. the only way to resolve
617 * this is to assume a 1-d mesh. For example if group 1 requires
618 * 7 processors, it is impossible to apply this to a 2d mesh.
619 */
620
621 tmpdim[0] = nprocg[iloop];
622 tmpdim[1] = 1;
623 tmpdim[2] = 1;
624 }
625 else {
626 num_level = nprocg[iloop];
627 }
628 totalproc = nprocg[iloop];
629 }
630 }
631 else {
632 tmp_nv = problem->num_vertices;
633 if (!graph->start.empty()) {
634 tmp_start = &graph->start[0];
635 }
636 if (!graph->adj.empty()) {
637 tmp_adj = &graph->adj[0];
638 }
639 if (!weight->vertices.empty()) {
640 tmp_vwgts = &weight->vertices[0];
641 }
642 if (!weight->edges.empty()) {
643 tmp_ewgts = &weight->edges[0];
644 }
645 tmp_x = x_ptr;
646 tmp_y = y_ptr;
647 tmp_z = z_ptr;
648 tmp_v2p = lb->vertex2proc;
649
650 int upper = machine->num_dims > 3 ? 3 : machine->num_dims;
651 for (int cnt = 0; cnt < upper; cnt++) {
652 tmpdim[cnt] = machine->dim[cnt];
653 }
654 if (machine->type == MachineType::MESH) {
655 totalproc = tmpdim[0];
656 if (tmpdim[1] != 0) {
657 totalproc *= tmpdim[1];
658 }
659 if (tmpdim[2] != 0) {
660 totalproc *= tmpdim[2];
661 }
662 }
663 else {
664 totalproc = num_level;
665 }
666 }
667
668 if (lb->type == Balance::INFILE) {
669 flag = input_assign(fp, const_cast<char *>(assignfile), tmp_nv, tmp_v2p);
670 }
671 else if (lb->type == Balance::ZPINCH) {
672 flag = ZPINCH_assign(machine, tmp_nv, tmp_x, tmp_y, tmp_z, tmp_v2p);
673 BALANCE_STATS(machine, nullptr, tmp_nv, tmp_v2p);
674 }
675 else if (lb->type == Balance::BRICK) {
676 flag = BRICK_assign(machine, tmp_nv, tmp_x, tmp_y, tmp_z, tmp_v2p);
677 BALANCE_STATS(machine, nullptr, tmp_nv, tmp_v2p);
678 }
679 #ifdef USE_ZOLTAN
680 else if (lb->type == Balance::ZOLTAN_RCB) {
681 flag = ZOLTAN_assign("RCB", totalproc, tmp_nv, tmp_vwgts, tmp_x, tmp_y, tmp_z, lb->ignore_z,
682 tmp_v2p, argc, argv);
683 BALANCE_STATS(machine, tmp_vwgts, tmp_nv, tmp_v2p);
684 }
685 else if (lb->type == Balance::ZOLTAN_RIB) {
686 flag = ZOLTAN_assign("RIB", totalproc, tmp_nv, tmp_vwgts, tmp_x, tmp_y, tmp_z, lb->ignore_z,
687 tmp_v2p, argc, argv);
688 BALANCE_STATS(machine, tmp_vwgts, tmp_nv, tmp_v2p);
689 }
690 else if (lb->type == Balance::ZOLTAN_HSFC) {
691 flag = ZOLTAN_assign("HSFC", totalproc, tmp_nv, tmp_vwgts, tmp_x, tmp_y, tmp_z,
692 lb->ignore_z, tmp_v2p, argc, argv);
693 BALANCE_STATS(machine, tmp_vwgts, tmp_nv, tmp_v2p);
694 }
695 #else
696 else if (lb->type == Balance::ZOLTAN_RCB || lb->type == Balance::ZOLTAN_RIB ||
697 lb->type == Balance::ZOLTAN_HSFC) {
698 Gen_Error(0, "fatal: Invalid load balance types -- Zoltan is not supported in this build");
699 goto cleanup;
700 }
701 #endif
702 else if (lb->type == Balance::LINEAR) {
703 fmt::print(stderr, "Using internal linear decomposition\n");
704 /* assign the elements to the processors linearly */
705 size_t cnt = mesh->num_elems / machine->num_procs;
706
707 /* The left overs */
708 int extra = (mesh->num_elems) % (machine->num_procs);
709
710 size_t end = 0;
711 for (int iproc = 0; iproc < machine->num_procs; iproc++) {
712 size_t start = end;
713 end += cnt;
714 if (iproc < extra) {
715 end++;
716 }
717
718 for (size_t ecnt = start; ecnt < end; ecnt++) {
719 lb->vertex2proc[ecnt] = iproc;
720 }
721 }
722 FREE_GRAPH = 0; /* Chaco not called, */
723
724 for (size_t i = 0; i < mesh->num_elems; i++) {
725 assert(lb->vertex2proc[i] < machine->num_procs);
726 }
727 }
728 else if (lb->type == Balance::SCATTERED) {
729 // Bad decomposition, useful for maximizing communication for testing algorithms...
730 /* each element 'e' assigned to processor 'e' % 'num_proc' */
731
732 for (size_t e = 0; e < mesh->num_elems; e += machine->num_procs) {
733 size_t iproc = 0;
734 size_t elem = e;
735 size_t end = elem + machine->num_procs;
736 if (end > mesh->num_elems) {
737 end = mesh->num_elems;
738 }
739 while (elem < end) {
740 lb->vertex2proc[elem++] = iproc++;
741 }
742 }
743 FREE_GRAPH = 0; /* Chaco not called, */
744 }
745 else {
746 fmt::print("===================Call Chaco===========================\n");
747 time1 = get_time();
748 flag = INTER_FACE(tmp_nv, (int *)tmp_start, (int *)tmp_adj, tmp_vwgts, tmp_ewgts, tmp_x,
749 tmp_y, tmp_z, const_cast<char *>(assignfile), (char *)nullptr, tmp_v2p,
750 arch, num_level, tmpdim, goal, glob_method, refine, (int)solve->rqi_flag,
751 solve->vmax, lb->num_sects, solve->tolerance, seed);
752 time2 = get_time();
753 fmt::print("========================================================\n");
754 fmt::print("Time in Chaco: {}s\n", time2 - time1);
755 }
756
757 if (flag != 0) {
758 Gen_Error(0, "fatal: Partitioner returned an error");
759 goto cleanup;
760 }
761
762 if (nloops > 1) {
763 for (int ecnt = 0; ecnt < nelemg[iloop]; ecnt++) {
764 tmp_v2p[ecnt] += start_proc;
765 }
766 start_proc += nprocg[iloop];
767 /* copy the assignment data back into assignment */
768 size_t elemp = 0;
769 for (size_t ecnt = 0; ecnt < problem->num_vertices; ecnt++) {
770 if (-lb->vertex2proc[ecnt] == group) {
771 lb->vertex2proc[ecnt] = tmp_v2p[elemp++];
772 }
773 }
774 }
775 } /* End: "for (iloop = 0; iloop < nloops; iloop++)" */
776 } /* End: "if (sphere->num < mesh->num_elems)" */
777
778 /* Free up coordinates if used */
779 if (problem->read_coords == ELB_TRUE) {
780 switch (mesh->num_dims) {
781 case 1:
782 free(y_node_ptr);
783 y_node_ptr = nullptr;
784 FALL_THROUGH;
785 case 2: free(z_node_ptr); z_node_ptr = nullptr;
786 }
787 }
788
789 /* free up memory for groups */
790 if (nloops > 1) {
791 if (problem->alloc_graph == ELB_TRUE) {
792 free(tmp_start);
793 free(tmp_adj);
794 }
795 free(tmp_v2p);
796 // FREE_GRAPH always 0 if nloops > 1
797 if (tmp_vwgts) {
798 free(tmp_vwgts);
799 tmp_vwgts = nullptr;
800 }
801 if (tmp_ewgts) {
802 free(tmp_ewgts);
803 tmp_ewgts = nullptr;
804 }
805 if (tmp_x) {
806 free(tmp_x);
807 }
808 if (tmp_y) {
809 free(tmp_y);
810 }
811 if (tmp_z) {
812 free(tmp_z);
813 }
814 problem->group_no.clear();
815 vec_free(mesh->eb_cnts);
816 /* since Chaco didn't free the graph, need to do it here */
817 vec_free(graph->start);
818 vec_free(graph->adj);
819 vec_free(weight->vertices);
820 vec_free(weight->edges);
821 }
822
823 if (problem->type == DecompType::ELEMENTAL) {
824 /*
825 * If this is an elemental load balance and there are spheres present
826 * then adjust lb->vertex2proc accordingly. The spheres are then
827 * distributed linearly to processors.
828 */
829 if (sphere->num > 0) {
830 // If type == LINEAR || SCATTERED, then the spheres were handled above (unless the model
831 // is
832 // all spheres...)
833 if ((lb->type != Balance::LINEAR && lb->type != Balance::SCATTERED) ||
834 sphere->num == mesh->num_elems) {
835
836 if (sphere->num != mesh->num_elems) {
837 // If all spheres, don't need to open up space...
838 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
839 /*
840 * First generate "holes" in the vertex2proc vector where the
841 * sphere assignments will be.
842 */
843 if (mesh->elem_type[ecnt] == ElementType::SPHERE) {
844 for (size_t cnt = (problem->num_vertices); cnt > ecnt; cnt--) {
845 lb->vertex2proc[cnt] = lb->vertex2proc[cnt - 1];
846 }
847
848 lb->vertex2proc[ecnt] = -1;
849 (problem->num_vertices)++;
850 }
851 }
852 }
853
854 /* Now assign the spheres to the processors linearly */
855 size_t cnt = sphere->num / machine->num_procs;
856
857 /* The left overs */
858 flag = (sphere->num) % (machine->num_procs);
859
860 size_t iproc = 0;
861 size_t cnt2 = 0;
862
863 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
864 if (mesh->elem_type[ecnt] == ElementType::SPHERE) {
865 lb->vertex2proc[ecnt] = iproc;
866 cnt2++;
867
868 /*
869 * If the processor ID is lower than the remainder then that
870 * processor gets an extra sphere
871 */
872 if ((iproc + 1) <= static_cast<size_t>(flag)) {
873 if (cnt2 >= (cnt + 1)) {
874 iproc++;
875 cnt2 = 0;
876 }
877 }
878 else {
879 if (cnt2 >= cnt) {
880 iproc++;
881 cnt2 = 0;
882 }
883 }
884 }
885 }
886 }
887 } /* End "if(sphere->num > 0)" */
888
889 if (problem->local_mech == 1) {
890 fmt::print("\n==============Looking For Local Issues==================\n");
891
892 if (problem->face_adj == 1 && problem->alloc_graph == ELB_TRUE) {
893 identify_mechanisms(machine, problem, mesh, lb, graph, Issues::LOCAL_ISSUES);
894 }
895 else {
896 /* need to free the bigger graph and create a face adjacent graph */
897 int tmp_alloc_graph;
898 int tmp_adjacency;
899
900 vec_free(graph->start);
901 vec_free(graph->adj);
902 vec_free(weight->vertices);
903 vec_free(weight->edges);
904
905 if (!graph->sur_elem.empty()) {
906 for (size_t cnt = 0; cnt < mesh->num_nodes; cnt++) {
907 vec_free(graph->sur_elem[cnt]);
908 }
909 vec_free(graph->sur_elem);
910 }
911
912 tmp_alloc_graph = problem->alloc_graph;
913 tmp_adjacency = problem->face_adj;
914
915 problem->alloc_graph = ELB_TRUE;
916 problem->face_adj = 1;
917
918 generate_graph(problem, mesh, graph, weight, sphere);
919
920 /*
921 * adjacency graph sent to identify_mechanisms must be 1 based
922 *
923 */
924
925 for (size_t cnt = 0; cnt < graph->nadj; cnt++) {
926 graph->adj[cnt]++;
927 }
928
929 identify_mechanisms(machine, problem, mesh, lb, graph, Issues::LOCAL_ISSUES);
930
931 problem->alloc_graph = tmp_alloc_graph;
932 problem->face_adj = tmp_adjacency;
933 }
934
935 fmt::print("============================================================\n");
936 fmt::print("\n");
937 }
938
939 // If requested, try to discover vertical columnar structures in
940 // the mesh and tweak the partitioning so that elements of a
941 // column are not on multiple processors
942 if (problem->fix_columns) {
943 Gen_Error(1, "INFO: Attempting to discover columns and fix their partitioning");
944 int nmoved = fix_column_partitions(lb, mesh, graph);
945 std::string mesg;
946 mesg = fmt::format("INFO: Reassigned partitions of {} elements", nmoved);
947 Gen_Error(1, mesg);
948 }
949
950 } // problem->type == ELEMENTAL
951
952 /* since Chaco didn't free the graph, need to do it here */
953 if (!FREE_GRAPH) {
954 vec_free(graph->start);
955 vec_free(graph->adj);
956 vec_free(weight->vertices);
957 vec_free(weight->edges);
958 }
959 if (fp != nullptr) {
960 fclose(fp);
961 }
962 return 1;
963
964 cleanup:
965 if (problem->read_coords == ELB_TRUE) {
966 switch (mesh->num_dims) {
967 case 1: free(y_node_ptr); FALL_THROUGH;
968 case 2: free(z_node_ptr);
969 }
970 }
971
972 if (lb->type == Balance::INFILE) {
973 fclose(fp);
974 }
975
976 if (nloops > 1) {
977 if (problem->alloc_graph == ELB_TRUE) {
978 free(tmp_start);
979 free(tmp_adj);
980 }
981 free(tmp_v2p);
982 // FREE_GRAPH always zero if nloops > 1
983 if (tmp_vwgts) {
984 free(tmp_vwgts);
985 }
986 if (tmp_ewgts) {
987 free(tmp_ewgts);
988 }
989 if (tmp_x) {
990 free(tmp_x);
991 }
992 if (tmp_y) {
993 free(tmp_y);
994 }
995 if (tmp_z) {
996 free(tmp_z);
997 }
998 problem->group_no.clear();
999 vec_free(mesh->eb_cnts);
1000 /* since Chaco didn't free the graph, need to do it here */
1001 vec_free(graph->start);
1002 vec_free(graph->adj);
1003 vec_free(weight->vertices);
1004 vec_free(weight->edges);
1005 }
1006 return 0;
1007 } /*---------------------- End generate_loadbal() ---------------------------*/
1008
1009 /*****************************************************************************/
1010 /*****************************************************************************/
1011 /*****************************************************************************/
1012 /* Function assign_fem() begins:
1013 *----------------------------------------------------------------------------
1014 * This function takes the load balance information generated by
1015 * generate_loadbal() and assigns the FEM quantities to processors based on
1016 * that load balance.
1017 *****************************************************************************/
1018 template int generate_maps(Machine_Description *machine, Problem_Description *problem,
1019 Mesh_Description<int> *mesh, LB_Description<int> *lb,
1020 Graph_Description<int> *graph);
1021
1022 template int generate_maps(Machine_Description *machine, Problem_Description *problem,
1023 Mesh_Description<int64_t> *mesh, LB_Description<int64_t> *lb,
1024 Graph_Description<int64_t> *graph);
1025
1026 template <typename INT>
1027 int generate_maps(Machine_Description *machine, Problem_Description *problem,
1028 Mesh_Description<INT> *mesh, LB_Description<INT> *lb,
1029 Graph_Description<INT> *graph)
1030 {
1031
1032 /*-----------------------------Execution Begins------------------------------*/
1033
1034 /* Generate the map for a nodal load balance */
1035 if (problem->type == DecompType::NODAL) {
1036 /*
1037 * Generate the nodal and elemental distribution for a nodal
1038 * decomposition.
1039 */
1040 if (!nodal_dist(lb, machine, mesh, graph)) {
1041 Gen_Error(0, "fatal: unable to find nodal distribution");
1042 return 0;
1043 }
1044 }
1045 else {
1046 /*
1047 * Generate the nodal and elemental distribution for an elemental
1048 * decomposition.
1049 */
1050 if (!elemental_dist(lb, machine, mesh, graph, problem)) {
1051 Gen_Error(0, "fatal: unable to find elemental distribution");
1052 return 0;
1053 }
1054 }
1055
1056 return 1;
1057
1058 } /*----------------------End generate_maps()----------------------------*/
1059
1060 /*****************************************************************************/
1061 /*****************************************************************************/
1062 /*****************************************************************************/
1063 namespace {
1064 /*****************************************************************************/
1065 /*****************************************************************************/
1066 /*****************************************************************************
1067 *----------------------------------------------------------------------------
1068 * This function looks for 3D elements that are connected to other elements
1069 * by only a node or edge resulting in a boundary face.
1070 *****************************************************************************/
1071 template <typename INT>
1072 int identify_mechanisms(Machine_Description *machine, Problem_Description *problem,
1073 Mesh_Description<INT> *mesh, LB_Description<INT> *lb,
1074 Graph_Description<INT> *graph, Issues check_type)
1075 {
1076 std::vector<int> list_ptr;
1077
1078 /*
1079 * look for discontinuities in the graph
1080 *
1081 */
1082
1083 if (problem->find_cnt_domains == 1) {
1084 if (check_type == Issues::GLOBAL_ISSUES) {
1085 size_t nrow = mesh->num_elems;
1086 std::vector<int> rows(nrow + 1);
1087 std::vector<int> list(nrow);
1088
1089 rows[0] = 1;
1090 for (size_t ecnt = 1; ecnt < mesh->num_elems; ecnt++) {
1091 auto distance = graph->start[ecnt] - graph->start[ecnt - 1] + 1;
1092 rows[ecnt] = rows[ecnt - 1] + distance;
1093 }
1094 rows[nrow] = graph->nadj + mesh->num_elems + 1;
1095 size_t nedges = rows[nrow] - 1;
1096 std::vector<int> columns(nedges);
1097
1098 size_t ki = 0;
1099 size_t kf = 0;
1100 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1101 columns[kf++] = ecnt + 1;
1102 size_t distance = rows[ecnt + 1] - rows[ecnt] - 1;
1103 for (size_t i = 0; i < distance; i++) {
1104 columns[kf++] = graph->adj[ki++] + 1;
1105 }
1106 }
1107
1108 size_t components =
1109 extract_connected_lists(nrow, Data(columns), Data(rows), Data(list), list_ptr);
1110
1111 if (components) {
1112 fmt::print("There are {} connected components.\n", components);
1113 for (size_t i = 0; i < components; i++) {
1114 ki = list_ptr[i];
1115 kf = list_ptr[i + 1] - 1;
1116 size_t distance = kf - ki + 1;
1117 fmt::print("Connection {} #elements {}\n", i + 1, distance);
1118 }
1119 }
1120 }
1121
1122 if (check_type == Issues::LOCAL_ISSUES) {
1123
1124 std::vector<int> proc_cnt(machine->num_procs);
1125 std::vector<INT> local_number(mesh->num_elems);
1126
1127 /*
1128 * after running through chaco, the adjacency graph entries have
1129 * been changed to 1 based
1130 */
1131 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1132 int proc = lb->vertex2proc[ecnt];
1133 proc_cnt[proc]++;
1134 local_number[ecnt] = proc_cnt[proc];
1135 }
1136
1137 int tmp_procs = machine->num_procs;
1138 for (int pcnt = 0; pcnt < tmp_procs; pcnt++) {
1139 if (proc_cnt[pcnt]) {
1140 int nrow = proc_cnt[pcnt];
1141 std::vector<int> rows(nrow + 1);
1142 std::vector<int> global_index(nrow);
1143 std::vector<int> list(nrow);
1144
1145 rows[0] = 1;
1146 size_t cnt = 0;
1147 size_t tcnt = 0;
1148 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1149 int proc = lb->vertex2proc[ecnt];
1150 assert(proc < machine->num_procs);
1151 if (proc == pcnt) {
1152 size_t end = 0;
1153 if (ecnt < (mesh->num_elems - 1)) {
1154 end = graph->start[ecnt + 1];
1155 }
1156 else {
1157 end = graph->nadj;
1158 }
1159 size_t distance = 1;
1160 for (size_t i = graph->start[ecnt]; i < end; i++) {
1161 int proc2 = lb->vertex2proc[graph->adj[i] - 1];
1162 assert(proc2 < machine->num_procs);
1163 if (proc2 == proc) {
1164 distance++;
1165 }
1166 }
1167 cnt++;
1168 rows[cnt] = rows[cnt - 1] + distance;
1169 tcnt += distance;
1170 }
1171 }
1172 rows[nrow] = tcnt + 1;
1173 size_t nedges = rows[nrow] - 1;
1174 std::vector<int> columns(nedges);
1175 {
1176 size_t kf = 0;
1177 size_t ki = 0;
1178 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1179 int proc = lb->vertex2proc[ecnt];
1180 assert(proc < machine->num_procs);
1181 if (proc == pcnt) {
1182 global_index[ki++] = ecnt;
1183 columns[kf++] = local_number[ecnt];
1184 size_t end = 0;
1185 if (ecnt < (mesh->num_elems - 1)) {
1186 end = graph->start[ecnt + 1];
1187 }
1188 else {
1189 end = graph->nadj;
1190 }
1191 for (size_t i = graph->start[ecnt]; i < end; i++) {
1192 int proc2 = lb->vertex2proc[graph->adj[i] - 1];
1193 assert(proc2 < machine->num_procs);
1194 if (proc2 == proc) {
1195 columns[kf++] = local_number[graph->adj[i] - 1];
1196 }
1197 }
1198 }
1199 }
1200 }
1201
1202 int components =
1203 extract_connected_lists(nrow, Data(columns), Data(rows), Data(list), list_ptr);
1204
1205 if (components > 0) {
1206 fmt::print("For Processor {} there are {} connected components.\n", pcnt, components);
1207 for (int i = 0; i < components; i++) {
1208 int ki = list_ptr[i];
1209 int kf = list_ptr[i + 1] - 1;
1210 int distance = kf - ki + 1;
1211 fmt::print("Connection {} #elements {}\n", i + 1, distance);
1212 }
1213 if (problem->dsd_add_procs == 1) {
1214 for (int i = 1; i < components; i++) {
1215 int ki = list_ptr[i];
1216 int kf = list_ptr[i + 1] - 1;
1217 for (int k = ki; k <= kf; k++) {
1218 lb->vertex2proc[global_index[list[k] - 1]] = machine->num_procs;
1219 }
1220 machine->num_procs++;
1221 }
1222 }
1223 }
1224 }
1225 }
1226 if (tmp_procs != machine->num_procs) {
1227 fmt::print("\n!!! Processor count increased to {} processors\n", machine->num_procs);
1228 fmt::print("!!! in order to make connected subdomains\n\n");
1229 }
1230 }
1231 }
1232
1233 /*
1234 * determine local element numbers for diagnostic output
1235 *
1236 */
1237
1238 if (problem->global_mech == 1 || problem->local_mech == 1) {
1239
1240 std::vector<INT> pt_list(graph->max_nsur);
1241 std::vector<INT> hold_elem(graph->max_nsur);
1242 std::vector<int> problems(mesh->num_nodes);
1243 std::vector<int> proc_cnt(machine->num_procs);
1244 std::vector<INT> local_number(mesh->num_elems);
1245
1246 if (check_type == Issues::LOCAL_ISSUES) {
1247 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1248 int proc = lb->vertex2proc[ecnt];
1249 assert(proc < machine->num_procs);
1250 proc_cnt[proc]++;
1251 local_number[ecnt] = proc_cnt[proc];
1252 }
1253 }
1254
1255 size_t num_found = 0;
1256 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1257 ElementType etype = mesh->elem_type[ecnt];
1258
1259 /* need to check for volume elements */
1260 if (is_3d_element(etype)) {
1261
1262 int nnodes = get_elem_info(ElementInfo::NNODES, mesh->elem_type[ecnt]);
1263
1264 for (int ncnt = 0; ncnt < nnodes; ncnt++) {
1265 size_t node = mesh->connect[ecnt][ncnt];
1266 problems[node] = 0;
1267 }
1268
1269 int nsides = get_elem_info(ElementInfo::NSIDES, etype);
1270 int proc = 0;
1271 if (check_type == Issues::LOCAL_ISSUES) {
1272 proc = lb->vertex2proc[ecnt];
1273 }
1274 else {
1275 proc = 0;
1276 }
1277 assert(proc < machine->num_procs);
1278
1279 /* check each side of this element */
1280
1281 INT side_nodes[MAX_SIDE_NODES];
1282 INT side_nodes2[MAX_SIDE_NODES];
1283 for (int nscnt = 0; nscnt < nsides; nscnt++) {
1284
1285 /* get the list of nodes on this side set */
1286 int side_cnt = ss_to_node_list(etype, mesh->connect[ecnt], (nscnt + 1), side_nodes);
1287
1288 for (int ncnt = 0; ncnt < side_cnt; ncnt++) {
1289
1290 size_t node = side_nodes[ncnt];
1291 size_t nhold = graph->sur_elem[node].size();
1292
1293 /*
1294 * look for the following cases
1295 * 1) bar elements connected to a volume element
1296 * 2) shell element connected to a edge or point of a volume
1297 * element and both its faces are boundaries
1298 *
1299 */
1300 for (size_t pcnt = 0; pcnt < nhold; pcnt++) {
1301
1302 size_t el2 = graph->sur_elem[node][pcnt];
1303 ElementType etype2 = mesh->elem_type[el2];
1304
1305 int proc2 = 0;
1306 if (check_type == Issues::LOCAL_ISSUES) {
1307 proc2 = lb->vertex2proc[el2];
1308 }
1309 assert(proc2 < machine->num_procs);
1310
1311 if (ecnt != el2 && proc == proc2) {
1312 if (etype2 == ElementType::BAR2 || etype2 == ElementType::BAR3 ||
1313 etype2 == ElementType::SHELL2 || etype2 == ElementType::SHELL3) {
1314 problems[node] = el2 + 1;
1315 }
1316 else if (etype2 == ElementType::SHELL4 || etype2 == ElementType::SHELL8 ||
1317 etype2 == ElementType::TSHELL3 || etype2 == ElementType::TSHELL6) {
1318 /*
1319 * look for an element connect to one of the shells faces (not edges)
1320 * one can look at elements connected to 3 of the nodes - cannot use
1321 * diagonals due to triangular shells
1322 */
1323
1324 int nsides2 = get_elem_info(ElementInfo::NSIDES, etype2);
1325
1326 size_t count = 0;
1327 for (int cnt = 0; cnt < nsides2; cnt++) {
1328
1329 ss_to_node_list(etype2, mesh->connect[el2], (cnt + 1), side_nodes2);
1330
1331 int nhold2 =
1332 find_inter(Data(graph->sur_elem[side_nodes2[0]]),
1333 Data(graph->sur_elem[side_nodes2[1]]),
1334 graph->sur_elem[side_nodes2[0]].size(),
1335 graph->sur_elem[side_nodes2[1]].size(), Data(pt_list));
1336
1337 for (int i = 0; i < nhold2; i++) {
1338 hold_elem[i] = graph->sur_elem[side_nodes2[0]][pt_list[i]];
1339 }
1340
1341 size_t nelem =
1342 find_inter(Data(hold_elem), Data(graph->sur_elem[side_nodes2[2]]), nhold2,
1343 graph->sur_elem[side_nodes2[2]].size(), Data(pt_list));
1344
1345 if (nelem >= 1) {
1346 count++;
1347 break;
1348 }
1349 }
1350
1351 /* at this point, a shell was connected to this
1352 * volume element. if count, then the shell has a
1353 * element connect to one of its faces and thus
1354 * this is not a mechanism. If !count, then this
1355 * is a mechanism.
1356 */
1357
1358 if (!count) {
1359 problems[node] = el2 + 1;
1360 }
1361 }
1362 }
1363 }
1364 }
1365 }
1366
1367 for (int ncnt = 0; ncnt < nnodes; ncnt++) {
1368 size_t node = mesh->connect[ecnt][ncnt];
1369 if (problems[node]) {
1370 size_t el2 = problems[node] - 1;
1371 ElementType etype2 = mesh->elem_type[el2];
1372
1373 if (check_type == Issues::LOCAL_ISSUES) {
1374 fmt::print("WARNING: On Processor {} Local Element {}"
1375 " ({}) has a mechanism through Global Node {}"
1376 " with Local Element {} ({})\n",
1377 proc, (size_t)local_number[ecnt], elem_name_from_enum(etype), node,
1378 (size_t)local_number[el2], elem_name_from_enum(etype2));
1379 if (problem->mech_add_procs == 1) {
1380 lb->vertex2proc[el2] = machine->num_procs;
1381 }
1382 }
1383 else {
1384 fmt::print("WARNING: Element {} ({}) has a mechanism through Node {} with Element "
1385 "{} ({})\n",
1386 ecnt + 1, elem_name_from_enum(etype), node, el2 + 1,
1387 elem_name_from_enum(etype2));
1388 }
1389 num_found++;
1390 }
1391 }
1392 }
1393 }
1394
1395 if (num_found) {
1396 fmt::print("Total mechanisms found = {}\n", num_found);
1397 if (check_type == Issues::LOCAL_ISSUES) {
1398 if (problem->mech_add_procs == 1) {
1399 machine->num_procs++;
1400 fmt::print("\n!!! Processor count increased to {} processors\n", machine->num_procs);
1401 fmt::print("!!! to move mechanisms to another processor\n\n");
1402 }
1403 }
1404 }
1405 else {
1406 fmt::print("NO mechanisms found\n");
1407 }
1408 }
1409
1410 return 1;
1411 }
1412
1413 template <typename INT>
1414 int nodal_dist(LB_Description<INT> *lb, Machine_Description *machine, Mesh_Description<INT> *mesh,
1415 Graph_Description<INT> *graph)
1416 {
1417 double time1 = get_time();
1418 lb->int_nodes.resize(machine->num_procs);
1419 lb->bor_nodes.resize(machine->num_procs);
1420 lb->ext_nodes.resize(machine->num_procs);
1421 lb->int_elems.resize(machine->num_procs);
1422 lb->bor_elems.resize(machine->num_procs); // Not used in nodal dist.
1423 lb->ext_procs.resize(machine->num_procs);
1424
1425 double time2 = get_time();
1426 fmt::print("Allocation time: {}s\n", time2 - time1);
1427
1428 /* Find the internal, border and external nodes */
1429 time1 = get_time();
1430 for (size_t ncnt = 0; ncnt < mesh->num_nodes; ncnt++) {
1431 int proc = lb->vertex2proc[ncnt];
1432 assert(proc < machine->num_procs);
1433 int internal = 1;
1434 int flag = 0;
1435 for (size_t ecnt = 0; ecnt < graph->sur_elem[ncnt].size(); ecnt++) {
1436 int elem = graph->sur_elem[ncnt][ecnt];
1437 ElementType etype = mesh->elem_type[elem];
1438 int nnodes = get_elem_info(ElementInfo::NNODES, etype);
1439 for (size_t i = 0; i < static_cast<size_t>(nnodes); i++) {
1440 int proc_n = lb->vertex2proc[mesh->connect[elem][i]];
1441 assert(proc_n < machine->num_procs);
1442 if (proc_n != proc) {
1443 /* "ncnt" is a border node and is an external node to proc_n */
1444 internal = 0;
1445 if (!flag) {
1446 flag = 1;
1447 lb->bor_nodes[proc].push_back(ncnt);
1448 }
1449
1450 /*
1451 ** to make sure that this node has not already been put
1452 ** in the external node list for proc_n I need to check
1453 ** only the last element in the current list
1454 */
1455 if (lb->ext_nodes[proc_n].empty() || (lb->ext_nodes[proc_n].back() != (INT)ncnt)) {
1456 lb->ext_nodes[proc_n].push_back(ncnt);
1457 lb->ext_procs[proc_n].push_back(proc);
1458 }
1459 }
1460 } /* End "for(i=0; i < nnodes; i++)" */
1461 } /* End "for(ecnt=0; ecnt < graph->nsur_elem[ncnt]; ecnt++)" */
1462
1463 if (internal) {
1464 /* "ncnt" is an internal node */
1465 lb->int_nodes[proc].push_back(ncnt);
1466 }
1467 } /* End "for(ncnt=0; ncnt < mesh->num_nodes; ncnt++)" */
1468 time2 = get_time();
1469 fmt::print("Time for nodal categorization: {}s\n", time2 - time1);
1470
1471 /* Find the internal elements */
1472 time1 = get_time();
1473 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1474 ElementType etype = mesh->elem_type[ecnt];
1475 int nnodes = get_elem_info(ElementInfo::NNODES, etype);
1476 for (size_t ncnt = 0; ncnt < static_cast<size_t>(nnodes); ncnt++) {
1477 int node = mesh->connect[ecnt][ncnt];
1478 int proc = lb->vertex2proc[node];
1479 assert(proc < machine->num_procs);
1480 /*
1481 ** since the outer loop is on the elements, I don't need to
1482 ** search over the entire list to find out if this element is
1483 ** already in it. If the element is in the processors list,
1484 ** then it must be the last element.
1485 */
1486 if ((lb->int_elems[proc].empty()) || (lb->int_elems[proc].back() != (INT)ecnt)) {
1487 lb->int_elems[proc].push_back(ecnt);
1488 }
1489 }
1490 }
1491 time2 = get_time();
1492 fmt::print("Elemental categorization: {}s\n", time2 - time1);
1493 return 1;
1494 } /*-----------------------------End nodal_dist()----------------------------*/
1495
1496 /*****************************************************************************/
1497 /*****************************************************************************/
1498 /*****************************************************************************/
1499 template <typename INT>
1500 int elemental_dist(LB_Description<INT> *lb, Machine_Description *machine,
1501 Mesh_Description<INT> *mesh, Graph_Description<INT> *graph,
1502 Problem_Description *problem)
1503 {
1504 /* Allocate memory */
1505 lb->int_nodes.resize(machine->num_procs);
1506 lb->bor_nodes.resize(machine->num_procs);
1507 lb->ext_nodes.resize(machine->num_procs); /* Not used in elemental dist */
1508
1509 lb->int_elems.resize(machine->num_procs);
1510 lb->bor_elems.resize(machine->num_procs);
1511
1512 lb->ext_procs.resize(machine->num_procs);
1513 lb->born_procs.resize(machine->num_procs);
1514
1515 lb->e_cmap_elems.resize(machine->num_procs);
1516 lb->e_cmap_sides.resize(machine->num_procs);
1517 lb->e_cmap_procs.resize(machine->num_procs);
1518 lb->e_cmap_neigh.resize(machine->num_procs);
1519
1520 /* allocate space to hold info about surrounding elements */
1521 std::vector<INT> pt_list(graph->max_nsur);
1522 std::vector<INT> hold_elem(graph->max_nsur);
1523
1524 /* Find the internal and border elements */
1525 double time1 = get_time();
1526
1527 int mesh_dim = mesh->num_dims;
1528 if (mesh_dim == 1) {
1529 std::vector<int> categorized(mesh->num_elems);
1530 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1531 int proce = lb->vertex2proc[ecnt];
1532 auto etype = mesh->elem_type[ecnt];
1533 int nsides = get_elem_info(ElementInfo::NSIDES, etype);
1534 assert(nsides == 2);
1535
1536 /* check each side of this element */
1537 for (int nscnt = 0; nscnt < nsides; nscnt++) {
1538
1539 /* get the node on this element side (should only be one)*/
1540 std::array<INT, MAX_SIDE_NODES> side_nodes;
1541 #ifndef NDEBUG
1542 int side_cnt =
1543 #endif
1544 ss_to_node_list(etype, mesh->connect[ecnt], (nscnt + 1), side_nodes.data());
1545 assert(side_cnt == 1);
1546
1547 size_t nhold = graph->sur_elem[side_nodes[0]].size();
1548 assert(nhold == 1 || nhold == 2);
1549 if (nhold == 2) {
1550 // 2 elements connected to this node -- `ecnt` and the other one...
1551 for (size_t ncnt = 0; ncnt < nhold; ncnt++) {
1552 size_t elem = graph->sur_elem[side_nodes[0]][ncnt];
1553 if (elem == ecnt) {
1554 continue;
1555 }
1556 int proc2 = lb->vertex2proc[elem];
1557 if (proce == proc2) {
1558 continue;
1559 }
1560 else {
1561 // Processors of the two elements are different, so we are
1562 // at a processor boundary...
1563 if (!categorized[ecnt]) {
1564 lb->bor_elems[proce].push_back(ecnt);
1565 categorized[ecnt] = 1;
1566 }
1567 lb->e_cmap_elems[proc2].push_back(elem);
1568 lb->e_cmap_sides[proc2].push_back(2 - ncnt);
1569 lb->e_cmap_procs[proc2].push_back(proce);
1570 lb->e_cmap_neigh[proc2].push_back(ecnt);
1571 }
1572 }
1573 }
1574 }
1575 if (!categorized[ecnt]) {
1576 lb->int_elems[proce].push_back(ecnt);
1577 categorized[ecnt] = 1;
1578 }
1579 }
1580 }
1581 else {
1582 std::array<INT, MAX_SIDE_NODES> side_nodes;
1583 for (size_t ecnt = 0; ecnt < mesh->num_elems; ecnt++) {
1584 int proc = lb->vertex2proc[ecnt];
1585 assert(proc < machine->num_procs);
1586 bool internal = true;
1587 int flag = 0;
1588 ElementType etype = mesh->elem_type[ecnt];
1589 int dim1 = get_elem_info(ElementInfo::NDIM, etype);
1590
1591 /* need to check for hex's or tet's */
1592 bool hflag1 = is_hex(etype);
1593
1594 /* a TET10 cannot connect to a HEX */
1595 bool tflag1 = is_tet(etype);
1596
1597 int nsides = get_elem_info(ElementInfo::NSIDES, etype);
1598
1599 /* check each side of this element */
1600 for (int nscnt = 0; nscnt < nsides; nscnt++) {
1601
1602 /* get the list of nodes on this element side */
1603 int side_cnt =
1604 ss_to_node_list(etype, mesh->connect[ecnt], (nscnt + 1), side_nodes.data());
1605
1606 /*
1607 * now determine how many side set nodes are needed to
1608 * determine if there is an element connected to this side.
1609 *
1610 * 2-D - need two nodes, so find one intersection
1611 * 3-D - need three nodes, so find two intersections
1612 * NOTE: must check to make sure that this number is not
1613 * larger than the number of nodes on the sides (ie - SHELL).
1614 */
1615
1616 int nnodes = mesh->num_dims;
1617 if (side_cnt < nnodes) {
1618 nnodes = side_cnt;
1619 }
1620 nnodes--; /* decrement to find the number of intersections needed */
1621
1622 INT nelem = 0; /* reset this in case no intersections are needed */
1623
1624 /*
1625 * need to handle hex's differently because of
1626 * the tet/hex combination
1627 */
1628
1629 if (!hflag1) { /* Not a hex */
1630
1631 /* ignore degenerate bars */
1632
1633 if (!((etype == ElementType::BAR2 || etype == ElementType::SHELL2) &&
1634 side_nodes[0] == side_nodes[1])) {
1635
1636 size_t nhold = graph->sur_elem[side_nodes[0]].size();
1637 for (size_t ncnt = 0; ncnt < nhold; ncnt++) {
1638 hold_elem[ncnt] = graph->sur_elem[side_nodes[0]][ncnt];
1639 }
1640
1641 for (int ncnt = 0; ncnt < nnodes; ncnt++) {
1642 /* Find elements connected to both node '0' and node 'ncnt+1' */
1643 nelem = find_inter(Data(hold_elem), Data(graph->sur_elem[side_nodes[(ncnt + 1)]]),
1644 nhold, graph->sur_elem[side_nodes[(ncnt + 1)]].size(),
1645 Data(pt_list));
1646
1647 if (nelem < 2) {
1648 break;
1649 }
1650
1651 nhold = nelem;
1652 for (int ncnt2 = 0; ncnt2 < nelem; ncnt2++) {
1653 hold_elem[ncnt2] = hold_elem[pt_list[ncnt2]];
1654 }
1655 }
1656 }
1657 else {
1658 fmt::print("WARNING: Element = {} is a DEGENERATE BAR\n", ecnt + 1);
1659 }
1660 }
1661 else { /* Is a hex */
1662
1663 /*
1664 * Hex faces are fairly complicated now. There are two
1665 * exceptions to the standard case:
1666 * 1. it is a degenerate hex (mimics a wedge). this has
1667 * two special faces, the first is a triangle, and the
1668 * second is a 2d line
1669 * 2. two tets are connected to this hex face
1670 */
1671
1672 /* first need to check for a degenerate element */
1673 int dflag = 0;
1674 if (side_nodes[0] == side_nodes[1] || side_nodes[0] == side_nodes[3]) {
1675 dflag++;
1676 }
1677 if (side_nodes[2] == side_nodes[1] || side_nodes[2] == side_nodes[3]) {
1678 dflag++;
1679 }
1680
1681 /*
1682 * if both flags are set, then this face is the 2d line,
1683 * and should be ignored with respect to elemental
1684 * communication maps
1685 */
1686 if (dflag == 2) {
1687 nelem = 1;
1688 }
1689 else {
1690 /*
1691 * In order to check for two tets connected to this face,
1692 * check the intersection of opposite corners of this face.
1693 * Both tets should show up in the intersection of one of the
1694 * sets of opposite corners (nothing should show up in the
1695 * other).
1696 */
1697
1698 /*
1699 * Initial check is side nodes 0 and 2 which are
1700 * diagonally opposite
1701 */
1702 int inode = 0;
1703 int node = 2;
1704 size_t nhold = 0;
1705 for (int ncnt = 0; ncnt < nnodes; ncnt++) {
1706 /* Find elements connected to both node 'inode' and node 'node' */
1707 nelem = find_inter(Data(graph->sur_elem[side_nodes[inode]]),
1708 Data(graph->sur_elem[side_nodes[node]]),
1709 graph->sur_elem[side_nodes[inode]].size(),
1710 graph->sur_elem[side_nodes[node]].size(), Data(pt_list));
1711
1712 if (nelem > 1) {
1713 if (ncnt == 0) {
1714 nhold = nelem;
1715 for (int ncnt2 = 0; ncnt2 < nelem; ncnt2++) {
1716 hold_elem[ncnt2] = graph->sur_elem[side_nodes[inode]][pt_list[ncnt2]];
1717 }
1718
1719 if (dflag) {
1720 /*
1721 * in this case, need to get an intersection with
1722 * another (unique) point since nodes 0 and 2
1723 * may represent an edge and not the diagonal
1724 */
1725 if (side_nodes[1] != side_nodes[0] && side_nodes[1] != side_nodes[2]) {
1726 node = 1;
1727 }
1728 else {
1729 node = 3;
1730 }
1731 }
1732 else {
1733 /*
1734 * in the non-degenerate case, if an element is connected
1735 * to two opposite nodes, then it must share a face.
1736 */
1737 break;
1738 }
1739 }
1740 else {
1741 /* This is the second or later time through this
1742 loop and each time through, there have been two
1743 or more elements that are connected to 'node'
1744 (which changes) and 'inode'. We want to make
1745 sure that the elements matched this time through
1746 were also in the list the first time through so
1747 that the elements contain nodes 0 1 2 of the face
1748 and not just 0 1 and 0 2...
1749 So, this time, only put an element in the list if
1750 it was in the list before.
1751 */
1752 for (size_t ncnt2 = 0; ncnt2 < nhold; ncnt2++) {
1753 hold_elem[ncnt2] = -hold_elem[ncnt2];
1754 }
1755 for (int ncnt3 = 0; ncnt3 < nelem; ncnt3++) {
1756 for (size_t ncnt2 = 0; ncnt2 < nhold; ncnt2++) {
1757 if (-hold_elem[ncnt2] ==
1758 graph->sur_elem[side_nodes[inode]][pt_list[ncnt3]]) {
1759 hold_elem[ncnt2] = graph->sur_elem[side_nodes[inode]][pt_list[ncnt3]];
1760 break;
1761 }
1762 }
1763 }
1764 /* Now, go through list and cull out element < 0 */
1765 size_t ncnt3 = 0;
1766 for (size_t ncnt2 = 0; ncnt2 < nhold; ncnt2++) {
1767 if (hold_elem[ncnt2] >= 0) {
1768 hold_elem[ncnt3] = hold_elem[ncnt2];
1769 ncnt3++;
1770 }
1771 }
1772 nelem = ncnt3;
1773 if (!dflag && nelem > 2) {
1774 fmt::print(
1775 stderr,
1776 "Possible corrupted mesh detected at element {}, strange connectivity.\n",
1777 ecnt);
1778 }
1779 }
1780 }
1781 else { /* nelem == 1 or 0 */
1782 if (!dflag) {
1783 nhold = graph->sur_elem[side_nodes[1]].size();
1784 for (size_t ncnt2 = 0; ncnt2 < nhold; ncnt2++) {
1785 hold_elem[ncnt2] = graph->sur_elem[side_nodes[1]][ncnt2];
1786 }
1787 }
1788 inode = 1;
1789 node = 3; /* The node diagonally opposite node 1 */
1790 }
1791 }
1792 }
1793 } /* "if (!hflag1)" */
1794
1795 /*
1796 * if there is an element on this side of ecnt, then there
1797 * will be at least two elements in the intersection (one
1798 * will be ecnt)
1799 */
1800 if (nelem > 1) {
1801
1802 /*
1803 * now go through and check each element in the list to see
1804 * if it on a different processor than ecnt. Don't need to
1805 * worry about ecnt (which is in the list) since it is on
1806 * the same processor as itself. Note that due to filtering
1807 * done above, we are guaranteed to either have an element
1808 * on a different processor or elem==ecnt.
1809 */
1810 for (int ncnt = 0; ncnt < nelem; ncnt++) {
1811
1812 INT elem = hold_elem[ncnt];
1813 int proc2 = lb->vertex2proc[elem];
1814 assert(proc2 < machine->num_procs);
1815
1816 if (proc != proc2) {
1817
1818 ElementType etype2 = mesh->elem_type[elem];
1819
1820 int dim2 = get_elem_info(ElementInfo::NDIM, etype2);
1821
1822 int diff = abs(dim1 - dim2);
1823
1824 /*
1825 * hex's to shells - ok
1826 * shells to bar - ok
1827 * hex to bar - BAD since a BAR will see a HEX but a HEX will not
1828 * see a BAR
1829 */
1830
1831 if (diff < 2) {
1832
1833 /* need to check for hex's */
1834 bool hflag2 = is_hex(etype2);
1835 bool tflag2 = is_tet(etype2);
1836
1837 /* check here for tet/hex combinations */
1838 int sid = 0;
1839 if ((tflag1 && hflag2) || (hflag1 && tflag2)) {
1840 /*
1841 * have to call a special function to get the side id
1842 * in these cases. In both cases, the number of side
1843 * nodes for the element will not be consistent with
1844 * side_cnt, and:
1845 *
1846 * TET/HEX - side_nodes only contains three of the
1847 * the side nodes of the hex.
1848 *
1849 * HEX/TET - Have to check that this tet shares a side
1850 * with the hex.
1851 */
1852 sid = get_side_id_hex_tet(mesh->elem_type[elem], mesh->connect[elem], side_cnt,
1853 side_nodes.data());
1854 }
1855 else {
1856 /*
1857 * get the side id of elem. Make sure that ecnt is
1858 * trying to communicate to a valid side of elem
1859 */
1860 std::array<INT, MAX_SIDE_NODES> mirror_nodes;
1861 side_cnt =
1862 get_ss_mirror(etype, side_nodes.data(), (nscnt + 1), mirror_nodes.data());
1863
1864 /*
1865 * small kludge to handle 6 node faces butted up against
1866 * 4 node faces
1867 */
1868 if (etype == ElementType::HEXSHELL && side_cnt == 6) {
1869 side_cnt = 4;
1870 }
1871
1872 /*
1873 * in order to get the correct side order for elem,
1874 * get the mirror of the side of ecnt
1875 */
1876 sid = get_side_id(mesh->elem_type[elem], mesh->connect[elem], side_cnt,
1877 mirror_nodes.data(), problem->skip_checks,
1878 problem->partial_adj);
1879 }
1880
1881 if (sid > 0) {
1882 /* Element is a border element */
1883 internal = false;
1884 if (!flag) {
1885 flag = 1;
1886 lb->bor_elems[proc].push_back(ecnt);
1887 }
1888
1889 /* now put ecnt into proc2's communications map */
1890 lb->e_cmap_elems[proc2].push_back(elem);
1891 lb->e_cmap_sides[proc2].push_back(sid);
1892 lb->e_cmap_procs[proc2].push_back(proc);
1893 lb->e_cmap_neigh[proc2].push_back(ecnt);
1894 }
1895 else if ((sid < 0) && (!problem->skip_checks)) {
1896 /*
1897 * too many errors with bad meshes, print out
1898 * more information here for diagnostics
1899 */
1900 std::string cmesg =
1901 fmt::format("Error returned while getting side id for communication map.");
1902 Gen_Error(0, cmesg);
1903 cmesg = fmt::format("Element 1: {}", (ecnt + 1));
1904 Gen_Error(0, cmesg);
1905 nnodes = get_elem_info(ElementInfo::NNODES, etype);
1906 cmesg = "connect table:";
1907 for (int i = 0; i < nnodes; i++) {
1908 std::string tmpstr = fmt::format(" {}", (size_t)(mesh->connect[ecnt][i] + 1));
1909 cmesg += tmpstr;
1910 }
1911 Gen_Error(0, cmesg);
1912 cmesg = fmt::format("side id: {}", static_cast<size_t>(nscnt + 1));
1913 Gen_Error(0, cmesg);
1914 cmesg = "side nodes:";
1915 for (int i = 0; i < side_cnt; i++) {
1916 std::string tmpstr = fmt::format(" {}", (size_t)(side_nodes[i] + 1));
1917 cmesg += tmpstr;
1918 }
1919 Gen_Error(0, cmesg);
1920 cmesg = fmt::format("Element 2: {}", (size_t)(elem + 1));
1921 Gen_Error(0, cmesg);
1922 nnodes = get_elem_info(ElementInfo::NNODES, etype2);
1923 cmesg = "connect table:";
1924 for (int i = 0; i < nnodes; i++) {
1925 std::string tmpstr = fmt::format(" {}", (size_t)(mesh->connect[elem][i] + 1));
1926 cmesg += tmpstr;
1927 }
1928 Gen_Error(0, cmesg);
1929 return 0; /* and get out of here */
1930
1931 } /* End "if sid < 0 && !problem>skip_checks" */
1932 } /* End "if (sid > 0)" */
1933 } /* End "if (proc != proc2)" */
1934 } /* End "for (ncnt = 0; ncnt < nelem; ncnt++)" */
1935 } /* End "if (nelem > 1)" */
1936 } /* End "for (nscnt = 0; nscnt < nsides; nscnt++)" */
1937
1938 if (internal) {
1939 lb->int_elems[proc].push_back(ecnt);
1940 }
1941 } /* End "for(ecnt=0; ecnt < mesh->num_elems; ecnt++)" */
1942 }
1943 double time2 = get_time();
1944 fmt::print("Time for elemental categorization: {}s\n", time2 - time1);
1945
1946 /* Find the internal and border nodes */
1947
1948 time1 = get_time();
1949 for (size_t ncnt = 0; ncnt < mesh->num_nodes; ncnt++) {
1950 bool internal = true;
1951 int proc = 0;
1952
1953 /* If a node is not connected to any elements (graph->nsur_elem[ncnt] == 0),
1954 then it will be assigned to processor 0 and treated as internal.
1955 */
1956
1957 if (!graph->sur_elem[ncnt].empty()) {
1958 size_t elem = graph->sur_elem[ncnt][0];
1959
1960 proc = lb->vertex2proc[elem];
1961 assert(proc < machine->num_procs);
1962 int flag = 0;
1963 for (size_t ecnt = 1; ecnt < graph->sur_elem[ncnt].size(); ecnt++) {
1964 int proc2 = lb->vertex2proc[graph->sur_elem[ncnt][ecnt]];
1965 assert(proc2 < machine->num_procs);
1966 /* check if the processor for any two surrounding elems differ */
1967 if (proc != proc2) {
1968 /* ncnt is a border node of proc */
1969 internal = false;
1970 /* first, I have to deal with node being border for proc */
1971 if (!flag) {
1972 flag = 1; /* only want to do this once */
1973 lb->bor_nodes[proc].push_back(ncnt);
1974 }
1975
1976 /*
1977 * now I have to put ncnt in the border list for proc2
1978 * I need to check to make sure that this node has not
1979 * already been added to this list. If it has, then it
1980 * is in the last position in the array
1981 */
1982 if ((lb->bor_nodes[proc2].empty()) || ((INT)ncnt != lb->bor_nodes[proc2].back())) {
1983 lb->bor_nodes[proc2].push_back(ncnt);
1984 }
1985 } /* if (proc != lb->vertex2proc[graph->sur_elem[ncnt][ecnt]]) */
1986 } /* for(ecnt=1; ecnt < graph->nsur_elem[ncnt]; ecnt++) */
1987 } /* if(graph->nsur_elem[ncnt]) */
1988
1989 if (internal) {
1990 /*
1991 * NOTE: if all of the processors above were the same, then
1992 * the one held in proc is the correct one
1993 */
1994 lb->int_nodes[proc].push_back(ncnt);
1995 }
1996 } /* for(ncnt=0; ncnt < machine->num_nodes; ncnt++) */
1997
1998 time2 = get_time();
1999 fmt::print("Nodal categorization: {}s\n", time2 - time1);
2000
2001 /* Allocate memory for the border node processor IDs */
2002 for (int proc = 0; proc < machine->num_procs; proc++) {
2003 if (!lb->bor_nodes[proc].empty()) {
2004 lb->born_procs[proc].resize(lb->bor_nodes[proc].size());
2005 }
2006 }
2007
2008 /* Now find the processor(s) associated with each border node */
2009 time1 = get_time();
2010 for (int pcnt = 0; pcnt < machine->num_procs; pcnt++) {
2011 for (size_t ncnt = 0; ncnt < lb->bor_nodes[pcnt].size(); ncnt++) {
2012 size_t node = lb->bor_nodes[pcnt][ncnt];
2013
2014 for (size_t ecnt = 0; ecnt < graph->sur_elem[node].size(); ecnt++) {
2015 size_t elem = graph->sur_elem[node][ecnt];
2016 INT proc = lb->vertex2proc[elem];
2017 assert(proc < machine->num_procs);
2018 if (proc != pcnt) {
2019 if (in_list(proc, lb->born_procs[pcnt][ncnt]) < 0) {
2020 lb->born_procs[pcnt][ncnt].push_back(proc);
2021 }
2022 } /* End "if(proc != pcnt)" */
2023 } /* End "for(ecnt=0; ecnt < graph->nsur_elems[node]; ecnt++)" */
2024 } /* End "for(ncnt=0; ncnt < lb->num_bor_nodes[pcnt]; ncnt++)" */
2025 } /* End "for(pcnt=0; pcnt < machine->num_procs; pcnt++)" */
2026
2027 time2 = get_time();
2028 fmt::print("Find procs for border nodes: {}s\n", time2 - time1);
2029
2030 /* Order the element communication maps by processor */
2031 time1 = get_time();
2032 for (int pcnt = 0; pcnt < machine->num_procs; pcnt++) {
2033 /* Note that this sort is multi-key */
2034 qsort4(&lb->e_cmap_procs[pcnt][0], /* 1st key */
2035 &lb->e_cmap_elems[pcnt][0], /* 2nd key */
2036 &lb->e_cmap_neigh[pcnt][0], /* 3rd key */
2037 &lb->e_cmap_sides[pcnt][0], /* 4th key */
2038 lb->e_cmap_procs[pcnt].size()); /* Size */
2039 }
2040 /*
2041 * At this point, each processors arrays are sorted on three keys:
2042 * [processor, element, neighbor]
2043 */
2044
2045 time2 = get_time();
2046 fmt::print("Order elem cmaps: {}s\n", time2 - time1);
2047
2048 /*
2049 * Now order the elemental communication maps so that they are
2050 * consistent between processors.
2051 */
2052 time1 = get_time();
2053 for (INT pcnt = 1; pcnt < machine->num_procs; pcnt++) {
2054 int save_fv1 = 0;
2055 auto size =
2056 static_cast<int64_t>(lb->e_cmap_procs[pcnt].size()); /* Define shortcuts size and procs */
2057 std::vector<INT> procs = lb->e_cmap_procs[pcnt];
2058
2059 INT fv1 = -1;
2060 INT lv1 = -1;
2061
2062 for (int pcnt2 = 0; pcnt2 < pcnt; pcnt2++) {
2063
2064 /*
2065 * Find the first and last entries for processor "pcnt2" in
2066 * the list of processor "pcnt".
2067 */
2068
2069 /* lb->c_cmap_procs[pcnt] is sorted based on processor.
2070 * From point 'save_fv1' search for 'pcnt2'
2071 * If not found, value is -1; else search for !pcnt2 from
2072 * that point forward.
2073 */
2074 int64_t i = save_fv1;
2075 while (i < size && procs[i] < pcnt2) {
2076 i++;
2077 }
2078 if (i >= size || procs[i] != pcnt2) {
2079 fv1 = -1;
2080 lv1 = -1;
2081 }
2082 else {
2083 fv1 = i;
2084 assert(procs[i] == pcnt2);
2085 for (lv1 = fv1; lv1 < size; lv1++) {
2086 if (procs[lv1] != pcnt2) {
2087 lv1 = lv1 - 1;
2088 assert(procs[lv1] == pcnt2);
2089 break;
2090 }
2091 }
2092 }
2093
2094 if (lv1 >= size) {
2095 lv1 = size - 1;
2096 }
2097
2098 if (lv1 != -1) {
2099 save_fv1 = lv1 + 1;
2100 }
2101
2102 #if 0
2103 /* Old method -- can use for verification by uncommenting this if block */
2104 {
2105 int tst_fv1, tst_lv1;
2106 find_first_last(pcnt2, size, procs, &tst_fv1, &tst_lv1);
2107 assert(tst_fv1 == fv1);
2108 assert(tst_lv1 == lv1);
2109 }
2110 #endif
2111
2112 if (fv1 >= 0) {
2113 /* Sort based on neighbor element */
2114 sort3(lv1 - fv1 + 1, (&lb->e_cmap_neigh[pcnt][fv1]), (&lb->e_cmap_elems[pcnt][fv1]),
2115 (&lb->e_cmap_sides[pcnt][fv1]));
2116 /*
2117 * Find the first and last entries for processor "pcnt" in
2118 * the list of processor "pcnt2".
2119 */
2120 INT fv2 = -1;
2121 INT lv2 = -1;
2122 find_first_last(pcnt, lb->e_cmap_procs[pcnt2].size(), &lb->e_cmap_procs[pcnt2][0], &fv2,
2123 &lv2);
2124 #if 1
2125 if (lv2 - fv2 != lv1 - fv1) {
2126 fmt::print(stderr, "{}: {} to {}\n", static_cast<size_t>(pcnt2), (size_t)fv1,
2127 (size_t)lv1);
2128 for (i = fv1; i <= lv1; i++) {
2129 fmt::print(stderr, "{}: {}\t{}\t{}\t{}\n", static_cast<size_t>(i),
2130 (size_t)lb->e_cmap_elems[pcnt][i], (size_t)lb->e_cmap_neigh[pcnt][i],
2131 (size_t)lb->e_cmap_procs[pcnt][i], (size_t)lb->e_cmap_sides[pcnt][i]);
2132 }
2133 fmt::print(stderr, "{}: {} to {}\n", (size_t)pcnt, (size_t)fv2, (size_t)lv2);
2134 for (i = fv2; i <= lv2; i++) {
2135 fmt::print(stderr, "{}: {}\t{}\t{}\t{}\n", static_cast<size_t>(i),
2136 (size_t)lb->e_cmap_elems[pcnt2][i], (size_t)lb->e_cmap_neigh[pcnt2][i],
2137 (size_t)lb->e_cmap_procs[pcnt2][i], (size_t)lb->e_cmap_sides[pcnt2][i]);
2138 }
2139 }
2140 #endif
2141 assert(lv2 - fv2 == lv1 - fv1);
2142
2143 /* Sort based on element -- This will then match order of
2144 * the fv1->lv1 arrays.
2145 */
2146 sort3(lv2 - fv2 + 1, (&lb->e_cmap_elems[pcnt2][fv2]), (&lb->e_cmap_neigh[pcnt2][fv2]),
2147 (&lb->e_cmap_sides[pcnt2][fv2]));
2148
2149 } /* End "if(fv1 >= 0)" */
2150 } /* End "for(pcnt2=0; pcnt2 < pcnt; pcnt2++)" */
2151 } /* End "for(pcnt=0; pcnt < machine->num_procs; pcnt++)" */
2152
2153 time2 = get_time();
2154 fmt::print("Make cmaps consistent: {}s\n", time2 - time1);
2155
2156 return 1;
2157 } /*--------------------------End elemental_dist()---------------------------*/
2158
2159 /*****************************************************************************/
2160 /*****************************************************************************/
2161 /*****************************************************************************/
2162 /*
2163 * Determine a graph's connected components
2164 * Input:
2165 * nrow = number of elements in the problem
2166 * rows = the pointer into columns. 1 based and of dimension nrow+1
2167 * The last value=1+dimension of columns.
2168 * columns = the element to element connectivity. Also 1 based
2169 * and includes the self connectivity.
2170 * Output:
2171 * return value = number of pieces
2172 * list = all the elements grouped by connectivity, allocated
2173 * before calling extract_connected_lists.
2174 * list_ptr = pointers to the start of each connected component in
2175 * list[]. The dimension of *list_ptr is the number of
2176 * connected components. Memory is allocated within the
2177 * routine. Memory must be freed using free(). List_ptr
2178 * is zero based.
2179 * Example:
2180 *
2181 * 1 2 3 4 5
2182 * 1 * * *
2183 * 2 *
2184 * 3 * *
2185 * 4 * *
2186 * 5 *
2187 * There are three connected components: { 1 3 4 }, { 2 } and { 5 }
2188 *
2189 * Input:
2190 * nrow=5
2191 * rows={ 1 4 5 7 9 10}
2192 * columns={1 3 4 2 1 3 1 4 5}
2193 *
2194 * Output:
2195 * returns 3
2196 * list= { 1 3 4 2 5 }
2197 * list_ptr={ 0 3 4 }
2198 */
2199
2200 int extract_connected_lists(int nrow, const int *columns, const int *rows, int *list,
2201 std::vector<int> &list_ptr)
2202 {
2203 int root;
2204 int nordered;
2205 int ni;
2206 int nf;
2207 int nni;
2208 int nnf;
2209 int i;
2210 int ki;
2211 int kf;
2212 int k;
2213 int j;
2214 int components;
2215 int too_many_components = 0;
2216 if (nrow == 0) {
2217 return (0);
2218 }
2219
2220 /* Reasonable guess for number of components */
2221 int pieces = 10 + (nrow / 10);
2222 list_ptr.resize(pieces);
2223 std::vector<int> mask(nrow, 1);
2224 root = 1;
2225
2226 components = 1;
2227 nordered = 1;
2228 list_ptr[components - 1] = nordered - 1;
2229 list[nordered - 1] = root;
2230 mask[root - 1] = 0;
2231 ni = 1;
2232 nf = 1;
2233 while (nordered < nrow) {
2234 if (nf == ni - 1) {
2235 ++components;
2236 if (components < pieces) {
2237 list_ptr[components - 1] = nordered;
2238 }
2239 else {
2240 too_many_components = 1;
2241 }
2242 for (i = 0; i < nrow; i++) {
2243 if (mask[i] == 1) {
2244 ++nordered;
2245 list[nordered - 1] = i + 1;
2246 mask[i] = 0;
2247 nf = ni;
2248 break;
2249 }
2250 }
2251 }
2252 nni = nf + 1;
2253 nnf = nni - 1;
2254 for (i = ni; i <= nf; i++) {
2255 ki = rows[list[i - 1] - 1] - 1;
2256 kf = rows[list[i - 1]] - 2;
2257 for (k = ki; k <= kf; k++) {
2258 j = columns[k];
2259 if (mask[j - 1] == 1) {
2260 ++nnf;
2261 ++nordered;
2262 mask[j - 1] = 0;
2263 list[nordered - 1] = j;
2264 }
2265 }
2266 }
2267 ni = nni;
2268 nf = nnf;
2269 }
2270 if (too_many_components == 0) {
2271 list_ptr[components] = nordered;
2272 return (components);
2273 }
2274
2275 /* Start over with list_ptr correctly allocated */
2276 list_ptr.resize(components);
2277 list_ptr.shrink_to_fit();
2278 for (i = 0; i < nrow; i++) {
2279 mask[i] = 1;
2280 }
2281
2282 components = 1;
2283 nordered = 1;
2284 list_ptr[components - 1] = nordered - 1;
2285 list[nordered - 1] = root;
2286 mask[root - 1] = 0;
2287 ni = 1;
2288 nf = 1;
2289 while (nordered < nrow) {
2290 if (nf == ni - 1) {
2291 ++components;
2292 list_ptr[components - 1] = nordered;
2293 for (i = 0; i < nrow; i++) {
2294 if (mask[i] == 1) {
2295 ++nordered;
2296 list[nordered - 1] = i + 1;
2297 mask[i] = 0;
2298 nf = ni;
2299 break;
2300 }
2301 }
2302 }
2303 nni = nf + 1;
2304 nnf = nni - 1;
2305 for (i = ni; i <= nf; i++) {
2306 ki = rows[list[i - 1] - 1] - 1;
2307 kf = rows[list[i - 1]] - 2;
2308 for (k = ki; k <= kf; k++) {
2309 j = columns[k];
2310 if (mask[j - 1] == 1) {
2311 ++nnf;
2312 ++nordered;
2313 mask[j - 1] = 0;
2314 list[nordered - 1] = j;
2315 }
2316 }
2317 }
2318 ni = nni;
2319 nf = nnf;
2320 }
2321 list_ptr[components] = nordered;
2322 return (components);
2323 }
2324
2325 /*****************************************************************************/
2326 int ZPINCH_assign(Machine_Description *machine, /* Machine MESH = nwedge * nslice */
2327 int ndot, /* Length of x, y, z, and part (== # of elements) */
2328 const float *x, /* x-coordinates */
2329 const float *y, /* y-coordinates */
2330 const float *z, /* z-coordinates */
2331 int *part /* Output: partition assignments for each element */
2332 )
2333 {
2334 /* Routine to generate a partition of a cylinder.
2335 * Assumptions:
2336 * Height of cylinder is aligned with z-axis.
2337 * Face of cylinder is centered at (x,y) = (0,0).
2338 * The x,y-plane is partitioned into wedge-shaped slices
2339 * (just like cutting a pie!).
2340 * The z-directon is partitioned into cylindrical slices
2341 * (just like cutting a hot dog!).
2342 *
2343 * Decomposition requested by Chris Garasi for Z-Pinch simulations,
2344 * NNSA Level-1 milestone for Petaflop Computer justification.
2345 * Decomposition implemented by Karen Devine, [email protected].
2346 * March 18, 2004
2347 */
2348
2349 double theta; /* angle of (x,y) (polar coordinates) */
2350
2351 if (ndot > 0 && (x == nullptr || y == nullptr || z == nullptr || part == nullptr)) {
2352 fmt::print(stderr, "KDD -- Bad input to ZPINCH_assign.\n");
2353 fmt::print(stderr, "KDD -- Contact Karen Devine, [email protected].\n");
2354 exit(-1);
2355 }
2356
2357 if (machine->type != MachineType::MESH) {
2358 fmt::print(stderr, "KDD -- Machine must be a MESH "
2359 "with # wedges * # slices processors.\n");
2360 fmt::print(stderr, "KDD -- Use nem_slice argument -m mesh=AxB, \n");
2361 fmt::print(stderr, "KDD -- where A = # wedges in x,y-plane and \n");
2362 fmt::print(stderr, "KDD -- B = # slices along z-axis.\n");
2363 exit(-1);
2364 }
2365 int nwedge = machine->dim[0];
2366 int nslice = machine->dim[1];
2367 fmt::print("ZPINCH: Computing\n"
2368 " {} slices in the z-direction\n"
2369 " {} wedges in the x,y-plane\n"
2370 " {} partitions total\n",
2371 nslice, nwedge, nslice * nwedge);
2372
2373 /* Compute the maximum values of z */
2374 float zmin = FLT_MAX; /* Minimum and maximum z-coordinate values */
2375 float zmax = -FLT_MAX;
2376 for (int i = 0; i < ndot; i++) {
2377 if (z[i] > zmax) {
2378 zmax = z[i];
2379 }
2380 if (z[i] < zmin) {
2381 zmin = z[i];
2382 }
2383 }
2384 double dz = zmax - zmin;
2385
2386 /* Compute maximum z for each slice, using uniform partition of zmin - zmax */
2387 std::vector<double> slice_max_z(nslice);
2388 for (int i = 0; i < nslice; i++) {
2389 slice_max_z[i] =
2390 static_cast<double>(zmin) + static_cast<double>(i + 1) * dz / static_cast<double>(nslice);
2391 }
2392
2393 /* Compute maximum angle for each wedge, using uniform partition of 2*M_PI */
2394 std::vector<double> wedge_max_theta(nwedge);
2395 for (int i = 0; i < nwedge; i++) {
2396 wedge_max_theta[i] = static_cast<double>(i + 1) * (2. * M_PI) / static_cast<double>(nwedge);
2397 }
2398
2399 /* Compute the partition assignment for each set of coordinates */
2400 double epsilon = 1e-07; /* tolerance that allows a point to be in wedge */
2401 for (int i = 0; i < ndot; i++) {
2402
2403 /* Compute the z slice that the element is in. */
2404 int slice = 0;
2405 if (dz > 0.) {
2406 slice =
2407 static_cast<int>(nslice * (static_cast<double>(z[i]) - static_cast<double>(zmin)) / dz);
2408 if (slice == nslice) {
2409 slice--; /* Handles z[i] == zmax correctly */
2410 }
2411
2412 /* Move dots within epsilon of upper end of slice into next slice */
2413 /* This step reduces jagged edges due to roundoff in coordinate values */
2414 if (slice != nslice - 1 && static_cast<double>(z[i]) > (slice_max_z[slice] - epsilon)) {
2415 slice++;
2416 }
2417 }
2418 else { /* 2D problem */
2419 slice = 0;
2420 }
2421
2422 /* Compute polar coordinate theta in x,y-plane for the element. */
2423 if (x[i] == 0.0F) {
2424 if (y[i] >= 0.0F) {
2425 theta = M_PI_2;
2426 }
2427 else {
2428 theta = 3. * M_PI_2;
2429 }
2430 }
2431 else {
2432 theta = std::atan2(y[i], x[i]); /* In range -M_PI_2 to M_PI_2 */
2433
2434 /* Convert to range 0 to 2*M_PI */
2435 if (x[i] < 0.0F) {
2436 theta += M_PI;
2437 }
2438 else if (y[i] < 0.0F) {
2439 theta += 2 * M_PI;
2440 }
2441 }
2442
2443 /* Compute the wedge that the element is in. */
2444 int wedge = static_cast<int>(nwedge * theta / (2 * M_PI));
2445 if (wedge == nwedge) {
2446 wedge--; /* Handles theta == 2*M_PI correctly */
2447 }
2448
2449 /* Move dots within epsilon of upper angle of wedge into next wedge */
2450 /* This step reduces jagged edges due to roundoff in coordinate values */
2451 if (theta > wedge_max_theta[wedge] - epsilon) {
2452 wedge = (wedge + 1) % nwedge;
2453 }
2454
2455 /* Compute the part that the element is in. */
2456 part[i] = (slice * nwedge + wedge);
2457 }
2458 return 0;
2459 }
2460
2461 /*****************************************************************************/
2462 void BRICK_slices(int nslices_d, /* # of subdomains in this dimension */
2463 int ndot, /* # of dots */
2464 const float *d, /* Array of ndot coordinates in this dimension */
2465 float *dmin, /* Output: Smallest value in d[] */
2466 float *dmax, /* Output: Largest value in d[] */
2467 double *delta, /* Output: dmax - dmin */
2468 std::vector<double> &slices_d /* Output: maximum d for each slice in dimension
2469 using uniform partition of dmax - dmin */
2470 )
2471 {
2472 /* Compute the min, max, delta and slices values for a single dimension. */
2473 /* KDDKDD Note: This routine could also be used by ZPINCH in the z-direction,
2474 * KDDKDD Note: but I don't want to tamper with code that already works. */
2475 int i;
2476
2477 *dmin = FLT_MAX; /* Minimum and maximum coordinate values */
2478 *dmax = -FLT_MAX;
2479
2480 /* Compute the minimum and maximum coordinate values */
2481 for (i = 0; i < ndot; i++) {
2482 if (d[i] > *dmax) {
2483 *dmax = d[i];
2484 }
2485 if (d[i] < *dmin) {
2486 *dmin = d[i];
2487 }
2488 }
2489 *delta = *dmax - *dmin;
2490
2491 /* Compute maximum coordinate value for each slice,
2492 using uniform partition of dmax - dmin */
2493 slices_d.reserve(nslices_d);
2494 for (i = 0; i < nslices_d; i++) {
2495 slices_d.push_back(static_cast<double>(*dmin) +
2496 static_cast<double>(i + 1) * *delta / static_cast<double>(nslices_d));
2497 }
2498 }
2499
2500 /*****************************************************************************/
2501 int BRICK_which_slice(int nslices_d, /* # of subdomains in this dimension */
2502 float d, /* Coordinate of dot in this dimension */
2503 float dmin, /* Smallest value in d[] */
2504 double delta, /* dmax - dmin */
2505 std::vector<double> &slices_d /* Maximum d for each slice in dimension using
2506 uniform partition of dmax - dmin */
2507 )
2508 {
2509 /* Function returning in which slice a coordinate d lies. */
2510 /* KDDKDD Note: This routine could also be used by ZPINCH in the z-direction,
2511 * KDDKDD Note: but I don't want to tamper with code that already works. */
2512
2513 int d_slice; /* Return value: The slice to which the coordinate is assigned */
2514 if (delta > 0.) {
2515 d_slice = static_cast<int>(nslices_d * static_cast<double>((d - dmin)) / delta);
2516 if (d_slice == nslices_d) {
2517 d_slice--; /* Handles d == dmax correctly */
2518 }
2519
2520 /* Move dots within epsilon of upper end of slice into next slice */
2521 /* This step reduces jagged edges due to roundoff in coordinate values */
2522 double epsilon = 5e-06; /* tolerance that allows a point to be in subdomain*/
2523 if (d_slice != nslices_d - 1 && static_cast<double>(d) > (slices_d[d_slice] - epsilon)) {
2524 d_slice++;
2525 }
2526 }
2527 else { /* not a 3D problem */
2528 d_slice = 0;
2529 }
2530
2531 return d_slice;
2532 }
2533
2534 /*****************************************************************************/
2535 int BRICK_assign(Machine_Description *machine, /* Machine MESH = nx * ny * nz */
2536 int ndot, /* Length of x, y, z, and part (== # of elements) */
2537 const float *x, /* x-coordinates */
2538 const float *y, /* y-coordinates */
2539 const float *z, /* z-coordinates */
2540 int *part /* Output: partition assignments for each element */
2541 )
2542 {
2543 /* Routine to generate a partition of an axis-aligned hexahedral domain.
2544 * Assumptions:
2545 * Hexahedral domain is axis-aligned.
2546 * For good balance, the number of elements in each dimension should
2547 * be divisible by the number of processors used in that dimension.
2548 * Each dimension is partitioned into equally sized regions, generating
2549 * subdomains that are axis-aligned hexahedra.
2550 *
2551 * Decomposition requested by Tom Brunner and Chris Garasi for
2552 * NNSA Level-1 milestone for Petaflop Computer justification.
2553 * Decomposition implemented by Karen Devine, [email protected].
2554 * June 10, 2005
2555 */
2556
2557 if (ndot > 0 && (x == nullptr || y == nullptr || z == nullptr || part == nullptr)) {
2558 fmt::print(stderr, "KDD -- Bad input to BRICK_assign.\n");
2559 fmt::print(stderr, "KDD -- Contact Karen Devine, [email protected].\n");
2560 exit(-1);
2561 }
2562
2563 if (machine->type != MachineType::MESH) {
2564 fmt::print(stderr, "KDD -- Machine must be a MESH "
2565 "with nx * ny * nz processors.\n");
2566 fmt::print(stderr, "KDD -- Use nem_slice argument -m mesh=AxBxC, \n");
2567 fmt::print(stderr, "KDD -- where A = nx, B = ny, and "
2568 "C = nz\n");
2569 exit(-1);
2570 }
2571 int nx = machine->dim[0];
2572 int ny = machine->dim[1];
2573 int nz = machine->dim[2];
2574
2575 fmt::print("BRICK: Computing\n"
2576 " {} subdomains in the x direction\n"
2577 " {} subdomains in the y direction\n"
2578 " {} subdomains in the z direction\n"
2579 " {} partitions total\n",
2580 nx, ny, nz, nx * ny * nz);
2581
2582 float xmin;
2583 float xmax; /* Minimum and maximum x-coordinate values */
2584 float ymin;
2585 float ymax; /* Minimum and maximum y-coordinate values */
2586 float zmin;
2587 float zmax; /* Minimum and maximum z-coordinate values */
2588 double dx; /* xmax - xmin */
2589 double dy; /* ymax - ymin */
2590 double dz; /* zmax - zmin */
2591 std::vector<double> slices_x; /* max x value in each slice. */
2592 std::vector<double> slices_y; /* max y value in each slice. */
2593 std::vector<double> slices_z; /* max z value in each slice. */
2594
2595 /* Compute bounds of subdomains in each dimension */
2596 BRICK_slices(nx, ndot, x, &xmin, &xmax, &dx, slices_x);
2597 BRICK_slices(ny, ndot, y, &ymin, &ymax, &dy, slices_y);
2598 BRICK_slices(nz, ndot, z, &zmin, &zmax, &dz, slices_z);
2599
2600 /* Compute the partition assignment for each set of coordinates */
2601 for (int i = 0; i < ndot; i++) {
2602
2603 /* Compute the slice in each dimension that the element is in */
2604 int x_slice = BRICK_which_slice(nx, x[i], xmin, dx, slices_x);
2605 int y_slice = BRICK_which_slice(ny, y[i], ymin, dy, slices_y);
2606 int z_slice = BRICK_which_slice(nz, z[i], zmin, dz, slices_z);
2607
2608 /* Compute the part that the element is in. */
2609 part[i] = (z_slice * (nx * ny) + y_slice * nx + x_slice);
2610 }
2611 return 0;
2612 }
2613
2614 #ifdef USE_ZOLTAN
2615 /*****************************************************************************/
2616 /***** Global data structure used by Zoltan callbacks. *****/
2617 /***** Could implement Zoltan callbacks without global data structure, *****/
2618 /***** but using the global data structure makes implementation quick. *****/
2619
2620 struct
2621 {
2622 size_t ndot; /* Length of x, y, z, and part (== # of elements) */
2623 int *vwgt; /* vertex weights */
2624 float *x; /* x-coordinates */
2625 float *y; /* y-coordinates */
2626 float *z; /* z-coordinates */
2627 } Zoltan_Data;
2628
2629 /*****************************************************************************/
2630 /***** ZOLTAN CALLBACK FUNCTIONS *****/
2631
2632 int zoltan_num_dim(void * /*data*/, int *ierr)
2633 {
2634 /* Return dimensionality of coordinate data.
2635 * Using global data structure Zoltan_Data, initialized in ZOLTAN_RCB_assign.
2636 */
2637 *ierr = ZOLTAN_OK;
2638 if (Zoltan_Data.z != nullptr) {
2639 return 3;
2640 }
2641 if (Zoltan_Data.y != nullptr) {
2642 return 2;
2643 }
2644 return 1;
2645 }
2646
2647 int zoltan_num_obj(void * /*data*/, int *ierr)
2648 {
2649 /* Return number of objects.
2650 * Using global data structure Zoltan_Data, initialized in ZOLTAN_RCB_assign.
2651 */
2652 *ierr = ZOLTAN_OK;
2653 return Zoltan_Data.ndot;
2654 }
2655
2656 void zoltan_obj_list(void * /*data*/, int /*ngid_ent*/, int /*nlid_ent*/, ZOLTAN_ID_PTR gids,
2657 ZOLTAN_ID_PTR /*lids*/, int wdim, float *wgts, int *ierr)
2658 {
2659 /* Return list of object IDs.
2660 * Return only global IDs; don't need local IDs since running in serial.
2661 * gids are array indices for coordinate and vwgts arrays.
2662 * Using global data structure Zoltan_Data, initialized in ZOLTAN_RCB_assign.
2663 */
2664 for (size_t i = 0; i < Zoltan_Data.ndot; i++) {
2665 gids[i] = i;
2666 if (wdim != 0) {
2667 wgts[i] = static_cast<float>(Zoltan_Data.vwgt[i]);
2668 }
2669 }
2670
2671 *ierr = ZOLTAN_OK;
2672 }
2673
2674 void zoltan_geom(void * /*data*/, int /*ngid_ent*/, int /*nlid_ent*/, int nobj,
2675 const ZOLTAN_ID_PTR gids, ZOLTAN_ID_PTR /*lids*/, int ndim, double *geom,
2676 int *ierr)
2677 {
2678 /* Return coordinates for objects.
2679 * gids are array indices for coordinate arrays.
2680 * Using global data structure Zoltan_Data, initialized in ZOLTAN_RCB_assign.
2681 */
2682
2683 for (int i = 0; i < nobj; i++) {
2684 size_t j = gids[i];
2685 geom[i * ndim] = Zoltan_Data.x[j];
2686 if (ndim > 1) {
2687 geom[i * ndim + 1] = Zoltan_Data.y[j];
2688 }
2689 if (ndim > 2) {
2690 geom[i * ndim + 2] = Zoltan_Data.z[j];
2691 }
2692 }
2693
2694 *ierr = ZOLTAN_OK;
2695 }
2696
2697 /*****************************************************************************/
2698 int ZOLTAN_assign(const char *method, /* Zoltan LB_METHOD to use. */
2699 int totalproc, /* # of processors for which to partition */
2700 size_t ndot, /* Length of x, y, z, and part (== # of elements) */
2701 int *vwgt, /* vertex weights */
2702 float *x, /* x-coordinates */
2703 float *y, /* y-coordinates */
2704 float *z, /* z-coordinates */
2705 int ignore_z, /* flag indicating whether to use z-coords*/
2706 int *part, /* Output: partition assignments for each element */
2707 int argc, /* Fields needed by MPI_Init */
2708 char *argv[] /* Fields needed by MPI_Init */
2709 )
2710 {
2711 /* Function to allow Zoltan to compute decomposition using RCB.
2712 * Assuming running Zoltan in serial (as nem_slice is serial).
2713 * Return PARTITION_ASSIGNMENTS from Zoltan_LB_Partition; they should
2714 * match what is needed in part array above.
2715 */
2716
2717 /* Copy mesh data and pointers into structure accessible from callback fns. */
2718 Zoltan_Data.ndot = ndot;
2719 Zoltan_Data.vwgt = vwgt;
2720 Zoltan_Data.x = x;
2721 Zoltan_Data.y = y;
2722 Zoltan_Data.z = (ignore_z != 0 ? nullptr : z);
2723
2724 /* Initialize Zoltan */
2725 float ver;
2726 int ierr = Zoltan_Initialize(argc, argv, &ver);
2727 if (ierr == ZOLTAN_FATAL) {
2728 fmt::print(stderr, "Error returned from Zoltan_Initialize ({}:{})\n", __FILE__, __LINE__);
2729 exit(-1);
2730 }
2731 struct Zoltan_Struct *zz = Zoltan_Create(MPI_COMM_WORLD); // CHECK: ALLOW MPI_COMM_WORLD
2732
2733 /* Register Callback functions */
2734 /* Using global Zoltan_Data; could register it here instead as data field. */
2735 ierr = Zoltan_Set_Fn(zz, ZOLTAN_NUM_GEOM_FN_TYPE,
2736 reinterpret_cast<ZOLTAN_VOID_FN *>(zoltan_num_dim), nullptr);
2737 if (ierr == ZOLTAN_FATAL) {
2738 fmt::print(stderr, "Error returned from Zoltan_Set_Fn ({}:{})\n", __FILE__, __LINE__);
2739 goto End;
2740 }
2741 ierr = Zoltan_Set_Fn(zz, ZOLTAN_NUM_OBJ_FN_TYPE,
2742 reinterpret_cast<ZOLTAN_VOID_FN *>(zoltan_num_obj), nullptr);
2743 if (ierr == ZOLTAN_FATAL) {
2744 fmt::print(stderr, "Error returned from Zoltan_Set_Fn ({}:{})\n", __FILE__, __LINE__);
2745 goto End;
2746 }
2747 ierr = Zoltan_Set_Fn(zz, ZOLTAN_OBJ_LIST_FN_TYPE,
2748 reinterpret_cast<ZOLTAN_VOID_FN *>(zoltan_obj_list), nullptr);
2749 if (ierr == ZOLTAN_FATAL) {
2750 fmt::print(stderr, "Error returned from Zoltan_Set_Fn ({}:{})\n", __FILE__, __LINE__);
2751 goto End;
2752 }
2753 ierr = Zoltan_Set_Fn(zz, ZOLTAN_GEOM_MULTI_FN_TYPE,
2754 reinterpret_cast<ZOLTAN_VOID_FN *>(zoltan_geom), nullptr);
2755 if (ierr == ZOLTAN_FATAL) {
2756 fmt::print(stderr, "Error returned from Zoltan_Set_Fn ({}:{})\n", __FILE__, __LINE__);
2757 goto End;
2758 }
2759
2760 /* Set parameters for Zoltan */
2761 {
2762 std::string str = fmt::format("{}", totalproc);
2763 ierr = Zoltan_Set_Param(zz, "NUM_GLOBAL_PARTITIONS", str.c_str());
2764 }
2765 if (ierr == ZOLTAN_FATAL) {
2766 fmt::print(stderr, "Error returned from Zoltan_Set_Param ({}:{})\n", __FILE__, __LINE__);
2767 goto End;
2768 }
2769 ierr = Zoltan_Set_Param(zz, "NUM_LID_ENTRIES", "0");
2770 if (ierr == ZOLTAN_FATAL) {
2771 fmt::print(stderr, "Error returned from Zoltan_Set_Param ({}:{})\n", __FILE__, __LINE__);
2772 goto End;
2773 }
2774 ierr = Zoltan_Set_Param(zz, "LB_METHOD", method);
2775 if (ierr == ZOLTAN_FATAL) {
2776 fmt::print(stderr, "Error returned from Zoltan_Set_Param ({}:{})\n", __FILE__, __LINE__);
2777 goto End;
2778 }
2779 ierr = Zoltan_Set_Param(zz, "REMAP", "0");
2780 if (ierr == ZOLTAN_FATAL) {
2781 fmt::print(stderr, "Error returned from Zoltan_Set_Param ({}:{})\n", __FILE__, __LINE__);
2782 goto End;
2783 }
2784 ierr = Zoltan_Set_Param(zz, "RETURN_LISTS", "PARTITION_ASSIGNMENTS");
2785 if (ierr == ZOLTAN_FATAL) {
2786 fmt::print(stderr, "Error returned from Zoltan_Set_Param ({}:{})\n", __FILE__, __LINE__);
2787 goto End;
2788 }
2789 if (vwgt != nullptr) {
2790 ierr = Zoltan_Set_Param(zz, "OBJ_WEIGHT_DIM", "1");
2791 if (ierr == ZOLTAN_FATAL) {
2792 fmt::print(stderr, "Error returned from Zoltan_Set_Param ({}:{})\n", __FILE__, __LINE__);
2793 goto End;
2794 }
2795 }
2796 if (ignore_z != 0) {
2797 ierr = Zoltan_Set_Param(zz, "RCB_RECTILINEAR_BLOCKS", "1");
2798 if (ierr == ZOLTAN_FATAL) {
2799 fmt::print(stderr, "Error returned from Zoltan_Set_Param ({}:{})\n", __FILE__, __LINE__);
2800 goto End;
2801 }
2802 }
2803
2804 /* Call partitioner */
2805 fmt::print("Using Zoltan version {}, method {}\n", static_cast<double>(ver), method);
2806 ZOLTAN_ID_PTR dummy1;
2807 ZOLTAN_ID_PTR dummy2; /* Empty output from Zoltan_LB_Partition */
2808 int dummy0;
2809 int *dummy3;
2810 int *dummy4; /* Empty output from Zoltan_LB_Partition */
2811 int zngid_ent;
2812 int znlid_ent; /* Useful output from Zoltan_LB_Partition */
2813 int znobj;
2814 ZOLTAN_ID_PTR zgids;
2815 ZOLTAN_ID_PTR zlids; /* Useful output from Zoltan_LB_Partition */
2816 int *zprocs, *zparts; /* Useful output from Zoltan_LB_Partition */
2817 int changes;
2818 ierr = Zoltan_LB_Partition(zz, &changes, &zngid_ent, &znlid_ent, &dummy0, &dummy1, &dummy2,
2819 &dummy3, &dummy4, &znobj, &zgids, &zlids, &zprocs, &zparts);
2820 if (ierr != 0) {
2821 fmt::print(stderr, "Error returned from Zoltan_LB_Partition ({}:{})\n", __FILE__, __LINE__);
2822 goto End;
2823 }
2824
2825 /* Sanity check */
2826 if (ndot != static_cast<size_t>(znobj)) {
2827 fmt::print(stderr, "Sanity check failed; ndot {} != znobj {}.\n", ndot,
2828 static_cast<size_t>(znobj));
2829 goto End;
2830 }
2831
2832 /* Convert data types from int to int. */
2833 for (size_t i = 0; i < ndot; i++) {
2834 part[zgids[i]] = zparts[i];
2835 }
2836
2837 End:
2838 /* Clean up */
2839 Zoltan_LB_Free_Part(&zgids, &zlids, &zprocs, &zparts);
2840 Zoltan_Destroy(&zz);
2841 if (ierr != 0) {
2842 MPI_Finalize();
2843 exit(-1);
2844 }
2845 return 0;
2846 }
2847 #endif
2848
2849 /*****************************************************************************/
2850 void BALANCE_STATS(Machine_Description *machine, /* Machine MESH = nwedge * nslice */
2851 const int *wgt, /* element weights; can be nullptr if no weights */
2852 size_t ndot, /* Length of x, y, z, and part (== # of elements) */
2853 int *part /* Partition assignments for each element */
2854 )
2855 {
2856 /* Routine to print some info about the ZPINCH, BRICK or ZOLTAN_RCB
2857 decompositions */
2858 std::vector<int> cntwgt;
2859
2860 int minwgt = INT_MAX;
2861 int maxwgt = 0;
2862 int sumwgt = 0;
2863
2864 int npart = machine->dim[0] * machine->dim[1] * machine->dim[2];
2865 std::vector<int> cnts(npart);
2866 if (wgt != nullptr) {
2867 cntwgt.resize(npart);
2868 }
2869 for (size_t i = 0; i < ndot; i++) {
2870 cnts[part[i]]++;
2871 if (wgt != nullptr) {
2872 cntwgt[part[i]] += wgt[i];
2873 }
2874 }
2875
2876 size_t sum = 0;
2877 int max = 0;
2878 int min = ndot;
2879 for (int i = 0; i < npart; i++) {
2880 if (cnts[i] > max) {
2881 max = cnts[i];
2882 }
2883 if (cnts[i] < min) {
2884 min = cnts[i];
2885 }
2886 sum += cnts[i];
2887 if (wgt != nullptr) {
2888 if (cntwgt[i] > maxwgt) {
2889 maxwgt = cntwgt[i];
2890 }
2891 if (cntwgt[i] < minwgt) {
2892 minwgt = cntwgt[i];
2893 }
2894 sumwgt += cntwgt[i];
2895 }
2896 if (cnts[i] == 0) {
2897 fmt::print("ZERO on {}\n", i);
2898 }
2899 }
2900
2901 fmt::print("CNT STATS: min = {} max = {} avg = {}\n", min, max,
2902 static_cast<double>(sum) / static_cast<double>(npart));
2903 if (wgt != nullptr) {
2904 fmt::print("WGT STATS: min = {} max = {} avg = {}\n", minwgt, maxwgt,
2905 static_cast<double>(sumwgt) / static_cast<double>(npart));
2906 }
2907 }
2908 } // namespace