Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * makwayfm.c
00005  *
00006  * This file contains code that performs the k-way refinement
00007  *
00008  * Started 3/1/96
00009  * George
00010  *
00011  * $Id$
00012  */
00013 
00014 #include <parmetislib.h>
00015 
00016 #define ProperSide(c, from, other) \
00017               (((c) == 0 && (from)-(other) < 0) || ((c) == 1 && (from)-(other) > 0))
00018 
00019 
00020 /*************************************************************************
00021 * This function performs k-way refinement
00022 **************************************************************************/
00023 void Moc_KWayAdaptiveRefine(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace, int npasses)
00024 {
00025   int h, i, ii, iii, j, k, c;
00026   int pass, nvtxs, nedges, ncon;
00027   int nmoves, nmoved;
00028   int me, firstvtx, lastvtx, yourlastvtx;
00029   int from, to = -1, oldto, oldcut, mydomain, yourdomain, imbalanced, overweight;
00030   int npes = ctrl->npes, mype = ctrl->mype, nparts = ctrl->nparts;
00031   int nlupd, nsupd, nnbrs, nchanged;
00032   idxtype *xadj, *ladjncy, *adjwgt, *vtxdist;
00033   idxtype *where, *tmp_where, *moved;
00034   floattype *lnpwgts, *gnpwgts, *ognpwgts, *pgnpwgts, *movewgts, *overfill;
00035   idxtype *update, *supdate, *rupdate, *pe_updates;
00036   idxtype *changed, *perm, *pperm, *htable;
00037   idxtype *peind, *recvptr, *sendptr;
00038   KeyValueType *swchanges, *rwchanges;
00039   RInfoType *rinfo, *myrinfo, *tmp_myrinfo, *tmp_rinfo;
00040   EdgeType *tmp_edegrees, *my_edegrees, *your_edegrees;
00041   floattype lbvec[MAXNCON], *nvwgt, *badmaxpwgt, *ubvec, *tpwgts, lbavg, ubavg;
00042   floattype oldgain, gain;
00043   floattype ipc_factor, redist_factor, vsize;
00044   int *nupds_pe, ndirty, nclean, dptr;
00045   int better, worse;
00046 
00047   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->KWayTmr));
00048 
00049   /*************************/
00050   /* set up common aliases */
00051   /*************************/
00052   nvtxs = graph->nvtxs;
00053   nedges = graph->nedges;
00054   ncon = graph->ncon;
00055 
00056   vtxdist = graph->vtxdist;
00057   xadj = graph->xadj;
00058   ladjncy = graph->adjncy;
00059   adjwgt = graph->adjwgt;
00060 
00061   firstvtx = vtxdist[mype];
00062   lastvtx = vtxdist[mype+1];
00063 
00064   where = graph->where;
00065   rinfo = graph->rinfo;
00066   lnpwgts = graph->lnpwgts;
00067   gnpwgts = graph->gnpwgts;
00068   ubvec = ctrl->ubvec;
00069   tpwgts = ctrl->tpwgts;
00070   ipc_factor = ctrl->ipc_factor;
00071   redist_factor = ctrl->redist_factor;
00072 
00073   nnbrs = graph->nnbrs;
00074   peind = graph->peind;
00075   recvptr = graph->recvptr;
00076   sendptr = graph->sendptr;
00077 
00078   changed = idxmalloc(nvtxs, "AKWR: changed");
00079   rwchanges = wspace->pairs;
00080   swchanges = rwchanges + recvptr[nnbrs];
00081 
00082   /************************************/
00083   /* set up important data structures */
00084   /************************************/
00085   perm = idxmalloc(nvtxs, "AKWR: perm");
00086   pperm = idxmalloc(nparts, "AKWR: pperm");
00087 
00088   update = idxmalloc(nvtxs, "AKWR: update");
00089   supdate = wspace->indices;
00090   rupdate = supdate + recvptr[nnbrs];
00091   nupds_pe = imalloc(npes, "AKWR: nupds_pe");
00092   htable = idxsmalloc(nvtxs+graph->nrecv, 0, "AKWR: lhtable");
00093   badmaxpwgt = fmalloc(nparts*ncon, "badmaxpwgt");
00094 
00095   for (i=0; i<nparts; i++) {
00096     for (h=0; h<ncon; h++) {
00097       badmaxpwgt[i*ncon+h] = ubvec[h]*tpwgts[i*ncon+h];
00098     }
00099   }
00100 
00101   movewgts = fmalloc(ncon*nparts, "AKWR: movewgts");
00102   ognpwgts = fmalloc(nparts*ncon, "AKWR: ognpwgts");
00103   pgnpwgts = fmalloc(nparts*ncon, "AKWR: pgnpwgts");
00104   overfill = fmalloc(nparts*ncon, "AKWR: overfill");
00105   moved = idxmalloc(nvtxs, "AKWR: moved");
00106   tmp_where = idxmalloc(nvtxs+graph->nrecv, "AKWR: tmp_where");
00107   tmp_rinfo = (RInfoType *)GKmalloc(sizeof(RInfoType)*nvtxs, "AKWR: tmp_rinfo");
00108   tmp_edegrees = (EdgeType *)GKmalloc(sizeof(EdgeType)*nedges, "AKWR: tmp_edegrees");
00109 
00110   idxcopy(nvtxs+graph->nrecv, where, tmp_where);
00111   for (i=0; i<nvtxs; i++) {
00112     tmp_rinfo[i].id = rinfo[i].id;
00113     tmp_rinfo[i].ed = rinfo[i].ed;
00114     tmp_rinfo[i].ndegrees = rinfo[i].ndegrees;
00115     tmp_rinfo[i].degrees = tmp_edegrees+xadj[i];
00116 
00117     for (j=0; j<rinfo[i].ndegrees; j++) {
00118       tmp_rinfo[i].degrees[j].edge = rinfo[i].degrees[j].edge;
00119       tmp_rinfo[i].degrees[j].ewgt = rinfo[i].degrees[j].ewgt;
00120     }
00121   }
00122 
00123   /*********************************************************/
00124   /* perform a small number of passes through the vertices */
00125   /*********************************************************/
00126   for (pass=0; pass<npasses; pass++) {
00127     oldcut = graph->mincut;
00128     if (mype == 0)
00129       RandomPermute(nparts, pperm, 1);
00130     MPI_Bcast((void *)pperm, nparts, IDX_DATATYPE, 0, ctrl->comm);
00131 /*    FastRandomPermute(nvtxs, perm, 1); */
00132 
00133     /*****************************/
00134     /* move dirty vertices first */
00135     /*****************************/
00136     ndirty = 0;
00137     for (i=0; i<nvtxs; i++)
00138       if (where[i] != mype)
00139         ndirty++;
00140 
00141     dptr = 0;
00142     for (i=0; i<nvtxs; i++)
00143       if (where[i] != mype)
00144         perm[dptr++] = i;
00145       else
00146         perm[ndirty++] = i;
00147 
00148     ASSERT(ctrl, ndirty == nvtxs);
00149     ndirty = dptr;
00150     nclean = nvtxs-dptr;
00151     FastRandomPermute(ndirty, perm, 0);
00152     FastRandomPermute(nclean, perm+ndirty, 0);
00153 
00154     /* check to see if the partitioning is imbalanced */
00155     Moc_ComputeParallelBalance(ctrl, graph, graph->where, lbvec);
00156     ubavg = savg(ncon, ubvec);
00157     lbavg = savg(ncon, lbvec);
00158     imbalanced = (lbavg > ubavg) ? 1 : 0;
00159 
00160     for (c=0; c<2; c++) {
00161       scopy(ncon*nparts, gnpwgts, ognpwgts);
00162       sset(ncon*nparts, 0.0, movewgts);
00163       nmoved = 0;
00164 
00165       /**********************************************/
00166       /* PASS ONE -- record stats for desired moves */
00167       /**********************************************/
00168       for (iii=0; iii<nvtxs; iii++) {
00169         i     = perm[iii];
00170         from  = tmp_where[i];
00171         nvwgt = graph->nvwgt+i*ncon;
00172         vsize = (floattype)(graph->vsize[i]);
00173 
00174         for (h=0; h<ncon; h++) {
00175           if (fabs(nvwgt[h]-gnpwgts[from*ncon+h]) < SMALLFLOAT)
00176             break;
00177         }
00178         if (h < ncon) 
00179           continue;
00180 
00181         /* only check border vertices */
00182         if (tmp_rinfo[i].ed <= 0)
00183           continue;
00184 
00185         my_edegrees = tmp_rinfo[i].degrees;
00186 
00187         for (k=0; k<tmp_rinfo[i].ndegrees; k++) {
00188           to = my_edegrees[k].edge;
00189           if (ProperSide(c, pperm[from], pperm[to])) {
00190             for (h=0; h<ncon; h++) {
00191               if (gnpwgts[to*ncon+h]+nvwgt[h] > badmaxpwgt[to*ncon+h] && nvwgt[h] > 0.0)
00192                 break;
00193             }
00194             if (h == ncon)
00195               break;
00196           }
00197         }
00198         oldto = to;
00199 
00200         /* check if a subdomain was found that fits */
00201         if (k < tmp_rinfo[i].ndegrees) {
00202           /**************************/
00203           /**************************/
00204           switch (ctrl->ps_relation) {
00205             case COUPLED:
00206               better = (oldto == mype) ? 1 : 0;
00207               worse = (from == mype) ? 1 : 0;
00208               break;
00209             case DISCOUPLED:
00210             default:
00211               better = (oldto == graph->home[i]) ? 1 : 0;
00212               worse = (from == graph->home[i]) ? 1 : 0;
00213               break;
00214           }
00215           /**************************/
00216           /**************************/
00217 
00218           oldgain = ipc_factor * (floattype)(my_edegrees[k].ewgt-tmp_rinfo[i].id);
00219           if (better) oldgain += redist_factor * vsize;
00220           if (worse) oldgain -= redist_factor * vsize;
00221 
00222           for (j=k+1; j<tmp_rinfo[i].ndegrees; j++) {
00223             to = my_edegrees[j].edge;
00224             if (ProperSide(c, pperm[from], pperm[to])) {
00225               /**************************/
00226               /**************************/
00227               switch (ctrl->ps_relation) {
00228                 case COUPLED:
00229                   better = (to == mype) ? 1 : 0;
00230                   break;
00231                 case DISCOUPLED:
00232                 default:
00233                   better = (to == graph->home[i]) ? 1 : 0;
00234                   break;
00235               }
00236               /**************************/
00237               /**************************/
00238 
00239               gain = ipc_factor * (floattype)(my_edegrees[j].ewgt-tmp_rinfo[i].id);
00240               if (better) gain += redist_factor * vsize;
00241               if (worse) gain -= redist_factor * vsize;
00242 
00243               for (h=0; h<ncon; h++)
00244                 if (gnpwgts[to*ncon+h]+nvwgt[h] > badmaxpwgt[to*ncon+h] && nvwgt[h] > 0.0)
00245                   break;
00246 
00247               if (h == ncon) {
00248                 if (gain > oldgain ||
00249                  (fabs(gain-oldgain) < SMALLFLOAT &&
00250                  IsHBalanceBetterTT(ncon,gnpwgts+oldto*ncon,gnpwgts+to*ncon,nvwgt,ubvec))){
00251                   oldgain = gain;
00252                   oldto = to;
00253                   k = j;
00254                 }
00255               }
00256             }
00257           }
00258           to = oldto;
00259           gain = oldgain;
00260 
00261           if (gain > 0.0 ||  
00262           (gain > -1.0*SMALLFLOAT &&
00263           (imbalanced ||  graph->level > 3  || iii % 8 == 0) &&
00264           IsHBalanceBetterFT(ncon,gnpwgts+from*ncon,gnpwgts+to*ncon,nvwgt,ubvec))){
00265 
00266             /****************************************/
00267             /* Update tmp arrays of the moved vertex */
00268             /****************************************/
00269             tmp_where[i] = to;
00270             moved[nmoved++] = i;
00271             for (h=0; h<ncon; h++) {
00272               INC_DEC(lnpwgts[to*ncon+h], lnpwgts[from*ncon+h], nvwgt[h]);
00273               INC_DEC(gnpwgts[to*ncon+h], gnpwgts[from*ncon+h], nvwgt[h]);
00274               INC_DEC(movewgts[to*ncon+h], movewgts[from*ncon+h], nvwgt[h]);
00275             }
00276 
00277             tmp_rinfo[i].ed += tmp_rinfo[i].id-my_edegrees[k].ewgt;
00278             SWAP(tmp_rinfo[i].id, my_edegrees[k].ewgt, j);
00279             if (my_edegrees[k].ewgt == 0) {
00280               tmp_rinfo[i].ndegrees--;
00281               my_edegrees[k].edge = my_edegrees[tmp_rinfo[i].ndegrees].edge;
00282               my_edegrees[k].ewgt = my_edegrees[tmp_rinfo[i].ndegrees].ewgt;
00283             }
00284             else {
00285               my_edegrees[k].edge = from;
00286             }
00287 
00288             /* Update the degrees of adjacent vertices */
00289             for (j=xadj[i]; j<xadj[i+1]; j++) {
00290               /* no need to bother about vertices on different pe's */
00291               if (ladjncy[j] >= nvtxs)
00292                 continue;
00293 
00294               me = ladjncy[j];
00295               mydomain = tmp_where[me];
00296 
00297               myrinfo = tmp_rinfo+me;
00298               your_edegrees = myrinfo->degrees;
00299 
00300               if (mydomain == from) {
00301                 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00302               }
00303               else {
00304                 if (mydomain == to) {
00305                   INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00306                 }
00307               }
00308 
00309               /* Remove contribution from the .ed of 'from' */
00310               if (mydomain != from) {
00311                 for (k=0; k<myrinfo->ndegrees; k++) {
00312                   if (your_edegrees[k].edge == from) {
00313                     if (your_edegrees[k].ewgt == adjwgt[j]) {
00314                       myrinfo->ndegrees--;
00315                       your_edegrees[k].edge = your_edegrees[myrinfo->ndegrees].edge;
00316                       your_edegrees[k].ewgt = your_edegrees[myrinfo->ndegrees].ewgt;
00317                     }
00318                     else {
00319                       your_edegrees[k].ewgt -= adjwgt[j];
00320                     }
00321                     break;
00322                   }
00323                 }
00324               }
00325 
00326               /* Add contribution to the .ed of 'to' */
00327               if (mydomain != to) {
00328                 for (k=0; k<myrinfo->ndegrees; k++) {
00329                   if (your_edegrees[k].edge == to) {
00330                     your_edegrees[k].ewgt += adjwgt[j];
00331                     break;
00332                   }
00333                 }
00334                 if (k == myrinfo->ndegrees) {
00335                   your_edegrees[myrinfo->ndegrees].edge = to;
00336                   your_edegrees[myrinfo->ndegrees++].ewgt = adjwgt[j];
00337                 }
00338               }
00339             }
00340           }
00341         }
00342       }
00343 
00344       /******************************************/
00345       /* Let processors know the subdomain wgts */
00346       /* if all proposed moves commit.          */
00347       /******************************************/
00348       MPI_Allreduce((void *)lnpwgts, (void *)pgnpwgts, nparts*ncon, MPI_DOUBLE, MPI_SUM, ctrl->comm);
00349 
00350       /**************************/
00351       /* compute overfill array */
00352       /**************************/
00353       overweight = 0;
00354       for (j=0; j<nparts; j++) {
00355         for (h=0; h<ncon; h++) {
00356           if (pgnpwgts[j*ncon+h] > ognpwgts[j*ncon+h]) 
00357             overfill[j*ncon+h] = (pgnpwgts[j*ncon+h]-badmaxpwgt[j*ncon+h]) / (pgnpwgts[j*ncon+h]-ognpwgts[j*ncon+h]);
00358           else 
00359             overfill[j*ncon+h] = 0.0;
00360 
00361           overfill[j*ncon+h] = amax(overfill[j*ncon+h], 0.0);
00362           overfill[j*ncon+h] *= movewgts[j*ncon+h];
00363 
00364           if (overfill[j*ncon+h] > 0.0)
00365             overweight = 1;
00366 
00367           ASSERTP(ctrl, ognpwgts[j*ncon+h] <= badmaxpwgt[j*ncon+h] || pgnpwgts[j*ncon+h] <= ognpwgts[j*ncon+h],
00368                   (ctrl, "%.4f %.4f %.4f\n", ognpwgts[j*ncon+h], badmaxpwgt[j*ncon+h], pgnpwgts[j*ncon+h]));
00369         }
00370       }
00371 
00372       /****************************************************/
00373       /* select moves to undo according to overfill array */
00374       /****************************************************/
00375       if (overweight == 1) {
00376         for (iii=0; iii<nmoved; iii++) {
00377           i = moved[iii];
00378           oldto = tmp_where[i];
00379           nvwgt = graph->nvwgt+i*ncon;
00380           my_edegrees = tmp_rinfo[i].degrees;
00381 
00382           for (k=0; k<tmp_rinfo[i].ndegrees; k++)
00383             if (my_edegrees[k].edge == where[i])
00384               break;
00385 
00386           for (h=0; h<ncon; h++)
00387             if (nvwgt[h] > 0.0 && overfill[oldto*ncon+h] > nvwgt[h]/4.0)
00388               break;
00389 
00390           /**********************************/
00391           /* nullify this move if necessary */
00392           /**********************************/
00393           if (k != tmp_rinfo[i].ndegrees && h != ncon) {
00394             moved[iii] = -1;
00395             from = oldto;
00396             to = where[i];
00397 
00398             for (h=0; h<ncon; h++) 
00399               overfill[oldto*ncon+h] = amax(overfill[oldto*ncon+h]-nvwgt[h], 0.0);
00400 
00401             tmp_where[i] = to;
00402             tmp_rinfo[i].ed += tmp_rinfo[i].id-my_edegrees[k].ewgt;
00403             SWAP(tmp_rinfo[i].id, my_edegrees[k].ewgt, j);
00404             if (my_edegrees[k].ewgt == 0) {
00405               tmp_rinfo[i].ndegrees--;
00406               my_edegrees[k].edge = my_edegrees[tmp_rinfo[i].ndegrees].edge;
00407               my_edegrees[k].ewgt = my_edegrees[tmp_rinfo[i].ndegrees].ewgt;
00408             }
00409             else {
00410               my_edegrees[k].edge = from;
00411             }
00412 
00413             for (h=0; h<ncon; h++) 
00414               INC_DEC(lnpwgts[to*ncon+h], lnpwgts[from*ncon+h], nvwgt[h]);
00415 
00416             /* Update the degrees of adjacent vertices */
00417             for (j=xadj[i]; j<xadj[i+1]; j++) {
00418               /* no need to bother about vertices on different pe's */
00419               if (ladjncy[j] >= nvtxs)
00420                 continue;
00421 
00422               me = ladjncy[j];
00423               mydomain = tmp_where[me];
00424 
00425               myrinfo = tmp_rinfo+me;
00426               your_edegrees = myrinfo->degrees;
00427 
00428               if (mydomain == from) {
00429                 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
00430               }
00431               else {
00432                 if (mydomain == to) {
00433                   INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
00434                 }
00435               }
00436 
00437               /* Remove contribution from the .ed of 'from' */
00438               if (mydomain != from) {
00439                 for (k=0; k<myrinfo->ndegrees; k++) {
00440                   if (your_edegrees[k].edge == from) {
00441                     if (your_edegrees[k].ewgt == adjwgt[j]) {
00442                       myrinfo->ndegrees--;
00443                       your_edegrees[k].edge = your_edegrees[myrinfo->ndegrees].edge;
00444                       your_edegrees[k].ewgt = your_edegrees[myrinfo->ndegrees].ewgt;
00445                     }
00446                     else {
00447                       your_edegrees[k].ewgt -= adjwgt[j];
00448                     }
00449                     break;
00450                   }
00451                 }
00452               }
00453 
00454               /* Add contribution to the .ed of 'to' */
00455               if (mydomain != to) {
00456                 for (k=0; k<myrinfo->ndegrees; k++) {
00457                   if (your_edegrees[k].edge == to) {
00458                     your_edegrees[k].ewgt += adjwgt[j];
00459                     break;
00460                   }
00461                 }
00462                 if (k == myrinfo->ndegrees) {
00463                   your_edegrees[myrinfo->ndegrees].edge = to;
00464                   your_edegrees[myrinfo->ndegrees++].ewgt = adjwgt[j];
00465                 }
00466               }
00467             }
00468           }
00469         }
00470       }
00471 
00472       /*************************************************/
00473       /* PASS TWO -- commit the remainder of the moves */
00474       /*************************************************/
00475       nlupd = nsupd = nmoves = nchanged = 0;
00476       for (iii=0; iii<nmoved; iii++) {
00477         i = moved[iii];
00478         if (i == -1)
00479           continue;
00480 
00481         where[i] = tmp_where[i]; 
00482 
00483         /* Make sure to update the vertex information */
00484         if (htable[i] == 0) {
00485           /* make sure you do the update */
00486           htable[i] = 1;
00487           update[nlupd++] = i;
00488         }
00489 
00490         /* Put the vertices adjacent to i into the update array */
00491         for (j=xadj[i]; j<xadj[i+1]; j++) {
00492           k = ladjncy[j];
00493           if (htable[k] == 0) {
00494             htable[k] = 1;
00495             if (k<nvtxs)
00496               update[nlupd++] = k;
00497             else
00498               supdate[nsupd++] = k;
00499           }
00500         }
00501         nmoves++;
00502 
00503         if (graph->pexadj[i+1]-graph->pexadj[i] > 0)
00504           changed[nchanged++] = i;
00505       }
00506 
00507       /* Tell interested pe's the new where[] info for the interface vertices */
00508       CommChangedInterfaceData(ctrl, graph, nchanged, changed, where, swchanges, rwchanges, wspace->pv4); 
00509 
00510 
00511       IFSET(ctrl->dbglvl, DBG_RMOVEINFO, rprintf(ctrl, "\t[%d %d], [%.4f],  [%d %d %d]\n",
00512             pass, c, badmaxpwgt[0], GlobalSESum(ctrl, nmoves), GlobalSESum(ctrl, nsupd), GlobalSESum(ctrl, nlupd)));
00513 
00514       /*-------------------------------------------------------------
00515       / Time to communicate with processors to send the vertices
00516       / whose degrees need to be update.
00517       /-------------------------------------------------------------*/
00518       /* Issue the receives first */
00519       for (i=0; i<nnbrs; i++) 
00520         MPI_Irecv((void *)(rupdate+sendptr[i]), sendptr[i+1]-sendptr[i], IDX_DATATYPE, peind[i], 1, ctrl->comm, ctrl->rreq+i);
00521 
00522       /* Issue the sends next. This needs some preporcessing */
00523       for (i=0; i<nsupd; i++) {
00524         htable[supdate[i]] = 0;
00525         supdate[i] = graph->imap[supdate[i]];
00526       }
00527       iidxsort(nsupd, supdate);
00528 
00529       for (j=i=0; i<nnbrs; i++) {
00530         yourlastvtx = vtxdist[peind[i]+1];
00531         for (k=j; k<nsupd && supdate[k] < yourlastvtx; k++); 
00532         MPI_Isend((void *)(supdate+j), k-j, IDX_DATATYPE, peind[i], 1, ctrl->comm, ctrl->sreq+i);
00533         j = k;
00534       }
00535 
00536       /* OK, now get into the loop waiting for the send/recv operations to finish */
00537       MPI_Waitall(nnbrs, ctrl->rreq, ctrl->statuses);
00538       for (i=0; i<nnbrs; i++) 
00539         MPI_Get_count(ctrl->statuses+i, IDX_DATATYPE, nupds_pe+i);
00540       MPI_Waitall(nnbrs, ctrl->sreq, ctrl->statuses);
00541 
00542 
00543       /*-------------------------------------------------------------
00544       / Place the recieved to-be updated vertices into update[] 
00545       /-------------------------------------------------------------*/
00546       for (i=0; i<nnbrs; i++) {
00547         pe_updates = rupdate+sendptr[i];
00548         for (j=0; j<nupds_pe[i]; j++) {
00549           k = pe_updates[j];
00550           if (htable[k-firstvtx] == 0) {
00551             htable[k-firstvtx] = 1;
00552             update[nlupd++] = k-firstvtx;
00553           }
00554         }
00555       }
00556 
00557 
00558       /*-------------------------------------------------------------
00559       / Update the rinfo of the vertices in the update[] array
00560       /-------------------------------------------------------------*/
00561       for (ii=0; ii<nlupd; ii++) {
00562         i = update[ii];
00563         ASSERT(ctrl, htable[i] == 1);
00564 
00565         htable[i] = 0;
00566 
00567         mydomain = where[i];
00568         myrinfo = rinfo+i;
00569         tmp_myrinfo = tmp_rinfo+i;
00570         my_edegrees = myrinfo->degrees;
00571         your_edegrees = tmp_myrinfo->degrees;
00572 
00573         graph->lmincut -= myrinfo->ed;
00574         myrinfo->ndegrees = 0;
00575         myrinfo->id = 0;
00576         myrinfo->ed = 0;
00577 
00578         for (j=xadj[i]; j<xadj[i+1]; j++) {
00579           yourdomain = where[ladjncy[j]];
00580           if (mydomain != yourdomain) {
00581             myrinfo->ed += adjwgt[j];
00582 
00583             for (k=0; k<myrinfo->ndegrees; k++) {
00584               if (my_edegrees[k].edge == yourdomain) {
00585                 my_edegrees[k].ewgt += adjwgt[j];
00586                 your_edegrees[k].ewgt += adjwgt[j];
00587                 break;
00588               }
00589             }
00590             if (k == myrinfo->ndegrees) {
00591               my_edegrees[k].edge = yourdomain;
00592               my_edegrees[k].ewgt = adjwgt[j];
00593               your_edegrees[k].edge = yourdomain;
00594               your_edegrees[k].ewgt = adjwgt[j];
00595               myrinfo->ndegrees++;
00596             }
00597             ASSERT(ctrl, myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
00598             ASSERT(ctrl, tmp_myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
00599 
00600           }
00601           else {
00602             myrinfo->id += adjwgt[j];
00603           }
00604         }
00605         graph->lmincut += myrinfo->ed;
00606 
00607         tmp_myrinfo->id = myrinfo->id;
00608         tmp_myrinfo->ed = myrinfo->ed;
00609         tmp_myrinfo->ndegrees = myrinfo->ndegrees;
00610       }
00611 
00612       /* finally, sum-up the partition weights */
00613       MPI_Allreduce((void *)lnpwgts, (void *)gnpwgts, nparts*ncon, MPI_DOUBLE, MPI_SUM, ctrl->comm);
00614     }
00615     graph->mincut = GlobalSESum(ctrl, graph->lmincut)/2;
00616 
00617     if (graph->mincut == oldcut)
00618       break;
00619   }
00620 
00621   GKfree((void **)&badmaxpwgt, (void **)&update, (void **)&nupds_pe, (void **)&htable, LTERM);
00622   GKfree((void **)&changed, (void **)&pperm, (void **)&perm, (void **)&moved, LTERM);
00623   GKfree((void **)&pgnpwgts, (void **)&ognpwgts, (void **)&overfill, (void **)&movewgts, LTERM);
00624   GKfree((void **)&tmp_where, (void **)&tmp_rinfo, (void **)&tmp_edegrees, LTERM);
00625 
00626   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->KWayTmr));
00627 }
00628 
00629
libs/ck-libs/parmetis/ParMETISLib/akwayfm.c
