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 <parmetislib.h>
00016 
00017 
00018 
00019 /*************************************************************************
00020 * This function computes the balance of the partitioning
00021 **************************************************************************/
00022 void Moc_ComputeSerialBalance(CtrlType *ctrl, GraphType *graph, idxtype *where, floattype *ubvec)
00023 {
00024   int i, j, nvtxs, ncon, nparts;
00025   idxtype *pwgts, *tvwgts, *vwgt;
00026   floattype *tpwgts, maximb;
00027 
00028   nvtxs  = graph->nvtxs;
00029   ncon   = graph->ncon;
00030   vwgt   = graph->vwgt;
00031   nparts = ctrl->nparts;
00032   tpwgts = ctrl->tpwgts;
00033 
00034   pwgts = idxsmalloc(nparts*ncon, 0, "pwgts");
00035   tvwgts = idxsmalloc(ncon, 0, "tvwgts");
00036 
00037   for (i=0; i<graph->nvtxs; i++) {
00038     for (j=0; j<ncon; j++) {
00039       pwgts[where[i]*ncon+j] += vwgt[i*ncon+j];
00040       tvwgts[j] += vwgt[i*ncon+j];
00041     }
00042   }
00043 
00044   /* The +1 in the following code is to deal with bad cases of tpwgts[i*ncon+j] == 0 */
00045   for (j=0; j<ncon; j++) {
00046     maximb = 0.0;
00047     for (i=0; i<nparts; i++)
00048       maximb = amax(maximb, (1.0+(floattype)pwgts[i*ncon+j])/(1.0+(tpwgts[i*ncon+j]*(floattype)tvwgts[j])));
00049     ubvec[j] = maximb;
00050   }
00051 
00052   GKfree((void **)&pwgts, (void **)&tvwgts, LTERM);
00053 }
00054 
00055 
00056 /*************************************************************************
00057 * This function computes the balance of the partitioning
00058 **************************************************************************/
00059 void Moc_ComputeParallelBalance(CtrlType *ctrl, GraphType *graph, idxtype *where, floattype *ubvec)
00060 {
00061   int i, j, nvtxs, ncon, nparts;
00062   floattype *nvwgt, *lnpwgts, *gnpwgts;
00063   floattype *tpwgts, maximb;
00064   floattype lminvwgts[MAXNCON], gminvwgts[MAXNCON];
00065 
00066   ncon   = graph->ncon;
00067   nvtxs  = graph->nvtxs;
00068   nvwgt  = graph->nvwgt;
00069   nparts = ctrl->nparts;
00070   tpwgts = ctrl->tpwgts;
00071 
00072   lnpwgts = fmalloc(nparts*ncon, "CPB: lnpwgts");
00073   gnpwgts = fmalloc(nparts*ncon, "CPB: gnpwgts");
00074   sset(nparts*ncon, 0.0, lnpwgts);
00075   sset(ncon, 1.0, lminvwgts);
00076 
00077   for (i=0; i<nvtxs; i++) {
00078     for (j=0; j<ncon; j++) {
00079       lnpwgts[where[i]*ncon+j] += nvwgt[i*ncon+j];
00080 
00081       /* The following is to deal with tpwgts[] that are 0.0 for certain partitions/constraints */
00082       lminvwgts[j] = (nvwgt[i*ncon+j] > 0.0 && lminvwgts[j] > nvwgt[i*ncon+j] ? nvwgt[i*ncon+j] : lminvwgts[j]);
00083     }
00084   }
00085 
00086   MPI_Allreduce((void *)(lnpwgts), (void *)(gnpwgts), nparts*ncon, MPI_DOUBLE, MPI_SUM, ctrl->comm);
00087   MPI_Allreduce((void *)(lminvwgts), (void *)(gminvwgts), ncon, MPI_DOUBLE, MPI_MIN, ctrl->comm);
00088 
00089   /* The +gminvwgts[j] in the following code is to deal with bad cases of tpwgts[i*ncon+j] == 0 */
00090   for (j=0; j<ncon; j++) {
00091     maximb = 0.0;
00092     for (i=0; i<nparts; i++)
00093       maximb = amax(maximb, (gminvwgts[j]+gnpwgts[i*ncon+j])/(gminvwgts[j]+tpwgts[i*ncon+j]));
00094     ubvec[j] = maximb;
00095   }
00096 
00097   GKfree((void **)&lnpwgts, (void **)&gnpwgts, LTERM);
00098 
00099   return;
00100 }
00101 
00102 
00103 /*************************************************************************
00104 * This function prints a matrix
00105 **************************************************************************/
00106 void Moc_PrintThrottleMatrix(CtrlType *ctrl, GraphType *graph, floattype *matrix)
00107 {
00108   int i, j;
00109 
00110   for (i=0; i<ctrl->npes; i++) {
00111     if (i == ctrl->mype) {
00112       for (j=0; j<ctrl->npes; j++)
00113         printf("%.3f ", matrix[j]);
00114       printf("\n");
00115       fflush(stdout);
00116     }
00117     MPI_Barrier(ctrl->comm);
00118   }
00119 
00120   if (ctrl->mype == 0) {
00121     printf("****************************\n");
00122     fflush(stdout);
00123   }
00124   MPI_Barrier(ctrl->comm);
00125 
00126   return;
00127 }
00128 
00129 
00130 /*************************************************************************
00131 *  This function computes stats for refinement
00132 **************************************************************************/
00133 void Moc_ComputeRefineStats(CtrlType *ctrl, GraphType *graph, floattype *ubvec)
00134 {
00135   int h, i, j, k;
00136   int nvtxs, ncon;
00137   idxtype *xadj, *adjncy, *adjwgt, *where;
00138   floattype *nvwgt, *lnpwgts, *gnpwgts;
00139   RInfoType *rinfo;
00140   int mype = ctrl->mype, nparts = ctrl->nparts;
00141   idxtype *gborder, *border, *gfrom, *from, *gto, *to, *connect, *gconnect;
00142   idxtype gain[20] = {0}, ggain[20];
00143   int lnborders, gnborders;
00144   int bestgain, pmoves, gpmoves, other;
00145   floattype tpwgts[MAXNCON], badmaxpwgt[MAXNCON];
00146   int HIST_FACTOR = graph->level + 1;
00147 
00148   nvtxs = graph->nvtxs;
00149   ncon = graph->ncon;
00150   xadj = graph->xadj;
00151   adjncy = graph->adjncy;
00152   adjwgt = graph->adjwgt;
00153   where = graph->where;
00154   lnpwgts = graph->lnpwgts;
00155   gnpwgts = graph->gnpwgts;
00156   rinfo = graph->rinfo;
00157 
00158   connect = idxsmalloc(nparts*nparts, 0, "CRS: connect");
00159   gconnect = idxmalloc(nparts*nparts, "CRS: gconnect");
00160   border = idxsmalloc(nparts, 0, "CRS: border");
00161   gborder = idxmalloc(nparts, "CRS: gborder");
00162   from = idxsmalloc(nparts, 0, "CRS: from");
00163   gfrom = idxmalloc(nparts, "CRS: gfrom");
00164   to = idxsmalloc(nparts, 0, "CRS: to");
00165   gto = idxmalloc(nparts, "CRS: gto");
00166 
00167   for (h=0; h<ncon; h++) {
00168     tpwgts[h] = ssum_strd(nparts, gnpwgts+h, ncon)/(floattype)(nparts);
00169     badmaxpwgt[h] = ubvec[h]*tpwgts[h];
00170   }
00171 
00172   if (mype == 0) printf("******************************\n");
00173   if (mype == 0) printf("******************************\n");
00174 
00175   /***************************************/
00176   if (mype == 0) {
00177     printf("subdomain weights:\n");
00178     for (h=0; h<ncon; h++) {
00179       for (i=0; i<nparts; i++)
00180         printf("%9.3f ", gnpwgts[i*ncon+h]);
00181       printf("\n");
00182     }
00183     printf("\n");
00184   }
00185 
00186   /***************************************/
00187   if (mype == 0) {
00188     printf("subdomain imbalance:\n");
00189     for (h=0; h<ncon; h++) {
00190       for (i=0; i<nparts; i++)
00191         printf("%9.3f ", gnpwgts[i*ncon+h] * (floattype)(nparts));
00192       printf("\n");
00193     }
00194     printf("\n");
00195   }
00196 
00197   /***************************************/
00198   for (i=0; i<nparts; i++)
00199     connect[i*nparts+i] = -1;
00200 
00201   for (i=0; i<nvtxs; i++) {
00202     for (j=xadj[i]; j<xadj[i+1]; j++) {
00203       if (where[i] != where[adjncy[j]]) {
00204         connect[where[i]*nparts+where[adjncy[j]]] = 1;
00205         connect[where[adjncy[j]]*nparts+where[i]] = 1;
00206       }
00207     }
00208   }
00209 
00210   MPI_Reduce((void *)connect, (void *)gconnect, nparts*nparts, IDX_DATATYPE, MPI_MAX, 0, ctrl->comm);
00211   if (mype == 0) { 
00212     printf("connectivity\n");
00213     for (i=0; i<nparts; i++) {
00214       printf("%d: ", i);
00215       for (j=0; j<nparts; j++)
00216         printf("%9d ", gconnect[i*nparts+j]);
00217       printf("\n");
00218     }
00219     printf("\n");
00220   }
00221 
00222   /***************************************/
00223   lnborders = 0;
00224   for (i=0; i<nvtxs; i++)
00225     if (rinfo[i].ndegrees > 0) {
00226       lnborders++;
00227       border[where[i]]++;
00228     } 
00229 
00230   MPI_Reduce((void *)border, (void *)gborder, nparts, IDX_DATATYPE, MPI_SUM, 0, ctrl->comm);
00231   gnborders = GlobalSESum(ctrl, lnborders);
00232   if (mype == 0) {
00233     printf("number of borders: %d\n", gnborders);
00234     for (i=0; i<nparts; i++)
00235       printf("%9d ", gborder[i]);
00236     printf("\n\n");
00237   }
00238 
00239   /***************************************/
00240   pmoves = 0;
00241   for (i=0; i<nvtxs; i++) {
00242     nvwgt = graph->nvwgt+i*ncon;
00243 
00244     for (j=0; j<rinfo[i].ndegrees; j++) {
00245       other = rinfo[i].degrees[j].edge;
00246       for (h=0; h<ncon; h++)
00247         if (gnpwgts[other*ncon+h]+nvwgt[h] > badmaxpwgt[h])
00248           break;
00249 
00250       if (h == ncon)
00251         break;
00252     }
00253 
00254     if (j < rinfo[i].ndegrees) {
00255       pmoves++;
00256       from[where[i]]++;
00257       to[other]++;
00258       for (k=j+1; k<rinfo[i].ndegrees; k++) {
00259         other = rinfo[i].degrees[k].edge;
00260         for (h=0; h<ncon; h++)
00261           if (gnpwgts[other*ncon+h]+nvwgt[h] > badmaxpwgt[h])
00262             break;
00263 
00264         if (h == ncon) {
00265           pmoves++;
00266           from[where[i]]++;
00267           to[other]++;
00268         }
00269       }
00270     }
00271   }
00272 
00273   gpmoves = GlobalSESum(ctrl, pmoves);
00274   MPI_Reduce((void *)from, (void *)gfrom, nparts, IDX_DATATYPE, MPI_SUM, 0, ctrl->comm);
00275   MPI_Reduce((void *)to, (void *)gto, nparts, IDX_DATATYPE, MPI_SUM, 0, ctrl->comm);
00276 
00277   if (mype == 0) {
00278     printf("possible moves: %d\n", gpmoves);
00279     printf("from   ");
00280     for (i=0; i<nparts; i++) {
00281       printf("%9d ", gfrom[i]);
00282     }
00283     printf("\n");
00284     printf("to     ");
00285     for (i=0; i<nparts; i++) {
00286       printf("%9d ", gto[i]);
00287     }
00288     printf("\n\n");
00289   }
00290 
00291   /***************************************/
00292   for (i=0; i<nvtxs; i++) {
00293     if (rinfo[i].ndegrees > 0) {
00294       bestgain = rinfo[i].degrees[0].ewgt-rinfo[i].id;
00295       for (j=0; j<rinfo[i].ndegrees; j++)
00296         bestgain = amax(bestgain, rinfo[i].degrees[j].ewgt-rinfo[i].id);
00297 
00298       if (bestgain / HIST_FACTOR >= 10) {
00299         gain[19]++;
00300         continue;
00301       }
00302 
00303       if (bestgain / HIST_FACTOR < -10) {
00304         gain[0]++;
00305         continue;
00306       }
00307 
00308       gain[(bestgain/HIST_FACTOR)+10]++;
00309     }
00310   }
00311 
00312   MPI_Reduce((void *)gain, (void *)ggain, 20, IDX_DATATYPE, MPI_SUM, 0, ctrl->comm);
00313   if (mype == 0) {
00314     printf("gain histogram (buckets of %d)\n", HIST_FACTOR);
00315     for (i=0; i<20; i++) {
00316       if (i == 10 || i == 11)
00317         printf("    ");
00318       printf("%d ", ggain[i]);
00319     }
00320     printf("\n\n");
00321   }
00322 
00323 
00324 
00325 
00326   /***************************************/
00327   if (mype == 0) printf("******************************\n");
00328   if (mype == 0) printf("******************************\n");
00329 
00330   GKfree((void **)&gconnect, (void **)&connect, (void **)&gborder, (void **)&border, (void **)&gfrom, (void **)&from, (void **)&gto, (void **)&to, LTERM);
00331   return;
00332 }
libs/ck-libs/parmetis/ParMETISLib/stat.c
