1 /*!
2 \file
3 \brief Functions for the edge-based balancing
4
5 \date Started 7/23/97
6 \author George
7 \author Copyright 1997-2011, Regents of the University of Minnesota
8 \version\verbatim $Id: balance.c 10187 2011-06-13 13:46:57Z karypis $ \endverbatim
9 */
10
11 #include "metislib.h"
12
13 /*************************************************************************
14 * This function is the entry poidx_t of the bisection balancing algorithms.
15 **************************************************************************/
Balance2Way(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts)16 void Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
17 {
18 if (ComputeLoadImbalanceDiff(graph, 2, ctrl->pijbm, ctrl->ubfactors) <= 0)
19 return;
20
21 if (graph->ncon == 1) {
22 /* return right away if the balance is OK */
23 if (iabs(ntpwgts[0]*graph->tvwgt[0]-graph->pwgts[0]) < 3*graph->tvwgt[0]/graph->nvtxs)
24 return;
25
26 if (graph->nbnd > 0)
27 Bnd2WayBalance(ctrl, graph, ntpwgts);
28 else
29 General2WayBalance(ctrl, graph, ntpwgts);
30 }
31 else {
32 McGeneral2WayBalance(ctrl, graph, ntpwgts);
33 }
34 }
35
36
37 /*************************************************************************
38 * This function balances two partitions by moving boundary nodes
39 * from the domain that is overweight to the one that is underweight.
40 **************************************************************************/
Bnd2WayBalance(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts)41 void Bnd2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
42 {
43 idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
44 idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
45 idx_t *moved, *perm;
46 rpq_t *queue;
47 idx_t higain, mincut, mindiff;
48 idx_t tpwgts[2];
49
50 WCOREPUSH;
51
52 nvtxs = graph->nvtxs;
53 xadj = graph->xadj;
54 vwgt = graph->vwgt;
55 adjncy = graph->adjncy;
56 adjwgt = graph->adjwgt;
57 where = graph->where;
58 id = graph->id;
59 ed = graph->ed;
60 pwgts = graph->pwgts;
61 bndptr = graph->bndptr;
62 bndind = graph->bndind;
63
64 moved = iwspacemalloc(ctrl, nvtxs);
65 perm = iwspacemalloc(ctrl, nvtxs);
66
67 /* Determine from which domain you will be moving data */
68 tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
69 tpwgts[1] = graph->tvwgt[0] - tpwgts[0];
70 mindiff = iabs(tpwgts[0]-pwgts[0]);
71 from = (pwgts[0] < tpwgts[0] ? 1 : 0);
72 to = (from+1)%2;
73
74 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
75 printf("Partitions: [%6"PRIDX" %6"PRIDX"] T[%6"PRIDX" %6"PRIDX"], Nv-Nb[%6"PRIDX" %6"PRIDX"]. ICut: %6"PRIDX" [B]\n",
76 pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd,
77 graph->mincut));
78
79 queue = rpqCreate(nvtxs);
80
81 iset(nvtxs, -1, moved);
82
83 ASSERT(ComputeCut(graph, where) == graph->mincut);
84 ASSERT(CheckBnd(graph));
85
86 /* Insert the boundary nodes of the proper partition whose size is OK in the priority queue */
87 nbnd = graph->nbnd;
88 irandArrayPermute(nbnd, perm, nbnd/5, 1);
89 for (ii=0; ii<nbnd; ii++) {
90 i = perm[ii];
91 ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
92 ASSERT(bndptr[bndind[i]] != -1);
93 if (where[bndind[i]] == from && vwgt[bndind[i]] <= mindiff)
94 rpqInsert(queue, bndind[i], ed[bndind[i]]-id[bndind[i]]);
95 }
96
97 mincut = graph->mincut;
98 for (nswaps=0; nswaps<nvtxs; nswaps++) {
99 if ((higain = rpqGetTop(queue)) == -1)
100 break;
101 ASSERT(bndptr[higain] != -1);
102
103 if (pwgts[to]+vwgt[higain] > tpwgts[to])
104 break;
105
106 mincut -= (ed[higain]-id[higain]);
107 INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
108
109 where[higain] = to;
110 moved[higain] = nswaps;
111
112 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
113 printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
114
115 /**************************************************************
116 * Update the id[i]/ed[i] values of the affected nodes
117 ***************************************************************/
118 SWAP(id[higain], ed[higain], tmp);
119 if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
120 BNDDelete(nbnd, bndind, bndptr, higain);
121
122 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
123 k = adjncy[j];
124 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
125 INC_DEC(id[k], ed[k], kwgt);
126
127 /* Update its boundary information and queue position */
128 if (bndptr[k] != -1) { /* If k was a boundary vertex */
129 if (ed[k] == 0) { /* Not a boundary vertex any more */
130 BNDDelete(nbnd, bndind, bndptr, k);
131 if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff) /* Remove it if in the queues */
132 rpqDelete(queue, k);
133 }
134 else { /* If it has not been moved, update its position in the queue */
135 if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
136 rpqUpdate(queue, k, ed[k]-id[k]);
137 }
138 }
139 else {
140 if (ed[k] > 0) { /* It will now become a boundary vertex */
141 BNDInsert(nbnd, bndind, bndptr, k);
142 if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
143 rpqInsert(queue, k, ed[k]-id[k]);
144 }
145 }
146 }
147 }
148
149 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
150 printf("\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
151
152 graph->mincut = mincut;
153 graph->nbnd = nbnd;
154
155 rpqDestroy(queue);
156
157 WCOREPOP;
158 }
159
160
161 /*************************************************************************
162 * This function balances two partitions by moving the highest gain
163 * (including negative gain) vertices to the other domain.
164 * It is used only when tha unbalance is due to non contigous
165 * subdomains. That is, the are no boundary vertices.
166 * It moves vertices from the domain that is overweight to the one that
167 * is underweight.
168 **************************************************************************/
General2WayBalance(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts)169 void General2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
170 {
171 idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
172 idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
173 idx_t *moved, *perm;
174 rpq_t *queue;
175 idx_t higain, mincut, mindiff;
176 idx_t tpwgts[2];
177
178 WCOREPUSH;
179
180 nvtxs = graph->nvtxs;
181 xadj = graph->xadj;
182 vwgt = graph->vwgt;
183 adjncy = graph->adjncy;
184 adjwgt = graph->adjwgt;
185 where = graph->where;
186 id = graph->id;
187 ed = graph->ed;
188 pwgts = graph->pwgts;
189 bndptr = graph->bndptr;
190 bndind = graph->bndind;
191
192 moved = iwspacemalloc(ctrl, nvtxs);
193 perm = iwspacemalloc(ctrl, nvtxs);
194
195 /* Determine from which domain you will be moving data */
196 tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
197 tpwgts[1] = graph->tvwgt[0] - tpwgts[0];
198 mindiff = iabs(tpwgts[0]-pwgts[0]);
199 from = (pwgts[0] < tpwgts[0] ? 1 : 0);
200 to = (from+1)%2;
201
202 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
203 printf("Partitions: [%6"PRIDX" %6"PRIDX"] T[%6"PRIDX" %6"PRIDX"], Nv-Nb[%6"PRIDX" %6"PRIDX"]. ICut: %6"PRIDX" [B]\n",
204 pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
205
206 queue = rpqCreate(nvtxs);
207
208 iset(nvtxs, -1, moved);
209
210 ASSERT(ComputeCut(graph, where) == graph->mincut);
211 ASSERT(CheckBnd(graph));
212
213 /* Insert the nodes of the proper partition whose size is OK in the priority queue */
214 irandArrayPermute(nvtxs, perm, nvtxs/5, 1);
215 for (ii=0; ii<nvtxs; ii++) {
216 i = perm[ii];
217 if (where[i] == from && vwgt[i] <= mindiff)
218 rpqInsert(queue, i, ed[i]-id[i]);
219 }
220
221 mincut = graph->mincut;
222 nbnd = graph->nbnd;
223 for (nswaps=0; nswaps<nvtxs; nswaps++) {
224 if ((higain = rpqGetTop(queue)) == -1)
225 break;
226
227 if (pwgts[to]+vwgt[higain] > tpwgts[to])
228 break;
229
230 mincut -= (ed[higain]-id[higain]);
231 INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
232
233 where[higain] = to;
234 moved[higain] = nswaps;
235
236 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
237 printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]\n", higain, from, ed[higain]-id[higain], vwgt[higain], mincut, pwgts[0], pwgts[1]));
238
239 /**************************************************************
240 * Update the id[i]/ed[i] values of the affected nodes
241 ***************************************************************/
242 SWAP(id[higain], ed[higain], tmp);
243 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
244 BNDDelete(nbnd, bndind, bndptr, higain);
245 if (ed[higain] > 0 && bndptr[higain] == -1)
246 BNDInsert(nbnd, bndind, bndptr, higain);
247
248 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
249 k = adjncy[j];
250
251 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
252 INC_DEC(id[k], ed[k], kwgt);
253
254 /* Update the queue position */
255 if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
256 rpqUpdate(queue, k, ed[k]-id[k]);
257
258 /* Update its boundary information */
259 if (ed[k] == 0 && bndptr[k] != -1)
260 BNDDelete(nbnd, bndind, bndptr, k);
261 else if (ed[k] > 0 && bndptr[k] == -1)
262 BNDInsert(nbnd, bndind, bndptr, k);
263 }
264 }
265
266 IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
267 printf("\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
268
269 graph->mincut = mincut;
270 graph->nbnd = nbnd;
271
272 rpqDestroy(queue);
273
274 WCOREPOP;
275 }
276
277
278 /*************************************************************************
279 * This function performs an edge-based FM refinement
280 **************************************************************************/
McGeneral2WayBalance(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts)281 void McGeneral2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
282 {
283 idx_t i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass,
284 me, limit, tmp, cnum;
285 idx_t *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *id, *ed, *bndptr, *bndind;
286 idx_t *moved, *swaps, *perm, *qnum, *qsizes;
287 idx_t higain, mincut, newcut, mincutorder;
288 real_t *invtvwgt, *minbalv, *newbalv, minbal, newbal;
289 rpq_t **queues;
290
291 WCOREPUSH;
292
293 nvtxs = graph->nvtxs;
294 ncon = graph->ncon;
295 xadj = graph->xadj;
296 vwgt = graph->vwgt;
297 adjncy = graph->adjncy;
298 adjwgt = graph->adjwgt;
299 invtvwgt = graph->invtvwgt;
300 where = graph->where;
301 id = graph->id;
302 ed = graph->ed;
303 pwgts = graph->pwgts;
304 bndptr = graph->bndptr;
305 bndind = graph->bndind;
306
307 moved = iwspacemalloc(ctrl, nvtxs);
308 swaps = iwspacemalloc(ctrl, nvtxs);
309 perm = iwspacemalloc(ctrl, nvtxs);
310 qnum = iwspacemalloc(ctrl, nvtxs);
311 newbalv = rwspacemalloc(ctrl, ncon);
312 minbalv = rwspacemalloc(ctrl, ncon);
313 qsizes = iwspacemalloc(ctrl, 2*ncon);
314
315 limit = gk_min(gk_max(0.01*nvtxs, 15), 100);
316
317 /* Initialize the queues */
318 queues = (rpq_t **)wspacemalloc(ctrl, 2*ncon*sizeof(rpq_t *));
319 for (i=0; i<2*ncon; i++) {
320 queues[i] = rpqCreate(nvtxs);
321 qsizes[i] = 0;
322 }
323
324 for (i=0; i<nvtxs; i++) {
325 qnum[i] = iargmax_nrm(ncon, vwgt+i*ncon, invtvwgt);
326 qsizes[2*qnum[i]+where[i]]++;
327 }
328
329
330 /* for the empty queues, move into them vertices from other queues */
331 for (from=0; from<2; from++) {
332 for (j=0; j<ncon; j++) {
333 if (qsizes[2*j+from] == 0) {
334 for (i=0; i<nvtxs; i++) {
335 if (where[i] != from)
336 continue;
337
338 k = iargmax2_nrm(ncon, vwgt+i*ncon, invtvwgt);
339 if (k == j &&
340 qsizes[2*qnum[i]+from] > qsizes[2*j+from] &&
341 vwgt[i*ncon+qnum[i]]*invtvwgt[qnum[i]] < 1.3*vwgt[i*ncon+j]*invtvwgt[j]) {
342 qsizes[2*qnum[i]+from]--;
343 qsizes[2*j+from]++;
344 qnum[i] = j;
345 }
346 }
347 }
348 }
349 }
350
351
352 minbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, minbalv);
353 ASSERT(minbal > 0.0);
354
355 newcut = mincut = graph->mincut;
356 mincutorder = -1;
357
358 if (ctrl->dbglvl&METIS_DBG_REFINE) {
359 printf("Parts: [");
360 for (l=0; l<ncon; l++)
361 printf("(%6"PRIDX" %6"PRIDX" %.3"PRREAL" %.3"PRREAL") ",
362 pwgts[l], pwgts[ncon+l], ntpwgts[l], ntpwgts[ncon+l]);
363 printf("] Nv-Nb[%5"PRIDX", %5"PRIDX"]. ICut: %6"PRIDX", LB: %+.3"PRREAL" [B]\n",
364 graph->nvtxs, graph->nbnd, graph->mincut, minbal);
365 }
366
367 iset(nvtxs, -1, moved);
368
369 ASSERT(ComputeCut(graph, where) == graph->mincut);
370 ASSERT(CheckBnd(graph));
371
372 /* Insert all nodes in the priority queues */
373 nbnd = graph->nbnd;
374 irandArrayPermute(nvtxs, perm, nvtxs/10, 1);
375 for (ii=0; ii<nvtxs; ii++) {
376 i = perm[ii];
377 rpqInsert(queues[2*qnum[i]+where[i]], i, ed[i]-id[i]);
378 }
379
380 for (nswaps=0; nswaps<nvtxs; nswaps++) {
381 if (minbal <= 0.0)
382 break;
383
384 SelectQueue(graph, ctrl->pijbm, ctrl->ubfactors, queues, &from, &cnum);
385 to = (from+1)%2;
386
387 if (from == -1 || (higain = rpqGetTop(queues[2*cnum+from])) == -1)
388 break;
389
390 newcut -= (ed[higain]-id[higain]);
391
392 iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
393 iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
394 newbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, newbalv);
395
396 if (newbal < minbal || (newbal == minbal &&
397 (newcut < mincut ||
398 (newcut == mincut && BetterBalance2Way(ncon, minbalv, newbalv))))) {
399 mincut = newcut;
400 minbal = newbal;
401 mincutorder = nswaps;
402 rcopy(ncon, newbalv, minbalv);
403 }
404 else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
405 newcut += (ed[higain]-id[higain]);
406 iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
407 iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
408 break;
409 }
410
411 where[higain] = to;
412 moved[higain] = nswaps;
413 swaps[nswaps] = higain;
414
415 if (ctrl->dbglvl&METIS_DBG_MOVEINFO) {
416 printf("Moved %6"PRIDX" from %"PRIDX"(%"PRIDX"). Gain: %5"PRIDX", "
417 "Cut: %5"PRIDX", NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);
418 for (l=0; l<ncon; l++)
419 printf("(%6"PRIDX", %6"PRIDX") ", pwgts[l], pwgts[ncon+l]);
420 printf(", %+.3"PRREAL" LB: %+.3"PRREAL"\n", minbal, newbal);
421 }
422
423
424 /**************************************************************
425 * Update the id[i]/ed[i] values of the affected nodes
426 ***************************************************************/
427 SWAP(id[higain], ed[higain], tmp);
428 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
429 BNDDelete(nbnd, bndind, bndptr, higain);
430 if (ed[higain] > 0 && bndptr[higain] == -1)
431 BNDInsert(nbnd, bndind, bndptr, higain);
432
433 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
434 k = adjncy[j];
435
436 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
437 INC_DEC(id[k], ed[k], kwgt);
438
439 /* Update the queue position */
440 if (moved[k] == -1)
441 rpqUpdate(queues[2*qnum[k]+where[k]], k, ed[k]-id[k]);
442
443 /* Update its boundary information */
444 if (ed[k] == 0 && bndptr[k] != -1)
445 BNDDelete(nbnd, bndind, bndptr, k);
446 else if (ed[k] > 0 && bndptr[k] == -1)
447 BNDInsert(nbnd, bndind, bndptr, k);
448 }
449 }
450
451
452
453 /****************************************************************
454 * Roll back computations
455 *****************************************************************/
456 for (nswaps--; nswaps>mincutorder; nswaps--) {
457 higain = swaps[nswaps];
458
459 to = where[higain] = (where[higain]+1)%2;
460 SWAP(id[higain], ed[higain], tmp);
461 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
462 BNDDelete(nbnd, bndind, bndptr, higain);
463 else if (ed[higain] > 0 && bndptr[higain] == -1)
464 BNDInsert(nbnd, bndind, bndptr, higain);
465
466 iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
467 iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+((to+1)%2)*ncon, 1);
468 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
469 k = adjncy[j];
470
471 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
472 INC_DEC(id[k], ed[k], kwgt);
473
474 if (bndptr[k] != -1 && ed[k] == 0)
475 BNDDelete(nbnd, bndind, bndptr, k);
476 if (bndptr[k] == -1 && ed[k] > 0)
477 BNDInsert(nbnd, bndind, bndptr, k);
478 }
479 }
480
481 if (ctrl->dbglvl&METIS_DBG_REFINE) {
482 printf("\tMincut: %6"PRIDX" at %5"PRIDX", NBND: %6"PRIDX", NPwgts: [",
483 mincut, mincutorder, nbnd);
484 for (l=0; l<ncon; l++)
485 printf("(%6"PRIDX", %6"PRIDX") ", pwgts[l], pwgts[ncon+l]);
486 printf("], LB: %.3"PRREAL"\n", ComputeLoadImbalance(graph, 2, ctrl->pijbm));
487 }
488
489 graph->mincut = mincut;
490 graph->nbnd = nbnd;
491
492
493 for (i=0; i<2*ncon; i++)
494 rpqDestroy(queues[i]);
495
496 WCOREPOP;
497 }
498
499