Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * mmatch.c
00005  *
00006  * This file contains code that finds a matching
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 matching
00020 **************************************************************************/
00021 void Moc_GlobalMatch_Balance(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace)
00022 {
00023   int h, i, ii, j, k;
00024   int nnbrs, nvtxs, ncon, cnvtxs, firstvtx, lastvtx, maxi, maxidx, nkept;
00025   int otherlastvtx, nrequests, nchanged, pass, nmatched, wside;
00026   idxtype *xadj, *ladjncy, *adjwgt, *vtxdist, *home, *myhome, *shome, *rhome;
00027   idxtype *match, *rmatch, *smatch;
00028   idxtype *peind, *sendptr, *recvptr;
00029   idxtype *perm, *iperm, *nperm, *changed;
00030   floattype *nvwgt, maxnvwgt;
00031   int *nreqs_pe;
00032   KeyValueType *match_requests, *match_granted, *pe_requests;
00033 
00034   maxnvwgt = 1.0/((floattype)(ctrl->nparts)*MAXNVWGT_FACTOR);
00035 
00036   graph->match_type = MATCH_GLOBAL;
00037 
00038   IFSET(ctrl->dbglvl, DBG_TIME, MPI_Barrier(ctrl->comm));
00039   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
00040 
00041   nvtxs = graph->nvtxs;
00042   ncon = graph->ncon;
00043   xadj = graph->xadj;
00044   ladjncy = graph->adjncy;
00045   adjwgt = graph->adjwgt;
00046   home = graph->home;
00047   nvwgt = graph->nvwgt;
00048 
00049   vtxdist = graph->vtxdist;
00050   firstvtx = vtxdist[ctrl->mype];
00051   lastvtx = vtxdist[ctrl->mype+1];
00052 
00053   match = graph->match = idxsmalloc(nvtxs+graph->nrecv, UNMATCHED, "HEM_Match: match");
00054   myhome = idxsmalloc(nvtxs+graph->nrecv, UNMATCHED, "HEM_Match: myhome");
00055 
00056   /*------------------------------------------------------------
00057   / Send/Receive the home information of interface vertices
00058   /------------------------------------------------------------*/
00059   if (ctrl->partType == ADAPTIVE_PARTITION || ctrl->partType == REFINE_PARTITION) {
00060     idxcopy(nvtxs, home, myhome);
00061     shome = wspace->indices;
00062     rhome = myhome + nvtxs;
00063     CommInterfaceData(ctrl, graph, myhome, shome, rhome);
00064   }
00065 
00066   nnbrs = graph->nnbrs;
00067   peind = graph->peind;
00068   sendptr = graph->sendptr;
00069   recvptr = graph->recvptr;
00070 
00071   /* Use wspace->indices as the tmp space for matching info of the boundary
00072    * vertices that are sent and received */
00073   rmatch = match + nvtxs;
00074   smatch = wspace->indices;
00075   changed = smatch+graph->nsend;
00076 
00077   /* Use wspace->indices as the tmp space for match requests of the boundary
00078    * vertices that are sent and received */
00079   match_requests = wspace->pairs;
00080   match_granted = match_requests + graph->nsend;
00081 
00082   nreqs_pe = ismalloc(nnbrs, 0, "Match_HEM: nreqs_pe");
00083 
00084   nkept = graph->gnvtxs/ctrl->npes - nvtxs;
00085 
00086   perm = (idxtype *)wspace->degrees;
00087   iperm = perm + nvtxs;
00088   FastRandomPermute(nvtxs, perm, 1);
00089   for (i=0; i<nvtxs; i++)
00090     iperm[perm[i]] = i;
00091 
00092   nperm = iperm + nvtxs;
00093   for (i=0; i<nnbrs; i++)
00094     nperm[i] = i;
00095 
00096   /*************************************************************
00097    * Go now and find a matching by doing multiple iterations
00098    *************************************************************/
00099   /* First nullify the heavy vertices */
00100   for (nchanged=i=0; i<nvtxs; i++) {
00101     for (h=0; h<ncon; h++)
00102       if (nvwgt[i*ncon+h] > maxnvwgt) {
00103         break;
00104       }
00105 
00106     if (h != ncon) {
00107       match[i] = TOO_HEAVY;
00108       nchanged++;
00109     }
00110   }
00111   if (GlobalSESum(ctrl, nchanged) > 0) {
00112     IFSET(ctrl->dbglvl, DBG_PROGRESS,
00113     rprintf(ctrl, "We found %d heavy vertices!\n", GlobalSESum(ctrl, nchanged)));
00114     CommInterfaceData(ctrl, graph, match, smatch, rmatch);
00115   }
00116 
00117 
00118   for (nmatched=pass=0; pass<NMATCH_PASSES; pass++) {
00119     wside = (graph->level+pass)%2;
00120     nchanged = nrequests = 0;
00121     for (ii=nmatched; ii<nvtxs; ii++) {
00122       i = perm[ii];
00123       if (match[i] == UNMATCHED) {  /* Unmatched */
00124         maxidx = i;
00125         maxi = -1;
00126 
00127         /* Find a heavy-edge matching */
00128         for (j=xadj[i]; j<xadj[i+1]; j++) {
00129           k = ladjncy[j];
00130           if (match[k] == UNMATCHED &&
00131                myhome[k] == myhome[i] &&
00132                (maxi == -1 ||
00133                adjwgt[maxi] < adjwgt[j] ||
00134                (maxidx < nvtxs &&
00135                k < nvtxs &&
00136                adjwgt[maxi] == adjwgt[j] &&
00137                BetterVBalance(ncon,nvwgt+i*ncon,nvwgt+maxidx*ncon,nvwgt+k*ncon) >= 0))) {
00138             maxi = j;
00139             maxidx = k;
00140           }
00141         }
00142 
00143         if (maxi != -1) {
00144           k = ladjncy[maxi];
00145           if (k < nvtxs) { /* Take care the local vertices first */
00146             /* Here we give preference the local matching by granting it right away */
00147             if (i <= k) {
00148               match[i] = firstvtx+k + KEEP_BIT;
00149               match[k] = firstvtx+i;
00150             }
00151             else {
00152               match[i] = firstvtx+k;
00153               match[k] = firstvtx+i + KEEP_BIT;
00154             }
00155             changed[nchanged++] = i;
00156             changed[nchanged++] = k;
00157           }
00158           else { /* Take care any remote boundary vertices */
00159             match[k] = MAYBE_MATCHED;
00160             /* Alternate among which vertices will issue the requests */
00161             if ((wside ==0 && firstvtx+i < graph->imap[k]) || (wside == 1 && firstvtx+i > graph->imap[k])) { 
00162               match[i] = MAYBE_MATCHED;
00163               match_requests[nrequests].key = graph->imap[k];
00164               match_requests[nrequests].val = firstvtx+i;
00165               nrequests++;
00166             }
00167           }
00168         }
00169       }
00170     }
00171 
00172 
00173 #ifdef DEBUG_MATCH
00174     PrintVector2(ctrl, nvtxs, firstvtx, match, "Match1");
00175     myprintf(ctrl, "[c: %2d] Nlocal: %d, Nrequests: %d\n", c, nlocal, nrequests);
00176 #endif
00177 
00178 
00179     /***********************************************************
00180     * Exchange the match_requests, requests for me are stored in
00181     * match_granted 
00182     ************************************************************/
00183     /* Issue the receives first. Note that from each PE can receive a maximum
00184        of the interface node that it needs to send it in the case of a mat-vec */
00185     for (i=0; i<nnbrs; i++) {
00186       MPI_Irecv((void *)(match_granted+recvptr[i]), 2*(recvptr[i+1]-recvptr[i]), IDX_DATATYPE,
00187                 peind[i], 1, ctrl->comm, ctrl->rreq+i);
00188     }
00189 
00190     /* Issue the sends next. This needs some work */
00191     ikeysort(nrequests, match_requests);
00192     for (j=i=0; i<nnbrs; i++) {
00193       otherlastvtx = vtxdist[peind[i]+1];
00194       for (k=j; k<nrequests && match_requests[k].key < otherlastvtx; k++);
00195       MPI_Isend((void *)(match_requests+j), 2*(k-j), IDX_DATATYPE, peind[i], 1, ctrl->comm, ctrl->sreq+i);
00196       j = k;
00197     }
00198 
00199     /* OK, now get into the loop waiting for the operations to finish */
00200     MPI_Waitall(nnbrs, ctrl->rreq, ctrl->statuses);
00201     for (i=0; i<nnbrs; i++) {
00202       MPI_Get_count(ctrl->statuses+i, IDX_DATATYPE, nreqs_pe+i);
00203       nreqs_pe[i] = nreqs_pe[i]/2;  /* Adjust for pairs of IDX_DATATYPE */
00204     }
00205     MPI_Waitall(nnbrs, ctrl->sreq, ctrl->statuses);
00206 
00207 
00208     /***********************************************************
00209     * Now, go and service the requests that you received in 
00210     * match_granted 
00211     ************************************************************/
00212     RandomPermute(nnbrs, nperm, 0);
00213     for (ii=0; ii<nnbrs; ii++) {
00214       i = nperm[ii];
00215       pe_requests = match_granted+recvptr[i];
00216       for (j=0; j<nreqs_pe[i]; j++) {
00217         k = pe_requests[j].key;
00218         ASSERTP(ctrl, k >= firstvtx && k < lastvtx, (ctrl, "%d %d %d %d %d\n", firstvtx, lastvtx, k, j, peind[i]));
00219         /* myprintf(ctrl, "Requesting a match %d %d\n", pe_requests[j].key, pe_requests[j].val); */
00220         if (match[k-firstvtx] == UNMATCHED) { /* Bingo, lets grant this request */
00221           changed[nchanged++] = k-firstvtx;
00222           if (nkept >= 0) { /* Flip a coin for who gets it */
00223             match[k-firstvtx] = pe_requests[j].val + KEEP_BIT;
00224             nkept--;
00225           }
00226           else {
00227             match[k-firstvtx] = pe_requests[j].val;
00228             pe_requests[j].key += KEEP_BIT;
00229             nkept++;
00230           }
00231           /* myprintf(ctrl, "Request from pe:%d (%d %d) granted!\n", peind[i], pe_requests[j].val, pe_requests[j].key); */ 
00232         }
00233         else { /* We are not granting the request */
00234           /* myprintf(ctrl, "Request from pe:%d (%d %d) not granted!\n", peind[i], pe_requests[j].val, pe_requests[j].key); */ 
00235           pe_requests[j].key = UNMATCHED;
00236         }
00237       }
00238     }
00239 
00240 
00241     /***********************************************************
00242     * Exchange the match_granted information. It is stored in
00243     * match_requests 
00244     ************************************************************/
00245     /* Issue the receives first. Note that from each PE can receive a maximum
00246        of the interface node that it needs to send during the case of a mat-vec */
00247     for (i=0; i<nnbrs; i++) {
00248       MPI_Irecv((void *)(match_requests+sendptr[i]), 2*(sendptr[i+1]-sendptr[i]), IDX_DATATYPE,
00249                 peind[i], 1, ctrl->comm, ctrl->rreq+i);
00250     }
00251 
00252     /* Issue the sends next. */
00253     for (i=0; i<nnbrs; i++) {
00254       MPI_Isend((void *)(match_granted+recvptr[i]), 2*nreqs_pe[i], IDX_DATATYPE, 
00255                 peind[i], 1, ctrl->comm, ctrl->sreq+i);
00256     }
00257 
00258     /* OK, now get into the loop waiting for the operations to finish */
00259     MPI_Waitall(nnbrs, ctrl->rreq, ctrl->statuses);
00260     for (i=0; i<nnbrs; i++) {
00261       MPI_Get_count(ctrl->statuses+i, IDX_DATATYPE, nreqs_pe+i);
00262       nreqs_pe[i] = nreqs_pe[i]/2;  /* Adjust for pairs of IDX_DATATYPE */
00263     }
00264     MPI_Waitall(nnbrs, ctrl->sreq, ctrl->statuses);
00265 
00266 
00267     /***********************************************************
00268     * Now, go and through the match_requests and update local
00269     * match information for the matchings that were granted.
00270     ************************************************************/
00271     for (i=0; i<nnbrs; i++) {
00272       pe_requests = match_requests+sendptr[i];
00273       for (j=0; j<nreqs_pe[i]; j++) {
00274         match[pe_requests[j].val-firstvtx] = pe_requests[j].key;
00275         if (pe_requests[j].key != UNMATCHED)
00276           changed[nchanged++] = pe_requests[j].val-firstvtx;
00277       }
00278     }
00279 
00280     for (i=0; i<nchanged; i++) {
00281       ii = iperm[changed[i]];
00282       perm[ii] = perm[nmatched];
00283       iperm[perm[nmatched]] = ii;
00284       nmatched++;
00285     }
00286 
00287     CommChangedInterfaceData(ctrl, graph, nchanged, changed, match, match_requests, match_granted, wspace->pv4);
00288   }
00289 
00290   /* Traverse the vertices and those that were unmatched, match them with themselves */
00291   cnvtxs = 0;
00292   for (i=0; i<nvtxs; i++) {
00293     if (match[i] == UNMATCHED || match[i] == TOO_HEAVY) {
00294       match[i] = (firstvtx+i) + KEEP_BIT;
00295       cnvtxs++;
00296     }
00297     else if (match[i] >= KEEP_BIT) {  /* A matched vertex which I get to keep */
00298       cnvtxs++;
00299     }
00300   }
00301 
00302   if (ctrl->dbglvl&DBG_MATCHINFO) {
00303     PrintVector2(ctrl, nvtxs, firstvtx, match, "Match");
00304     myprintf(ctrl, "Cnvtxs: %d\n", cnvtxs);
00305     rprintf(ctrl, "Done with matching...\n");
00306   }
00307 
00308   GKfree((void **)(&myhome), (void **)(&nreqs_pe), LTERM);
00309 
00310   IFSET(ctrl->dbglvl, DBG_TIME, MPI_Barrier(ctrl->comm));
00311   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
00312   IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ContractTmr));
00313 
00314   Moc_Global_CreateCoarseGraph(ctrl, graph, wspace, cnvtxs);
00315 
00316   IFSET(ctrl->dbglvl, DBG_TIME, MPI_Barrier(ctrl->comm));
00317   IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ContractTmr));
00318 
00319 }
00320
libs/ck-libs/parmetis/ParMETISLib/match.c
