From 69f2911e04ffb1b19eef1fafb8c040af271f656e Mon Sep 17 00:00:00 2001
From: Tor Aamodt <aamodt@ece.ubc.ca>
Date: Thu, 15 Jul 2010 18:09:46 -0800
Subject: creating branch for adding support for CUDA 3.x and Fermi

[git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 6829]
---
 .../ParMetis-3.1/ParMETISLib/balancemylink.c       | 342 +++++++++++++++++++++
 1 file changed, 342 insertions(+)
 create mode 100644 benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/ParMETISLib/balancemylink.c

(limited to 'benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/ParMETISLib/balancemylink.c')

diff --git a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/ParMETISLib/balancemylink.c b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/ParMETISLib/balancemylink.c
new file mode 100644
index 0000000..dd944d1
--- /dev/null
+++ b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/ParMETISLib/balancemylink.c
@@ -0,0 +1,342 @@
+/*
+ * Copyright 1997, Regents of the University of Minnesota
+ *
+ * balancemylink.c
+ *
+ * This file contains code that implements the edge-based FM refinement
+ *
+ * Started 7/23/97
+ * George
+ *
+ * $Id: balancemylink.c,v 1.2 2003/07/21 17:18:48 karypis Exp $
+ */
+
+#include <parmetislib.h>
+#define	PE	0
+
+/*************************************************************************
+* This function performs an edge-based FM refinement
+**************************************************************************/
+int BalanceMyLink(CtrlType *ctrl, GraphType *graph, idxtype *home, int me,
+  int you, float *flows, float maxdiff, float *diff_cost, float *diff_lbavg,
+  float avgvwgt)
+{
+  int h, i, ii, j, k;
+  int nvtxs, ncon;
+  int nqueues, minval, maxval, higain, vtx, edge, totalv;
+  int from, to, qnum, index, nchanges, cut, tmp;
+  int pass, nswaps, nmoves, multiplier;
+  idxtype *xadj, *vsize, *adjncy, *adjwgt, *where, *ed, *id;
+  idxtype *hval, *nvpq, *inq, *map, *rmap, *ptr, *myqueue, *changes;
+  float *nvwgt, lbvec[MAXNCON], pwgts[MAXNCON*2], tpwgts[MAXNCON*2], my_wgt[MAXNCON];
+  float newgain, oldgain = 0.0;
+  float lbavg, bestflow, mycost;
+  float ipc_factor, redist_factor, ftmp;
+  FPQueueType *queues;
+int mype;
+MPI_Comm_rank(MPI_COMM_WORLD, &mype);
+
+  nvtxs = graph->nvtxs;
+  ncon = graph->ncon;
+  xadj = graph->xadj;
+  nvwgt = graph->nvwgt;
+  vsize = graph->vsize;
+  adjncy = graph->adjncy;
+  adjwgt = graph->adjwgt;
+  where = graph->where;
+  ipc_factor = ctrl->ipc_factor;
+  redist_factor = ctrl->redist_factor;
+
+  hval = idxmalloc(nvtxs*7, "hval");
+  id = hval + nvtxs;
+  ed = hval + nvtxs*2;
+  map = hval + nvtxs*3;
+  rmap = hval + nvtxs*4;
+  myqueue = hval + nvtxs*5;
+  changes = hval + nvtxs*6;
+
+  sset(ncon*2, 0.0, pwgts);
+  for (h=0; h<ncon; h++) {
+    tpwgts[h] = -1.0 * flows[h];
+    tpwgts[ncon+h] = flows[h];
+  }
+
+  for (i=0; i<nvtxs; i++) {
+    if (where[i] == me) {
+      for (h=0; h<ncon; h++) {
+        tpwgts[h] += nvwgt[i*ncon+h];
+        pwgts[h] += nvwgt[i*ncon+h];
+      }
+    }
+    else {
+      ASSERTS(where[i] == you);
+      for (h=0; h<ncon; h++) {
+        tpwgts[ncon+h] += nvwgt[i*ncon+h];
+        pwgts[ncon+h] += nvwgt[i*ncon+h];
+      }
+    }
+  }
+
+  /* we don't want any tpwgts to be less than zero */
+  for (h=0; h<ncon; h++) {
+    if (tpwgts[h] < 0.0) {
+      tpwgts[ncon+h] += tpwgts[h];
+      tpwgts[h] = 0.0;
+    }
+
+    if (tpwgts[ncon+h] < 0.0) {
+      tpwgts[h] += tpwgts[ncon+h];
+      tpwgts[ncon+h] = 0.0;
+    }
+  }
+
+  /*******************************/
+  /* insert vertices into queues */
+  /*******************************/
+  minval = maxval = 0;
+  multiplier = 1;
+  for (i=0; i<ncon; i++) {
+    multiplier *= (i+1);
+    maxval += i*multiplier;
+    minval += (ncon-1-i)*multiplier;
+  }
+
+  nqueues = maxval-minval+1;
+  nvpq = idxsmalloc(nqueues, 0, "nvpq");
+  ptr = idxmalloc(nqueues+1, "ptr");
+  inq = idxmalloc(nqueues*2, "inq");
+  queues = (FPQueueType *)(GKmalloc(sizeof(FPQueueType)*nqueues*2, "queues"));
+
+  for (i=0; i<nvtxs; i++)
+    hval[i] = Moc_HashVwgts(ncon, nvwgt+i*ncon) - minval;
+
+  for (i=0; i<nvtxs; i++)
+    nvpq[hval[i]]++;
+
+  ptr[0] = 0;
+  for (i=0; i<nqueues; i++)
+    ptr[i+1] = ptr[i] + nvpq[i];
+
+  for (i=0; i<nvtxs; i++) {
+    map[i] = ptr[hval[i]];
+    rmap[ptr[hval[i]]++] = i;
+  }
+
+  for (i=nqueues-1; i>0; i--)
+    ptr[i] = ptr[i-1];
+  ptr[0] = 0;
+
+  /* initialize queues */
+  for (i=0; i<nqueues; i++)
+    if (nvpq[i] > 0) {
+      FPQueueInit(queues+i, nvpq[i]);
+      FPQueueInit(queues+i+nqueues, nvpq[i]);
+    }
+
+  /* compute internal/external degrees */
+  idxset(nvtxs, 0, id);
+  idxset(nvtxs, 0, ed);
+  for (j=0; j<nvtxs; j++)
+    for (k=xadj[j]; k<xadj[j+1]; k++)
+      if (where[adjncy[k]] == where[j])
+        id[j] += adjwgt[k];
+      else 
+        ed[j] += adjwgt[k];
+
+  nswaps = 0;
+  for (pass=0; pass<N_MOC_BAL_PASSES; pass++) {
+    idxset(nvtxs, -1, myqueue); 
+    idxset(nqueues*2, 0, inq);
+
+    /* insert vertices into correct queues */
+    for (j=0; j<nvtxs; j++) {
+      index = (where[j] == me) ? 0 : nqueues;
+
+      newgain = ipc_factor*(float)(ed[j]-id[j]);
+      if (home[j] == me || home[j] == you) {
+        if (where[j] == home[j])
+          newgain -= redist_factor*(float)vsize[j];
+        else
+          newgain += redist_factor*(float)vsize[j];
+      }
+
+      FPQueueInsert(queues+hval[j]+index, map[j]-ptr[hval[j]], newgain);
+      myqueue[j] = (where[j] == me) ? 0 : 1;
+      inq[hval[j]+index]++;
+    }
+
+/*    bestflow = sfavg(ncon, flows); */
+    for (j=0, h=0; h<ncon; h++)
+      if (fabs(flows[h]) > fabs(flows[j])) j = h;
+        bestflow = fabs(flows[j]);
+
+    nchanges = nmoves = 0;
+    for (ii=0; ii<nvtxs/2; ii++) {
+      from = -1;
+      Moc_DynamicSelectQueue(nqueues, ncon, me, you, inq, flows, &from,
+      &qnum, minval, avgvwgt, maxdiff);
+
+      /* can't find a vertex in one subdomain, try the other */
+      if (from != -1 && qnum == -1) {
+        from = (from == me) ? you : me;
+
+        if (from == me) {
+          for (j=0; j<ncon; j++)
+            if (flows[j] > avgvwgt)
+              break;
+        }
+        else {
+          for (j=0; j<ncon; j++)
+            if (flows[j] < -1.0*avgvwgt)
+              break;
+        }
+
+        if (j != ncon)
+          Moc_DynamicSelectQueue(nqueues, ncon, me, you, inq, flows, &from,
+          &qnum, minval, avgvwgt, maxdiff);
+      }
+
+      if (qnum == -1)
+        break;
+
+      to = (from == me) ? you : me;
+      index = (from == me) ? 0 : nqueues;
+      higain = FPQueueGetMax(queues+qnum+index);
+      inq[qnum+index]--;
+      ASSERTS(higain != -1);
+
+      /*****************/
+      /* make the swap */
+      /*****************/
+      vtx = rmap[higain+ptr[qnum]];
+      myqueue[vtx] = -1;
+      where[vtx] = to;
+      nswaps++;
+      nmoves++;
+
+      /* update the flows */
+      for (j=0; j<ncon; j++)
+        flows[j] += (to == me) ? nvwgt[vtx*ncon+j] : -1.0*nvwgt[vtx*ncon+j];
+ 
+/*      ftmp = sfavg(ncon, flows); */
+      for (j=0, h=0; h<ncon; h++)
+        if (fabs(flows[h]) > fabs(flows[j])) j = h;
+          ftmp = fabs(flows[j]);
+
+      if (ftmp < bestflow) {
+        bestflow = ftmp;
+        nchanges = 0;
+      }
+      else {
+        changes[nchanges++] = vtx;
+      }
+
+      SWAP(id[vtx], ed[vtx], tmp);
+
+      for (j=xadj[vtx]; j<xadj[vtx+1]; j++) {
+        edge = adjncy[j];
+
+        /* must compute oldgain before changing id/ed */
+        if (myqueue[edge] != -1) {
+          oldgain = ipc_factor*(float)(ed[edge]-id[edge]);
+          if (home[edge] == me || home[edge] == you) {
+            if (where[edge] == home[edge])
+              oldgain -= redist_factor*(float)vsize[edge];
+            else
+              oldgain += redist_factor*(float)vsize[edge];
+          }
+        }
+
+        tmp = (to == where[edge] ? adjwgt[j] : -adjwgt[j]);
+        INC_DEC(id[edge], ed[edge], tmp);
+
+        if (myqueue[edge] != -1) {
+          newgain = ipc_factor*(float)(ed[edge]-id[edge]);
+          if (home[edge] == me || home[edge] == you) {
+            if (where[edge] == home[edge])
+              newgain -= redist_factor*(float)vsize[edge];
+            else
+              newgain += redist_factor*(float)vsize[edge];
+          }
+
+          FPQueueUpdate(queues+hval[edge]+(nqueues*myqueue[edge]),
+          map[edge]-ptr[hval[edge]], oldgain, newgain);
+        }
+      }
+    }
+
+    /****************************/
+    /* now go back to best flow */
+    /****************************/
+    nswaps -= nchanges;
+    nmoves -= nchanges;
+    for (i=0; i<nchanges; i++) {
+      vtx = changes[i];
+      from = where[vtx];
+      where[vtx] = to = (from == me) ? you : me;
+
+      SWAP(id[vtx], ed[vtx], tmp);
+      for (j=xadj[vtx]; j<xadj[vtx+1]; j++) {
+        edge = adjncy[j];
+        tmp = (to == where[edge] ? adjwgt[j] : -adjwgt[j]);
+        INC_DEC(id[edge], ed[edge], tmp);
+      }
+    }
+
+    for (i=0; i<nqueues; i++) {
+      if (nvpq[i] > 0) {
+        FPQueueReset(queues+i);
+        FPQueueReset(queues+i+nqueues);
+      }
+    }
+
+    if (nmoves == 0)
+      break;
+  }
+
+  /***************************/
+  /* compute 2-way imbalance */
+  /***************************/
+  sset(ncon, 0.0, my_wgt);
+  for (i=0; i<nvtxs; i++)
+    if (where[i] == me)
+      for (h=0; h<ncon; h++)
+        my_wgt[h] += nvwgt[i*ncon+h];
+
+  for (i=0; i<ncon; i++) {
+    ftmp =  (pwgts[i]+pwgts[ncon+i])/2.0;
+    if (ftmp != 0.0)
+      lbvec[i] = fabs(my_wgt[i]-tpwgts[i]) / ftmp;
+    else
+      lbvec[i] = 0.0;
+  }
+  lbavg = savg(ncon, lbvec);
+  *diff_lbavg = lbavg;
+
+  /****************/
+  /* compute cost */
+  /****************/
+  cut = totalv = 0;
+  for (i=0; i<nvtxs; i++) {
+    if (where[i] != home[i])
+      totalv += vsize[i];
+
+      for (j=xadj[i]; j<xadj[i+1]; j++) 
+        if (where[adjncy[j]] != where[i])
+          cut += adjwgt[j];
+  }
+  cut /= 2;
+  mycost = cut*ipc_factor + totalv*redist_factor;
+  *diff_cost = mycost;
+
+  /* free memory */
+  for (i=0; i<nqueues; i++)
+    if (nvpq[i] > 0) {
+      FPQueueFree(queues+i);
+      FPQueueFree(queues+i+nqueues);
+    }
+
+  GKfree((void **)&hval, (void **)&nvpq, (void **)&ptr, (void **)&inq, (void **)&queues, LTERM);
+  return nswaps;
+}
+
-- 
cgit v1.3