Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * coarsen.c
00005  *
00006  * This file contains code that finds a matching and performs the coarsening
00007  *
00008  * Started 2/22/96
00009  * George
00010  *
00011  * $Id$
00012  *
00013  */
00014 
00015 #include <parmetislib.h>
00016 
00017 
00018 /*************************************************************************
00019 * This function finds a HEM matching between local vertices only
00020 **************************************************************************/
00021 void Mc_LocalMatch_HEM(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace)
00022 {
00023   int h, i, ii, j, k;
00024   int nvtxs, ncon, cnvtxs, firstvtx, maxi, maxidx, edge; 
00025   idxtype *xadj, *ladjncy, *adjwgt, *vtxdist, *home, *myhome, *shome, *rhome;
00026   idxtype *perm, *match;
00027   floattype maxnvwgt, *nvwgt;
00028 
00029   graph->match_type = MATCH_LOCAL;
00030   maxnvwgt = 1.0/((floattype)(ctrl->nparts)*MAXVWGT_FACTOR);
00031 
00032   IFSET(ctrl->dbglvl, DBG_TIME, MPI_Barrier(ctrl->comm));
00033   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00034 
00035   nvtxs = graph->nvtxs;
00036   ncon = graph->ncon;
00037   xadj = graph->xadj;
00038   nvwgt = graph->nvwgt;
00039   ladjncy = graph->adjncy;
00040   adjwgt = graph->adjwgt;
00041   home = graph->home;
00042 
00043   vtxdist = graph->vtxdist;
00044   firstvtx = vtxdist[ctrl->mype];
00045 
00046   match = graph->match = idxmalloc(nvtxs+graph->nrecv, "HEM_Match: match");
00047   myhome = idxsmalloc(nvtxs+graph->nrecv, UNMATCHED, "HEM_Match: myhome");
00048 
00049   idxset(nvtxs, UNMATCHED, match);
00050   idxset(graph->nrecv, 0, match+nvtxs);  /* Easy way to handle remote vertices */
00051 
00052   /*------------------------------------------------------------
00053   / Send/Receive the home information of interface vertices
00054   /------------------------------------------------------------*/
00055   if (ctrl->partType == ADAPTIVE_PARTITION || ctrl->partType == REFINE_PARTITION) {
00056     idxcopy(nvtxs, home, myhome);
00057     shome = wspace->indices;
00058     rhome = myhome + nvtxs;
00059     CommInterfaceData(ctrl, graph, myhome, shome, rhome);
00060   }
00061 
00062   /*************************************************************
00063    * Go now and find a local matching 
00064    *************************************************************/
00065   perm = wspace->indices;
00066   FastRandomPermute(nvtxs, perm, 1);
00067   cnvtxs = 0;
00068   for (ii=0; ii<nvtxs; ii++) {
00069     i = perm[ii];
00070     if (match[i] == UNMATCHED) {
00071       maxidx = maxi = -1;
00072 
00073       /* Find a heavy-edge matching, if the weight of the vertex is OK */
00074       for (h=0; h<ncon; h++)
00075         if (nvwgt[i*ncon+h] > maxnvwgt)
00076           break;
00077 
00078       if (h == ncon) {
00079         for (j=xadj[i]; j<xadj[i+1]; j++) {
00080           edge = ladjncy[j];
00081 
00082           /* match only with local vertices */
00083           if (myhome[edge] != myhome[i] || edge >= nvtxs)
00084             continue;
00085 
00086           for (h=0; h<ncon; h++)
00087             if (nvwgt[edge*ncon+h] > maxnvwgt) 
00088               break;
00089 
00090           if (h == ncon) {
00091             if (match[edge] == UNMATCHED &&
00092               (maxi == -1 ||
00093                adjwgt[maxi] < adjwgt[j] ||
00094               (adjwgt[maxi] == adjwgt[j] &&
00095                BetterVBalance(ncon,nvwgt+i*ncon,nvwgt+maxidx*ncon,nvwgt+edge*ncon) >= 0))) {
00096               maxi = j;
00097               maxidx = edge;
00098             }
00099           }
00100         }
00101       }
00102 
00103       if (maxi != -1) {
00104         k = ladjncy[maxi];
00105         if (i <= k) {
00106           match[i] = firstvtx+k + KEEP_BIT;
00107           match[k] = firstvtx+i;
00108         }
00109         else {
00110           match[i] = firstvtx+k;
00111           match[k] = firstvtx+i + KEEP_BIT;
00112         }
00113       }
00114       else {
00115         match[i] = (firstvtx+i) + KEEP_BIT;
00116       }
00117       cnvtxs++;
00118     }
00119   }
00120 
00121   CommInterfaceData(ctrl, graph, match, wspace->indices, match+nvtxs);
00122   GKfree((void **)(&myhome), LTERM);
00123 
00124 #ifdef DEBUG_MATCH
00125   PrintVector2(ctrl, nvtxs, firstvtx, match, "Match1");
00126 #endif
00127 
00128 
00129   if (ctrl->dbglvl&DBG_MATCHINFO) {
00130     PrintVector2(ctrl, nvtxs, firstvtx, match, "Match");
00131     myprintf(ctrl, "Cnvtxs: %d\n", cnvtxs);
00132     rprintf(ctrl, "Done with matching...\n");
00133   }
00134 
00135   IFSET(ctrl->dbglvl, DBG_TIME, MPI_Barrier(ctrl->comm));
00136   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00137 
00138   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ContractTmr));
00139   Mc_Local_CreateCoarseGraph(ctrl, graph, wspace, cnvtxs);
00140   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ContractTmr));
00141 
00142 }
00143 
00144 
00145 
00146 
00147 
00148 /*************************************************************************
00149 * This function creates the coarser graph
00150 **************************************************************************/
00151 void Mc_Local_CreateCoarseGraph(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace, int cnvtxs)
00152 {
00153   int h, i, j, k, l;
00154   int nvtxs, ncon, nedges, firstvtx, cfirstvtx;
00155   int npes=ctrl->npes, mype=ctrl->mype;
00156   int cnedges, v, u;
00157   idxtype *xadj, *vwgt, *vsize, *ladjncy, *adjwgt, *vtxdist, *where, *home;
00158   idxtype *match, *cmap;
00159   idxtype *cxadj, *cvwgt, *cvsize = NULL, *cadjncy, *cadjwgt, *cvtxdist, *chome = NULL, *cwhere = NULL;
00160   floattype *cnvwgt;
00161   GraphType *cgraph;
00162   int mask=(1<<13)-1, htable[8192], htableidx[8192];
00163 
00164   nvtxs = graph->nvtxs;
00165   ncon = graph->ncon;
00166 
00167   vtxdist = graph->vtxdist;
00168   xadj = graph->xadj;
00169   vwgt = graph->vwgt;
00170   home = graph->home;
00171   vsize = graph->vsize;
00172   ladjncy = graph->adjncy;
00173   adjwgt = graph->adjwgt;
00174   where = graph->where;
00175   match = graph->match;
00176 
00177   firstvtx = vtxdist[mype];
00178 
00179   cmap = graph->cmap = idxmalloc(nvtxs+graph->nrecv, "CreateCoarseGraph: cmap");
00180 
00181   /* Initialize the coarser graph */
00182   cgraph = CreateGraph();
00183   cgraph->nvtxs = cnvtxs;
00184   cgraph->level = graph->level+1;
00185   cgraph->ncon = ncon;
00186 
00187   cgraph->finer = graph;
00188   graph->coarser = cgraph;
00189 
00190 
00191   /*************************************************************
00192   * Obtain the vtxdist of the coarser graph 
00193   **************************************************************/
00194   cvtxdist = cgraph->vtxdist = idxmalloc(npes+1, "CreateCoarseGraph: cvtxdist");
00195   cvtxdist[npes] = cnvtxs;  /* Use last position in the cvtxdist as a temp buffer */
00196 
00197   MPI_Allgather((void *)(cvtxdist+npes), 1, IDX_DATATYPE, (void *)cvtxdist, 1, IDX_DATATYPE, ctrl->comm);
00198 
00199   MAKECSR(i, npes, cvtxdist);
00200 
00201   cgraph->gnvtxs = cvtxdist[npes];
00202 
00203 #ifdef DEBUG_CONTRACT
00204   PrintVector(ctrl, npes+1, 0, cvtxdist, "cvtxdist");
00205 #endif
00206 
00207 
00208   /*************************************************************
00209   * Construct the cmap vector 
00210   **************************************************************/
00211   cfirstvtx = cvtxdist[mype];
00212 
00213   /* Create the cmap of what you know so far locally */
00214   cnvtxs = 0;
00215   for (i=0; i<nvtxs; i++) {
00216     if (match[i] >= KEEP_BIT) {
00217       k = match[i] - KEEP_BIT;
00218       if (k<firstvtx+i)
00219         continue;  /* i has been matched via the (k,i) side */
00220 
00221       cmap[i] = cfirstvtx + cnvtxs++;
00222       if (k != firstvtx+i) {
00223         cmap[k-firstvtx] = cmap[i];
00224         match[k-firstvtx] += KEEP_BIT;  /* Add the KEEP_BIT to simplify coding */
00225       }
00226     }
00227   }
00228 
00229   CommInterfaceData(ctrl, graph, cmap, wspace->indices, cmap+nvtxs);
00230 
00231 
00232 #ifdef DEBUG_CONTRACT
00233   PrintVector(ctrl, nvtxs, firstvtx, cmap, "Cmap");
00234 #endif
00235 
00236 
00237 
00238   /*************************************************************
00239   * Finally, create the coarser graph
00240   **************************************************************/
00241   /* Allocate memory for the coarser graph, and fire up coarsening */
00242   cxadj = cgraph->xadj = idxmalloc(cnvtxs+1, "CreateCoarserGraph: cxadj");
00243   cvwgt = cgraph->vwgt = idxmalloc(cnvtxs*ncon, "CreateCoarserGraph: cvwgt");
00244   cnvwgt = cgraph->nvwgt = fmalloc(cnvtxs*ncon, "CreateCoarserGraph: cnvwgt");
00245   if (ctrl->partType == ADAPTIVE_PARTITION || ctrl->partType == REFINE_PARTITION)
00246     chome = cgraph->home = idxmalloc(cnvtxs, "CreateCoarserGraph: chome");
00247   if (vsize != NULL)
00248     cvsize = cgraph->vsize = idxmalloc(cnvtxs, "CreateCoarserGraph: cvsize");
00249   if (where != NULL)
00250     cwhere = cgraph->where = idxmalloc(cnvtxs, "CreateCoarserGraph: cwhere");
00251   cadjncy = idxmalloc(2*graph->nedges, "CreateCoarserGraph: cadjncy");
00252   cadjwgt = cadjncy+graph->nedges;
00253 
00254   iset(8192, -1, htable);
00255 
00256   cxadj[0] = cnvtxs = cnedges = 0;
00257   for (i=0; i<nvtxs; i++) {
00258     v = firstvtx+i; 
00259     u = match[i]-KEEP_BIT;
00260 
00261     if (v > u) 
00262       continue;  /* I have already collapsed it as (u,v) */
00263 
00264     /* Collapse the v vertex first, which you know that is local */
00265     for (h=0; h<ncon; h++)
00266       cvwgt[cnvtxs*ncon+h] = vwgt[i*ncon+h];
00267     if (ctrl->partType == ADAPTIVE_PARTITION || ctrl->partType == REFINE_PARTITION)
00268       chome[cnvtxs] = home[i];
00269     if (vsize != NULL)
00270       cvsize[cnvtxs] = vsize[i];
00271     if (where != NULL)
00272       cwhere[cnvtxs] = where[i];
00273     nedges = 0;
00274 
00275     for (j=xadj[i]; j<xadj[i+1]; j++) {
00276       k = cmap[ladjncy[j]];
00277       if (k != cfirstvtx+cnvtxs) {  /* If this is not an internal edge */
00278         l = k&mask;
00279         if (htable[l] == -1) { /* Seeing this for first time */
00280           htable[l] = k;
00281           htableidx[l] = cnedges+nedges;
00282           cadjncy[cnedges+nedges] = k; 
00283           cadjwgt[cnedges+nedges++] = adjwgt[j];
00284         }
00285         else if (htable[l] == k) {
00286           cadjwgt[htableidx[l]] += adjwgt[j];
00287         }
00288         else { /* Now you have to go and do a search. Expensive case */
00289           for (l=0; l<nedges; l++) {
00290             if (cadjncy[cnedges+l] == k)
00291               break;
00292           }
00293           if (l < nedges) {
00294             cadjwgt[cnedges+l] += adjwgt[j];
00295           }
00296           else {
00297             cadjncy[cnedges+nedges] = k; 
00298             cadjwgt[cnedges+nedges++] = adjwgt[j];
00299           }
00300         }
00301       }
00302     }
00303 
00304     /* Collapse the u vertex next */
00305     if (v != u) { 
00306       u -= firstvtx;
00307       for (h=0; h<ncon; h++)
00308         cvwgt[cnvtxs*ncon+h] += vwgt[u*ncon+h];
00309       if (vsize != NULL)
00310         cvsize[cnvtxs] += vsize[u];
00311       if (where != NULL && cwhere[cnvtxs] != where[u])
00312         myprintf(ctrl, "Something went wrong with the where local matching! %d %d\n", cwhere[cnvtxs], where[u]);
00313 
00314       for (j=xadj[u]; j<xadj[u+1]; j++) {
00315         k = cmap[ladjncy[j]];
00316         if (k != cfirstvtx+cnvtxs) {  /* If this is not an internal edge */
00317           l = k&mask;
00318           if (htable[l] == -1) { /* Seeing this for first time */
00319             htable[l] = k;
00320             htableidx[l] = cnedges+nedges;
00321             cadjncy[cnedges+nedges] = k; 
00322             cadjwgt[cnedges+nedges++] = adjwgt[j];
00323           }
00324           else if (htable[l] == k) {
00325             cadjwgt[htableidx[l]] += adjwgt[j];
00326           }
00327           else { /* Now you have to go and do a search. Expensive case */
00328             for (l=0; l<nedges; l++) {
00329               if (cadjncy[cnedges+l] == k)
00330                 break;
00331             }
00332             if (l < nedges) {
00333               cadjwgt[cnedges+l] += adjwgt[j];
00334             }
00335             else {
00336               cadjncy[cnedges+nedges] = k; 
00337               cadjwgt[cnedges+nedges++] = adjwgt[j];
00338             }
00339           }
00340         }
00341       }
00342     }
00343 
00344     cnedges += nedges;
00345     for (j=cxadj[cnvtxs]; j<cnedges; j++)
00346       htable[cadjncy[j]&mask] = -1;  /* reset the htable */
00347     cxadj[++cnvtxs] = cnedges;
00348   }
00349 
00350   cgraph->nedges = cnedges;
00351 
00352   for (j=0; j<cnvtxs; j++)
00353     for (h=0; h<ncon; h++)
00354       cgraph->nvwgt[j*ncon+h] = (floattype)(cvwgt[j*ncon+h])/(floattype)(ctrl->tvwgts[h]);
00355 
00356   cgraph->adjncy = idxmalloc(cnedges, "CreateCoarserGraph: cadjncy");
00357   cgraph->adjwgt = idxmalloc(cnedges, "CreateCoarserGraph: cadjwgt");
00358   idxcopy(cnedges, cadjncy, cgraph->adjncy);
00359   idxcopy(cnedges, cadjwgt, cgraph->adjwgt);
00360   GKfree((void **)&cadjncy, (void **)&graph->where, LTERM); /* Note that graph->where works fine even if it is NULL */
00361 
00362 }
00363 
00364
libs/ck-libs/parmetis/ParMETISLib/lmatch.c
