Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
kwayrefine.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * kwayrefine.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: kwayrefine.c,v 1.1 1998/11/27 17:59:17 karypis Exp $
12  */
13 
14 #include <metis.h>
15 
16 
17 /*************************************************************************
18 * This function is the entry point of refinement
19 **************************************************************************/
20 void RefineKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
21 {
22  int i, nlevels, mustfree=0;
23  GraphType *ptr;
24 
26 
27  /* Compute the parameters of the coarsest graph */
28  ComputeKWayPartitionParams(ctrl, graph, nparts);
29 
30  /* Take care any non-contiguity */
31  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr1));
32  if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
33  EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
34  EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
35  EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
36  }
37  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr1));
38 
39  /* Determine how many levels are there */
40  for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++);
41 
42  for (i=0; ;i++) {
43  /* PrintSubDomainGraph(graph, nparts, graph->where); */
44  if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN && (i == nlevels/2 || i == nlevels/2+1))
45  EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
46 
47  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
48 
49  if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
50  ComputeKWayBalanceBoundary(ctrl, graph, nparts);
51  if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN)
52  Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1);
53  else
54  Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1);
55  ComputeKWayBoundary(ctrl, graph, nparts);
56  }
57 
58  switch (ctrl->RType) {
59  case RTYPE_KWAYRANDOM:
60  Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1);
61  break;
62  case RTYPE_KWAYGREEDY:
63  Greedy_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10);
64  break;
66  Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1);
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  if (graph->vwgt == NULL) {
80  graph->vwgt = idxsmalloc(graph->nvtxs, 1, "RefineKWay: graph->vwgt");
81  graph->adjwgt = idxsmalloc(graph->nedges, 1, "RefineKWay: graph->adjwgt");
82  mustfree = 1;
83  }
84  ProjectKWayPartition(ctrl, graph, nparts);
85  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
86  }
87 
88  if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
89  ComputeKWayBalanceBoundary(ctrl, graph, nparts);
90  if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
91  Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8);
92  Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
93  }
94  else {
95  Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8);
96  Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
97  }
98  }
99 
100  /* Take care any trivial non-contiguity */
101  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr2));
102  EliminateComponents(ctrl, graph, nparts, tpwgts, ubfactor);
103  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr2));
104 
105  if (mustfree)
106  GKfree(&graph->vwgt, &graph->adjwgt, LTERM);
107 
108  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
109 }
110 
111 
112 /*************************************************************************
113 * This function allocates memory for k-way edge refinement
114 **************************************************************************/
116 {
117  int nvtxs, pad64;
118 
119  nvtxs = graph->nvtxs;
120 
121  pad64 = (3*nvtxs+nparts)%2;
122 
123  graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(RInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateKWayPartitionMemory: rdata");
124  graph->pwgts = graph->rdata;
125  graph->where = graph->rdata + nparts;
126  graph->bndptr = graph->rdata + nvtxs + nparts;
127  graph->bndind = graph->rdata + 2*nvtxs + nparts;
128  graph->rinfo = (RInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
129 
130 /*
131  if (ctrl->wspace.edegrees != NULL)
132  free(ctrl->wspace.edegrees);
133  ctrl->wspace.edegrees = (EDegreeType *)GKmalloc(graph->nedges*sizeof(EDegreeType), "AllocateKWayPartitionMemory: edegrees");
134 */
135 }
136 
137 
138 /*************************************************************************
139 * This function computes the initial id/ed
140 **************************************************************************/
142 {
143  int i, j, k, l, nvtxs, nbnd, mincut, me, other;
144  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
145  RInfoType *rinfo, *myrinfo;
146  EDegreeType *myedegrees;
147 
148  nvtxs = graph->nvtxs;
149  xadj = graph->xadj;
150  vwgt = graph->vwgt;
151  adjncy = graph->adjncy;
152  adjwgt = graph->adjwgt;
153 
154  where = graph->where;
155  pwgts = idxset(nparts, 0, graph->pwgts);
156  bndind = graph->bndind;
157  bndptr = idxset(nvtxs, -1, graph->bndptr);
158  rinfo = graph->rinfo;
159 
160 
161  /*------------------------------------------------------------
162  / Compute now the id/ed degrees
163  /------------------------------------------------------------*/
164  ctrl->wspace.cdegree = 0;
165  nbnd = mincut = 0;
166  for (i=0; i<nvtxs; i++) {
167  me = where[i];
168  pwgts[me] += vwgt[i];
169 
170  myrinfo = rinfo+i;
171  myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
172  myrinfo->edegrees = NULL;
173 
174  for (j=xadj[i]; j<xadj[i+1]; j++) {
175  if (me != where[adjncy[j]])
176  myrinfo->ed += adjwgt[j];
177  }
178  myrinfo->id = graph->adjwgtsum[i] - myrinfo->ed;
179 
180  if (myrinfo->ed > 0)
181  mincut += myrinfo->ed;
182 
183  if (myrinfo->ed-myrinfo->id >= 0)
184  BNDInsert(nbnd, bndind, bndptr, i);
185 
186  /* Time to compute the particular external degrees */
187  if (myrinfo->ed > 0) {
188  myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
189  ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
190 
191  for (j=xadj[i]; j<xadj[i+1]; j++) {
192  other = where[adjncy[j]];
193  if (me != other) {
194  for (k=0; k<myrinfo->ndegrees; k++) {
195  if (myedegrees[k].pid == other) {
196  myedegrees[k].ed += adjwgt[j];
197  break;
198  }
199  }
200  if (k == myrinfo->ndegrees) {
201  myedegrees[myrinfo->ndegrees].pid = other;
202  myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
203  }
204  }
205  }
206 
207  ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
208  }
209  }
210 
211  graph->mincut = mincut/2;
212  graph->nbnd = nbnd;
213 
214 }
215 
216 
217 
218 /*************************************************************************
219 * This function projects a partition, and at the same time computes the
220 * parameters for refinement.
221 **************************************************************************/
222 void ProjectKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
223 {
224  int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
225  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
226  idxtype *cmap, *where, *bndptr, *bndind;
227  idxtype *cwhere;
228  GraphType *cgraph;
229  RInfoType *crinfo, *rinfo, *myrinfo;
230  EDegreeType *myedegrees;
231  idxtype *htable;
232 
233  cgraph = graph->coarser;
234  cwhere = cgraph->where;
235  crinfo = cgraph->rinfo;
236 
237  nvtxs = graph->nvtxs;
238  cmap = graph->cmap;
239  xadj = graph->xadj;
240  adjncy = graph->adjncy;
241  adjwgt = graph->adjwgt;
242  adjwgtsum = graph->adjwgtsum;
243 
244  AllocateKWayPartitionMemory(ctrl, graph, nparts);
245  where = graph->where;
246  rinfo = graph->rinfo;
247  bndind = graph->bndind;
248  bndptr = idxset(nvtxs, -1, graph->bndptr);
249 
250  /* Go through and project partition and compute id/ed for the nodes */
251  for (i=0; i<nvtxs; i++) {
252  k = cmap[i];
253  where[i] = cwhere[k];
254  cmap[i] = crinfo[k].ed; /* For optimization */
255  }
256 
257  htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
258 
259  ctrl->wspace.cdegree = 0;
260  for (nbnd=0, i=0; i<nvtxs; i++) {
261  me = where[i];
262 
263  myrinfo = rinfo+i;
264  myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
265  myrinfo->edegrees = NULL;
266 
267  myrinfo->id = adjwgtsum[i];
268 
269  if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
270  istart = xadj[i];
271  iend = xadj[i+1];
272 
273  myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
274  ctrl->wspace.cdegree += iend-istart;
275 
276  ndegrees = 0;
277  for (j=istart; j<iend; j++) {
278  other = where[adjncy[j]];
279  if (me != other) {
280  myrinfo->ed += adjwgt[j];
281  if ((k = htable[other]) == -1) {
282  htable[other] = ndegrees;
283  myedegrees[ndegrees].pid = other;
284  myedegrees[ndegrees++].ed = adjwgt[j];
285  }
286  else {
287  myedegrees[k].ed += adjwgt[j];
288  }
289  }
290  }
291  myrinfo->id -= myrinfo->ed;
292 
293  /* Remove space for edegrees if it was interior */
294  if (myrinfo->ed == 0) {
295  myrinfo->edegrees = NULL;
296  ctrl->wspace.cdegree -= iend-istart;
297  }
298  else {
299  if (myrinfo->ed-myrinfo->id >= 0)
300  BNDInsert(nbnd, bndind, bndptr, i);
301 
302  myrinfo->ndegrees = ndegrees;
303 
304  for (j=0; j<ndegrees; j++)
305  htable[myedegrees[j].pid] = -1;
306  }
307  }
308  }
309 
310  idxcopy(nparts, cgraph->pwgts, graph->pwgts);
311  graph->mincut = cgraph->mincut;
312  graph->nbnd = nbnd;
313 
314  FreeGraph(graph->coarser);
315  graph->coarser = NULL;
316 
317  idxwspacefree(ctrl, nparts);
318 
319  ASSERT(CheckBnd2(graph));
320 
321 }
322 
323 
324 
325 /*************************************************************************
326 * This function checks if the partition weights are within the balance
327 * contraints
328 **************************************************************************/
329 int IsBalanced(idxtype *pwgts, int nparts, float *tpwgts, float ubfactor)
330 {
331  int i, j, tvwgt;
332 
333  tvwgt = idxsum(nparts, pwgts);
334  for (i=0; i<nparts; i++) {
335  if (pwgts[i] > tpwgts[i]*tvwgt*(ubfactor+0.005))
336  return 0;
337  }
338 
339  return 1;
340 }
341 
342 
343 /*************************************************************************
344 * This function computes the boundary definition for balancing
345 **************************************************************************/
346 void ComputeKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
347 {
348  int i, nvtxs, nbnd;
349  idxtype *bndind, *bndptr;
350 
351  nvtxs = graph->nvtxs;
352  bndind = graph->bndind;
353  bndptr = idxset(nvtxs, -1, graph->bndptr);
354 
355 
356  /*------------------------------------------------------------
357  / Compute the new boundary
358  /------------------------------------------------------------*/
359  nbnd = 0;
360  for (i=0; i<nvtxs; i++) {
361  if (graph->rinfo[i].ed-graph->rinfo[i].id >= 0)
362  BNDInsert(nbnd, bndind, bndptr, i);
363  }
364 
365  graph->nbnd = nbnd;
366 }
367 
368 /*************************************************************************
369 * This function computes the boundary definition for balancing
370 **************************************************************************/
372 {
373  int i, nvtxs, nbnd;
374  idxtype *bndind, *bndptr;
375 
376  nvtxs = graph->nvtxs;
377  bndind = graph->bndind;
378  bndptr = idxset(nvtxs, -1, graph->bndptr);
379 
380 
381  /*------------------------------------------------------------
382  / Compute the new boundary
383  /------------------------------------------------------------*/
384  nbnd = 0;
385  for (i=0; i<nvtxs; i++) {
386  if (graph->rinfo[i].ed > 0)
387  BNDInsert(nbnd, bndind, bndptr, i);
388  }
389 
390  graph->nbnd = nbnd;
391 }
392 
EDegreeType * edegrees
Definition: struct.h:102
timer ProjectTmr
Definition: struct.h:230
timer RefTmr
Definition: struct.h:230
#define idxwspacefree
Definition: rename.h:165
int ndegrees
Definition: struct.h:121
#define Greedy_KWayEdgeBalance
Definition: rename.h:102
#define ComputeKWayBalanceBoundary
Definition: rename.h:112
idxtype * pwgts
Definition: struct.h:176
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
#define Random_KWayEdgeRefineMConn
Definition: rename.h:362
int nbnd
Definition: struct.h:177
idxtype ed
Definition: struct.h:79
#define Random_KWayEdgeRefine
Definition: rename.h:100
idxtype pid
Definition: struct.h:78
#define FreeGraph
Definition: rename.h:169
#define RTYPE_KWAYRANDOM_MCONN
Definition: defs.h:121
#define EliminateComponents
Definition: rename.h:368
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: macros.h:102
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
idxtype * rdata
Definition: struct.h:157
#define AllocateKWayPartitionMemory
Definition: rename.h:107
timer AuxTmr1
Definition: struct.h:230
#define idxwspacemalloc
Definition: rename.h:164
struct graphdef * coarser
Definition: struct.h:198
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
struct graphdef * finer
Definition: struct.h:198
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
#define Greedy_KWayEdgeRefine
Definition: rename.h:101
int idxtype
Definition: struct.h:19
#define RTYPE_KWAYRANDOM
Definition: defs.h:119
#define idxsmalloc
Definition: rename.h:386
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
int ed
Definition: struct.h:120
#define EliminateSubDomainEdges
Definition: rename.h:366
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxcopy(n, a, b)
Definition: macros.h:44
RInfoType * rinfo
Definition: struct.h:184
int cdegree
Definition: struct.h:104
void GKfree(void **ptr1,...)
Definition: util.c:121
#define ProjectKWayPartition
Definition: rename.h:109
#define CheckBnd2
Definition: rename.h:45
idxtype * bndind
Definition: struct.h:178
timer AuxTmr2
Definition: struct.h:230
timer UncoarsenTmr
Definition: struct.h:230
#define ComputeKWayPartitionParams
Definition: rename.h:108
idxtype * vwgt
Definition: struct.h:163
#define DBG_TIME
Definition: defs.h:154
int RType
Definition: struct.h:219
EDegreeType * edegrees
Definition: struct.h:122
#define Greedy_KWayEdgeBalanceMConn
Definition: rename.h:363
int nedges
Definition: struct.h:161
#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 ASSERT(expr)
Definition: macros.h:130
#define RefineKWay
Definition: rename.h:106
#define ComputeKWayBoundary
Definition: rename.h:111
int id
Definition: struct.h:120
idxtype * adjncy
Definition: struct.h:165
#define RTYPE_KWAYGREEDY
Definition: defs.h:120
idxtype * xadj
Definition: struct.h:162
#define starttimer(tmr)
Definition: macros.h:53