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]
---
 .../CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c | 267 +++++++++++++++++++++
 1 file changed, 267 insertions(+)
 create mode 100644 benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c

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

diff --git a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c
new file mode 100644
index 0000000..509f457
--- /dev/null
+++ b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c
@@ -0,0 +1,267 @@
+/*
+ * Copyright 1997, Regents of the University of Minnesota
+ *
+ * match.c
+ *
+ * This file contains the code that computes matchings and creates the next
+ * level coarse graph.
+ *
+ * Started 7/23/97
+ * George
+ *
+ * $Id: match.c,v 1.1 2003/07/16 15:55:06 karypis Exp $
+ *
+ */
+
+#include <metis.h>
+
+
+/*************************************************************************
+* This function finds a matching using the HEM heuristic
+**************************************************************************/
+void Match_RM(CtrlType *ctrl, GraphType *graph)
+{
+  int i, ii, j, nvtxs, cnvtxs, maxidx;
+  idxtype *xadj, *vwgt, *adjncy, *adjwgt;
+  idxtype *match, *cmap, *perm;
+
+  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
+
+  nvtxs = graph->nvtxs;
+  xadj = graph->xadj;
+  vwgt = graph->vwgt;
+  adjncy = graph->adjncy;
+  adjwgt = graph->adjwgt;
+
+  cmap = graph->cmap;
+  match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
+
+  perm = idxwspacemalloc(ctrl, nvtxs);
+  RandomPermute(nvtxs, perm, 1);
+
+  cnvtxs = 0;
+  for (ii=0; ii<nvtxs; ii++) {
+    i = perm[ii];
+
+    if (match[i] == UNMATCHED) {  /* Unmatched */
+      maxidx = i;
+
+      /* Find a random matching, subject to maxvwgt constraints */
+      for (j=xadj[i]; j<xadj[i+1]; j++) {
+        if (match[adjncy[j]] == UNMATCHED && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
+          maxidx = adjncy[j];
+          break;
+        }
+      }
+
+      cmap[i] = cmap[maxidx] = cnvtxs++;
+      match[i] = maxidx;
+      match[maxidx] = i;
+    }
+  }
+
+  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
+
+  CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
+
+  idxwspacefree(ctrl, nvtxs);
+  idxwspacefree(ctrl, nvtxs);
+}
+
+
+/*************************************************************************
+* This function finds a matching using the HEM heuristic
+**************************************************************************/
+void Match_RM_NVW(CtrlType *ctrl, GraphType *graph)
+{
+  int i, ii, j, nvtxs, cnvtxs, maxidx;
+  idxtype *xadj, *adjncy;
+  idxtype *match, *cmap, *perm;
+
+  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
+
+  nvtxs = graph->nvtxs;
+  xadj = graph->xadj;
+  adjncy = graph->adjncy;
+
+  cmap = graph->cmap;
+  match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
+
+  perm = idxwspacemalloc(ctrl, nvtxs);
+  RandomPermute(nvtxs, perm, 1);
+
+  cnvtxs = 0;
+  for (ii=0; ii<nvtxs; ii++) {
+    i = perm[ii];
+
+    if (match[i] == UNMATCHED) {  /* Unmatched */
+      maxidx = i;
+
+      /* Find a random matching, subject to maxvwgt constraints */
+      for (j=xadj[i]; j<xadj[i+1]; j++) {
+        if (match[adjncy[j]] == UNMATCHED) {
+          maxidx = adjncy[j];
+          break;
+        }
+      }
+
+      cmap[i] = cmap[maxidx] = cnvtxs++;
+      match[i] = maxidx;
+      match[maxidx] = i;
+    }
+  }
+
+  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
+
+  CreateCoarseGraph_NVW(ctrl, graph, cnvtxs, match, perm);
+
+  idxwspacefree(ctrl, nvtxs);
+  idxwspacefree(ctrl, nvtxs);
+}
+
+
+
+/*************************************************************************
+* This function finds a matching using the HEM heuristic
+**************************************************************************/
+void Match_HEM(CtrlType *ctrl, GraphType *graph)
+{
+  int i, ii, j, k, nvtxs, cnvtxs, maxidx, maxwgt;
+  idxtype *xadj, *vwgt, *adjncy, *adjwgt;
+  idxtype *match, *cmap, *perm;
+
+  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
+
+  nvtxs = graph->nvtxs;
+  xadj = graph->xadj;
+  vwgt = graph->vwgt;
+  adjncy = graph->adjncy;
+  adjwgt = graph->adjwgt;
+
+  cmap = graph->cmap;
+  match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
+
+  perm = idxwspacemalloc(ctrl, nvtxs);
+  RandomPermute(nvtxs, perm, 1);
+
+  cnvtxs = 0;
+  for (ii=0; ii<nvtxs; ii++) {
+    i = perm[ii];
+
+    if (match[i] == UNMATCHED) {  /* Unmatched */
+      maxidx = i;
+      maxwgt = 0;
+
+      /* Find a heavy-edge matching, subject to maxvwgt constraints */
+      for (j=xadj[i]; j<xadj[i+1]; j++) {
+        k = adjncy[j];
+        if (match[k] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[k] <= ctrl->maxvwgt) {
+          maxwgt = adjwgt[j];
+          maxidx = adjncy[j];
+        }
+      }
+
+      cmap[i] = cmap[maxidx] = cnvtxs++;
+      match[i] = maxidx;
+      match[maxidx] = i;
+    }
+  }
+
+  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
+
+  CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
+
+  idxwspacefree(ctrl, nvtxs);
+  idxwspacefree(ctrl, nvtxs);
+}
+
+
+
+/*************************************************************************
+* This function finds a matching using the HEM heuristic
+**************************************************************************/
+void Match_SHEM(CtrlType *ctrl, GraphType *graph)
+{
+  int i, ii, j, k, nvtxs, cnvtxs, maxidx, maxwgt, avgdegree;
+  idxtype *xadj, *vwgt, *adjncy, *adjwgt;
+  idxtype *match, *cmap, *degrees, *perm, *tperm;
+
+  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
+
+  nvtxs = graph->nvtxs;
+  xadj = graph->xadj;
+  vwgt = graph->vwgt;
+  adjncy = graph->adjncy;
+  adjwgt = graph->adjwgt;
+
+  cmap = graph->cmap;
+  match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
+
+  perm = idxwspacemalloc(ctrl, nvtxs);
+  tperm = idxwspacemalloc(ctrl, nvtxs);
+  degrees = idxwspacemalloc(ctrl, nvtxs);
+
+  RandomPermute(nvtxs, tperm, 1);
+  avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
+  for (i=0; i<nvtxs; i++) 
+    degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
+  BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);
+
+  cnvtxs = 0;
+
+  /* Take care any islands. Islands are matched with non-islands due to coarsening */
+  for (ii=0; ii<nvtxs; ii++) {
+    i = perm[ii];
+
+    if (match[i] == UNMATCHED) {  /* Unmatched */
+      if (xadj[i] < xadj[i+1])
+        break;
+
+      maxidx = i;
+      for (j=nvtxs-1; j>ii; j--) {
+        k = perm[j];
+        if (match[k] == UNMATCHED && xadj[k] < xadj[k+1]) {
+          maxidx = k;
+          break;
+        }
+      }
+
+      cmap[i] = cmap[maxidx] = cnvtxs++;
+      match[i] = maxidx;
+      match[maxidx] = i;
+    }
+  }
+
+  /* Continue with normal matching */
+  for (; ii<nvtxs; ii++) {
+    i = perm[ii];
+
+    if (match[i] == UNMATCHED) {  /* Unmatched */
+      maxidx = i;
+      maxwgt = 0;
+
+      /* Find a heavy-edge matching, subject to maxvwgt constraints */
+      for (j=xadj[i]; j<xadj[i+1]; j++) {
+        if (match[adjncy[j]] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
+          maxwgt = adjwgt[j];
+          maxidx = adjncy[j];
+        }
+      }
+
+      cmap[i] = cmap[maxidx] = cnvtxs++;
+      match[i] = maxidx;
+      match[maxidx] = i;
+    }
+  }
+
+  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
+
+  idxwspacefree(ctrl, nvtxs);  /* degrees */
+  idxwspacefree(ctrl, nvtxs);  /* tperm */
+
+  CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
+
+  idxwspacefree(ctrl, nvtxs);
+  idxwspacefree(ctrl, nvtxs);
+}
+
-- 
cgit v1.3