Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * medge_refine.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 * This function projects a partition.
00021 **************************************************************************/
00022 void Moc_ProjectPartition(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace)
00023 {
00024   int i, nvtxs, nnbrs = -1, firstvtx, cfirstvtx;
00025   idxtype *match, *cmap, *where, *cwhere;
00026   idxtype *peind, *slens = NULL, *rlens = NULL;
00027   KeyValueType *rcand, *scand = NULL;
00028   GraphType *cgraph;
00029 
00030 
00031   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
00032 
00033   cgraph = graph->coarser;
00034   cwhere = cgraph->where;
00035   cfirstvtx = cgraph->vtxdist[ctrl->mype];
00036 
00037   nvtxs = graph->nvtxs;
00038   match = graph->match;
00039   cmap = graph->cmap;
00040   where = graph->where = idxmalloc(nvtxs+graph->nrecv, "ProjectPartition: graph->where");
00041   firstvtx = graph->vtxdist[ctrl->mype];
00042 
00043 
00044   if (graph->match_type == MATCH_GLOBAL) {  /* Only if global matching is on */
00045     /*------------------------------------------------------------
00046     / Start the transmission of the remote where information 
00047     /------------------------------------------------------------*/
00048     scand = wspace->pairs;
00049     nnbrs = graph->nnbrs;
00050     peind = graph->peind;
00051     slens = graph->slens;
00052     rlens = graph->rlens;
00053     rcand = graph->rcand;
00054 
00055     /* Issue the receives first */
00056     for (i=0; i<nnbrs; i++) {
00057       if (slens[i+1]-slens[i] > 0) /* Issue a receive only if you are getting something */
00058         MPI_Irecv((void *)(scand+slens[i]), 2*(slens[i+1]-slens[i]), IDX_DATATYPE, peind[i], 1, ctrl->comm, ctrl->rreq+i);
00059     }
00060 
00061 #ifdef DEBUG_PROJECT
00062     PrintPairs(ctrl, rlens[nnbrs], rcand, "rcand"); 
00063 #endif
00064 
00065     /* Put the where[rcand[].key] into the val field */
00066     for (i=0; i<rlens[nnbrs]; i++) {
00067       ASSERT(ctrl, rcand[i].val >= 0 && rcand[i].val < cgraph->nvtxs);
00068       rcand[i].val = cwhere[rcand[i].val];
00069     }
00070 
00071 #ifdef DEBUG_PROJECT
00072     PrintPairs(ctrl, rlens[nnbrs], rcand, "rcand");
00073     PrintVector(ctrl, nvtxs, firstvtx, cmap, "cmap");
00074 #endif
00075 
00076     /* Issue the sends next */
00077     for (i=0; i<nnbrs; i++) {
00078       if (rlens[i+1]-rlens[i] > 0) /* Issue a send only if you are sending something */
00079         MPI_Isend((void *)(rcand+rlens[i]), 2*(rlens[i+1]-rlens[i]), IDX_DATATYPE, peind[i], 1, ctrl->comm, ctrl->sreq+i);
00080     }
00081   }
00082 
00083   /*------------------------------------------------------------
00084   / Project local vertices first
00085   /------------------------------------------------------------*/
00086   for (i=0; i<nvtxs; i++) {
00087     if (match[i] >= KEEP_BIT) {
00088       ASSERT(ctrl, cmap[i]-cfirstvtx>=0 && cmap[i]-cfirstvtx<cgraph->nvtxs);
00089       where[i] = cwhere[cmap[i]-cfirstvtx];
00090     }
00091   }
00092 
00093   if (graph->match_type == MATCH_GLOBAL) {  /* Only if global matching is on */
00094     /*------------------------------------------------------------
00095     / Wait for the nonblocking operations to finish
00096     /------------------------------------------------------------*/
00097     for (i=0; i<nnbrs; i++) {
00098       if (rlens[i+1]-rlens[i] > 0)  
00099         MPI_Wait(ctrl->sreq+i, &ctrl->status);
00100     }
00101     for (i=0; i<nnbrs; i++) {
00102       if (slens[i+1]-slens[i] > 0)  
00103         MPI_Wait(ctrl->rreq+i, &ctrl->status);
00104     }
00105 
00106 #ifdef DEBUG_PROJECT
00107     PrintPairs(ctrl, slens[nnbrs], scand, "scand"); 
00108 #endif
00109 
00110     /*------------------------------------------------------------
00111     / Project received vertices now
00112     /------------------------------------------------------------*/
00113     for (i=0; i<slens[nnbrs]; i++) {
00114       ASSERTP(ctrl, scand[i].key-firstvtx>=0 && scand[i].key-firstvtx<graph->nvtxs, (ctrl, "%d %d %d\n", scand[i].key, firstvtx, graph->nvtxs));
00115       where[scand[i].key-firstvtx] = scand[i].val;
00116     }
00117   }
00118 
00119 
00120   FreeGraph(graph->coarser);
00121   graph->coarser = NULL;
00122 
00123   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
00124 }
00125 
00126 
00127 
00128 /*************************************************************************
00129 * This function computes the initial id/ed 
00130 **************************************************************************/
00131 void Moc_ComputePartitionParams(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace)
00132 {
00133   int h, i, j, k;
00134   int nvtxs, ncon;
00135   int firstvtx, lastvtx;
00136   idxtype *xadj, *ladjncy, *adjwgt, *vtxdist;
00137   floattype *lnpwgts, *gnpwgts;
00138   idxtype *where, *swhere, *rwhere;
00139   RInfoType *rinfo, *myrinfo;
00140   EdgeType *edegrees;
00141   int me, other;
00142 
00143   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->KWayInitTmr));
00144 
00145 
00146   nvtxs = graph->nvtxs;
00147   ncon = graph->ncon;
00148 
00149   vtxdist = graph->vtxdist;
00150   xadj = graph->xadj;
00151   ladjncy = graph->adjncy;
00152   adjwgt = graph->adjwgt;
00153 
00154   where = graph->where;
00155   rinfo = graph->rinfo = (RInfoType *)GKmalloc(sizeof(RInfoType)*nvtxs, "CPP: rinfo");
00156   lnpwgts = graph->lnpwgts = fmalloc(ctrl->nparts*ncon, "CPP: lnpwgts");
00157   gnpwgts = graph->gnpwgts = fmalloc(ctrl->nparts*ncon, "CPP: gnpwgts");
00158 
00159   sset(ctrl->nparts*ncon, 0, lnpwgts);
00160 
00161   firstvtx = vtxdist[ctrl->mype];
00162   lastvtx = vtxdist[ctrl->mype+1];
00163 
00164   /*------------------------------------------------------------
00165   / Send/Receive the where information of interface vertices
00166   /------------------------------------------------------------*/
00167   swhere = wspace->indices;
00168   rwhere = where + nvtxs;
00169 
00170   CommInterfaceData(ctrl, graph, where, swhere, rwhere); 
00171 
00172 #ifdef DEBUG_COMPUTEPPARAM
00173   PrintVector(ctrl, nvtxs, firstvtx, where, "where");
00174 #endif
00175 
00176   ASSERT(ctrl, wspace->nlarge >= xadj[nvtxs]);
00177 
00178   /*------------------------------------------------------------
00179   / Compute now the id/ed degrees
00180   /------------------------------------------------------------*/
00181   graph->lmincut = 0;
00182   for (i=0; i<nvtxs; i++) {
00183     me = where[i];
00184     myrinfo = rinfo+i;
00185 
00186     for (h=0; h<ncon; h++)
00187       lnpwgts[me*ncon+h] += graph->nvwgt[i*ncon+h];
00188 
00189     myrinfo->degrees = wspace->degrees + xadj[i];
00190     myrinfo->ndegrees = myrinfo->id = myrinfo->ed = 0;
00191 
00192     for (j=xadj[i]; j<xadj[i+1]; j++) {
00193       if (me == where[ladjncy[j]])
00194         myrinfo->id += adjwgt[j];
00195       else
00196         myrinfo->ed += adjwgt[j];
00197     }
00198 
00199 
00200     if (myrinfo->ed > 0) {  /* Time to do some serious work */
00201       graph->lmincut += myrinfo->ed;
00202       edegrees = myrinfo->degrees;
00203 
00204       for (j=xadj[i]; j<xadj[i+1]; j++) {
00205         other = where[ladjncy[j]];
00206         if (me != other) {
00207           for (k=0; k<myrinfo->ndegrees; k++) {
00208             if (edegrees[k].edge == other) {
00209               edegrees[k].ewgt += adjwgt[j];
00210               break;
00211             }
00212           }
00213           if (k == myrinfo->ndegrees) {
00214             edegrees[k].edge = other;
00215             edegrees[k].ewgt = adjwgt[j];
00216             myrinfo->ndegrees++;
00217           }
00218           ASSERT(ctrl, myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
00219         }
00220       }
00221     }
00222   }
00223 
00224 #ifdef DEBUG_COMPUTEPPARAM
00225   PrintVector(ctrl, ctrl->nparts*ncon, 0, lnpwgts, "lnpwgts");
00226 #endif
00227 
00228   /* Finally, sum-up the partition weights */
00229   MPI_Allreduce((void *)lnpwgts, (void *)gnpwgts, ctrl->nparts*ncon, MPI_DOUBLE, MPI_SUM, ctrl->comm);
00230 
00231   graph->mincut = GlobalSESum(ctrl, graph->lmincut)/2;
00232 
00233 #ifdef DEBUG_COMPUTEPPARAM
00234   PrintVector(ctrl, ctrl->nparts*ncon, 0, gnpwgts, "gnpwgts");
00235 #endif
00236 
00237   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->KWayInitTmr));
00238 }
00239
libs/ck-libs/parmetis/ParMETISLib/kwayrefine.c
