Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * meshpart.c
00005  *
00006  * This file contains routines for partitioning finite element meshes.
00007  *
00008  * Started 9/29/97
00009  * George
00010  *
00011  * $Id: meshpart.c 13931 2013-03-29 16:48:48Z karypis $
00012  *
00013  */
00014 
00015 #include "metislib.h"
00016 
00017 
00018 /*************************************************************************
00019 * This function partitions a finite element mesh by partitioning its nodal
00020 * graph using KMETIS and then assigning elements in a load balanced fashion.
00021 **************************************************************************/
00022 int METIS_PartMeshNodal(idx_t *ne, idx_t *nn, idx_t *eptr, idx_t *eind, 
00023           idx_t *vwgt, idx_t *vsize, idx_t *nparts, real_t *tpwgts, 
00024           idx_t *options, idx_t *objval, idx_t *epart, idx_t *npart)
00025 {
00026   int sigrval=0, renumber=0, ptype;
00027   idx_t *xadj=NULL, *adjncy=NULL;
00028   idx_t ncon=1, pnumflag=0;
00029   int rstatus=METIS_OK;
00030 
00031   /* set up malloc cleaning code and signal catchers */
00032   if (!gk_malloc_init()) 
00033     return METIS_ERROR_MEMORY;
00034 
00035   gk_sigtrap();
00036 
00037   if ((sigrval = gk_sigcatch()) != 0) 
00038     goto SIGTHROW;
00039 
00040   renumber = GETOPTION(options, METIS_OPTION_NUMBERING, 0);
00041   ptype    = GETOPTION(options, METIS_OPTION_PTYPE, METIS_PTYPE_KWAY);
00042 
00043   /* renumber the mesh */
00044   if (renumber) {
00045     ChangeMesh2CNumbering(*ne, eptr, eind);
00046     options[METIS_OPTION_NUMBERING] = 0;
00047   }
00048 
00049   /* get the nodal graph */
00050   rstatus = METIS_MeshToNodal(ne, nn, eptr, eind, &pnumflag, &xadj, &adjncy);
00051   if (rstatus != METIS_OK)
00052     raise(SIGERR);
00053 
00054   /* partition the graph */
00055   if (ptype == METIS_PTYPE_KWAY) 
00056     rstatus = METIS_PartGraphKway(nn, &ncon, xadj, adjncy, vwgt, vsize, NULL, 
00057                   nparts, tpwgts, NULL, options, objval, npart);
00058   else 
00059     rstatus = METIS_PartGraphRecursive(nn, &ncon, xadj, adjncy, vwgt, vsize, NULL, 
00060                   nparts, tpwgts, NULL, options, objval, npart);
00061 
00062   if (rstatus != METIS_OK)
00063     raise(SIGERR);
00064 
00065   /* partition the other side of the mesh */
00066   InduceRowPartFromColumnPart(*ne, eptr, eind, epart, npart, *nparts, tpwgts);
00067 
00068 
00069 SIGTHROW:
00070   if (renumber) {
00071     ChangeMesh2FNumbering2(*ne, *nn, eptr, eind, epart, npart);
00072     options[METIS_OPTION_NUMBERING] = 1;
00073   }
00074 
00075   METIS_Free(xadj);
00076   METIS_Free(adjncy);
00077 
00078   gk_siguntrap();
00079   gk_malloc_cleanup(0);
00080 
00081   return metis_rcode(sigrval);
00082 }
00083 
00084 
00085 
00086 /*************************************************************************
00087 * This function partitions a finite element mesh by partitioning its dual
00088 * graph using KMETIS and then assigning nodes in a load balanced fashion.
00089 **************************************************************************/
00090 int METIS_PartMeshDual(idx_t *ne, idx_t *nn, idx_t *eptr, idx_t *eind, 
00091           idx_t *vwgt, idx_t *vsize, idx_t *ncommon, idx_t *nparts, 
00092           real_t *tpwgts, idx_t *options, idx_t *objval, idx_t *epart, 
00093           idx_t *npart) 
00094 {
00095   int sigrval=0, renumber=0, ptype;
00096   idx_t i, j;
00097   idx_t *xadj=NULL, *adjncy=NULL, *nptr=NULL, *nind=NULL;
00098   idx_t ncon=1, pnumflag=0;
00099   int rstatus = METIS_OK;
00100 
00101   /* set up malloc cleaning code and signal catchers */
00102   if (!gk_malloc_init()) 
00103     return METIS_ERROR_MEMORY;
00104 
00105   gk_sigtrap();
00106 
00107   if ((sigrval = gk_sigcatch()) != 0) 
00108     goto SIGTHROW;
00109 
00110   renumber = GETOPTION(options, METIS_OPTION_NUMBERING, 0);
00111   ptype    = GETOPTION(options, METIS_OPTION_PTYPE, METIS_PTYPE_KWAY);
00112 
00113   /* renumber the mesh */
00114   if (renumber) {
00115     ChangeMesh2CNumbering(*ne, eptr, eind);
00116     options[METIS_OPTION_NUMBERING] = 0;
00117   }
00118 
00119   /* get the dual graph */
00120   rstatus = METIS_MeshToDual(ne, nn, eptr, eind, ncommon, &pnumflag, &xadj, &adjncy);
00121   if (rstatus != METIS_OK)
00122     raise(SIGERR);
00123 
00124   /* partition the graph */
00125   if (ptype == METIS_PTYPE_KWAY) 
00126     rstatus = METIS_PartGraphKway(ne, &ncon, xadj, adjncy, vwgt, vsize, NULL, 
00127                   nparts, tpwgts, NULL, options, objval, epart);
00128   else 
00129     rstatus = METIS_PartGraphRecursive(ne, &ncon, xadj, adjncy, vwgt, vsize, NULL, 
00130                   nparts, tpwgts, NULL, options, objval, epart);
00131 
00132   if (rstatus != METIS_OK)
00133     raise(SIGERR);
00134 
00135 
00136   /* construct the node-element list */
00137   nptr = ismalloc(*nn+1, 0, "METIS_PartMeshDual: nptr");
00138   nind = imalloc(eptr[*ne], "METIS_PartMeshDual: nind");
00139 
00140   for (i=0; i<*ne; i++) {
00141     for (j=eptr[i]; j<eptr[i+1]; j++)
00142       nptr[eind[j]]++;
00143   }
00144   MAKECSR(i, *nn, nptr);
00145 
00146   for (i=0; i<*ne; i++) {
00147     for (j=eptr[i]; j<eptr[i+1]; j++)
00148       nind[nptr[eind[j]]++] = i;
00149   }
00150   SHIFTCSR(i, *nn, nptr);
00151 
00152   /* partition the other side of the mesh */
00153   InduceRowPartFromColumnPart(*nn, nptr, nind, npart, epart, *nparts, tpwgts);
00154 
00155   gk_free((void **)&nptr, &nind, LTERM);
00156 
00157 
00158 SIGTHROW:
00159   if (renumber) {
00160     ChangeMesh2FNumbering2(*ne, *nn, eptr, eind, epart, npart);
00161     options[METIS_OPTION_NUMBERING] = 1;
00162   }
00163 
00164   METIS_Free(xadj);
00165   METIS_Free(adjncy);
00166 
00167   gk_siguntrap();
00168   gk_malloc_cleanup(0);
00169 
00170   return metis_rcode(sigrval);
00171 }
00172 
00173 
00174 
00175 /*************************************************************************/
00178 /*************************************************************************/
00179 void InduceRowPartFromColumnPart(idx_t nrows, idx_t *rowptr, idx_t *rowind,
00180          idx_t *rpart, idx_t *cpart, idx_t nparts, real_t *tpwgts)
00181 {
00182   idx_t i, j, k, me;
00183   idx_t nnbrs, *pwgts, *nbrdom, *nbrwgt, *nbrmrk;
00184   idx_t *itpwgts;
00185 
00186   pwgts  = ismalloc(nparts, 0, "InduceRowPartFromColumnPart: pwgts");
00187   nbrdom = ismalloc(nparts, 0, "InduceRowPartFromColumnPart: nbrdom");
00188   nbrwgt = ismalloc(nparts, 0, "InduceRowPartFromColumnPart: nbrwgt");
00189   nbrmrk = ismalloc(nparts, -1, "InduceRowPartFromColumnPart: nbrmrk");
00190 
00191   iset(nrows, -1, rpart);
00192 
00193   /* setup the integer target partition weights */
00194   itpwgts = imalloc(nparts, "InduceRowPartFromColumnPart: itpwgts");
00195   if (tpwgts == NULL) {
00196     iset(nparts, 1+nrows/nparts, itpwgts);
00197   }
00198   else {
00199     for (i=0; i<nparts; i++)
00200       itpwgts[i] = 1+nrows*tpwgts[i];
00201   }
00202 
00203   /* first assign the rows consisting only of columns that belong to 
00204      a single partition. Assign rows that are empty to -2 (un-assigned) */
00205   for (i=0; i<nrows; i++) {
00206     if (rowptr[i+1]-rowptr[i] == 0) {
00207       rpart[i] = -2;
00208       continue;
00209     }
00210 
00211     me = cpart[rowind[rowptr[i]]];
00212     for (j=rowptr[i]+1; j<rowptr[i+1]; j++) {
00213       if (cpart[rowind[j]] != me)
00214         break;
00215     }
00216     if (j == rowptr[i+1]) {
00217       rpart[i] = me;
00218       pwgts[me]++;
00219     }
00220   }
00221 
00222   /* next assign the rows consisting of columns belonging to multiple
00223      partitions in a  balanced way */
00224   for (i=0; i<nrows; i++) {
00225     if (rpart[i] == -1) { 
00226       for (nnbrs=0, j=rowptr[i]; j<rowptr[i+1]; j++) {
00227         me = cpart[rowind[j]];
00228         if (nbrmrk[me] == -1) {
00229           nbrdom[nnbrs] = me; 
00230           nbrwgt[nnbrs] = 1; 
00231           nbrmrk[me] = nnbrs++;
00232         }
00233         else {
00234           nbrwgt[nbrmrk[me]]++;
00235         }
00236       }
00237       ASSERT(nnbrs > 0);
00238 
00239       /* assign it first to the domain with most things in common */
00240       rpart[i] = nbrdom[iargmax(nnbrs, nbrwgt)];
00241 
00242       /* if overweight, assign it to the light domain */
00243       if (pwgts[rpart[i]] > itpwgts[rpart[i]]) {
00244         for (j=0; j<nnbrs; j++) {
00245           if (pwgts[nbrdom[j]] < itpwgts[nbrdom[j]] ||
00246               pwgts[nbrdom[j]]-itpwgts[nbrdom[j]] < pwgts[rpart[i]]-itpwgts[rpart[i]]) {
00247             rpart[i] = nbrdom[j];
00248             break;
00249           }
00250         }
00251       }
00252       pwgts[rpart[i]]++;
00253 
00254       /* reset nbrmrk array */
00255       for (j=0; j<nnbrs; j++) 
00256         nbrmrk[nbrdom[j]] = -1;
00257     }
00258   }
00259 
00260   gk_free((void **)&pwgts, &nbrdom, &nbrwgt, &nbrmrk, &itpwgts, LTERM);
00261 
00262 }
libs/ck-libs/metis/libmetis/meshpart.c
