From 11b308e7363e937966b035b4891db32b4eece3bf Mon Sep 17 00:00:00 2001 From: Tor Aamodt 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] --- .../DG/3rdParty/ParMetis-3.1/METISLib/subdomains.c | 1295 -------------------- 1 file changed, 1295 deletions(-) delete mode 100644 benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/subdomains.c (limited to 'benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/subdomains.c') diff --git a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/subdomains.c b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/subdomains.c deleted file mode 100644 index 6fc65e7..0000000 --- a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/subdomains.c +++ /dev/null @@ -1,1295 +0,0 @@ -/* - * Copyright 1997, Regents of the University of Minnesota - * - * subdomains.c - * - * This file contains functions that deal with prunning the number of - * adjacent subdomains in KMETIS - * - * Started 7/15/98 - * George - * - * $Id: subdomains.c,v 1.2 2003/07/31 06:14:01 karypis Exp $ - * - */ - -#include - - -/************************************************************************* -* This function performs k-way refinement -**************************************************************************/ -void Random_KWayEdgeRefineMConn(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses, int ffactor) -{ - int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees; - int from, me, to, oldcut, vwgt, gain; - int maxndoms, nadd; - idxtype *xadj, *adjncy, *adjwgt; - idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts; - idxtype *phtable, *pmat, *pmatptr, *ndoms; - EDegreeType *myedegrees; - RInfoType *myrinfo; - - nvtxs = graph->nvtxs; - xadj = graph->xadj; - adjncy = graph->adjncy; - adjwgt = graph->adjwgt; - - bndptr = graph->bndptr; - bndind = graph->bndind; - - where = graph->where; - pwgts = graph->pwgts; - - pmat = ctrl->wspace.pmat; - phtable = idxwspacemalloc(ctrl, nparts); - ndoms = idxwspacemalloc(ctrl, nparts); - - ComputeSubDomainGraph(graph, nparts, pmat, ndoms); - - /* Setup the weight intervals of the various subdomains */ - minwgt = idxwspacemalloc(ctrl, nparts); - maxwgt = idxwspacemalloc(ctrl, nparts); - itpwgts = idxwspacemalloc(ctrl, nparts); - tvwgt = idxsum(nparts, pwgts); - ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt)); - - for (i=0; idbglvl, DBG_REFINE, - printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n", - pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], - 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd, - graph->mincut)); - - for (pass=0; passmincut); - - maxndoms = ndoms[idxamax(nparts, ndoms)]; - - oldcut = graph->mincut; - nbnd = graph->nbnd; - - RandomPermute(nbnd, perm, 1); - for (nmoves=iii=0; iiinbnd; iii++) { - ii = perm[iii]; - if (ii >= nbnd) - continue; - i = bndind[ii]; - - myrinfo = graph->rinfo+i; - - if (myrinfo->ed >= myrinfo->id) { /* Total ED is too high */ - from = where[i]; - vwgt = graph->vwgt[i]; - - if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from]) - continue; /* This cannot be moved! */ - - myedegrees = myrinfo->edegrees; - myndegrees = myrinfo->ndegrees; - - /* Determine the valid domains */ - for (j=0; j maxndoms-1) { - phtable[to] = 0; - nadd = maxndoms; - break; - } - nadd++; - } - } - if (ndoms[to]+nadd > maxndoms) - phtable[to] = 0; - if (nadd == 0) - phtable[to] = 2; - } - - /* Find the first valid move */ - j = myrinfo->id; - for (k=0; kid. Allow good nodes to move */ - if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0) - break; - } - if (k == myndegrees) - continue; /* break out if you did not find a candidate */ - - for (j=k+1; j myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) || - (myedegrees[j].ed == myedegrees[k].ed && - itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])) - k = j; - } - - to = myedegrees[k].pid; - - j = 0; - if (myedegrees[k].ed-myrinfo->id > 0) - j = 1; - else if (myedegrees[k].ed-myrinfo->id == 0) { - if (/*(iii&7) == 0 ||*/ phtable[myedegrees[k].pid] == 2 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from]) - j = 1; - } - if (j == 0) - continue; - - /*===================================================================== - * If we got here, we can now move the vertex from 'from' to 'to' - *======================================================================*/ - graph->mincut -= myedegrees[k].ed-myrinfo->id; - - IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut)); - - /* Update pmat to reflect the move of 'i' */ - pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed); - pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed); - if (pmat[from*nparts+to] == 0) { - ndoms[from]--; - if (ndoms[from]+1 == maxndoms) - maxndoms = ndoms[idxamax(nparts, ndoms)]; - } - if (pmat[to*nparts+from] == 0) { - ndoms[to]--; - if (ndoms[to]+1 == maxndoms) - maxndoms = ndoms[idxamax(nparts, ndoms)]; - } - - /* Update where, weight, and ID/ED information of the vertex you moved */ - where[i] = to; - INC_DEC(pwgts[to], pwgts[from], vwgt); - myrinfo->ed += myrinfo->id-myedegrees[k].ed; - SWAP(myrinfo->id, myedegrees[k].ed, j); - if (myedegrees[k].ed == 0) - myedegrees[k] = myedegrees[--myrinfo->ndegrees]; - else - myedegrees[k].pid = from; - - if (myrinfo->ed-myrinfo->id < 0) - BNDDelete(nbnd, bndind, bndptr, i); - - /* Update the degrees of adjacent vertices */ - for (j=xadj[i]; jrinfo+ii; - if (myrinfo->edegrees == NULL) { - myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree; - ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii]; - } - myedegrees = myrinfo->edegrees; - - ASSERT(CheckRInfo(myrinfo)); - - if (me == from) { - INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]); - - if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1) - BNDInsert(nbnd, bndind, bndptr, ii); - } - else if (me == to) { - INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]); - - if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1) - BNDDelete(nbnd, bndind, bndptr, ii); - } - - /* Remove contribution from the .ed of 'from' */ - if (me != from) { - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == from) { - if (myedegrees[k].ed == adjwgt[j]) - myedegrees[k] = myedegrees[--myrinfo->ndegrees]; - else - myedegrees[k].ed -= adjwgt[j]; - break; - } - } - } - - /* Add contribution to the .ed of 'to' */ - if (me != to) { - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == to) { - myedegrees[k].ed += adjwgt[j]; - break; - } - } - if (k == myrinfo->ndegrees) { - myedegrees[myrinfo->ndegrees].pid = to; - myedegrees[myrinfo->ndegrees++].ed = adjwgt[j]; - } - } - - /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */ - if (me != from && me != to) { - pmat[me*nparts+from] -= adjwgt[j]; - pmat[from*nparts+me] -= adjwgt[j]; - if (pmat[me*nparts+from] == 0) { - ndoms[me]--; - if (ndoms[me]+1 == maxndoms) - maxndoms = ndoms[idxamax(nparts, ndoms)]; - } - if (pmat[from*nparts+me] == 0) { - ndoms[from]--; - if (ndoms[from]+1 == maxndoms) - maxndoms = ndoms[idxamax(nparts, ndoms)]; - } - - if (pmat[me*nparts+to] == 0) { - ndoms[me]++; - if (ndoms[me] > maxndoms) { - IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms)); - maxndoms = ndoms[me]; - } - } - if (pmat[to*nparts+me] == 0) { - ndoms[to]++; - if (ndoms[to] > maxndoms) { - IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms)); - maxndoms = ndoms[to]; - } - } - pmat[me*nparts+to] += adjwgt[j]; - pmat[to*nparts+me] += adjwgt[j]; - } - - ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]); - ASSERT(CheckRInfo(myrinfo)); - - } - nmoves++; - } - } - - graph->nbnd = nbnd; - - IFSET(ctrl->dbglvl, DBG_REFINE, - printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %5d, Vol: %5d, %d\n", - pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], - 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, - graph->mincut, ComputeVolume(graph, where), idxsum(nparts, ndoms))); - - if (graph->mincut == oldcut) - break; - } - - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nvtxs); -} - - - -/************************************************************************* -* This function performs k-way refinement -**************************************************************************/ -void Greedy_KWayEdgeBalanceMConn(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses) -{ - int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves; - int from, me, to, oldcut, vwgt, maxndoms, nadd; - idxtype *xadj, *adjncy, *adjwgt; - idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts; - idxtype *phtable, *pmat, *pmatptr, *ndoms; - EDegreeType *myedegrees; - RInfoType *myrinfo; - PQueueType queue; - - nvtxs = graph->nvtxs; - xadj = graph->xadj; - adjncy = graph->adjncy; - adjwgt = graph->adjwgt; - - bndind = graph->bndind; - bndptr = graph->bndptr; - - where = graph->where; - pwgts = graph->pwgts; - - pmat = ctrl->wspace.pmat; - phtable = idxwspacemalloc(ctrl, nparts); - ndoms = idxwspacemalloc(ctrl, nparts); - - ComputeSubDomainGraph(graph, nparts, pmat, ndoms); - - - /* Setup the weight intervals of the various subdomains */ - minwgt = idxwspacemalloc(ctrl, nparts); - maxwgt = idxwspacemalloc(ctrl, nparts); - itpwgts = idxwspacemalloc(ctrl, nparts); - tvwgt = idxsum(nparts, pwgts); - ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt)); - - for (i=0; iadjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]); - - IFSET(ctrl->dbglvl, DBG_REFINE, - printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n", - pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0], - 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd, - graph->mincut)); - - for (pass=0; passmincut); - - /* Check to see if things are out of balance, given the tolerance */ - for (i=0; i maxwgt[i]) - break; - } - if (i == nparts) /* Things are balanced. Return right away */ - break; - - PQueueReset(&queue); - idxset(nvtxs, -1, moved); - - oldcut = graph->mincut; - nbnd = graph->nbnd; - - RandomPermute(nbnd, perm, 1); - for (ii=0; iirinfo[i].ed - graph->rinfo[i].id); - moved[i] = 2; - } - - maxndoms = ndoms[idxamax(nparts, ndoms)]; - - for (nmoves=0;;) { - if ((i = PQueueGetMax(&queue)) == -1) - break; - moved[i] = 1; - - myrinfo = graph->rinfo+i; - from = where[i]; - vwgt = graph->vwgt[i]; - - if (pwgts[from]-vwgt < minwgt[from]) - continue; /* This cannot be moved! */ - - myedegrees = myrinfo->edegrees; - myndegrees = myrinfo->ndegrees; - - /* Determine the valid domains */ - for (j=0; j maxndoms-1) { - phtable[to] = 0; - nadd = maxndoms; - break; - } - nadd++; - } - } - if (ndoms[to]+nadd > maxndoms) - phtable[to] = 0; - } - - for (k=0; k minwgt[to] && myedegrees[k].ed-myrinfo->id < 0) - continue; - - /*===================================================================== - * If we got here, we can now move the vertex from 'from' to 'to' - *======================================================================*/ - graph->mincut -= myedegrees[k].ed-myrinfo->id; - - IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut)); - - /* Update pmat to reflect the move of 'i' */ - pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed); - pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed); - if (pmat[from*nparts+to] == 0) { - ndoms[from]--; - if (ndoms[from]+1 == maxndoms) - maxndoms = ndoms[idxamax(nparts, ndoms)]; - } - if (pmat[to*nparts+from] == 0) { - ndoms[to]--; - if (ndoms[to]+1 == maxndoms) - maxndoms = ndoms[idxamax(nparts, ndoms)]; - } - - - /* Update where, weight, and ID/ED information of the vertex you moved */ - where[i] = to; - INC_DEC(pwgts[to], pwgts[from], vwgt); - myrinfo->ed += myrinfo->id-myedegrees[k].ed; - SWAP(myrinfo->id, myedegrees[k].ed, j); - if (myedegrees[k].ed == 0) - myedegrees[k] = myedegrees[--myrinfo->ndegrees]; - else - myedegrees[k].pid = from; - - if (myrinfo->ed == 0) - BNDDelete(nbnd, bndind, bndptr, i); - - /* Update the degrees of adjacent vertices */ - for (j=xadj[i]; jrinfo+ii; - if (myrinfo->edegrees == NULL) { - myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree; - ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii]; - } - myedegrees = myrinfo->edegrees; - - ASSERT(CheckRInfo(myrinfo)); - - oldgain = (myrinfo->ed-myrinfo->id); - - if (me == from) { - INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]); - - if (myrinfo->ed > 0 && bndptr[ii] == -1) - BNDInsert(nbnd, bndind, bndptr, ii); - } - else if (me == to) { - INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]); - - if (myrinfo->ed == 0 && bndptr[ii] != -1) - BNDDelete(nbnd, bndind, bndptr, ii); - } - - /* Remove contribution from the .ed of 'from' */ - if (me != from) { - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == from) { - if (myedegrees[k].ed == adjwgt[j]) - myedegrees[k] = myedegrees[--myrinfo->ndegrees]; - else - myedegrees[k].ed -= adjwgt[j]; - break; - } - } - } - - /* Add contribution to the .ed of 'to' */ - if (me != to) { - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == to) { - myedegrees[k].ed += adjwgt[j]; - break; - } - } - if (k == myrinfo->ndegrees) { - myedegrees[myrinfo->ndegrees].pid = to; - myedegrees[myrinfo->ndegrees++].ed = adjwgt[j]; - } - } - - /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */ - if (me != from && me != to) { - pmat[me*nparts+from] -= adjwgt[j]; - pmat[from*nparts+me] -= adjwgt[j]; - if (pmat[me*nparts+from] == 0) { - ndoms[me]--; - if (ndoms[me]+1 == maxndoms) - maxndoms = ndoms[idxamax(nparts, ndoms)]; - } - if (pmat[from*nparts+me] == 0) { - ndoms[from]--; - if (ndoms[from]+1 == maxndoms) - maxndoms = ndoms[idxamax(nparts, ndoms)]; - } - - if (pmat[me*nparts+to] == 0) { - ndoms[me]++; - if (ndoms[me] > maxndoms) { - IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms)); - maxndoms = ndoms[me]; - } - } - if (pmat[to*nparts+me] == 0) { - ndoms[to]++; - if (ndoms[to] > maxndoms) { - IFSET(ctrl->dbglvl, DBG_REFINE, printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms)); - maxndoms = ndoms[to]; - } - } - pmat[me*nparts+to] += adjwgt[j]; - pmat[to*nparts+me] += adjwgt[j]; - } - - /* Update the queue */ - if (me == to || me == from) { - gain = myrinfo->ed-myrinfo->id; - if (moved[ii] == 2) { - if (myrinfo->ed > 0) - PQueueUpdate(&queue, ii, oldgain, gain); - else { - PQueueDelete(&queue, ii, oldgain); - moved[ii] = -1; - } - } - else if (moved[ii] == -1 && myrinfo->ed > 0) { - PQueueInsert(&queue, ii, gain); - moved[ii] = 2; - } - } - - ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]); - ASSERT(CheckRInfo(myrinfo)); - } - nmoves++; - } - - graph->nbnd = nbnd; - - IFSET(ctrl->dbglvl, DBG_REFINE, - printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, %d\n", - pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], - 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut,idxsum(nparts, ndoms))); - } - - PQueueFree(ctrl, &queue); - - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nvtxs); - idxwspacefree(ctrl, nvtxs); - -} - - - - -/************************************************************************* -* This function computes the subdomain graph -**************************************************************************/ -void PrintSubDomainGraph(GraphType *graph, int nparts, idxtype *where) -{ - int i, j, k, me, nvtxs, total, max; - idxtype *xadj, *adjncy, *adjwgt, *pmat; - - nvtxs = graph->nvtxs; - xadj = graph->xadj; - adjncy = graph->adjncy; - adjwgt = graph->adjwgt; - - pmat = idxsmalloc(nparts*nparts, 0, "ComputeSubDomainGraph: pmat"); - - for (i=0; i 0) - k++; - } - total += k; - - if (k > max) - max = k; -/* - printf("%2d -> %2d ", i, k); - for (j=0; j 0) - printf("[%2d %4d] ", j, pmat[i*nparts+j]); - } - printf("\n"); -*/ - } - printf("Total adjacent subdomains: %d, Max: %d\n", total, max); - - free(pmat); -} - - - -/************************************************************************* -* This function computes the subdomain graph -**************************************************************************/ -void ComputeSubDomainGraph(GraphType *graph, int nparts, idxtype *pmat, idxtype *ndoms) -{ - int i, j, k, me, nvtxs, ndegrees; - idxtype *xadj, *adjncy, *adjwgt, *where; - RInfoType *rinfo; - EDegreeType *edegrees; - - nvtxs = graph->nvtxs; - xadj = graph->xadj; - adjncy = graph->adjncy; - adjwgt = graph->adjwgt; - where = graph->where; - rinfo = graph->rinfo; - - idxset(nparts*nparts, 0, pmat); - - for (i=0; i 0) { - me = where[i]; - ndegrees = rinfo[i].ndegrees; - edegrees = rinfo[i].edegrees; - - k = me*nparts; - for (j=0; j 0) - ndoms[i]++; - } - } - -} - - - - - -/************************************************************************* -* This function computes the subdomain graph -**************************************************************************/ -void EliminateSubDomainEdges(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts) -{ - int i, ii, j, k, me, other, nvtxs, total, max, avg, totalout, nind, ncand, ncand2, target, target2, nadd; - int min, move, cpwgt, tvwgt; - idxtype *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *maxpwgt, *pmat, *ndoms, *mypmat, *otherpmat, *ind; - KeyValueType *cand, *cand2; - - nvtxs = graph->nvtxs; - xadj = graph->xadj; - adjncy = graph->adjncy; - vwgt = graph->vwgt; - adjwgt = graph->adjwgt; - - where = graph->where; - pwgts = graph->pwgts; /* We assume that this is properly initialized */ - - maxpwgt = idxwspacemalloc(ctrl, nparts); - ndoms = idxwspacemalloc(ctrl, nparts); - otherpmat = idxwspacemalloc(ctrl, nparts); - ind = idxwspacemalloc(ctrl, nvtxs); - pmat = ctrl->wspace.pmat; - - cand = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand"); - cand2 = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand"); - - /* Compute the pmat matrix and ndoms */ - ComputeSubDomainGraph(graph, nparts, pmat, ndoms); - - - /* Compute the maximum allowed weight for each domain */ - tvwgt = idxsum(nparts, pwgts); - for (i=0; i 0) { - cand2[ncand2].key = mypmat[i]; - cand2[ncand2++].val = i; - } - } - ikeysort(ncand2, cand2); - - move = 0; - for (min=0; min totalout/(2*ndoms[me])) - break; - - other = cand2[min].val; - - /*printf("\tMinOut: %d to %d\n", mypmat[other], other);*/ - - idxset(nparts, 0, otherpmat); - - /* Go and find the vertices in 'other' that are connected in 'me' */ - for (nind=0, i=0; i 0) { - cand[ncand].key = -otherpmat[i]; - cand[ncand++].val = i; - } - } - ikeysort(ncand, cand); - - /* - * Go through and the select the first domain that is common with 'me', and - * does not increase the ndoms[target] higher than my ndoms, subject to the - * maxpwgt constraint. Traversal is done from the mostly connected to the least. - */ - target = target2 = -1; - for (i=0; i 0) { - if (pwgts[k] + cpwgt > maxpwgt[k]) /* Check if balance will go off */ - continue; - - for (j=0; j 0 && ndoms[j] >= ndoms[me]-1 && pmat[nparts*j+k] == 0) - break; - } - if (j == nparts) { /* No bad second level effects */ - for (nadd=0, j=0; j 0 && pmat[nparts*k+j] == 0) - nadd++; - } - - /*printf("\t\tto=%d, nadd=%d, %d\n", k, nadd, ndoms[k]);*/ - if (target2 == -1 && ndoms[k]+nadd < ndoms[me]) { - target2 = k; - } - if (nadd == 0) { - target = k; - break; - } - } - } - } - if (target == -1 && target2 != -1) - target = target2; - - if (target == -1) { - /* printf("\t\tCould not make the move\n");*/ - continue; - } - - /*printf("\t\tMoving to %d\n", target);*/ - - /* Update the partition weights */ - INC_DEC(pwgts[target], pwgts[other], cpwgt); - - MoveGroupMConn(ctrl, graph, ndoms, pmat, nparts, target, nind, ind); - - move = 1; - break; - } - - if (move == 0) - break; - } - - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nvtxs); - - GKfree(&cand, &cand2, LTERM); -} - - -/************************************************************************* -* This function moves a collection of vertices and updates their rinfo -**************************************************************************/ -void MoveGroupMConn(CtrlType *ctrl, GraphType *graph, idxtype *ndoms, idxtype *pmat, - int nparts, int to, int nind, idxtype *ind) -{ - int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees; - int from, me; - idxtype *xadj, *adjncy, *adjwgt; - idxtype *where, *bndptr, *bndind; - EDegreeType *myedegrees; - RInfoType *myrinfo; - - nvtxs = graph->nvtxs; - xadj = graph->xadj; - adjncy = graph->adjncy; - adjwgt = graph->adjwgt; - - where = graph->where; - bndptr = graph->bndptr; - bndind = graph->bndind; - - nbnd = graph->nbnd; - - for (iii=0; iiirinfo+i; - if (myrinfo->edegrees == NULL) { - myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree; - ctrl->wspace.cdegree += xadj[i+1]-xadj[i]; - myrinfo->ndegrees = 0; - } - myedegrees = myrinfo->edegrees; - - /* find the location of 'to' in myrinfo or create it if it is not there */ - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == to) - break; - } - if (k == myrinfo->ndegrees) { - myedegrees[k].pid = to; - myedegrees[k].ed = 0; - myrinfo->ndegrees++; - } - - graph->mincut -= myedegrees[k].ed-myrinfo->id; - - /* Update pmat to reflect the move of 'i' */ - pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed); - pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed); - if (pmat[from*nparts+to] == 0) - ndoms[from]--; - if (pmat[to*nparts+from] == 0) - ndoms[to]--; - - /* Update where, weight, and ID/ED information of the vertex you moved */ - where[i] = to; - myrinfo->ed += myrinfo->id-myedegrees[k].ed; - SWAP(myrinfo->id, myedegrees[k].ed, j); - if (myedegrees[k].ed == 0) - myedegrees[k] = myedegrees[--myrinfo->ndegrees]; - else - myedegrees[k].pid = from; - - if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1) - BNDDelete(nbnd, bndind, bndptr, i); - - /* Update the degrees of adjacent vertices */ - for (j=xadj[i]; jrinfo+ii; - if (myrinfo->edegrees == NULL) { - myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree; - ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii]; - } - myedegrees = myrinfo->edegrees; - - ASSERT(CheckRInfo(myrinfo)); - - if (me == from) { - INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]); - - if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1) - BNDInsert(nbnd, bndind, bndptr, ii); - } - else if (me == to) { - INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]); - - if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1) - BNDDelete(nbnd, bndind, bndptr, ii); - } - - /* Remove contribution from the .ed of 'from' */ - if (me != from) { - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == from) { - if (myedegrees[k].ed == adjwgt[j]) - myedegrees[k] = myedegrees[--myrinfo->ndegrees]; - else - myedegrees[k].ed -= adjwgt[j]; - break; - } - } - } - - /* Add contribution to the .ed of 'to' */ - if (me != to) { - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == to) { - myedegrees[k].ed += adjwgt[j]; - break; - } - } - if (k == myrinfo->ndegrees) { - myedegrees[myrinfo->ndegrees].pid = to; - myedegrees[myrinfo->ndegrees++].ed = adjwgt[j]; - } - } - - /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */ - if (me != from && me != to) { - pmat[me*nparts+from] -= adjwgt[j]; - pmat[from*nparts+me] -= adjwgt[j]; - if (pmat[me*nparts+from] == 0) - ndoms[me]--; - if (pmat[from*nparts+me] == 0) - ndoms[from]--; - - if (pmat[me*nparts+to] == 0) - ndoms[me]++; - if (pmat[to*nparts+me] == 0) - ndoms[to]++; - - pmat[me*nparts+to] += adjwgt[j]; - pmat[to*nparts+me] += adjwgt[j]; - } - - ASSERT(CheckRInfo(myrinfo)); - } - - ASSERT(CheckRInfo(graph->rinfo+i)); - } - - graph->nbnd = nbnd; - -} - - - - -/************************************************************************* -* This function finds all the connected components induced by the -* partitioning vector in wgraph->where and tries to push them around to -* remove some of them -**************************************************************************/ -void EliminateComponents(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor) -{ - int i, ii, j, jj, k, me, nvtxs, tvwgt, first, last, nleft, ncmps, cwgt, other, target, deltawgt; - idxtype *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *maxpwgt; - idxtype *cpvec, *touched, *perm, *todo, *cind, *cptr, *npcmps; - - nvtxs = graph->nvtxs; - xadj = graph->xadj; - adjncy = graph->adjncy; - vwgt = graph->vwgt; - adjwgt = graph->adjwgt; - - where = graph->where; - pwgts = graph->pwgts; - - touched = idxset(nvtxs, 0, idxwspacemalloc(ctrl, nvtxs)); - cptr = idxwspacemalloc(ctrl, nvtxs+1); - cind = idxwspacemalloc(ctrl, nvtxs); - perm = idxwspacemalloc(ctrl, nvtxs); - todo = idxwspacemalloc(ctrl, nvtxs); - maxpwgt = idxwspacemalloc(ctrl, nparts); - cpvec = idxwspacemalloc(ctrl, nparts); - npcmps = idxset(nparts, 0, idxwspacemalloc(ctrl, nparts)); - - for (i=0; i 0) { - if (first == last) { /* Find another starting vertex */ - cptr[++ncmps] = first; - ASSERT(touched[todo[0]] == 0); - i = todo[0]; - cind[last++] = i; - touched[i] = 1; - me = where[i]; - npcmps[me]++; - } - - i = cind[first++]; - k = perm[i]; - j = todo[k] = todo[--nleft]; - perm[j] = k; - - for (j=xadj[i]; j nparts) { /* There are more components than processors */ - /* First determine the max allowed load imbalance */ - tvwgt = idxsum(nparts, pwgts); - for (i=0; i .30*pwgts[me]) - continue; /* Skip the component if it is over 30% of the weight */ - - /* Determine the connectivity */ - idxset(nparts, 0, cpvec); - for (j=cptr[i]; j 0 && (cwgt < deltawgt || pwgts[j] + cwgt < maxpwgt[j])) { - if (target == -1 || cpvec[target] < cpvec[j]) - target = j; - } - } - - /* printf("\tMoving it to %d [%d]\n", target, cpvec[target]);*/ - - if (target != -1) { - /* Assign all the vertices of 'me' to 'target' and update data structures */ - INC_DEC(pwgts[target], pwgts[me], cwgt); - npcmps[me]--; - - MoveGroup(ctrl, graph, nparts, target, i, cptr, cind); - } - } - - } - - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nparts); - idxwspacefree(ctrl, nvtxs); - idxwspacefree(ctrl, nvtxs); - idxwspacefree(ctrl, nvtxs); - idxwspacefree(ctrl, nvtxs); - idxwspacefree(ctrl, nvtxs+1); - -} - - -/************************************************************************* -* This function moves a collection of vertices and updates their rinfo -**************************************************************************/ -void MoveGroup(CtrlType *ctrl, GraphType *graph, int nparts, int to, int gid, idxtype *ptr, idxtype *ind) -{ - int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees; - int from, me; - idxtype *xadj, *adjncy, *adjwgt; - idxtype *where, *bndptr, *bndind; - EDegreeType *myedegrees; - RInfoType *myrinfo; - - nvtxs = graph->nvtxs; - xadj = graph->xadj; - adjncy = graph->adjncy; - adjwgt = graph->adjwgt; - - where = graph->where; - bndptr = graph->bndptr; - bndind = graph->bndind; - - nbnd = graph->nbnd; - - for (iii=ptr[gid]; iiirinfo+i; - if (myrinfo->edegrees == NULL) { - myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree; - ctrl->wspace.cdegree += xadj[i+1]-xadj[i]; - myrinfo->ndegrees = 0; - } - myedegrees = myrinfo->edegrees; - - /* find the location of 'to' in myrinfo or create it if it is not there */ - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == to) - break; - } - if (k == myrinfo->ndegrees) { - myedegrees[k].pid = to; - myedegrees[k].ed = 0; - myrinfo->ndegrees++; - } - - graph->mincut -= myedegrees[k].ed-myrinfo->id; - - - /* Update where, weight, and ID/ED information of the vertex you moved */ - where[i] = to; - myrinfo->ed += myrinfo->id-myedegrees[k].ed; - SWAP(myrinfo->id, myedegrees[k].ed, j); - if (myedegrees[k].ed == 0) - myedegrees[k] = myedegrees[--myrinfo->ndegrees]; - else - myedegrees[k].pid = from; - - if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1) - BNDDelete(nbnd, bndind, bndptr, i); - - /* Update the degrees of adjacent vertices */ - for (j=xadj[i]; jrinfo+ii; - if (myrinfo->edegrees == NULL) { - myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree; - ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii]; - } - myedegrees = myrinfo->edegrees; - - ASSERT(CheckRInfo(myrinfo)); - - if (me == from) { - INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]); - - if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1) - BNDInsert(nbnd, bndind, bndptr, ii); - } - else if (me == to) { - INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]); - - if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1) - BNDDelete(nbnd, bndind, bndptr, ii); - } - - /* Remove contribution from the .ed of 'from' */ - if (me != from) { - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == from) { - if (myedegrees[k].ed == adjwgt[j]) - myedegrees[k] = myedegrees[--myrinfo->ndegrees]; - else - myedegrees[k].ed -= adjwgt[j]; - break; - } - } - } - - /* Add contribution to the .ed of 'to' */ - if (me != to) { - for (k=0; kndegrees; k++) { - if (myedegrees[k].pid == to) { - myedegrees[k].ed += adjwgt[j]; - break; - } - } - if (k == myrinfo->ndegrees) { - myedegrees[myrinfo->ndegrees].pid = to; - myedegrees[myrinfo->ndegrees++].ed = adjwgt[j]; - } - } - - ASSERT(CheckRInfo(myrinfo)); - } - - ASSERT(CheckRInfo(graph->rinfo+i)); - } - - graph->nbnd = nbnd; - -} - -- cgit v1.3