initbalance.c

Handles Hexahedral, Tetrahedral, Quadrilateral, and Triangle meshes. Lagrangian, Hierarchic, and Mon

      SerialRemap(&cgraph, ctrl->nparts, home, lwhere, part, ctrl->tpwgts);
    }

    MPI_Comm_free(&srcomm);
  }
  /**************************************/
  /* The other half do global diffusion */
  /**************************************/
  else {
    /******************************************************************/
    /* The next stmt is required to balance out the sr MPI_Comm_split */
    /******************************************************************/
    MPI_Comm_split(ipcomm, MPI_UNDEFINED, 0, &srcomm);

    if (ncon == 1) {
      rating = WavefrontDiffusion(&myctrl, agraph, home);
      Moc_ComputeSerialBalance(ctrl, &cgraph, part, lbvec);
      lbsum = ssum(ncon, lbvec);

      /* Determine which PE computed the best partitioning */
      MPI_Allreduce((void *)&rating, (void *)&max_rating, 1, MPI_FLOAT, MPI_MAX, ipcomm);
      MPI_Allreduce((void *)&lbsum, (void *)&min_lbsum, 1, MPI_FLOAT, MPI_MIN, ipcomm);

      lpecost.rank = ctrl->mype;
      lpecost.cost = lbsum;
      if (min_lbsum < UNBALANCE_FRACTION * (float)(ncon)) {
        if (lbsum < UNBALANCE_FRACTION * (float)(ncon))
          lpecost.cost = rating;
        else
          lpecost.cost = max_rating + lbsum;
      }

      MPI_Allreduce((void *)&lpecost, (void *)&gpecost, 1, MPI_FLOAT_INT, MPI_MINLOC, ipcomm);

      /* Now send this to the coordinating processor */
      if (ctrl->mype == gpecost.rank && ctrl->mype != gd_pe)
        MPI_Send((void *)part, nvtxs, IDX_DATATYPE, gd_pe, 1, ctrl->comm);

      if (ctrl->mype != gpecost.rank && ctrl->mype == gd_pe)
        MPI_Recv((void *)part, nvtxs, IDX_DATATYPE, gpecost.rank, 1, ctrl->comm, &status);

      if (ctrl->mype == gd_pe) {
        idxcopy(nvtxs, part, lwhere);
        SerialRemap(&cgraph, ctrl->nparts, home, lwhere, part, ctrl->tpwgts);
      }
    }
    else {
      Moc_Diffusion(&myctrl, agraph, graph->vtxdist, agraph->where, home, wspace, N_MOC_GD_PASSES);
    }
  }

  if (graph->ncon <= MAX_NCON_FOR_DIFFUSION) {
    if (ctrl->mype == sr_pe  || ctrl->mype == gd_pe) {
      /********************************************************************/
      /* The coordinators from each group decide on the best partitioning */
      /********************************************************************/
      my_cut = (float) ComputeSerialEdgeCut(&cgraph);
      my_totalv = (float) Mc_ComputeSerialTotalV(&cgraph, home);
      Moc_ComputeSerialBalance(ctrl, &cgraph, part, lbvec);
      my_balance = ssum(cgraph.ncon, lbvec);
      my_balance /= (float) cgraph.ncon;
      my_cost = ctrl->ipc_factor * my_cut + REDIST_WGT * ctrl->redist_base * my_totalv;

      IFSET(ctrl->dbglvl, DBG_REFINEINFO, printf("%s initial cut: %.1f, totalv: %.1f, balance: %.3f\n",
      (ctrl->mype == sr_pe ? "scratch-remap" : "diffusion"), my_cut, my_totalv, my_balance));

      if (ctrl->mype == gd_pe) {
        buffer[0] = my_cost;
        buffer[1] = my_balance;
        MPI_Send((void *)buffer, 2, MPI_FLOAT, sr_pe, 1, ctrl->comm);
      }
      else {
        MPI_Recv((void *)buffer, 2, MPI_FLOAT, gd_pe, 1, ctrl->comm, &status);
        your_cost = buffer[0];
        your_balance = buffer[1];
      }
    }

    if (ctrl->mype == sr_pe) {
      who_wins = gd_pe;
      if ((my_balance < 1.1 && your_balance > 1.1) ||
          (my_balance < 1.1 && your_balance < 1.1 && my_cost < your_cost) ||
          (my_balance > 1.1 && your_balance > 1.1 && my_balance < your_balance)) {
        who_wins = sr_pe;
      }
    }

    MPI_Bcast((void *)&who_wins, 1, MPI_INT, sr_pe, ctrl->comm);
  }
  else {
    who_wins = sr_pe;
  }

  MPI_Bcast((void *)part, nvtxs, IDX_DATATYPE, who_wins, ctrl->comm);
  idxcopy(graph->nvtxs, part+vtxdist[ctrl->mype], graph->where);

  MPI_Comm_free(&ipcomm);
  GKfree((void **)&xadj, (void **)&mytpwgts, LTERM);

