Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * stat.c
00005  *
00006  * This file computes various statistics
00007  *
00008  * Started 7/25/97
00009  * George
00010  *
00011  * $Id$
00012  *
00013  */
00014 
00015 #include <metis.h>
00016 
00017 
00018 /*************************************************************************
00019 * This function computes cuts and balance information
00020 **************************************************************************/
00021 void ComputePartitionInfo(GraphType *graph, int nparts, idxtype *where)
00022 {
00023   int i, j, k, nvtxs, ncon, mustfree=0;
00024   idxtype *xadj, *adjncy, *vwgt, *adjwgt, *kpwgts, *tmpptr;
00025   idxtype *padjncy, *padjwgt, *padjcut;
00026 
00027   nvtxs = graph->nvtxs;
00028   ncon = graph->ncon;
00029   xadj = graph->xadj;
00030   adjncy = graph->adjncy;
00031   vwgt = graph->vwgt;
00032   adjwgt = graph->adjwgt;
00033 
00034   if (vwgt == NULL) {
00035     vwgt = graph->vwgt = idxsmalloc(nvtxs, 1, "vwgt");
00036     mustfree = 1;
00037   }
00038   if (adjwgt == NULL) {
00039     adjwgt = graph->adjwgt = idxsmalloc(xadj[nvtxs], 1, "adjwgt");
00040     mustfree += 2;
00041   }
00042 
00043   printf("%d-way Cut: %5d, Vol: %5d, ", nparts, ComputeCut(graph, where), ComputeVolume(graph, where));
00044 
00045   /* Compute balance information */
00046   kpwgts = idxsmalloc(ncon*nparts, 0, "ComputePartitionInfo: kpwgts");
00047 
00048   for (i=0; i<nvtxs; i++) {
00049     for (j=0; j<ncon; j++) 
00050       kpwgts[where[i]*ncon+j] += vwgt[i*ncon+j];
00051   }
00052 
00053   if (ncon == 1) {
00054     printf("\tBalance: %5.3f out of %5.3f\n", 
00055             1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)),
00056             1.0*nparts*vwgt[idxamax(nvtxs, vwgt)]/(1.0*idxsum(nparts, kpwgts)));
00057   }
00058   else {
00059     printf("\tBalance:");
00060     for (j=0; j<ncon; j++) 
00061       printf(" (%5.3f out of %5.3f)", 
00062             1.0*nparts*kpwgts[ncon*idxamax_strd(nparts, kpwgts+j, ncon)+j]/(1.0*idxsum_strd(nparts, kpwgts+j, ncon)),
00063             1.0*nparts*vwgt[ncon*idxamax_strd(nvtxs, vwgt+j, ncon)+j]/(1.0*idxsum_strd(nparts, kpwgts+j, ncon)));
00064     printf("\n");
00065   }
00066 
00067 
00068   /* Compute p-adjncy information */
00069   padjncy = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjncy");
00070   padjwgt = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
00071   padjcut = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
00072 
00073   idxset(nparts, 0, kpwgts);
00074   for (i=0; i<nvtxs; i++) {
00075     for (j=xadj[i]; j<xadj[i+1]; j++) {
00076       if (where[i] != where[adjncy[j]]) {
00077         padjncy[where[i]*nparts+where[adjncy[j]]] = 1;
00078         padjcut[where[i]*nparts+where[adjncy[j]]] += adjwgt[j];
00079         if (kpwgts[where[adjncy[j]]] == 0) {
00080           padjwgt[where[i]*nparts+where[adjncy[j]]]++;
00081           kpwgts[where[adjncy[j]]] = 1;
00082         }
00083       }
00084     }
00085     for (j=xadj[i]; j<xadj[i+1]; j++) 
00086       kpwgts[where[adjncy[j]]] = 0;
00087   }
00088 
00089   for (i=0; i<nparts; i++)
00090     kpwgts[i] = idxsum(nparts, padjncy+i*nparts);
00091   printf("Min/Max/Avg/Bal # of adjacent     subdomains: %5d %5d %5.2f %7.3f\n",
00092     kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], 
00093     1.0*idxsum(nparts, kpwgts)/(1.0*nparts), 
00094     1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)));
00095 
00096   for (i=0; i<nparts; i++)
00097     kpwgts[i] = idxsum(nparts, padjcut+i*nparts);
00098   printf("Min/Max/Avg/Bal # of adjacent subdomain cuts: %5d %5d %5d %7.3f\n",
00099     kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts, 
00100     1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)));
00101 
00102   for (i=0; i<nparts; i++)
00103     kpwgts[i] = idxsum(nparts, padjwgt+i*nparts);
00104   printf("Min/Max/Avg/Bal/Frac # of interface    nodes: %5d %5d %5d %7.3f %7.3f\n",
00105     kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts, 
00106     1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)), 1.0*idxsum(nparts, kpwgts)/(1.0*nvtxs));
00107 
00108   tmpptr = graph->where;
00109   graph->where = where;
00110   for (i=0; i<nparts; i++)
00111     IsConnectedSubdomain(NULL, graph, i, 1);
00112   graph->where = tmpptr;
00113 
00114   if (mustfree == 1 || mustfree == 3) {
00115     free(vwgt);
00116     graph->vwgt = NULL;
00117   }
00118   if (mustfree == 2 || mustfree == 3) {
00119     free(adjwgt);
00120     graph->adjwgt = NULL;
00121   }
00122 
00123   GKfree(&kpwgts, &padjncy, &padjwgt, &padjcut, LTERM);
00124 }
00125 
00126 
00127 /*************************************************************************
00128 * This function computes cuts and balance information
00129 **************************************************************************/
00130 void ComputePartitionInfoBipartite(GraphType *graph, int nparts, idxtype *where)
00131 {
00132   int i, j, k, nvtxs, ncon, mustfree=0;
00133   idxtype *xadj, *adjncy, *vwgt, *vsize, *adjwgt, *kpwgts, *tmpptr;
00134   idxtype *padjncy, *padjwgt, *padjcut;
00135 
00136   nvtxs = graph->nvtxs;
00137   ncon = graph->ncon;
00138   xadj = graph->xadj;
00139   adjncy = graph->adjncy;
00140   vwgt = graph->vwgt;
00141   vsize = graph->vsize;
00142   adjwgt = graph->adjwgt;
00143 
00144   if (vwgt == NULL) {
00145     vwgt = graph->vwgt = idxsmalloc(nvtxs, 1, "vwgt");
00146     mustfree = 1;
00147   }
00148   if (adjwgt == NULL) {
00149     adjwgt = graph->adjwgt = idxsmalloc(xadj[nvtxs], 1, "adjwgt");
00150     mustfree += 2;
00151   }
00152 
00153   printf("%d-way Cut: %5d, Vol: %5d, ", nparts, ComputeCut(graph, where), ComputeVolume(graph, where));
00154 
00155   /* Compute balance information */
00156   kpwgts = idxsmalloc(ncon*nparts, 0, "ComputePartitionInfo: kpwgts");
00157 
00158   for (i=0; i<nvtxs; i++) {
00159     for (j=0; j<ncon; j++) 
00160       kpwgts[where[i]*ncon+j] += vwgt[i*ncon+j];
00161   }
00162 
00163   if (ncon == 1) {
00164     printf("\tBalance: %5.3f out of %5.3f\n", 
00165             1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)),
00166             1.0*nparts*vwgt[idxamax(nvtxs, vwgt)]/(1.0*idxsum(nparts, kpwgts)));
00167   }
00168   else {
00169     printf("\tBalance:");
00170     for (j=0; j<ncon; j++) 
00171       printf(" (%5.3f out of %5.3f)", 
00172             1.0*nparts*kpwgts[ncon*idxamax_strd(nparts, kpwgts+j, ncon)+j]/(1.0*idxsum_strd(nparts, kpwgts+j, ncon)),
00173             1.0*nparts*vwgt[ncon*idxamax_strd(nvtxs, vwgt+j, ncon)+j]/(1.0*idxsum_strd(nparts, kpwgts+j, ncon)));
00174     printf("\n");
00175   }
00176 
00177 
00178   /* Compute p-adjncy information */
00179   padjncy = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjncy");
00180   padjwgt = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
00181   padjcut = idxsmalloc(nparts*nparts, 0, "ComputePartitionInfo: padjwgt");
00182 
00183   idxset(nparts, 0, kpwgts);
00184   for (i=0; i<nvtxs; i++) {
00185     for (j=xadj[i]; j<xadj[i+1]; j++) {
00186       if (where[i] != where[adjncy[j]]) {
00187         padjncy[where[i]*nparts+where[adjncy[j]]] = 1;
00188         padjcut[where[i]*nparts+where[adjncy[j]]] += adjwgt[j];
00189         if (kpwgts[where[adjncy[j]]] == 0) {
00190           padjwgt[where[i]*nparts+where[adjncy[j]]] += vsize[i];
00191           kpwgts[where[adjncy[j]]] = 1;
00192         }
00193       }
00194     }
00195     for (j=xadj[i]; j<xadj[i+1]; j++) 
00196       kpwgts[where[adjncy[j]]] = 0;
00197   }
00198 
00199   for (i=0; i<nparts; i++)
00200     kpwgts[i] = idxsum(nparts, padjncy+i*nparts);
00201   printf("Min/Max/Avg/Bal # of adjacent     subdomains: %5d %5d %5d %7.3f\n",
00202     kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts, 
00203     1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)));
00204 
00205   for (i=0; i<nparts; i++)
00206     kpwgts[i] = idxsum(nparts, padjcut+i*nparts);
00207   printf("Min/Max/Avg/Bal # of adjacent subdomain cuts: %5d %5d %5d %7.3f\n",
00208     kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts, 
00209     1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)));
00210 
00211   for (i=0; i<nparts; i++)
00212     kpwgts[i] = idxsum(nparts, padjwgt+i*nparts);
00213   printf("Min/Max/Avg/Bal/Frac # of interface    nodes: %5d %5d %5d %7.3f %7.3f\n",
00214     kpwgts[idxamin(nparts, kpwgts)], kpwgts[idxamax(nparts, kpwgts)], idxsum(nparts, kpwgts)/nparts, 
00215     1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts)), 1.0*idxsum(nparts, kpwgts)/(1.0*nvtxs));
00216 
00217 
00218   if (mustfree == 1 || mustfree == 3) {
00219     free(vwgt);
00220     graph->vwgt = NULL;
00221   }
00222   if (mustfree == 2 || mustfree == 3) {
00223     free(adjwgt);
00224     graph->adjwgt = NULL;
00225   }
00226 
00227   GKfree(&kpwgts, &padjncy, &padjwgt, &padjcut, LTERM);
00228 }
00229 
00230 
00231 
00232 /*************************************************************************
00233 * This function computes the balance of the partitioning
00234 **************************************************************************/
00235 void ComputePartitionBalance(GraphType *graph, int nparts, idxtype *where, floattype *ubvec)
00236 {
00237   int i, j, nvtxs, ncon;
00238   idxtype *kpwgts, *vwgt;
00239   floattype balance;
00240 
00241   nvtxs = graph->nvtxs;
00242   ncon = graph->ncon;
00243   vwgt = graph->vwgt;
00244 
00245   kpwgts = idxsmalloc(nparts, 0, "ComputePartitionInfo: kpwgts");
00246 
00247   if (vwgt == NULL && ncon == 1) {
00248     for (i=0; i<nvtxs; i++)
00249       kpwgts[where[i]]++;
00250     ubvec[0] = 1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*nvtxs);
00251   }
00252   else {
00253     for (j=0; j<ncon; j++) {
00254       idxset(nparts, 0, kpwgts);
00255       for (i=0; i<graph->nvtxs; i++)
00256         kpwgts[where[i]] += vwgt[i*ncon+j];
00257 
00258       ubvec[j] = 1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts));
00259     }
00260   }
00261 
00262   free(kpwgts);
00263 
00264 }
00265 
00266 
00267 /*************************************************************************
00268 * This function computes the balance of the element partitioning
00269 **************************************************************************/
00270 floattype ComputeElementBalance(int ne, int nparts, idxtype *where)
00271 {
00272   int i;
00273   idxtype *kpwgts;
00274   floattype balance;
00275 
00276   kpwgts = idxsmalloc(nparts, 0, "ComputeElementBalance: kpwgts");
00277 
00278   for (i=0; i<ne; i++)
00279     kpwgts[where[i]]++;
00280 
00281   balance = 1.0*nparts*kpwgts[idxamax(nparts, kpwgts)]/(1.0*idxsum(nparts, kpwgts));
00282 
00283   free(kpwgts);
00284 
00285   return balance;
00286 
00287 }
00288 
00289 
00290 /*************************************************************************
00291 * This function computes the balance of the partitioning
00292 **************************************************************************/
00293 void Moc_ComputePartitionBalance(GraphType *graph, int nparts, idxtype *where, floattype *ubvec)
00294 {
00295   int i, j, nvtxs, ncon;
00296   floattype *kpwgts, *nvwgt;
00297   floattype balance;
00298 
00299   nvtxs = graph->nvtxs;
00300   ncon = graph->ncon;
00301   nvwgt = graph->nvwgt;
00302 
00303   kpwgts = fmalloc(nparts, "ComputePartitionInfo: kpwgts");
00304 
00305   for (j=0; j<ncon; j++) {
00306     sset(nparts, 0.0, kpwgts);
00307     for (i=0; i<graph->nvtxs; i++)
00308       kpwgts[where[i]] += nvwgt[i*ncon+j];
00309 
00310     ubvec[j] = (floattype)nparts*kpwgts[samax(nparts, kpwgts)]/ssum(nparts, kpwgts);
00311   }
00312 
00313   free(kpwgts);
00314 
00315 }
00316
libs/ck-libs/parmetis/METISLib/stat.c
