1 /* This software was developed by Bruce Hendrickson and Robert Leland *
2 * at Sandia National Laboratories under US Department of Energy *
3 * contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
4
5 #include <stdio.h>
6 #include <math.h>
7 #include "params.h"
8 #include "defs.h"
9 #include "structs.h"
10
11
12 static int check_params(), check_assignment();
13
14 /* Check graph and input options and parameters. */
check_input(graph,nvtxs,nedges,igeom,coords,graphname,assignment,goal,architecture,ndims_tot,mesh_dims,global_method,local_method,rqi_flag,vmax,ndims,eigtol)15 int check_input(graph, nvtxs, nedges, igeom, coords,
16 graphname, assignment, goal,
17 architecture, ndims_tot, mesh_dims,
18 global_method, local_method, rqi_flag, vmax, ndims,
19 eigtol)
20 struct vtx_data **graph; /* linked lists of vertex data */
21 int nvtxs; /* number of vertices */
22 int nedges; /* number of edges */
23 int igeom; /* geometric dimension for inertial method */
24 float **coords; /* coordinates for inertial method */
25 char *graphname; /* graph input file name */
26 short *assignment; /* set numbers if read-from-file */
27 double *goal; /* desired sizes of different sets */
28 int architecture; /* 0=> hypercube, d=> d-dimensional mesh */
29 int ndims_tot; /* number of hypercube dimensions */
30 int mesh_dims[3]; /* size of mesh in each dimension */
31 int global_method; /* global partitioning algorithm */
32 int local_method; /* local partitioning algorithm */
33 int rqi_flag; /* flag for RQI/symmlq eigensolver */
34 int *vmax; /* smallest acceptable coarsened nvtxs */
35 int ndims; /* partitioning level */
36 double eigtol; /* tolerance for eigen-pairs */
37 {
38 extern FILE *Output_File; /* output file or null */
39 extern int DEBUG_TRACE; /* trace main execution path? */
40 extern int MATCH_TYPE; /* which type of contraction matching to use? */
41 double vwgt_sum, vwgt_sum2; /* sums of values in vwgts and goals */
42 int flag; /* does input data pass all the tests? */
43 int flag_graph; /* does graph check out OK? */
44 int flag_params; /* do params look OK? */
45 int flag_assign; /* does assignment look good? */
46 int nprocs; /* number of processors partitioning for */
47 int i; /* loop counter */
48 int check_graph(), check_params(), check_assignment();
49
50 if (DEBUG_TRACE > 0) {
51 printf("<Entering check_input>\n");
52 }
53
54 /* First check for consistency in the graph. */
55 if (graph != NULL) {
56 flag_graph = check_graph(graph, nvtxs, nedges);
57 if (flag_graph) {
58 if (graphname != NULL)
59 printf("ERRORS in graph input file %s.\n", graphname);
60 if (Output_File != NULL) {
61 fprintf(Output_File, "ERRORS in graph input file %s.\n",
62 graphname);
63 }
64 else
65 printf("ERRORS in graph.\n");
66 if (Output_File != NULL) {
67 fprintf(Output_File, "ERRORS in graph.\n");
68 }
69 }
70 }
71
72 else {
73 /* Only allowed if simple or inertial w/o KL and no weights. */
74 flag_graph = FALSE;
75 if (global_method == 1 || global_method == 2 || local_method == 1) {
76 printf("No graph input. Only allowed for inertial or simple methods without KL.\n");
77 flag_graph = TRUE;
78 }
79 }
80
81 /* Now check the input values. */
82 flag = FALSE;
83 flag_assign = FALSE;
84
85 if (architecture < 0 || architecture > 3) {
86 printf("Machine architecture parameter = %d, must be in [0,3].\n", architecture);
87 flag = TRUE;
88 }
89
90 else if (architecture == 0) {
91 if (ndims_tot < 0) {
92 printf("Dimension of hypercube = %d, must be at least 1.\n", ndims_tot);
93 flag = TRUE;
94 }
95 }
96
97 else if (architecture > 0) {
98 if (architecture == 1 && mesh_dims[0] <= 0) {
99 printf("Size of 1-D mesh improperly specified, %d.\n", mesh_dims[0]);
100 flag = TRUE;
101 }
102 if (architecture == 2 && (mesh_dims[0] <= 0 || mesh_dims[1] <= 0)) {
103 printf("Size of 2-D mesh improperly specified, %dx%d.\n", mesh_dims[0], mesh_dims[1]);
104 flag = TRUE;
105 }
106 if (architecture == 2 && (mesh_dims[0] <= 0 || mesh_dims[1] <= 0 || mesh_dims[2] <= 0)) {
107 printf("Size of 3-D mesh improperly specified, %dx%dx%d.\n",
108 mesh_dims[0], mesh_dims[1], mesh_dims[2]);
109 flag = TRUE;
110 }
111 }
112
113 if (ndims < 1 || ndims > MAXDIMS) {
114 printf("Partitioning at each step = %d, should be in [1,%d].\n",
115 ndims, MAXDIMS);
116 flag = TRUE;
117 }
118
119 if (architecture == 0)
120 nprocs = 1 << ndims_tot;
121 else if (architecture > 0)
122 nprocs = mesh_dims[0] * mesh_dims[1] * mesh_dims[2];
123 if (1 << ndims > nprocs) {
124 printf("Partitioning step %d too large for %d processors.\n",
125 ndims, nprocs);
126 flag = TRUE;
127 }
128
129 if (global_method < 1 || global_method > 7) {
130 printf("Global partitioning method = %d, must be in [1,7].\n", global_method);
131 flag = TRUE;
132 }
133
134 if (local_method < 1 || local_method > 2) {
135 printf("Local partitioning method = %d, must be in [1,2].\n", local_method);
136 flag = TRUE;
137 }
138
139 if (global_method == 1 || (global_method == 2 && rqi_flag)) {
140 i = 2 * (1 << ndims);
141 if (*vmax < i) {
142 printf("WARNING: Number of vertices in coarse graph (%d) being reset to %d.\n",
143 *vmax, i);
144 if (Output_File != NULL) {
145 fprintf(Output_File,
146 "WARNING: Number of vertices in coarse graph (%d) being reset to %d.\n",
147 *vmax, i);
148 }
149 *vmax = i;
150 }
151 }
152
153 if ((global_method == 1 || global_method == 2) && eigtol <= 0) {
154 printf("Eigen tolerance (%g) must be positive value\n", eigtol);
155 flag = TRUE;
156 }
157
158 if (global_method == 3 ||
159 (MATCH_TYPE == 5 && (global_method == 1 ||
160 (global_method == 2 && rqi_flag)))) {
161 if (igeom < 1 || igeom > 3) {
162 printf("Geometry must be 1-, 2- or 3-dimensional\n");
163 flag = TRUE;
164 }
165 if (igeom > 0 && coords == NULL) {
166 printf("No coordinates given\n");
167 flag = FALSE;
168 }
169 else if (igeom > 0 && coords[0] == NULL) {
170 printf("No X-coordinates given\n");
171 flag = TRUE;
172 }
173 else if (igeom > 1 && coords[1] == NULL) {
174 printf("No Y-coordinates given\n");
175 flag = TRUE;
176 }
177 else if (igeom > 2 && coords[2] == NULL) {
178 printf("No Z-coordinates given\n");
179 flag = TRUE;
180 }
181 }
182
183 if (global_method == 7 && local_method == 1) {
184 if (nprocs > 1<<ndims) {
185 printf("Can only use local method on single level of read-in assignment,\n");
186 printf(" but ndims = %d, while number of processors = %d.\n",
187 ndims, nprocs);
188 flag = TRUE;
189 }
190 }
191
192 /* Now check for consistency in the goal array. */
193 if (graph != NULL) {
194 vwgt_sum = 0;
195 for (i = 1; i <= nvtxs; i++) {
196 vwgt_sum += graph[i]->vwgt;
197 }
198 }
199 else {
200 vwgt_sum = nvtxs;
201 }
202
203 vwgt_sum2 = 0;
204 for (i = 0; i < nprocs; i++) {
205 if (goal[i] < 0) {
206 printf("goal[%d] is %g, but should be nonnegative.\n", i, goal[i]);
207 flag = TRUE;
208 }
209 vwgt_sum2 += goal[i];
210 }
211
212 if (fabs(vwgt_sum - vwgt_sum2) > 1e-5 * (vwgt_sum + vwgt_sum2)) {
213 printf("Sum of values in goal (%g) not equal to sum of vertex weights (%g).\n",
214 vwgt_sum2, vwgt_sum);
215 flag = TRUE;
216 }
217
218 /* Check assignment file if read in. */
219 if (global_method == 7 && !flag) {
220 flag_assign = check_assignment(assignment, nvtxs, nprocs, ndims, local_method);
221 }
222
223 /* Add some checks for model parameters */
224
225 /* Finally, check the parameters. */
226 flag_params = check_params(global_method, local_method, rqi_flag, ndims);
227
228 flag = flag || flag_graph || flag_assign || flag_params;
229
230 return (flag);
231 }
232
233
234
235
236
check_params(global_method,local_method,rqi_flag,ndims)237 static int check_params(global_method, local_method, rqi_flag, ndims)
238 int global_method; /* global partitioning algorithm */
239 int local_method; /* local partitioning algorithm */
240 int rqi_flag; /* use multilevel eigensolver? */
241 int ndims; /* number of eigenvectors */
242 {
243 extern FILE *Output_File; /* Output file or null */
244 extern int ECHO; /* print input/param options? to file? (-2..2) */
245 extern int EXPERT; /* is user an expert? */
246 extern int OUTPUT_METRICS; /* controls formatting of output */
247 extern int OUTPUT_TIME; /* at what level to display timing */
248
249 extern int LANCZOS_TYPE; /* type of Lanczos to use */
250 extern double EIGEN_TOLERANCE; /* eigen-tolerance convergence criteria */
251 extern int LANCZOS_SO_INTERVAL; /* interval between orthog checks in SO */
252 extern double BISECTION_SAFETY; /* divides Lanczos bisection tol */
253 extern int LANCZOS_CONVERGENCE_MODE;/* Lanczos convergence test type */
254 extern int RQI_CONVERGENCE_MODE; /* rqi convergence test type: */
255 extern double WARNING_ORTHTOL; /* warn if Ares/bjitol this big */
256 extern double WARNING_MISTOL; /* warn if Ares/bjitol this big */
257 extern int LANCZOS_SO_PRECISION; /* single or double precision? */
258
259 extern int PERTURB; /* randomly perturb matrix in spectral method? */
260 extern int NPERTURB; /* if so, how many edges to modify? */
261 extern double PERTURB_MAX; /* largest value for perturbation */
262 extern int MAPPING_TYPE; /* how to map from eigenvectors to partition */
263 extern int COARSE_NLEVEL_RQI; /* levels between RQI calls */
264 extern int OPT3D_NTRIES; /* # local opts to look for global min in opt3d */
265
266 extern int KL_METRIC; /* KL interset cost: 1=>cuts, 2=>hops */
267 extern int KL_BAD_MOVES; /* number of unhelpful moves in a row allowed */
268 extern int KL_NTRIES_BAD; /* # unhelpful passes before quitting KL */
269 extern double KL_IMBALANCE; /* allowed imbalance in KL */
270
271 extern double COARSEN_RATIO_MIN; /* required coarsening reduction */
272 extern int COARSE_NLEVEL_KL;/* # levels between KL calls in uncoarsening */
273 extern int MATCH_TYPE; /* which type of contraction matching to use? */
274
275 extern int SIMULATOR; /* simulate the communication? */
276
277 extern int TERM_PROP; /* perform terminal propagation? */
278 extern double CUT_TO_HOP_COST; /* ..if so, relativ cut/hop importance */
279 int flag_params;
280
281 flag_params = FALSE;
282 if (ECHO < -2 || ECHO > 2) {
283 printf("ECHO (%d) should be in [-2,2].\n", ECHO);
284 flag_params = TRUE;
285 }
286
287 if (OUTPUT_METRICS < -2 || OUTPUT_METRICS > 2) {
288 printf("WARNING: OUTPUT_METRICS (%d) should be in [-2,2].\n", OUTPUT_METRICS);
289 if (Output_File != NULL) {
290 fprintf(Output_File,
291 "WARNING: OUTPUT_METRICS (%d) should be in [-2,2].\n", OUTPUT_METRICS);
292 }
293 }
294 if (OUTPUT_TIME < 0 || OUTPUT_TIME > 2) {
295 printf("WARNING: OUTPUT_TIME (%d) should be in [0,2].\n", OUTPUT_TIME);
296 if (Output_File != NULL) {
297 fprintf(Output_File,
298 "WARNING: OUTPUT_TIME (%d) should be in [0,2].\n", OUTPUT_TIME);
299 }
300 }
301
302 if (global_method == 1 || global_method == 2) {
303 if (EXPERT) {
304 if (LANCZOS_TYPE < 1 || LANCZOS_TYPE > 4) {
305 printf("LANCZOS_TYPE (%d) should be in [1,4].\n", LANCZOS_TYPE);
306 flag_params = TRUE;
307 }
308 }
309 else {
310 if (LANCZOS_TYPE < 1 || LANCZOS_TYPE > 3) {
311 printf("LANCZOS_TYPE (%d) should be in [1,3].\n", LANCZOS_TYPE);
312 flag_params = TRUE;
313 }
314 }
315 if (EIGEN_TOLERANCE <= 0) {
316 printf("EIGEN_TOLERANCE (%g) should be positive.\n", EIGEN_TOLERANCE);
317 flag_params = TRUE;
318 }
319 if (LANCZOS_SO_INTERVAL <= 0) {
320 printf("LANCZOS_SO_INTERVAL (%d) should be positive.\n",
321 LANCZOS_SO_INTERVAL);
322 flag_params = TRUE;
323 }
324 if (LANCZOS_SO_INTERVAL == 1) {
325 printf("WARNING: More efficient if LANCZOS_SO_INTERVAL = 2, not 1.\n");
326 if (Output_File != NULL) {
327 fprintf(Output_File,
328 "WARNING: More efficient if LANCZOS_SO_INTERVAL = 2, not 1.\n");
329 }
330 }
331 if (BISECTION_SAFETY <= 0) {
332 printf("BISECTION_SAFETY (%g) should be positive.\n", BISECTION_SAFETY);
333 flag_params = TRUE;
334 }
335 if (LANCZOS_CONVERGENCE_MODE < 0 || LANCZOS_CONVERGENCE_MODE > 1) {
336 printf("LANCZOS_CONVERGENCE_MODE (%d) should be in [0,1].\n",
337 LANCZOS_CONVERGENCE_MODE);
338 flag_params = TRUE;
339 }
340
341 if (WARNING_ORTHTOL == 0) {
342 printf("WARNING: WARNING_ORTHTOL (%g) should be positive.\n",
343 WARNING_ORTHTOL);
344 if (Output_File != NULL) {
345 fprintf(Output_File,
346 "WARNING: WARNING_ORTHTOL (%g) should be positive.\n",
347 WARNING_ORTHTOL);
348 }
349 }
350 if (WARNING_MISTOL == 0) {
351 printf("WARNING: WARNING_MISTOL (%g) should be positive.\n",
352 WARNING_MISTOL);
353 if (Output_File != NULL) {
354 fprintf(Output_File,
355 "WARNING: WARNING_MISTOL (%g) should be positive.\n",
356 WARNING_MISTOL);
357 }
358 }
359
360 if (LANCZOS_SO_PRECISION < 1 || LANCZOS_SO_PRECISION > 2) {
361 printf("LANCZOS_SO_PRECISION (%d) should be in [1,2].\n",
362 LANCZOS_SO_PRECISION);
363 flag_params = TRUE;
364 }
365
366 if (PERTURB) {
367 if (NPERTURB < 0) {
368 printf("NPERTURB (%d) should be nonnegative.\n", NPERTURB);
369 flag_params = TRUE;
370 }
371 if (NPERTURB > 0 && PERTURB_MAX < 0) {
372 printf("PERTURB_MAX (%g) should be nonnegative.\n", PERTURB_MAX);
373 flag_params = TRUE;
374 }
375 }
376
377 if (MAPPING_TYPE < 0 || MAPPING_TYPE > 3) {
378 printf("MAPPING_TYPE (%d) should be in [0,3].\n", MAPPING_TYPE);
379 flag_params = TRUE;
380 }
381
382 if (ndims == 3 && OPT3D_NTRIES <= 0) {
383 printf("OPT3D_NTRIES (%d) should be positive.\n", OPT3D_NTRIES);
384 flag_params = TRUE;
385 }
386
387 if (global_method == 2 && rqi_flag) {
388 if (COARSE_NLEVEL_RQI <= 0) {
389 printf("COARSE_NLEVEL_RQI (%d) should be positive.\n",
390 COARSE_NLEVEL_RQI);
391 flag_params = TRUE;
392 }
393
394 if (RQI_CONVERGENCE_MODE < 0 || RQI_CONVERGENCE_MODE > 1) {
395 printf("RQI_CONVERGENCE_MODE (%d) should be in [0,1].\n",
396 RQI_CONVERGENCE_MODE);
397 flag_params = TRUE;
398 }
399
400 if (TERM_PROP) {
401 printf("WARNING: Using default Lanczos for extended eigenproblem, not RQI/Symmlq.\n");
402 }
403 }
404
405 if (global_method == 1) {
406 if (COARSE_NLEVEL_KL <= 0) {
407 printf("COARSE_NLEVEL_KL (%d) should be positive.\n",
408 COARSE_NLEVEL_KL);
409 flag_params = TRUE;
410 }
411 }
412
413 if (global_method == 1 || (global_method == 2 && rqi_flag)) {
414 if (COARSEN_RATIO_MIN < .5) {
415 printf("COARSEN_RATIO_MIN (%g) should be at least 1/2.\n",
416 COARSEN_RATIO_MIN);
417 flag_params = TRUE;
418 }
419 if (MATCH_TYPE < 1 || MATCH_TYPE > 5) {
420 printf("MATCH_TYPE (%d) should be in [1,4].\n", MATCH_TYPE);
421 flag_params = TRUE;
422 }
423 }
424
425 /*
426 if (global_method == 1 && LIMIT_KL_EWGTS && EWGT_RATIO_MAX <= 0) {
427 printf("EWGT_RATIO_MAX (%g) should be at positive.\n",
428 EWGT_RATIO_MAX);
429 flag_params = TRUE;
430 }
431 */
432 }
433
434 if (global_method == 1 || local_method == 1) {
435 if (KL_METRIC < 1 || KL_METRIC > 2) {
436 printf("KL_METRIC (%d) should be in [0,1].\n", KL_METRIC);
437 flag_params = TRUE;
438 }
439 if (KL_BAD_MOVES < 0) {
440 printf("KL_BAD_MOVES (%d) should be non-negative.\n", KL_BAD_MOVES);
441 flag_params = TRUE;
442 }
443 if (KL_NTRIES_BAD < 0) {
444 printf("KL_NTRIES_BAD (%d) should be non-negative.\n", KL_NTRIES_BAD);
445 flag_params = TRUE;
446 }
447 if (KL_IMBALANCE < 0.0 || KL_IMBALANCE > 1.0) {
448 printf("KL_IMBALANCE (%g) should be in [0,1].\n", KL_IMBALANCE);
449 flag_params = TRUE;
450 }
451 }
452
453 if (SIMULATOR < 0 || SIMULATOR > 3) {
454 printf("SIMULATOR (%d) should be in [0,3].\n", SIMULATOR);
455 flag_params = TRUE;
456 }
457
458 if (TERM_PROP) {
459 if (CUT_TO_HOP_COST <= 0) {
460 printf("CUT_TO_HOP_COST (%g) should be positive.\n", CUT_TO_HOP_COST);
461 flag_params = TRUE;
462 }
463 if (ndims > 1) {
464 printf("WARNING: May ignore terminal propagation in spectral quadri/octa section\n");
465 }
466 }
467
468 return (flag_params);
469 }
470
471
check_assignment(assignment,nvtxs,nsets_tot,ndims,local_method)472 static int check_assignment(assignment, nvtxs, nsets_tot, ndims, local_method)
473 short *assignment; /* set numbers if read-from-file */
474 int nvtxs; /* number of vertices */
475 int nsets_tot; /* total number of desired sets */
476 {
477 int flag; /* return status */
478 int nsets; /* number of sets created at each level */
479 int i; /* loop counter */
480
481 nsets = 1<< ndims;
482 flag = FALSE;
483
484 for (i=1; i<=nvtxs && !flag; i++) {
485 if (assignment[i] < 0) {
486 printf("Assignment[%d] = %d less than zero.\n", i, assignment[i]);
487 flag = TRUE;
488 }
489 else if (assignment[i] >= nsets_tot) {
490 printf("Assignment[%d] = %d, too large for %d sets.\n",
491 i, assignment[i], nsets_tot);
492 flag = TRUE;
493 }
494 else if (local_method == 1 && assignment[i] >= nsets) {
495 printf("Can only use local method on single level of read-in assignment,\n");
496 printf(" but assignment[%d] = %d.\n", i, assignment[i]);
497 flag = TRUE;
498 }
499 }
500
501 return(flag);
502 }
503