Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * ometis.c
00005  *
00006  * This is the entry point of parallel ordering
00007  *
00008  * Started 10/19/96
00009  * George
00010  *
00011  * $Id$
00012  *
00013  */
00014 
00015 #include <parmetislib.h>
00016 
00017 
00018 
00019 
00020 /***********************************************************************************
00021 * This function is the entry point of the parallel ordering algorithm.
00022 * This function assumes that the graph is already nice partitioned among the 
00023 * processors and then proceeds to perform recursive bisection.
00024 ************************************************************************************/
00025 void ParMETIS_V3_NodeND(idxtype *vtxdist, idxtype *xadj, idxtype *adjncy, int *numflag,
00026               int *options, idxtype *order, idxtype *sizes, MPI_Comm *comm)
00027 {
00028   int i, j;
00029   int ltvwgts[MAXNCON];
00030   int nparts, npes, mype, wgtflag = 0, seed = GLOBAL_SEED;
00031   CtrlType ctrl;
00032   WorkSpaceType wspace;
00033   GraphType *graph, *mgraph;
00034   idxtype *morder;
00035   int minnvtxs;
00036 
00037   MPI_Comm_size(*comm, &npes);
00038   MPI_Comm_rank(*comm, &mype);
00039   nparts = npes;
00040 
00041   if (!ispow2(npes)) {
00042     if (mype == 0)
00043       printf("Error: The number of processors must be a power of 2!\n");
00044     return;
00045   }
00046 
00047   if (vtxdist[npes] < (int)((floattype)(npes*npes)*1.2)) {
00048     if (mype == 0)
00049       printf("Error: Too many processors for this many vertices.\n");
00050     return;
00051   }
00052 
00053   minnvtxs = vtxdist[1]-vtxdist[0];
00054   for (i=0; i<npes; i++)
00055     minnvtxs = (minnvtxs < vtxdist[i+1]-vtxdist[i]) ? minnvtxs : vtxdist[i+1]-vtxdist[i];
00056 
00057   if (minnvtxs < (int)((floattype)npes*1.1)) {
00058     if (mype == 0)
00059       printf("Error: vertices are not distributed equally.\n");
00060     return;
00061   }
00062  
00063 
00064   if (*numflag == 1) 
00065     ChangeNumbering(vtxdist, xadj, adjncy, order, npes, mype, 1);
00066 
00067   SetUpCtrl(&ctrl, nparts, options[PMV3_OPTION_DBGLVL], *comm);
00068   ctrl.CoarsenTo = amin(vtxdist[npes]+1, 25*npes);
00069 
00070   ctrl.CoarsenTo = amin(vtxdist[npes]+1, 25*amax(npes, nparts));
00071   ctrl.seed = mype;
00072   ctrl.sync = seed;
00073   ctrl.partType = STATIC_PARTITION;
00074   ctrl.ps_relation = -1;
00075   ctrl.tpwgts = fsmalloc(nparts, 1.0/(floattype)(nparts), "tpwgts");
00076   ctrl.ubvec[0] = 1.03;
00077 
00078   graph = Moc_SetUpGraph(&ctrl, 1, vtxdist, xadj, NULL, adjncy, NULL, &wgtflag);
00079 
00080   PreAllocateMemory(&ctrl, graph, &wspace);
00081 
00082   /*=======================================================
00083    * Compute the initial k-way partitioning 
00084    =======================================================*/
00085   IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
00086   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00087   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00088 
00089   Moc_Global_Partition(&ctrl, graph, &wspace);
00090 
00091   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00092   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00093   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimingInfo(&ctrl));
00094 
00095   /*=======================================================
00096    * Move the graph according to the partitioning
00097    =======================================================*/
00098   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00099   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.MoveTmr));
00100 
00101   MALLOC_CHECK(NULL);
00102   graph->ncon = 1;
00103   mgraph = Moc_MoveGraph(&ctrl, graph, &wspace);
00104   MALLOC_CHECK(NULL);
00105 
00106   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00107   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.MoveTmr));
00108 
00109   /*=======================================================
00110    * Now compute an ordering of the moved graph
00111    =======================================================*/
00112   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00113   IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
00114 
00115   FreeWSpace(&wspace);
00116   PreAllocateMemory(&ctrl, mgraph, &wspace);
00117 
00118   ctrl.ipart = ISEP_NODE;
00119   ctrl.CoarsenTo = amin(vtxdist[npes]+1, amax(20*npes, 1000));
00120 
00121   /* compute tvwgts */
00122   for (j=0; j<mgraph->ncon; j++)
00123     ltvwgts[j] = 0;
00124 
00125   for (i=0; i<mgraph->nvtxs; i++)
00126     for (j=0; j<mgraph->ncon; j++)
00127       ltvwgts[j] += mgraph->vwgt[i*mgraph->ncon+j];
00128 
00129   for (j=0; j<mgraph->ncon; j++)
00130     ctrl.tvwgts[j] = GlobalSESum(&ctrl, ltvwgts[j]);
00131 
00132   mgraph->nvwgt = fmalloc(mgraph->nvtxs*mgraph->ncon, "mgraph->nvwgt");
00133   for (i=0; i<mgraph->nvtxs; i++)
00134     for (j=0; j<mgraph->ncon; j++)
00135       mgraph->nvwgt[i*mgraph->ncon+j] = (floattype)(mgraph->vwgt[i*mgraph->ncon+j]) / (floattype)(ctrl.tvwgts[j]);
00136 
00137 
00138   morder = idxmalloc(mgraph->nvtxs, "PAROMETIS: morder");
00139   MultilevelOrder(&ctrl, mgraph, morder, sizes, &wspace);
00140 
00141   MALLOC_CHECK(NULL);
00142 
00143   /* Invert the ordering back to the original graph */
00144   ProjectInfoBack(&ctrl, graph, order, morder, &wspace);
00145 
00146   MALLOC_CHECK(NULL);
00147 
00148   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00149   IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
00150   IFSET(ctrl.dbglvl, DBG_TIME, PrintTimingInfo(&ctrl));
00151   IFSET(ctrl.dbglvl, DBG_TIME, MPI_Barrier(ctrl.gcomm));
00152 
00153   free(ctrl.tpwgts);
00154   free(morder);
00155   FreeGraph(mgraph);
00156   FreeInitialGraphAndRemap(graph, 0);
00157   FreeWSpace(&wspace);
00158   FreeCtrl(&ctrl);
00159 
00160   if (*numflag == 1) 
00161     ChangeNumbering(vtxdist, xadj, adjncy, order, npes, mype, 0);
00162 
00163   MALLOC_CHECK(NULL);
00164 }
00165 
00166 
00167 /***********************************************************************************
00168 * This function is the entry point of the parallel ordering algorithm.
00169 * This function assumes that the graph is already nice partitioned among the 
00170 * processors and then proceeds to perform recursive bisection.
00171 ************************************************************************************/
00172 void PAROMETIS(idxtype *vtxdist, idxtype *xadj, idxtype *vwgt, idxtype *adjncy, idxtype *adjwgt, 
00173                 idxtype *order, idxtype *sizes, int *options, MPI_Comm comm)
00174 {
00175   int numflag, newoptions[5];
00176 
00177   newoptions[0] = 1;
00178   newoptions[PMV3_OPTION_DBGLVL] = options[4];
00179   newoptions[PMV3_OPTION_SEED] = GLOBAL_SEED;
00180 
00181   numflag = options[3];
00182 
00183   ParMETIS_V3_NodeND(vtxdist, xadj, adjncy, &numflag, newoptions, order, sizes, &comm);
00184 
00185   options[0] = -1;
00186 
00187 }
00188
libs/ck-libs/parmetis/ParMETISLib/ometis.c