/* For whatever reason, FreeGraph crashes here...so explicitly free the memory.
  FreeGraph(agraph);
*/
  GKfree((void **)&agraph->xadj, (void **)&agraph->adjncy, (void **)&agraph->vwgt, (void **)&agraph->nvwgt, LTERM);
  GKfree((void **)&agraph->vsize, (void **)&agraph->adjwgt, (void **)&agraph->label, LTERM);
  GKfree((void **)&agraph, LTERM);

  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));

}


/* NOTE: this subroutine should work for static, adaptive, single-, and multi-contraint */
/*************************************************************************
* This function assembles the graph into a single processor
**************************************************************************/
GraphType *Moc_AssembleAdaptiveGraph(CtrlType *ctrl, GraphType *graph, WorkSpaceType *wspace)
{
  int i, j, k, l, gnvtxs, nvtxs, ncon, gnedges, nedges, gsize;
  idxtype *xadj, *vwgt, *vsize, *adjncy, *adjwgt, *vtxdist, *imap;
  idxtype *axadj, *aadjncy, *aadjwgt, *avwgt, *avsize = NULL, *alabel;
  idxtype *mygraph, *ggraph;
  int *rcounts, *rdispls, mysize;
  float *anvwgt;
  GraphType *agraph;

  gnvtxs  = graph->gnvtxs;
  nvtxs   = graph->nvtxs;
  ncon    = graph->ncon;
  nedges  = graph->xadj[nvtxs];
  xadj    = graph->xadj;
  vwgt    = graph->vwgt;
  vsize   = graph->vsize;
  adjncy  = graph->adjncy;
  adjwgt  = graph->adjwgt;
  vtxdist = graph->vtxdist;
  imap    = graph->imap;

  /*************************************************************/
  /* Determine the # of idxtype to receive from each processor */
  /*************************************************************/
  rcounts = imalloc(ctrl->npes, "AssembleGraph: rcounts");
  switch (ctrl->partType) {
    case STATIC_PARTITION:
      mysize = (1+ncon)*nvtxs + 2*nedges;
      break;
    case ADAPTIVE_PARTITION:
    case REFINE_PARTITION:
      mysize = (2+ncon)*nvtxs + 2*nedges;
      break;
    default:
      printf("WARNING: bad value for ctrl->partType %d\n", ctrl->partType);
      break;
  }
  MPI_Allgather((void *)(&mysize), 1, MPI_INT, (void *)rcounts, 1, MPI_INT, ctrl->comm);

  rdispls = imalloc(ctrl->npes+1, "AssembleGraph: rdispls");
  rdispls[0] = 0;
  for (i=1; i<ctrl->npes+1; i++)
    rdispls[i] = rdispls[i-1] + rcounts[i-1];

  /* Construct the one-array storage format of the assembled graph */
  mygraph = (mysize <= wspace->maxcore ? wspace->core : idxmalloc(mysize, "AssembleGraph: mygraph"));
  for (k=i=0; i<nvtxs; i++) {
    mygraph[k++] = xadj[i+1]-xadj[i];
    for (j=0; j<ncon; j++)
      mygraph[k++] = vwgt[i*ncon+j];
    if (ctrl->partType == ADAPTIVE_PARTITION || ctrl->partType == REFINE_PARTITION)
      mygraph[k++] = vsize[i];
    for (j=xadj[i]; j<xadj[i+1]; j++) {
      mygraph[k++] = imap[adjncy[j]];
      mygraph[k++] = adjwgt[j];
    }
  }
  ASSERT(ctrl, mysize == k);

  /**************************************/
  /* Assemble and send the entire graph */
  /**************************************/
  gsize = rdispls[ctrl->npes];
  ggraph = (gsize <= wspace->maxcore-mysize ? wspace->core+mysize : idxmalloc(gsize, "AssembleGraph: ggraph"));
  MPI_Allgatherv((void *)mygraph, mysize, IDX_DATATYPE, (void *)ggraph, rcounts, rdispls, IDX_DATATYPE, ctrl->comm);

  GKfree((void **)&rcounts, (void **)&rdispls, LTERM);
  if (mysize > wspace->maxcore)
    free(mygraph);

  agraph = CreateGraph();
  agraph->nvtxs = gnvtxs;
  switch (ctrl->partType) {
    case STATIC_PARTITION:
      agraph->nedges = gnedges = (gsize-(1+ncon)*gnvtxs)/2;
      break;
    case ADAPTIVE_PARTITION:
    case REFINE_PARTITION:
      agraph->nedges = gnedges = (gsize-(2+ncon)*gnvtxs)/2;
      break;
    default:
      printf("WARNING: bad value for ctrl->partType %d\n", ctrl->partType);
      agraph->nedges = gnedges = -1;
      break;
  }

  agraph->ncon = ncon;

  /*******************************************/
  /* Allocate memory for the assembled graph */
  /*******************************************/
  axadj = agraph->xadj = idxmalloc(gnvtxs+1, "AssembleGraph: axadj");
  avwgt = agraph->vwgt = idxmalloc(gnvtxs*ncon, "AssembleGraph: avwgt");
  anvwgt = agraph->nvwgt = fmalloc(gnvtxs*ncon, "AssembleGraph: anvwgt");
  aadjncy = agraph->adjncy = idxmalloc(gnedges, "AssembleGraph: adjncy");
  aadjwgt = agraph->adjwgt = idxmalloc(gnedges, "AssembleGraph: adjwgt");
  alabel = agraph->label = idxmalloc(gnvtxs, "AssembleGraph: alabel");
  if (ctrl->partType == ADAPTIVE_PARTITION || ctrl->partType == REFINE_PARTITION)
    avsize = agraph->vsize = idxmalloc(gnvtxs, "AssembleGraph: avsize");

  for (k=j=i=0; i<gnvtxs; i++) {
    axadj[i] = ggraph[k++];
    for (l=0; l<ncon; l++)
      avwgt[i*ncon+l] = ggraph[k++];
    if (ctrl->partType == ADAPTIVE_PARTITION || ctrl->partType == REFINE_PARTITION)
      avsize[i] = ggraph[k++];
    for (l=0; l<axadj[i]; l++) {
      aadjncy[j] = ggraph[k++];
      aadjwgt[j] = ggraph[k++];
      j++;
    }
  }

  /*********************************/
  /* Now fix up the received graph */
  /*********************************/
  MAKECSR(i, gnvtxs, axadj);

  for (i=0; i<gnvtxs; i++)
    for (j=0; j<ncon; j++)
      anvwgt[i*ncon+j] = (float)(agraph->vwgt[i*ncon+j]) / (float)(ctrl->tvwgts[j]);

  for (i=0; i<gnvtxs; i++)
    alabel[i] = i;

  if (gsize > wspace->maxcore-mysize)
    free(ggraph);

  return agraph;
}