Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * xyzpart.c
00005  *
00006  * This file contains code that implements a coordinate based partitioning
00007  *
00008  * Started 7/11/97
00009  * George
00010  *
00011  * $Id$
00012  *
00013  */
00014 
00015 #include <parmetislib.h>
00016 
00017 
00018 /*************************************************************************
00019 * This function implements a simple coordinate based partitioning
00020 **************************************************************************/
00021 void Coordinate_Partition(CtrlType *ctrl, GraphType *graph, int ndims, floattype *xyz, 
00022                           int setup, WorkSpaceType *wspace)
00023 {
00024   int i, j, k, nvtxs, firstvtx, icoord, coords[3];
00025   idxtype *vtxdist;
00026   floattype max[3], min[3], gmin[3], gmax[3], shift[3], scale[3];
00027   KeyValueType *cand;
00028 
00029   if (setup)
00030     SetUp(ctrl, graph, wspace);
00031   else
00032     graph->nrecv = 0;
00033 
00034   nvtxs = graph->nvtxs;
00035   vtxdist = graph->vtxdist;
00036 
00037   firstvtx = vtxdist[ctrl->mype];
00038 
00039   cand = (KeyValueType *)GKmalloc(nvtxs*sizeof(KeyValueType), "Coordinate_Partition: cand");
00040 
00041   /* Compute parameters for coordinate transformation */
00042   for (k=0; k<ndims; k++) {
00043     min[k] = +10000000;
00044     max[k] = -10000000;
00045   }
00046   for (i=0; i<nvtxs; i++) {
00047     for (k=0; k<ndims; k++) {
00048       if (xyz[i*ndims+k] < min[k])
00049         min[k] = xyz[i*ndims+k];
00050       if (xyz[i*ndims+k] > max[k])
00051         max[k] = xyz[i*ndims+k];
00052     }
00053   }
00054 
00055   /* Compute global min and max */
00056   MPI_Allreduce((void *)min, (void *)gmin, ndims, MPI_DOUBLE, MPI_MIN, ctrl->comm);
00057   MPI_Allreduce((void *)max, (void *)gmax, ndims, MPI_DOUBLE, MPI_MAX, ctrl->comm);
00058 
00059   /* myprintf(ctrl, "Coordinate Range: %e %e, Global %e %e\n", min[0], max[0], gmin[0], gmax[0]); */
00060 
00061   for (k=0; k<ndims; k++) {
00062     /* rprintf(ctrl, "Dim#%d: %e %e, span: %e\n", k, gmin[k], gmax[k], gmax[k]-gmin[k]); */
00063     shift[k] = -gmin[k];
00064     if (gmax[k] != gmin[k])
00065       scale[k] = 1.0/(gmax[k]-gmin[k]);
00066     else
00067       scale[k] = 1.0;
00068   }
00069 
00070   switch (ctrl->xyztype) {
00071     case XYZ_XCOORD:
00072       for (i=0; i<nvtxs; i++) {
00073         cand[i].key = 1000000*((xyz[i*ndims]+shift[0])*scale[0]);
00074         ASSERT(ctrl, cand[i].key>=0 && cand[i].key<=1000000);
00075         cand[i].val = firstvtx+i;
00076       }
00077       break;
00078     case XYZ_SPFILL:
00079       for (i=0; i<nvtxs; i++) {
00080         for (k=0; k<ndims; k++)
00081           coords[k] = 1024*((xyz[i*ndims+k]+shift[k])*scale[k]);
00082         for (icoord=0, j=9; j>=0; j--) {
00083           for (k=0; k<ndims; k++)
00084             icoord = (icoord<<1) + (coords[k]&(1<<j) ? 1 : 0);
00085         }
00086         cand[i].key = icoord;
00087         cand[i].val = firstvtx+i;
00088       }
00089       break;
00090     default:
00091       errexit("Unknown XYZ_Type type!\n");
00092   }
00093 
00094 
00095   /* Partition using sorting */
00096   PartSort(ctrl, graph, cand, wspace);
00097 
00098   free(cand);
00099 
00100 }
00101 
00102 
00103 
00104 /*************************************************************************
00105 * This function sorts a distributed list of KeyValueType in increasing 
00106 * order, and uses it to compute a partition. It uses samplesort. 
00107 **************************************************************************/
00108 void PartSort(CtrlType *ctrl, GraphType *graph, KeyValueType *elmnts, WorkSpaceType *wspace)
00109 {
00110   int i, j, k, nvtxs, nrecv, npes=ctrl->npes, mype=ctrl->mype, firstvtx, lastvtx;
00111   idxtype *scounts, *rcounts, *vtxdist, *perm;
00112   KeyValueType *relmnts, *mypicks, *allpicks;
00113 
00114   nvtxs   = graph->nvtxs;
00115   vtxdist = graph->vtxdist;
00116 
00117   scounts = wspace->pv1;
00118   rcounts = wspace->pv2;
00119 
00120   /* Allocate memory for the splitters */
00121   mypicks  = (KeyValueType *)GKmalloc(sizeof(KeyValueType)*(npes+1), "ParSort: mypicks");
00122   allpicks = (KeyValueType *)GKmalloc(sizeof(KeyValueType)*npes*npes, "ParSort: allpicks");
00123 
00124   /* Sort the local elements */
00125   ikeysort(nvtxs, elmnts);
00126 
00127   /* Select the local npes-1 equally spaced elements */
00128   for (i=1; i<npes; i++) { 
00129     mypicks[i-1].key = elmnts[i*(nvtxs/npes)].key;
00130     mypicks[i-1].val = elmnts[i*(nvtxs/npes)].val;
00131   }
00132 
00133   /* PrintPairs(ctrl, npes-1, mypicks, "Mypicks"); */
00134 
00135   /* Gather the picks to all the processors */
00136   MPI_Allgather((void *)mypicks, 2*(npes-1), IDX_DATATYPE, (void *)allpicks, 2*(npes-1), IDX_DATATYPE, ctrl->comm);
00137 
00138   /* PrintPairs(ctrl, npes*(npes-1), allpicks, "Allpicks"); */
00139 
00140   /* Sort all the picks */
00141   ikeyvalsort(npes*(npes-1), allpicks);
00142 
00143   /* PrintPairs(ctrl, npes*(npes-1), allpicks, "Allpicks"); */
00144 
00145   /* Select the final splitters. Set the boundaries to simplify coding */
00146   for (i=1; i<npes; i++)
00147     mypicks[i] = allpicks[i*(npes-1)];
00148   mypicks[0].key    = MIN_INT;
00149   mypicks[npes].key = MAX_INT;
00150 
00151   /* PrintPairs(ctrl, npes+1, mypicks, "Mypicks"); */
00152 
00153   /* Compute the number of elements that belong to each bucket */
00154   idxset(npes, 0, scounts);
00155   for (j=i=0; i<nvtxs; i++) {
00156     if (elmnts[i].key < mypicks[j+1].key || (elmnts[i].key == mypicks[j+1].key && elmnts[i].val < mypicks[j+1].val))
00157       scounts[j]++;
00158     else
00159       scounts[++j]++;
00160   }
00161   MPI_Alltoall(scounts, 1, IDX_DATATYPE, rcounts, 1, IDX_DATATYPE, ctrl->comm);
00162 
00163 /*
00164   PrintVector(ctrl, npes, 0, scounts, "Scounts");
00165   PrintVector(ctrl, npes, 0, rcounts, "Rcounts");
00166 */
00167 
00168   /* Allocate memory for sorted elements and receive them */
00169   MAKECSR(i, npes, scounts);
00170   MAKECSR(i, npes, rcounts);
00171   nrecv = rcounts[npes];
00172   if (wspace->nlarge >= nrecv)
00173     relmnts = (KeyValueType *)wspace->pairs;
00174   else
00175     relmnts = (KeyValueType *)GKmalloc(sizeof(KeyValueType)*nrecv, "ParSort: relmnts");
00176 
00177   /* Issue the receives first */
00178   for (i=0; i<npes; i++) 
00179     MPI_Irecv((void *)(relmnts+rcounts[i]), 2*(rcounts[i+1]-rcounts[i]), IDX_DATATYPE, i, 1, ctrl->comm, ctrl->rreq+i);
00180 
00181   /* Issue the sends next */
00182   for (i=0; i<npes; i++) 
00183     MPI_Isend((void *)(elmnts+scounts[i]), 2*(scounts[i+1]-scounts[i]), IDX_DATATYPE, i, 1, ctrl->comm, ctrl->sreq+i);
00184 
00185   MPI_Waitall(npes, ctrl->rreq, ctrl->statuses);
00186   MPI_Waitall(npes, ctrl->sreq, ctrl->statuses);
00187 
00188 
00189   /* OK, now do the local sort of the relmnts. Use perm to keep track original order */
00190   perm = idxmalloc(nrecv, "ParSort: perm");
00191   for (i=0; i<nrecv; i++) {
00192     perm[i] = relmnts[i].val;
00193     relmnts[i].val = i;
00194   }
00195   ikeysort(nrecv, relmnts);
00196 
00197 
00198   /* Compute what needs to be shifted */
00199   MPI_Scan((void *)(&nrecv), (void *)(&lastvtx), 1, MPI_INT, MPI_SUM, ctrl->comm);
00200   firstvtx = lastvtx-nrecv;  
00201 
00202   /*myprintf(ctrl, "first, last: %d %d\n", firstvtx, lastvtx); */
00203 
00204   for (j=0, i=0; i<npes; i++) {
00205     if (vtxdist[i+1] > firstvtx) {  /* Found the first PE that is passed me */
00206       if (vtxdist[i+1] >= lastvtx) {
00207         /* myprintf(ctrl, "Shifting %d elements to processor %d\n", lastvtx-firstvtx, i); */
00208         for (k=0; k<lastvtx-firstvtx; k++, j++) 
00209           relmnts[relmnts[j].val].key = i;
00210       }
00211       else {
00212         /* myprintf(ctrl, "Shifting %d elements to processor %d\n", vtxdist[i+1]-firstvtx, i); */
00213         for (k=0; k<vtxdist[i+1]-firstvtx; k++, j++) 
00214           relmnts[relmnts[j].val].key = i;
00215 
00216         firstvtx = vtxdist[i+1];
00217       }
00218     }
00219     if (vtxdist[i+1] >= lastvtx)
00220       break;
00221   }
00222 
00223   /* Reverse the ordering on the relmnts[].val */
00224   for (i=0; i<nrecv; i++) {
00225     ASSERTP(ctrl, relmnts[i].key>=0 && relmnts[i].key<npes, (ctrl, "%d %d\n", i, relmnts[i].key));
00226     relmnts[i].val = perm[i];
00227   }
00228 
00229   /* OK, now sent it back */
00230   /* Issue the receives first */
00231   for (i=0; i<npes; i++) 
00232     MPI_Irecv((void *)(elmnts+scounts[i]), 2*(scounts[i+1]-scounts[i]), IDX_DATATYPE, i, 1, ctrl->comm, ctrl->rreq+i);
00233 
00234   /* Issue the sends next */
00235   for (i=0; i<npes; i++) 
00236     MPI_Isend((void *)(relmnts+rcounts[i]), 2*(rcounts[i+1]-rcounts[i]), IDX_DATATYPE, i, 1, ctrl->comm, ctrl->sreq+i);
00237 
00238   MPI_Waitall(npes, ctrl->rreq, ctrl->statuses);
00239   MPI_Waitall(npes, ctrl->sreq, ctrl->statuses);
00240 
00241 
00242   /* Construct a partition for the graph */
00243   graph->where = idxmalloc(graph->nvtxs+graph->nrecv, "PartSort: graph->where");
00244   firstvtx = vtxdist[mype];
00245   for (i=0; i<nvtxs; i++) {
00246     ASSERTP(ctrl, elmnts[i].key>=0 && elmnts[i].key<npes, (ctrl, "%d %d\n", i, elmnts[i].key));
00247     ASSERTP(ctrl, elmnts[i].val>=vtxdist[mype] && elmnts[i].val<vtxdist[mype+1], (ctrl, "%d %d %d %d\n", i, vtxdist[mype], vtxdist[mype+1], elmnts[i].val));
00248     graph->where[elmnts[i].val-firstvtx] = elmnts[i].key;
00249   }
00250 
00251 
00252   GKfree((void **)&mypicks, (void **)&allpicks, (void **)&perm, LTERM);
00253   if (wspace->nlarge < nrecv)
00254     free(relmnts);
00255 
00256 }
00257
libs/ck-libs/parmetis/ParMETISLib/xyzpart.c
