Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
kwayvolrefine.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * kwayvolrefine.c
5  *
6  * This file contains the driving routines for multilevel k-way refinement
7  *
8  * Started 7/28/97
9  * George
10  *
11  * $Id: kwayvolrefine.c,v 1.2 1998/11/30 16:13:57 karypis Exp $
12  */
13 
14 #include <metis.h>
15 
16 
17 /*************************************************************************
18 * This function is the entry point of refinement
19 **************************************************************************/
20 void RefineVolKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts,
21  float *tpwgts, float ubfactor)
22 {
23  int i, nlevels;
24  GraphType *ptr;
25 
27 
28  /* Take care any non-contiguity */
29  if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
30  ComputeVolKWayPartitionParams(ctrl, graph, nparts);
31  EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
32  EliminateVolSubDomainEdges(ctrl, graph, nparts, tpwgts);
33  EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
34  }
35 
36 
37  /* Determine how many levels are there */
38  for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++);
39 
40  /* Compute the parameters of the coarsest graph */
41  ComputeVolKWayPartitionParams(ctrl, graph, nparts);
42 
43  for (i=0; ;i++) {
44  /*PrintSubDomainGraph(graph, nparts, graph->where);*/
45  MALLOC_CHECK(NULL);
46  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
47 
48  if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
49  ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
50  switch (ctrl->RType) {
51  case RTYPE_KWAYRANDOM:
52  Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1);
53  break;
55  Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1);
56  break;
57  }
58  ComputeVolKWayBoundary(ctrl, graph, nparts);
59  }
60 
61  switch (ctrl->RType) {
62  case RTYPE_KWAYRANDOM:
63  Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
64  break;
66  Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
67  break;
68  }
69  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
70 
71  if (graph == orggraph)
72  break;
73 
74  GKfree(&graph->gdata, LTERM); /* Deallocate the graph related arrays */
75 
76  graph = graph->finer;
77 
78  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
79  ProjectVolKWayPartition(ctrl, graph, nparts);
80  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
81  }
82 
83  if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
84  ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
85  switch (ctrl->RType) {
86  case RTYPE_KWAYRANDOM:
87  Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8);
88  Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
89  break;
91  Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8);
92  Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
93  break;
94  }
95  }
96 
97  EliminateVolComponents(ctrl, graph, nparts, tpwgts, ubfactor);
98 
99  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
100 }
101 
102 
103 
104 /*************************************************************************
105 * This function allocates memory for k-way edge refinement
106 **************************************************************************/
108 {
109  int nvtxs, pad64;
110 
111  nvtxs = graph->nvtxs;
112 
113  pad64 = (3*nvtxs+nparts)%2;
114 
115  graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(VRInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateVolKWayPartitionMemory: rdata");
116  graph->pwgts = graph->rdata;
117  graph->where = graph->rdata + nparts;
118  graph->bndptr = graph->rdata + nvtxs + nparts;
119  graph->bndind = graph->rdata + 2*nvtxs + nparts;
120  graph->vrinfo = (VRInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
121 
122 }
123 
124 
125 
126 /*************************************************************************
127 * This function computes the initial id/ed
128 **************************************************************************/
130 {
131  int i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid;
132  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where;
133  VRInfoType *rinfo, *myrinfo, *orinfo;
134  VEDegreeType *myedegrees, *oedegrees;
135 
136  nvtxs = graph->nvtxs;
137  xadj = graph->xadj;
138  vwgt = graph->vwgt;
139  adjncy = graph->adjncy;
140  adjwgt = graph->adjwgt;
141 
142  where = graph->where;
143  pwgts = idxset(nparts, 0, graph->pwgts);
144  rinfo = graph->vrinfo;
145 
146 
147  /*------------------------------------------------------------
148  / Compute now the id/ed degrees
149  /------------------------------------------------------------*/
150  ctrl->wspace.cdegree = 0;
151  mincut = 0;
152  for (i=0; i<nvtxs; i++) {
153  me = where[i];
154  pwgts[me] += vwgt[i];
155 
156  myrinfo = rinfo+i;
157  myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
158  myrinfo->edegrees = NULL;
159 
160  for (j=xadj[i]; j<xadj[i+1]; j++) {
161  if (me == where[adjncy[j]]) {
162  myrinfo->id += adjwgt[j];
163  myrinfo->nid++;
164  }
165  }
166  myrinfo->ed = graph->adjwgtsum[i] - myrinfo->id;
167 
168  mincut += myrinfo->ed;
169 
170  /* Time to compute the particular external degrees */
171  if (myrinfo->ed > 0) {
172  myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
173  ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
174 
175  for (j=xadj[i]; j<xadj[i+1]; j++) {
176  other = where[adjncy[j]];
177  if (me != other) {
178  for (k=0; k<myrinfo->ndegrees; k++) {
179  if (myedegrees[k].pid == other) {
180  myedegrees[k].ed += adjwgt[j];
181  myedegrees[k].ned++;
182  break;
183  }
184  }
185  if (k == myrinfo->ndegrees) {
186  myedegrees[myrinfo->ndegrees].gv = 0;
187  myedegrees[myrinfo->ndegrees].pid = other;
188  myedegrees[myrinfo->ndegrees].ed = adjwgt[j];
189  myedegrees[myrinfo->ndegrees++].ned = 1;
190  }
191  }
192  }
193 
194  ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
195  }
196  }
197  graph->mincut = mincut/2;
198 
199 
200  ComputeKWayVolGains(ctrl, graph, nparts);
201 
202 }
203 
204 
205 
206 /*************************************************************************
207 * This function computes the initial id/ed
208 **************************************************************************/
209 void ComputeKWayVolGains(CtrlType *ctrl, GraphType *graph, int nparts)
210 {
211  int i, ii, j, k, kk, l, nvtxs, me, other, pid, myndegrees;
212  idxtype *xadj, *vsize, *adjncy, *adjwgt, *where, *bndind, *bndptr, *ophtable;
213  VRInfoType *rinfo, *myrinfo, *orinfo;
214  VEDegreeType *myedegrees, *oedegrees;
215 
216  nvtxs = graph->nvtxs;
217  xadj = graph->xadj;
218  vsize = graph->vsize;
219  adjncy = graph->adjncy;
220  adjwgt = graph->adjwgt;
221 
222  where = graph->where;
223  bndind = graph->bndind;
224  bndptr = idxset(nvtxs, -1, graph->bndptr);
225  rinfo = graph->vrinfo;
226 
227  ophtable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
228 
229  /*------------------------------------------------------------
230  / Compute now the iv/ev degrees
231  /------------------------------------------------------------*/
232  graph->minvol = graph->nbnd = 0;
233  for (i=0; i<nvtxs; i++) {
234  myrinfo = rinfo+i;
235  myrinfo->gv = -MAXIDX;
236 
237  if (myrinfo->ndegrees > 0) {
238  me = where[i];
239  myedegrees = myrinfo->edegrees;
240  myndegrees = myrinfo->ndegrees;
241 
242  graph->minvol += myndegrees*vsize[i];
243 
244  for (j=xadj[i]; j<xadj[i+1]; j++) {
245  ii = adjncy[j];
246  other = where[ii];
247  orinfo = rinfo+ii;
248  oedegrees = orinfo->edegrees;
249 
250  for (k=0; k<orinfo->ndegrees; k++)
251  ophtable[oedegrees[k].pid] = k;
252  ophtable[other] = 1; /* this is to simplify coding */
253 
254  if (me == other) {
255  /* Find which domains 'i' is connected and 'ii' is not and update their gain */
256  for (k=0; k<myndegrees; k++) {
257  if (ophtable[myedegrees[k].pid] == -1)
258  myedegrees[k].gv -= vsize[ii];
259  }
260  }
261  else {
262  ASSERT(ophtable[me] != -1);
263 
264  if (oedegrees[ophtable[me]].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
265  /* Increase the gains for all the common domains between 'i' and 'ii' */
266  for (k=0; k<myndegrees; k++) {
267  if (ophtable[myedegrees[k].pid] != -1)
268  myedegrees[k].gv += vsize[ii];
269  }
270  }
271  else {
272  /* Find which domains 'i' is connected and 'ii' is not and update their gain */
273  for (k=0; k<myndegrees; k++) {
274  if (ophtable[myedegrees[k].pid] == -1)
275  myedegrees[k].gv -= vsize[ii];
276  }
277  }
278  }
279 
280  for (kk=0; kk<orinfo->ndegrees; kk++)
281  ophtable[oedegrees[kk].pid] = -1;
282  ophtable[other] = -1;
283  }
284 
285  /* Compute the max vgain */
286  for (k=0; k<myndegrees; k++) {
287  if (myedegrees[k].gv > myrinfo->gv)
288  myrinfo->gv = myedegrees[k].gv;
289  }
290  }
291 
292  if (myrinfo->ed > 0 && myrinfo->id == 0)
293  myrinfo->gv += vsize[i];
294 
295  if (myrinfo->gv >= 0 || myrinfo->ed-myrinfo->id >= 0)
296  BNDInsert(graph->nbnd, bndind, bndptr, i);
297  }
298 
299  idxwspacefree(ctrl, nparts);
300 
301 }
302 
303 
304 
305 /*************************************************************************
306 * This function projects a partition, and at the same time computes the
307 * parameters for refinement.
308 **************************************************************************/
310 {
311  int i, j, k, nvtxs, me, other, istart, iend, ndegrees;
312  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
313  idxtype *cmap, *where;
314  idxtype *cwhere;
315  GraphType *cgraph;
316  VRInfoType *crinfo, *rinfo, *myrinfo;
317  VEDegreeType *myedegrees;
318  idxtype *htable;
319 
320  cgraph = graph->coarser;
321  cwhere = cgraph->where;
322  crinfo = cgraph->vrinfo;
323 
324  nvtxs = graph->nvtxs;
325  cmap = graph->cmap;
326  xadj = graph->xadj;
327  adjncy = graph->adjncy;
328  adjwgt = graph->adjwgt;
329  adjwgtsum = graph->adjwgtsum;
330 
331  AllocateVolKWayPartitionMemory(ctrl, graph, nparts);
332  where = graph->where;
333  rinfo = graph->vrinfo;
334 
335  /* Go through and project partition and compute id/ed for the nodes */
336  for (i=0; i<nvtxs; i++) {
337  k = cmap[i];
338  where[i] = cwhere[k];
339  cmap[i] = crinfo[k].ed; /* For optimization */
340  }
341 
342  htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
343 
344  ctrl->wspace.cdegree = 0;
345  for (i=0; i<nvtxs; i++) {
346  me = where[i];
347 
348  myrinfo = rinfo+i;
349  myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
350  myrinfo->edegrees = NULL;
351 
352  myrinfo->id = adjwgtsum[i];
353  myrinfo->nid = xadj[i+1]-xadj[i];
354 
355  if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
356  istart = xadj[i];
357  iend = xadj[i+1];
358 
359  myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
360  ctrl->wspace.cdegree += iend-istart;
361 
362  ndegrees = 0;
363  for (j=istart; j<iend; j++) {
364  other = where[adjncy[j]];
365  if (me != other) {
366  myrinfo->ed += adjwgt[j];
367  myrinfo->nid--;
368  if ((k = htable[other]) == -1) {
369  htable[other] = ndegrees;
370  myedegrees[ndegrees].gv = 0;
371  myedegrees[ndegrees].pid = other;
372  myedegrees[ndegrees].ed = adjwgt[j];
373  myedegrees[ndegrees++].ned = 1;
374  }
375  else {
376  myedegrees[k].ed += adjwgt[j];
377  myedegrees[k].ned++;
378  }
379  }
380  }
381  myrinfo->id -= myrinfo->ed;
382 
383  /* Remove space for edegrees if it was interior */
384  if (myrinfo->ed == 0) {
385  myrinfo->edegrees = NULL;
386  ctrl->wspace.cdegree -= iend-istart;
387  }
388  else {
389  myrinfo->ndegrees = ndegrees;
390 
391  for (j=0; j<ndegrees; j++)
392  htable[myedegrees[j].pid] = -1;
393  }
394  }
395  }
396 
397  ComputeKWayVolGains(ctrl, graph, nparts);
398 
399  idxcopy(nparts, cgraph->pwgts, graph->pwgts);
400  graph->mincut = cgraph->mincut;
401 
402  FreeGraph(graph->coarser);
403  graph->coarser = NULL;
404 
405  idxwspacefree(ctrl, nparts);
406 
407 }
408 
409 
410 
411 /*************************************************************************
412 * This function computes the boundary definition for balancing
413 **************************************************************************/
415 {
416  int i, nvtxs, nbnd;
417  idxtype *bndind, *bndptr;
418 
419  nvtxs = graph->nvtxs;
420  bndind = graph->bndind;
421  bndptr = idxset(nvtxs, -1, graph->bndptr);
422 
423 
424  /*------------------------------------------------------------
425  / Compute the new boundary
426  /------------------------------------------------------------*/
427  nbnd = 0;
428  for (i=0; i<nvtxs; i++) {
429  if (graph->vrinfo[i].gv >=0 || graph->vrinfo[i].ed-graph->vrinfo[i].id >= 0)
430  BNDInsert(nbnd, bndind, bndptr, i);
431  }
432 
433  graph->nbnd = nbnd;
434 }
435 
436 /*************************************************************************
437 * This function computes the boundary definition for balancing
438 **************************************************************************/
440 {
441  int i, nvtxs, nbnd;
442  idxtype *bndind, *bndptr;
443 
444  nvtxs = graph->nvtxs;
445  bndind = graph->bndind;
446  bndptr = idxset(nvtxs, -1, graph->bndptr);
447 
448 
449  /*------------------------------------------------------------
450  / Compute the new boundary
451  /------------------------------------------------------------*/
452  nbnd = 0;
453  for (i=0; i<nvtxs; i++) {
454  if (graph->vrinfo[i].ed > 0)
455  BNDInsert(nbnd, bndind, bndptr, i);
456  }
457 
458  graph->nbnd = nbnd;
459 }
460 
#define EliminateVolSubDomainEdges
Definition: rename.h:125
timer ProjectTmr
Definition: struct.h:230
timer RefTmr
Definition: struct.h:230
#define idxwspacefree
Definition: rename.h:165
VEDegreeType * vedegrees
Definition: struct.h:103
VEDegreeType * edegrees
Definition: struct.h:136
idxtype * pwgts
Definition: struct.h:176
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
VRInfoType * vrinfo
Definition: struct.h:187
#define ComputeKWayVolGains
Definition: rename.h:132
int ndegrees
Definition: struct.h:135
int nbnd
Definition: struct.h:177
int id
Definition: struct.h:133
#define ProjectVolKWayPartition
Definition: rename.h:133
#define FreeGraph
Definition: rename.h:169
#define RTYPE_KWAYRANDOM_MCONN
Definition: defs.h:121
#define Random_KWayVolRefine
Definition: rename.h:116
#define MAXIDX
Definition: struct.h:24
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: macros.h:102
int mincut
Definition: struct.h:175
#define Greedy_KWayVolBalance
Definition: rename.h:118
idxtype * bndptr
Definition: struct.h:178
idxtype * rdata
Definition: struct.h:157
#define idxwspacemalloc
Definition: rename.h:164
struct graphdef * coarser
Definition: struct.h:198
#define stoptimer(tmr)
Definition: macros.h:54
struct graphdef * finer
Definition: struct.h:198
idxtype ned
Definition: struct.h:89
HitTile_Vector graph
idxtype ed
Definition: struct.h:89
idxtype pid
Definition: struct.h:88
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
int nid
Definition: struct.h:133
int idxtype
Definition: struct.h:19
int gv
Definition: struct.h:134
#define RTYPE_KWAYRANDOM
Definition: defs.h:119
#define ComputeVolKWayBoundary
Definition: rename.h:134
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxcopy(n, a, b)
Definition: macros.h:44
int cdegree
Definition: struct.h:104
void EliminateVolComponents(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
Definition: kwayvolfm.c:1614
#define Random_KWayVolRefineMConn
Definition: rename.h:117
idxtype gv
Definition: struct.h:90
int ed
Definition: struct.h:133
void GKfree(void **ptr1,...)
Definition: util.c:121
idxtype * bndind
Definition: struct.h:178
timer UncoarsenTmr
Definition: struct.h:230
#define Greedy_KWayVolBalanceMConn
Definition: rename.h:119
#define MALLOC_CHECK(ptr)
Definition: macros.h:83
idxtype * vwgt
Definition: struct.h:163
#define RefineVolKWay
Definition: rename.h:129
#define AllocateVolKWayPartitionMemory
Definition: rename.h:130
#define DBG_TIME
Definition: defs.h:154
int RType
Definition: struct.h:219
int minvol
Definition: struct.h:175
#define idxmalloc
Definition: rename.h:383
idxtype * gdata
Definition: struct.h:157
#define IsBalanced
Definition: rename.h:110
int nvtxs
Definition: struct.h:161
WorkSpaceType wspace
Definition: struct.h:227
#define ComputeVolKWayPartitionParams
Definition: rename.h:131
#define ASSERT(expr)
Definition: macros.h:130
idxtype * vsize
Definition: struct.h:164
#define ComputeVolKWayBalanceBoundary
Definition: rename.h:135
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define starttimer(tmr)
Definition: macros.h:53