/* This software was developed by Bruce Hendrickson and Robert Leland *
* at Sandia National Laboratories under US Department of Energy *
* contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
#include <stdio.h>
#include "defs.h"
#include "structs.h"
/* Print metrics of partition quality. */
void countup_cube(graph, nvtxs, assignment, ndims, ndims_tot, print_lev,
outfile, using_ewgts)
struct vtx_data **graph; /* graph data structure */
int nvtxs; /* number of vtxs in graph */
short *assignment; /* set number of each vtx (length nvtxs+1) */
int ndims; /* number of cuts at each level */
int ndims_tot; /* total number of divisions of graph */
int print_lev; /* level of output */
FILE *outfile; /* output file if not NULL */
int using_ewgts; /* are edge weights being used? */
{
double *hopsize; /* number of hops for each set */
double *cutsize; /* number of cuts for each set */
int *setsize; /* number of vtxs in each set */
int *setseen; /* flags for sets adjacent to a particular set */
int *inorder; /* list of vtxs in each set */
int *startptr; /* indices into inorder array */
double ncuts; /* total number of edges connecting sets */
double nhops; /* total cuts weighted by hypercube hops */
double ewgt; /* edge weight */
int nsets; /* number of sets after a level */
int vtx; /* vertex in graph */
int set, set2, set3; /* sets neighboring vtxs are assigned to */
int onbdy; /* counts number of neighboring set for a vtx */
int bdyvtxs; /* sum of onbdy values for a set */
int internal; /* number of internal nodes in a set */
int min_internal; /* smallest number of internal vertices */
int max_internal; /* largest number of internal vertices */
int total_internal; /* total number of internal vertices */
int min_size, max_size; /* smallest and largest set sizes */
int tot_size; /* total of all set sizes */
double bdyvtx_hops; /* bdyvtxs weighted by wire lengths */
double bdyvtx_hops_tot; /* total bdyvtx_hops */
double bdyvtx_hops_max; /* largest value of bdyvtx_hops among all sets */
double bdyvtx_hops_min; /* smallest value of bdyvtx_hops among all sets */
int neighbor_sets; /* number of neighboring sets for a set */
double total_bdyvtxs; /* sum of all onbdy values in whole graph */
int total_neighbors; /* number of neighboring sets in graph */
double maxcuts; /* largest cuts among all processors */
double mincuts; /* smallest cuts among all processors */
double maxhops; /* largest hops among all processors */
double minhops; /* smallest hops among all processors */
double maxbdy; /* largest bdy_vtxs among all processors */
double minbdy; /* smallest bdy_vtxs among all processors */
int maxneighbors; /* largest neighbor_sets among all processors */
int minneighbors; /* smallest neighbor_sets among all processors */
int neighbor; /* neighbor of a vertex */
int mask; /* mask for active bits */
int bits; /* bit pattern for counting hops */
int start_dims; /* starting dimension for output loop */
int level; /* recursion level of partition */
int print2file; /* should I print to a file? */
int i, j, k, l, ll; /* loop counters */
double *smalloc();
int abs(), sfree();
print2file = (outfile != NULL);
ewgt = 1;
nsets = (1 << ndims_tot);
cutsize = (double *) smalloc((unsigned) nsets * sizeof(double));
hopsize = (double *) smalloc((unsigned) nsets * sizeof(double));
setsize = (int *) smalloc((unsigned) nsets * sizeof(int));
setseen = (int *) smalloc((unsigned) nsets * sizeof(int));
startptr = (int *) smalloc((unsigned) (nsets + 1) * sizeof(int));
inorder = (int *) smalloc((unsigned) nvtxs * sizeof(int));
for (j = 0; j < nsets; j++)
setsize[j] = 0;
for (i = 1; i <= nvtxs; i++)
++setsize[assignment[i]];
/* Modify setsize to become index into vertex list. */
for (j = 1; j < nsets; j++)
setsize[j] += setsize[j - 1];
for (j = nsets - 1; j > 0; j--)
startptr[j] = setsize[j] = setsize[j - 1];
startptr[0] = setsize[0] = 0;
startptr[nsets] = nvtxs;
for (i = 1; i <= nvtxs; i++) {
set = assignment[i];
inorder[setsize[set]] = i;
setsize[set]++;
}
if (abs(print_lev) > 1) { /* Print data from all levels of recursion. */
start_dims = ndims;
level = 0;
}
else { /* Only print data from final level. */
start_dims = ndims_tot;
level = (ndims_tot + ndims - 1) / ndims - 1;
}
k = start_dims;
while (k <= ndims_tot) {
level++;
nsets = (1 << k);
for (j = 0; j < nsets; j++) {
cutsize[j] = 0;
hopsize[j] = 0;
setsize[j] = 0;
}
mask = 0;
for (j = 0; j < k; j++)
mask = (mask << 1) + 1;
for (i = 1; i <= nvtxs; i++) {
set = assignment[i] & mask;
setsize[set] += graph[i]->vwgt;
for (j = 1; j < graph[i]->nedges; j++) {
neighbor = graph[i]->edges[j];
set2 = assignment[neighbor] & mask;
if (set != set2) {
if (using_ewgts)
ewgt = graph[i]->ewgts[j];
cutsize[set] += ewgt;
bits = set ^ set2;
for (l = bits; l; l >>= 1)
if (l & 1)
hopsize[set] += ewgt;
}
}
}
tot_size = 0;
max_size = 0;
for (set = 0; set < nsets; set++) {
tot_size += setsize[set];
if (setsize[set] > max_size)
max_size = setsize[set];
}
min_size = max_size;
for (set = 0; set < nsets; set++) {
if (setsize[set] < min_size)
min_size = setsize[set];
}
ncuts = nhops = 0;
total_bdyvtxs = total_neighbors = 0;
bdyvtx_hops_tot = bdyvtx_hops_max = bdyvtx_hops_min = 0;
maxcuts = mincuts = 0;
maxhops = minhops = 0;
total_internal = 0;
min_internal = max_size;
max_internal = 0;
maxbdy = minbdy = 0;
maxneighbors = minneighbors = 0;
printf("\nAfter level %d (nsets = %d):\n", level, nsets);
if (print2file)
fprintf(outfile, "\nAfter level %d (nsets = %d):\n", level, nsets);
if (print_lev < 0) {
printf(" set size cuts hops bndy_vtxs adj_sets\n");
if (print2file)
fprintf(outfile, " set size cuts hops bndy_vtxs adj_sets\n");
}
for (set = 0; set < nsets; set++) {
internal = setsize[set];
for (i = 0; i < nsets; i++)
setseen[i] = 0;
/* Compute number of set neighbors, and number of vtxs on boundary. */
/* Loop through multiple assignments defining current set. */
bdyvtxs = 0;
bdyvtx_hops = 0;
for (l = 0; l < (1 << (ndims_tot - k)); l++) {
set2 = (l << k) + set;
for (i = startptr[set2]; i < startptr[set2 + 1]; i++) {
onbdy = 0;
vtx = inorder[i];
for (j = 1; j < graph[vtx]->nedges; j++) {
neighbor = graph[vtx]->edges[j];
set3 = assignment[neighbor] & mask;
if (set3 != set) { /* Is vtx on boundary? */
/* Has this neighboring set been seen already? */
if (setseen[set3] >= 0) {
bits = set ^ set3;
for (ll = bits; ll; ll >>= 1)
if (ll & 1)
++bdyvtx_hops;
++onbdy;
setseen[set3] = -setseen[set3] - 1;
}
}
}
/* Now reset all the setseen values to be positive. */
if (onbdy != 0) {
for (j = 1; j < graph[vtx]->nedges; j++) {
neighbor = graph[vtx]->edges[j];
set3 = assignment[neighbor] & mask;
if (setseen[set3] < 0)
setseen[set3] = -setseen[set3];
}
internal -= graph[vtx]->vwgt;
}
bdyvtxs += onbdy;
}
}
total_internal += internal;
bdyvtx_hops_tot += bdyvtx_hops;
if (bdyvtx_hops > bdyvtx_hops_max)
bdyvtx_hops_max = bdyvtx_hops;
if (set == 0 || bdyvtx_hops < bdyvtx_hops_min)
bdyvtx_hops_min = bdyvtx_hops;
if (internal > max_internal)
max_internal = internal;
if (set == 0 || internal < min_internal)
min_internal = internal;
/* Now count up the number of neighboring sets. */
neighbor_sets = 0;
for (i = 0; i < nsets; i++) {
if (setseen[i] != 0)
++neighbor_sets;
}
if (print_lev < 0) {
printf(" %5d %5d %6g %6g %6d %6d\n",
set, setsize[set], cutsize[set], hopsize[set],
bdyvtxs, neighbor_sets);
if (print2file)
fprintf(outfile, " %5d %5d %6g %6g %6d %6d\n",
set, setsize[set], cutsize[set], hopsize[set],
bdyvtxs, neighbor_sets);
}
if (cutsize[set] > maxcuts)
maxcuts = cutsize[set];
if (set == 0 || cutsize[set] < mincuts) {
mincuts = cutsize[set];
}
if (hopsize[set] > maxhops)
maxhops = hopsize[set];
if (set == 0 || hopsize[set] < minhops) {
minhops = hopsize[set];
}
if (bdyvtxs > maxbdy)
maxbdy = bdyvtxs;
if (set == 0 || bdyvtxs < minbdy) {
minbdy = bdyvtxs;
}
if (neighbor_sets > maxneighbors)
maxneighbors = neighbor_sets;
if (set == 0 || neighbor_sets < minneighbors)
minneighbors = neighbor_sets;
ncuts += cutsize[set];
nhops += hopsize[set];
total_bdyvtxs += bdyvtxs;
total_neighbors += neighbor_sets;
}
ncuts /= 2;
nhops /= 2;
printf("\n");
printf(" Total Max/Set Min/Set\n");
printf(" ----- ------- -------\n");
printf("Set Size: %11d %11d %11d\n",
tot_size, max_size, min_size);
printf("Edge Cuts: %11g %11g %11g\n",
ncuts, maxcuts, mincuts);
printf("Hypercube Hops: %11g %11g %11g\n",
nhops, maxhops, minhops);
printf("Boundary Vertices: %11g %11g %11g\n",
total_bdyvtxs, maxbdy, minbdy);
printf("Boundary Vertex Hops: %11g %11g %11g\n",
bdyvtx_hops_tot, bdyvtx_hops_max, bdyvtx_hops_min);
printf("Adjacent Sets: %11d %11d %11d\n",
total_neighbors, maxneighbors, minneighbors);
printf("Internal Vertices: %11d %11d %11d\n\n",
total_internal, max_internal, min_internal);
if (print2file) {
fprintf(outfile, "\n");
fprintf(outfile, " Total Max/Set Min/Set\n");
fprintf(outfile, " ----- ------- -------\n");
fprintf(outfile, "Set Size: %11d %11d %11d\n",
tot_size, max_size, min_size);
fprintf(outfile, "Edge Cuts: %11g %11g %11g\n",
ncuts, maxcuts, mincuts);
fprintf(outfile, "Hypercube Hops: %11g %11g %11g\n",
nhops, maxhops, minhops);
fprintf(outfile, "Boundary Vertices: %11g %11g %11g\n",
total_bdyvtxs, maxbdy, minbdy);
fprintf(outfile, "Boundary Vertex Hops: %11g %11g %11g\n",
bdyvtx_hops_tot, bdyvtx_hops_max, bdyvtx_hops_min);
fprintf(outfile, "Adjacent Sets: %11d %11d %11d\n",
total_neighbors, maxneighbors, minneighbors);
fprintf(outfile, "Internal Vertices: %11d %11d %11d\n\n",
total_internal, max_internal, min_internal);
}
if (k == ndims_tot)
k++;
else {
k += ndims;
if (k > ndims_tot)
k = ndims_tot;
}
}
sfree((char *) cutsize);
sfree((char *) hopsize);
sfree((char *) setsize);
sfree((char *) setseen);
sfree((char *) startptr);
sfree((char *) inorder);
}
syntax highlighted by Code2HTML, v. 0.9.1