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 "defs.h"
7 #include "structs.h"
8
9 /* Print metrics of partition quality. */
10
countup_cube(graph,nvtxs,assignment,ndims,ndims_tot,print_lev,outfile,using_ewgts)11 void countup_cube(graph, nvtxs, assignment, ndims, ndims_tot, print_lev,
12 outfile, using_ewgts)
13 struct vtx_data **graph; /* graph data structure */
14 int nvtxs; /* number of vtxs in graph */
15 short *assignment; /* set number of each vtx (length nvtxs+1) */
16 int ndims; /* number of cuts at each level */
17 int ndims_tot; /* total number of divisions of graph */
18 int print_lev; /* level of output */
19 FILE *outfile; /* output file if not NULL */
20 int using_ewgts; /* are edge weights being used? */
21 {
22 double *hopsize; /* number of hops for each set */
23 double *cutsize; /* number of cuts for each set */
24 int *setsize; /* number of vtxs in each set */
25 int *setseen; /* flags for sets adjacent to a particular set */
26 int *inorder; /* list of vtxs in each set */
27 int *startptr; /* indices into inorder array */
28 double ncuts; /* total number of edges connecting sets */
29 double nhops; /* total cuts weighted by hypercube hops */
30 double ewgt; /* edge weight */
31 int nsets; /* number of sets after a level */
32 int vtx; /* vertex in graph */
33 int set, set2, set3; /* sets neighboring vtxs are assigned to */
34 int onbdy; /* counts number of neighboring set for a vtx */
35 int bdyvtxs; /* sum of onbdy values for a set */
36 int internal; /* number of internal nodes in a set */
37 int min_internal; /* smallest number of internal vertices */
38 int max_internal; /* largest number of internal vertices */
39 int total_internal; /* total number of internal vertices */
40 int min_size, max_size; /* smallest and largest set sizes */
41 int tot_size; /* total of all set sizes */
42 double bdyvtx_hops; /* bdyvtxs weighted by wire lengths */
43 double bdyvtx_hops_tot; /* total bdyvtx_hops */
44 double bdyvtx_hops_max; /* largest value of bdyvtx_hops among all sets */
45 double bdyvtx_hops_min; /* smallest value of bdyvtx_hops among all sets */
46 int neighbor_sets; /* number of neighboring sets for a set */
47 double total_bdyvtxs; /* sum of all onbdy values in whole graph */
48 int total_neighbors; /* number of neighboring sets in graph */
49 double maxcuts; /* largest cuts among all processors */
50 double mincuts; /* smallest cuts among all processors */
51 double maxhops; /* largest hops among all processors */
52 double minhops; /* smallest hops among all processors */
53 double maxbdy; /* largest bdy_vtxs among all processors */
54 double minbdy; /* smallest bdy_vtxs among all processors */
55 int maxneighbors; /* largest neighbor_sets among all processors */
56 int minneighbors; /* smallest neighbor_sets among all processors */
57 int neighbor; /* neighbor of a vertex */
58 int mask; /* mask for active bits */
59 int bits; /* bit pattern for counting hops */
60 int start_dims; /* starting dimension for output loop */
61 int level; /* recursion level of partition */
62 int print2file; /* should I print to a file? */
63 int i, j, k, l, ll; /* loop counters */
64 double *smalloc();
65 int abs(), sfree();
66
67 print2file = (outfile != NULL);
68 ewgt = 1;
69
70 nsets = (1 << ndims_tot);
71 cutsize = (double *) smalloc((unsigned) nsets * sizeof(double));
72 hopsize = (double *) smalloc((unsigned) nsets * sizeof(double));
73 setsize = (int *) smalloc((unsigned) nsets * sizeof(int));
74
75 setseen = (int *) smalloc((unsigned) nsets * sizeof(int));
76 startptr = (int *) smalloc((unsigned) (nsets + 1) * sizeof(int));
77 inorder = (int *) smalloc((unsigned) nvtxs * sizeof(int));
78 for (j = 0; j < nsets; j++)
79 setsize[j] = 0;
80 for (i = 1; i <= nvtxs; i++)
81 ++setsize[assignment[i]];
82
83 /* Modify setsize to become index into vertex list. */
84 for (j = 1; j < nsets; j++)
85 setsize[j] += setsize[j - 1];
86 for (j = nsets - 1; j > 0; j--)
87 startptr[j] = setsize[j] = setsize[j - 1];
88 startptr[0] = setsize[0] = 0;
89 startptr[nsets] = nvtxs;
90 for (i = 1; i <= nvtxs; i++) {
91 set = assignment[i];
92 inorder[setsize[set]] = i;
93 setsize[set]++;
94 }
95
96 if (abs(print_lev) > 1) { /* Print data from all levels of recursion. */
97 start_dims = ndims;
98 level = 0;
99 }
100 else { /* Only print data from final level. */
101 start_dims = ndims_tot;
102 level = (ndims_tot + ndims - 1) / ndims - 1;
103 }
104 k = start_dims;
105 while (k <= ndims_tot) {
106 level++;
107 nsets = (1 << k);
108 for (j = 0; j < nsets; j++) {
109 cutsize[j] = 0;
110 hopsize[j] = 0;
111 setsize[j] = 0;
112 }
113 mask = 0;
114 for (j = 0; j < k; j++)
115 mask = (mask << 1) + 1;
116
117 for (i = 1; i <= nvtxs; i++) {
118 set = assignment[i] & mask;
119 setsize[set] += graph[i]->vwgt;
120 for (j = 1; j < graph[i]->nedges; j++) {
121 neighbor = graph[i]->edges[j];
122 set2 = assignment[neighbor] & mask;
123 if (set != set2) {
124 if (using_ewgts)
125 ewgt = graph[i]->ewgts[j];
126 cutsize[set] += ewgt;
127 bits = set ^ set2;
128 for (l = bits; l; l >>= 1)
129 if (l & 1)
130 hopsize[set] += ewgt;
131 }
132 }
133 }
134
135 tot_size = 0;
136 max_size = 0;
137 for (set = 0; set < nsets; set++) {
138 tot_size += setsize[set];
139 if (setsize[set] > max_size)
140 max_size = setsize[set];
141 }
142
143 min_size = max_size;
144 for (set = 0; set < nsets; set++) {
145 if (setsize[set] < min_size)
146 min_size = setsize[set];
147 }
148
149 ncuts = nhops = 0;
150 total_bdyvtxs = total_neighbors = 0;
151 bdyvtx_hops_tot = bdyvtx_hops_max = bdyvtx_hops_min = 0;
152 maxcuts = mincuts = 0;
153 maxhops = minhops = 0;
154 total_internal = 0;
155 min_internal = max_size;
156 max_internal = 0;
157 maxbdy = minbdy = 0;
158 maxneighbors = minneighbors = 0;
159
160 printf("\nAfter level %d (nsets = %d):\n", level, nsets);
161 if (print2file)
162 fprintf(outfile, "\nAfter level %d (nsets = %d):\n", level, nsets);
163 if (print_lev < 0) {
164 printf(" set size cuts hops bndy_vtxs adj_sets\n");
165 if (print2file)
166 fprintf(outfile, " set size cuts hops bndy_vtxs adj_sets\n");
167 }
168 for (set = 0; set < nsets; set++) {
169 internal = setsize[set];
170 for (i = 0; i < nsets; i++)
171 setseen[i] = 0;
172 /* Compute number of set neighbors, and number of vtxs on boundary. */
173 /* Loop through multiple assignments defining current set. */
174 bdyvtxs = 0;
175 bdyvtx_hops = 0;
176 for (l = 0; l < (1 << (ndims_tot - k)); l++) {
177 set2 = (l << k) + set;
178 for (i = startptr[set2]; i < startptr[set2 + 1]; i++) {
179 onbdy = 0;
180 vtx = inorder[i];
181 for (j = 1; j < graph[vtx]->nedges; j++) {
182 neighbor = graph[vtx]->edges[j];
183 set3 = assignment[neighbor] & mask;
184 if (set3 != set) { /* Is vtx on boundary? */
185 /* Has this neighboring set been seen already? */
186 if (setseen[set3] >= 0) {
187 bits = set ^ set3;
188 for (ll = bits; ll; ll >>= 1)
189 if (ll & 1)
190 ++bdyvtx_hops;
191 ++onbdy;
192 setseen[set3] = -setseen[set3] - 1;
193 }
194 }
195 }
196 /* Now reset all the setseen values to be positive. */
197 if (onbdy != 0) {
198 for (j = 1; j < graph[vtx]->nedges; j++) {
199 neighbor = graph[vtx]->edges[j];
200 set3 = assignment[neighbor] & mask;
201 if (setseen[set3] < 0)
202 setseen[set3] = -setseen[set3];
203 }
204 internal -= graph[vtx]->vwgt;
205 }
206 bdyvtxs += onbdy;
207 }
208 }
209
210 total_internal += internal;
211 bdyvtx_hops_tot += bdyvtx_hops;
212 if (bdyvtx_hops > bdyvtx_hops_max)
213 bdyvtx_hops_max = bdyvtx_hops;
214 if (set == 0 || bdyvtx_hops < bdyvtx_hops_min)
215 bdyvtx_hops_min = bdyvtx_hops;
216 if (internal > max_internal)
217 max_internal = internal;
218 if (set == 0 || internal < min_internal)
219 min_internal = internal;
220
221 /* Now count up the number of neighboring sets. */
222 neighbor_sets = 0;
223 for (i = 0; i < nsets; i++) {
224 if (setseen[i] != 0)
225 ++neighbor_sets;
226 }
227
228 if (print_lev < 0) {
229 printf(" %5d %5d %6g %6g %6d %6d\n",
230 set, setsize[set], cutsize[set], hopsize[set],
231 bdyvtxs, neighbor_sets);
232 if (print2file)
233 fprintf(outfile, " %5d %5d %6g %6g %6d %6d\n",
234 set, setsize[set], cutsize[set], hopsize[set],
235 bdyvtxs, neighbor_sets);
236 }
237 if (cutsize[set] > maxcuts)
238 maxcuts = cutsize[set];
239 if (set == 0 || cutsize[set] < mincuts) {
240 mincuts = cutsize[set];
241 }
242 if (hopsize[set] > maxhops)
243 maxhops = hopsize[set];
244 if (set == 0 || hopsize[set] < minhops) {
245 minhops = hopsize[set];
246 }
247 if (bdyvtxs > maxbdy)
248 maxbdy = bdyvtxs;
249 if (set == 0 || bdyvtxs < minbdy) {
250 minbdy = bdyvtxs;
251 }
252 if (neighbor_sets > maxneighbors)
253 maxneighbors = neighbor_sets;
254 if (set == 0 || neighbor_sets < minneighbors)
255 minneighbors = neighbor_sets;
256 ncuts += cutsize[set];
257 nhops += hopsize[set];
258 total_bdyvtxs += bdyvtxs;
259 total_neighbors += neighbor_sets;
260 }
261 ncuts /= 2;
262 nhops /= 2;
263
264 printf("\n");
265 printf(" Total Max/Set Min/Set\n");
266 printf(" ----- ------- -------\n");
267 printf("Set Size: %11d %11d %11d\n",
268 tot_size, max_size, min_size);
269 printf("Edge Cuts: %11g %11g %11g\n",
270 ncuts, maxcuts, mincuts);
271 printf("Hypercube Hops: %11g %11g %11g\n",
272 nhops, maxhops, minhops);
273 printf("Boundary Vertices: %11g %11g %11g\n",
274 total_bdyvtxs, maxbdy, minbdy);
275 printf("Boundary Vertex Hops: %11g %11g %11g\n",
276 bdyvtx_hops_tot, bdyvtx_hops_max, bdyvtx_hops_min);
277 printf("Adjacent Sets: %11d %11d %11d\n",
278 total_neighbors, maxneighbors, minneighbors);
279 printf("Internal Vertices: %11d %11d %11d\n\n",
280 total_internal, max_internal, min_internal);
281
282 if (print2file) {
283 fprintf(outfile, "\n");
284 fprintf(outfile, " Total Max/Set Min/Set\n");
285 fprintf(outfile, " ----- ------- -------\n");
286 fprintf(outfile, "Set Size: %11d %11d %11d\n",
287 tot_size, max_size, min_size);
288 fprintf(outfile, "Edge Cuts: %11g %11g %11g\n",
289 ncuts, maxcuts, mincuts);
290 fprintf(outfile, "Hypercube Hops: %11g %11g %11g\n",
291 nhops, maxhops, minhops);
292 fprintf(outfile, "Boundary Vertices: %11g %11g %11g\n",
293 total_bdyvtxs, maxbdy, minbdy);
294 fprintf(outfile, "Boundary Vertex Hops: %11g %11g %11g\n",
295 bdyvtx_hops_tot, bdyvtx_hops_max, bdyvtx_hops_min);
296 fprintf(outfile, "Adjacent Sets: %11d %11d %11d\n",
297 total_neighbors, maxneighbors, minneighbors);
298 fprintf(outfile, "Internal Vertices: %11d %11d %11d\n\n",
299 total_internal, max_internal, min_internal);
300 }
301
302 if (k == ndims_tot)
303 k++;
304 else {
305 k += ndims;
306 if (k > ndims_tot)
307 k = ndims_tot;
308 }
309 }
310
311 sfree((char *) cutsize);
312 sfree((char *) hopsize);
313 sfree((char *) setsize);
314 sfree((char *) setseen);
315 sfree((char *) startptr);
316 sfree((char *) inorder);
317 }
318