From 11b308e7363e937966b035b4891db32b4eece3bf Mon Sep 17 00:00:00 2001
From: Tor Aamodt <aamodt@ece.ubc.ca>
Date: Fri, 1 Oct 2010 08:55:28 -0800
Subject: integrating recent changes from fermi-test into fermi (i'll use
 "fermi" for more disruptive changes to the pipeline model such as updating
 the MSHRs and getting rid of the warp tracker, ripping out DWF, etc...)

[git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 7805]
---
 .../ParMetis-3.1/ParMETISLib/balancemylink.c       | 342 ---------------------
 1 file changed, 342 deletions(-)
 delete 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
deleted file mode 100644
index dd944d1..0000000
--- a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/ParMETISLib/balancemylink.c
+++ /dev/null
@@ -1,342 +0,0 @@
-/*
- * 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