creating branch for adding support for CUDA 3.x and Fermi

[git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 6829]

1 files changed, 468 insertions, 0 deletions

diff --git a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/kwayvolrefine.c b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/kwayvolrefine.c
new file mode 100644
index 0000000..7cf248d
--- /dev/null
+++ b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/kwayvolrefine.c
@@ -0,0 +1,468 @@
+/*
+ * Copyright 1997, Regents of the University of Minnesota
+ *
+ * kwayvolrefine.c
+ *
+ * This file contains the driving routines for multilevel k-way refinement
+ *
+ * Started 7/28/97
+ * George
+ *
+ * $Id: kwayvolrefine.c,v 1.1 2003/07/16 15:55:05 karypis Exp $
+ */
+
+#include <metis.h>
+
+
+/*************************************************************************
+* This function is the entry point of refinement
+**************************************************************************/
+void RefineVolKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, 
+                   float *tpwgts, float ubfactor)
+{
+  int i, nlevels;
+  GraphType *ptr;
+
+  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
+
+  /* Take care any non-contiguity */
+  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr1));
+  if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
+    ComputeVolKWayPartitionParams(ctrl, graph, nparts);
+    EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
+    EliminateVolSubDomainEdges(ctrl, graph, nparts, tpwgts);
+    EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
+  }
+  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr1));
+
+
+  /* Determine how many levels are there */
+  for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++); 
+
+  /* Compute the parameters of the coarsest graph */
+  ComputeVolKWayPartitionParams(ctrl, graph, nparts);
+
+  for (i=0; ;i++) {
+    /*PrintSubDomainGraph(graph, nparts, graph->where);*/
+    MALLOC_CHECK(NULL);
+    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
+
+    if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
+      ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
+      switch (ctrl->RType) {
+        case RTYPE_KWAYRANDOM:
+          Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
+          break;
+        case RTYPE_KWAYRANDOM_MCONN:
+          Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
+          break;
+      }
+      ComputeVolKWayBoundary(ctrl, graph, nparts);
+    }
+
+    switch (ctrl->RType) {
+      case RTYPE_KWAYRANDOM:
+        Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1); 
+        break;
+      case RTYPE_KWAYRANDOM_MCONN:
+        Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1); 
+        break;
+    }
+    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
+
+    if (graph == orggraph)
+      break;
+
+    GKfree(&graph->gdata, LTERM);  /* Deallocate the graph related arrays */
+
+    graph = graph->finer;
+
+    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
+    ProjectVolKWayPartition(ctrl, graph, nparts);
+    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
+  }
+
+  if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
+    ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
+    switch (ctrl->RType) {
+      case RTYPE_KWAYRANDOM:
+        Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
+        Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
+        break;
+      case RTYPE_KWAYRANDOM_MCONN:
+        Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
+        Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
+        break;
+    }
+  }
+
+  EliminateVolComponents(ctrl, graph, nparts, tpwgts, ubfactor); 
+
+  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
+}
+
+
+
+/*************************************************************************
+* This function allocates memory for k-way edge refinement
+**************************************************************************/
+void AllocateVolKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
+{
+  int nvtxs, pad64;
+
+  nvtxs = graph->nvtxs;
+
+  pad64 = (3*nvtxs+nparts)%2;
+
+  graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(VRInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateVolKWayPartitionMemory: rdata");
+  graph->pwgts          = graph->rdata;
+  graph->where          = graph->rdata + nparts;
+  graph->bndptr         = graph->rdata + nvtxs + nparts;
+  graph->bndind         = graph->rdata + 2*nvtxs + nparts;
+  graph->vrinfo          = (VRInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
+
+}
+
+
+
+/*************************************************************************
+* This function computes the initial id/ed 
+**************************************************************************/
+void ComputeVolKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
+{
+  int i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid; 
+  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where;
+  VRInfoType *rinfo, *myrinfo, *orinfo;
+  VEDegreeType *myedegrees, *oedegrees;
+
+  nvtxs = graph->nvtxs;
+  xadj = graph->xadj;
+  vwgt = graph->vwgt;
+  adjncy = graph->adjncy;
+  adjwgt = graph->adjwgt;
+
+  where = graph->where;
+  pwgts = idxset(nparts, 0, graph->pwgts);
+  rinfo = graph->vrinfo;
+
+starttimer(ctrl->AuxTmr1);
+
+  /*------------------------------------------------------------
+  / Compute now the id/ed degrees
+  /------------------------------------------------------------*/
+  ctrl->wspace.cdegree = 0;
+  mincut = 0;
+  for (i=0; i<nvtxs; i++) {
+    me = where[i];
+    pwgts[me] += vwgt[i];
+
+    myrinfo = rinfo+i;
+    myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
+    myrinfo->edegrees = NULL;
+
+    for (j=xadj[i]; j<xadj[i+1]; j++) {
+      if (me == where[adjncy[j]]) {
+        myrinfo->id += adjwgt[j];
+        myrinfo->nid++;
+      }
+    }
+    myrinfo->ed = graph->adjwgtsum[i] - myrinfo->id;
+
+    mincut += myrinfo->ed;
+
+    /* Time to compute the particular external degrees */
+    if (myrinfo->ed > 0) { 
+      myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
+      ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
+
+      for (j=xadj[i]; j<xadj[i+1]; j++) {
+        other = where[adjncy[j]];
+        if (me != other) {
+          for (k=0; k<myrinfo->ndegrees; k++) {
+            if (myedegrees[k].pid == other) {
+              myedegrees[k].ed += adjwgt[j];
+              myedegrees[k].ned++;
+              break;
+            }
+          }
+          if (k == myrinfo->ndegrees) {
+            myedegrees[myrinfo->ndegrees].gv = 0;
+            myedegrees[myrinfo->ndegrees].pid = other;
+            myedegrees[myrinfo->ndegrees].ed = adjwgt[j];
+            myedegrees[myrinfo->ndegrees++].ned = 1;
+          }
+        }
+      }
+
+      ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
+    }
+  }
+  graph->mincut = mincut/2;
+
+stoptimer(ctrl->AuxTmr1);
+
+  ComputeKWayVolGains(ctrl, graph, nparts);
+
+}
+
+
+
+/*************************************************************************
+* This function computes the initial id/ed 
+**************************************************************************/
+void ComputeKWayVolGains(CtrlType *ctrl, GraphType *graph, int nparts)
+{
+  int i, ii, j, k, kk, l, nvtxs, me, other, pid, myndegrees; 
+  idxtype *xadj, *vsize, *adjncy, *adjwgt, *where, *bndind, *bndptr, *ophtable;
+  VRInfoType *rinfo, *myrinfo, *orinfo;
+  VEDegreeType *myedegrees, *oedegrees;
+
+  nvtxs = graph->nvtxs;
+  xadj = graph->xadj;
+  vsize = graph->vsize;
+  adjncy = graph->adjncy;
+  adjwgt = graph->adjwgt;
+
+  where = graph->where;
+  bndind = graph->bndind;
+  bndptr = idxset(nvtxs, -1, graph->bndptr);
+  rinfo = graph->vrinfo;
+
+starttimer(ctrl->AuxTmr2);
+
+  ophtable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
+
+  /*------------------------------------------------------------
+  / Compute now the iv/ev degrees
+  /------------------------------------------------------------*/
+  graph->minvol = graph->nbnd = 0;
+  for (i=0; i<nvtxs; i++) {
+    myrinfo = rinfo+i;
+    myrinfo->gv = -MAXIDX;
+
+    if (myrinfo->ndegrees > 0) {
+      me = where[i];
+      myedegrees = myrinfo->edegrees;
+      myndegrees = myrinfo->ndegrees;
+
+      graph->minvol += myndegrees*vsize[i];
+
+      for (j=xadj[i]; j<xadj[i+1]; j++) {
+        ii = adjncy[j];
+        other = where[ii];
+        orinfo = rinfo+ii;
+        oedegrees = orinfo->edegrees;
+
+        for (k=0; k<orinfo->ndegrees; k++) 
+          ophtable[oedegrees[k].pid] = k;
+        ophtable[other] = 1;  /* this is to simplify coding */
+
+        if (me == other) {
+          /* Find which domains 'i' is connected and 'ii' is not and update their gain */
+          for (k=0; k<myndegrees; k++) {
+            if (ophtable[myedegrees[k].pid] == -1)
+              myedegrees[k].gv -= vsize[ii];
+          }
+        }
+        else {
+          ASSERT(ophtable[me] != -1);
+
+          if (oedegrees[ophtable[me]].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
+            /* Increase the gains for all the common domains between 'i' and 'ii' */
+            for (k=0; k<myndegrees; k++) {
+              if (ophtable[myedegrees[k].pid] != -1) 
+                myedegrees[k].gv += vsize[ii];
+            }
+          }
+          else {
+            /* Find which domains 'i' is connected and 'ii' is not and update their gain */
+            for (k=0; k<myndegrees; k++) {
+              if (ophtable[myedegrees[k].pid] == -1) 
+                myedegrees[k].gv -= vsize[ii];
+            }
+          }
+        }
+
+        for (kk=0; kk<orinfo->ndegrees; kk++) 
+          ophtable[oedegrees[kk].pid] = -1;
+        ophtable[other] = -1;
+      }
+
+      /* Compute the max vgain */
+      for (k=0; k<myndegrees; k++) {
+        if (myedegrees[k].gv > myrinfo->gv)
+          myrinfo->gv = myedegrees[k].gv;
+      }
+    }
+
+    if (myrinfo->ed > 0 && myrinfo->id == 0) 
+      myrinfo->gv += vsize[i];
+
+    if (myrinfo->gv >= 0 || myrinfo->ed-myrinfo->id >= 0)
+      BNDInsert(graph->nbnd, bndind, bndptr, i);
+  }
+
+stoptimer(ctrl->AuxTmr2);
+
+  idxwspacefree(ctrl, nparts);
+
+}
+
+
+
+/*************************************************************************
+* This function projects a partition, and at the same time computes the
+* parameters for refinement.
+**************************************************************************/
+void ProjectVolKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
+{
+  int i, j, k, nvtxs, me, other, istart, iend, ndegrees;
+  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
+  idxtype *cmap, *where;
+  idxtype *cwhere;
+  GraphType *cgraph;
+  VRInfoType *crinfo, *rinfo, *myrinfo;
+  VEDegreeType *myedegrees;
+  idxtype *htable;
+
+  cgraph = graph->coarser;
+  cwhere = cgraph->where;
+  crinfo = cgraph->vrinfo;
+
+  nvtxs = graph->nvtxs;
+  cmap = graph->cmap;
+  xadj = graph->xadj;
+  adjncy = graph->adjncy;
+  adjwgt = graph->adjwgt;
+  adjwgtsum = graph->adjwgtsum;
+
+  AllocateVolKWayPartitionMemory(ctrl, graph, nparts);
+  where = graph->where;
+  rinfo = graph->vrinfo;
+
+  /* Go through and project partition and compute id/ed for the nodes */
+  for (i=0; i<nvtxs; i++) {
+    k = cmap[i];
+    where[i] = cwhere[k];
+    cmap[i] = crinfo[k].ed;  /* For optimization */
+  }
+
+  htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
+
+  ctrl->wspace.cdegree = 0;
+  for (i=0; i<nvtxs; i++) {
+    me = where[i];
+
+    myrinfo = rinfo+i;
+    myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
+    myrinfo->edegrees = NULL;
+
+    myrinfo->id = adjwgtsum[i];
+    myrinfo->nid = xadj[i+1]-xadj[i];
+
+    if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
+      istart = xadj[i];
+      iend = xadj[i+1];
+
+      myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
+      ctrl->wspace.cdegree += iend-istart;
+
+      ndegrees = 0;
+      for (j=istart; j<iend; j++) {
+        other = where[adjncy[j]];
+        if (me != other) {
+          myrinfo->ed += adjwgt[j];
+          myrinfo->nid--;
+          if ((k = htable[other]) == -1) {
+            htable[other] = ndegrees;
+            myedegrees[ndegrees].gv = 0;
+            myedegrees[ndegrees].pid = other;
+            myedegrees[ndegrees].ed = adjwgt[j];
+            myedegrees[ndegrees++].ned = 1;
+          }
+          else {
+            myedegrees[k].ed += adjwgt[j];
+            myedegrees[k].ned++;
+          }
+        }
+      }
+      myrinfo->id -= myrinfo->ed;
+
+      /* Remove space for edegrees if it was interior */
+      if (myrinfo->ed == 0) { 
+        myrinfo->edegrees = NULL;
+        ctrl->wspace.cdegree -= iend-istart;
+      }
+      else {
+        myrinfo->ndegrees = ndegrees;
+
+        for (j=0; j<ndegrees; j++)
+          htable[myedegrees[j].pid] = -1;
+      }
+    }
+  }
+
+  ComputeKWayVolGains(ctrl, graph, nparts);
+
+  idxcopy(nparts, cgraph->pwgts, graph->pwgts);
+  graph->mincut = cgraph->mincut;
+
+  FreeGraph(graph->coarser);
+  graph->coarser = NULL;
+
+  idxwspacefree(ctrl, nparts);
+
+}
+
+
+
+/*************************************************************************
+* This function computes the boundary definition for balancing
+**************************************************************************/
+void ComputeVolKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
+{
+  int i, nvtxs, nbnd;
+  idxtype *bndind, *bndptr;
+
+  nvtxs = graph->nvtxs;
+  bndind = graph->bndind;
+  bndptr = idxset(nvtxs, -1, graph->bndptr);
+
+
+  /*------------------------------------------------------------
+  / Compute the new boundary
+  /------------------------------------------------------------*/
+  nbnd = 0;
+  for (i=0; i<nvtxs; i++) {
+    if (graph->vrinfo[i].gv >=0 || graph->vrinfo[i].ed-graph->vrinfo[i].id >= 0) 
+      BNDInsert(nbnd, bndind, bndptr, i);
+  }
+
+  graph->nbnd = nbnd;
+}
+
+/*************************************************************************
+* This function computes the boundary definition for balancing
+**************************************************************************/
+void ComputeVolKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
+{
+  int i, nvtxs, nbnd;
+  idxtype *bndind, *bndptr;
+
+  nvtxs = graph->nvtxs;
+  bndind = graph->bndind;
+  bndptr = idxset(nvtxs, -1, graph->bndptr);
+
+
+  /*------------------------------------------------------------
+  / Compute the new boundary
+  /------------------------------------------------------------*/
+  nbnd = 0;
+  for (i=0; i<nvtxs; i++) {
+    if (graph->vrinfo[i].ed > 0) 
+      BNDInsert(nbnd, bndind, bndptr, i);
+  }
+
+  graph->nbnd = nbnd;
+}
+