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 **************************************************************************/
RefineVolKWay(CtrlType * ctrl,GraphType * orggraph,GraphType * graph,int nparts,float * tpwgts,float ubfactor)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
26 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
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;
54 case RTYPE_KWAYRANDOM_MCONN:
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;
65 case RTYPE_KWAYRANDOM_MCONN:
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((void **) &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;
90 case RTYPE_KWAYRANDOM_MCONN:
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 **************************************************************************/
AllocateVolKWayPartitionMemory(CtrlType * ctrl,GraphType * graph,int nparts)107 void AllocateVolKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
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 **************************************************************************/
ComputeVolKWayPartitionParams(CtrlType * ctrl,GraphType * graph,int nparts)129 void ComputeVolKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
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 **************************************************************************/
ComputeKWayVolGains(CtrlType * ctrl,GraphType * graph,int nparts)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 **************************************************************************/
ProjectVolKWayPartition(CtrlType * ctrl,GraphType * graph,int nparts)309 void ProjectVolKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
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 **************************************************************************/
ComputeVolKWayBoundary(CtrlType * ctrl,GraphType * graph,int nparts)414 void ComputeVolKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
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 **************************************************************************/
ComputeVolKWayBalanceBoundary(CtrlType * ctrl,GraphType * graph,int nparts)439 void ComputeVolKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
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
461