1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * mfm2.c
5 *
6 * This file contains code that implements the edge-based FM refinement
7 *
8 * Started 7/23/97
9 * George
10 *
11 * $Id: mfm2.c,v 1.2 1998/11/30 14:50:44 karypis Exp $
12 */
13
14 #include "metis.h"
15
16
17 /*************************************************************************
18 * This function performs an edge-based FM refinement
19 **************************************************************************/
MocFM_2WayEdgeRefine2(CtrlType * ctrl,GraphType * graph,float * tpwgts,float * orgubvec,int npasses)20 void MocFM_2WayEdgeRefine2(CtrlType *ctrl, GraphType *graph, float *tpwgts, float *orgubvec,
21 int npasses)
22 {
23 int i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, me, limit, tmp, cnum;
24 idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
25 idxtype *moved, *swaps, *perm, *qnum;
26 float *nvwgt, *npwgts, origdiff[MAXNCON], origbal[MAXNCON], minbal[MAXNCON];
27 PQueueType parts[MAXNCON][2];
28 int higain, oldgain, mincut, initcut, newcut, mincutorder;
29 float *maxwgt, *minwgt, ubvec[MAXNCON], tvec[MAXNCON];
30
31 nvtxs = graph->nvtxs;
32 ncon = graph->ncon;
33 xadj = graph->xadj;
34 nvwgt = graph->nvwgt;
35 adjncy = graph->adjncy;
36 adjwgt = graph->adjwgt;
37 where = graph->where;
38 id = graph->id;
39 ed = graph->ed;
40 npwgts = graph->npwgts;
41 bndptr = graph->bndptr;
42 bndind = graph->bndind;
43
44 moved = idxwspacemalloc(ctrl, nvtxs);
45 swaps = idxwspacemalloc(ctrl, nvtxs);
46 perm = idxwspacemalloc(ctrl, nvtxs);
47 qnum = idxwspacemalloc(ctrl, nvtxs);
48
49 limit = (int) amin(amax(0.01*nvtxs, 15), 100);
50
51 Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, origbal);
52 for (i=0; i<ncon; i++) {
53 origdiff[i] = fabs(tpwgts[0]-npwgts[i]);
54 ubvec[i] = amax(origbal[i], orgubvec[i]);
55 }
56
57 /* Setup the weight intervals of the two subdomains */
58 minwgt = fwspacemalloc(ctrl, 2*ncon);
59 maxwgt = fwspacemalloc(ctrl, 2*ncon);
60
61 for (i=0; i<2; i++) {
62 for (j=0; j<ncon; j++) {
63 maxwgt[i*ncon+j] = tpwgts[i]*ubvec[j];
64 minwgt[i*ncon+j] = tpwgts[i]*(1.0/ubvec[j]);
65 }
66 }
67
68 /* Initialize the queues */
69 for (i=0; i<ncon; i++) {
70 PQueueInit(ctrl, &parts[i][0], nvtxs, PLUS_GAINSPAN+1);
71 PQueueInit(ctrl, &parts[i][1], nvtxs, PLUS_GAINSPAN+1);
72 }
73 for (i=0; i<nvtxs; i++)
74 qnum[i] = samax(ncon, nvwgt+i*ncon);
75
76
77 if (ctrl->dbglvl&DBG_REFINE) {
78 printf("Parts: [");
79 for (l=0; l<ncon; l++)
80 printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
81 printf("] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: ", tpwgts[0], tpwgts[1],
82 graph->nvtxs, graph->nbnd, graph->mincut);
83 for (i=0; i<ncon; i++)
84 printf("%.3f ", origbal[i]);
85 printf("\n");
86 }
87
88 idxset(nvtxs, -1, moved);
89 for (pass=0; pass<npasses; pass++) { /* Do a number of passes */
90 for (i=0; i<ncon; i++) {
91 PQueueReset(&parts[i][0]);
92 PQueueReset(&parts[i][1]);
93 }
94
95 mincutorder = -1;
96 newcut = mincut = initcut = graph->mincut;
97 Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, minbal);
98
99 ASSERT(ComputeCut(graph, where) == graph->mincut);
100 ASSERT(CheckBnd(graph));
101
102 /* Insert boundary nodes in the priority queues */
103 nbnd = graph->nbnd;
104 RandomPermute(nbnd, perm, 1);
105 for (ii=0; ii<nbnd; ii++) {
106 i = bndind[perm[ii]];
107 ASSERT(ed[i] > 0 || id[i] == 0);
108 ASSERT(bndptr[i] != -1);
109 PQueueInsert(&parts[qnum[i]][where[i]], i, ed[i]-id[i]);
110 }
111
112 for (nswaps=0; nswaps<nvtxs; nswaps++) {
113 SelectQueue2(ncon, npwgts, tpwgts, &from, &cnum, parts, maxwgt);
114 to = (from+1)%2;
115
116 if (from == -1 || (higain = PQueueGetMax(&parts[cnum][from])) == -1)
117 break;
118 ASSERT(bndptr[higain] != -1);
119
120 newcut -= (ed[higain]-id[higain]);
121 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
122 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
123
124 Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, tvec);
125 if ((newcut < mincut && AreAllBelow(ncon, tvec, ubvec)) ||
126 (newcut == mincut && IsBetter2wayBalance(ncon, tvec, minbal, ubvec))) {
127 mincut = newcut;
128 for (i=0; i<ncon; i++)
129 minbal[i] = tvec[i];
130 mincutorder = nswaps;
131 }
132 else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
133 newcut += (ed[higain]-id[higain]);
134 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
135 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
136 break;
137 }
138
139 where[higain] = to;
140 moved[higain] = nswaps;
141 swaps[nswaps] = higain;
142
143 if (ctrl->dbglvl&DBG_MOVEINFO) {
144 printf("Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);
145 for (l=0; l<ncon; l++)
146 printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
147
148 printf(", LB: ");
149 for (i=0; i<ncon; i++)
150 printf("%.3f ", tvec[i]);
151 if (mincutorder == nswaps)
152 printf(" *\n");
153 else
154 printf("\n");
155 }
156
157
158 /**************************************************************
159 * Update the id[i]/ed[i] values of the affected nodes
160 ***************************************************************/
161 SWAP(id[higain], ed[higain], tmp);
162 if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
163 BNDDelete(nbnd, bndind, bndptr, higain);
164
165 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
166 k = adjncy[j];
167 oldgain = ed[k]-id[k];
168
169 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
170 INC_DEC(id[k], ed[k], kwgt);
171
172 /* Update its boundary information and queue position */
173 if (bndptr[k] != -1) { /* If k was a boundary vertex */
174 if (ed[k] == 0) { /* Not a boundary vertex any more */
175 BNDDelete(nbnd, bndind, bndptr, k);
176 if (moved[k] == -1) /* Remove it if in the queues */
177 PQueueDelete(&parts[qnum[k]][where[k]], k, oldgain);
178 }
179 else { /* If it has not been moved, update its position in the queue */
180 if (moved[k] == -1)
181 PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-id[k]);
182 }
183 }
184 else {
185 if (ed[k] > 0) { /* It will now become a boundary vertex */
186 BNDInsert(nbnd, bndind, bndptr, k);
187 if (moved[k] == -1)
188 PQueueInsert(&parts[qnum[k]][where[k]], k, ed[k]-id[k]);
189 }
190 }
191 }
192
193 }
194
195
196 /****************************************************************
197 * Roll back computations
198 *****************************************************************/
199 for (i=0; i<nswaps; i++)
200 moved[swaps[i]] = -1; /* reset moved array */
201 for (nswaps--; nswaps>mincutorder; nswaps--) {
202 higain = swaps[nswaps];
203
204 to = where[higain] = (where[higain]+1)%2;
205 SWAP(id[higain], ed[higain], tmp);
206 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
207 BNDDelete(nbnd, bndind, bndptr, higain);
208 else if (ed[higain] > 0 && bndptr[higain] == -1)
209 BNDInsert(nbnd, bndind, bndptr, higain);
210
211 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
212 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
213 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
214 k = adjncy[j];
215
216 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
217 INC_DEC(id[k], ed[k], kwgt);
218
219 if (bndptr[k] != -1 && ed[k] == 0)
220 BNDDelete(nbnd, bndind, bndptr, k);
221 if (bndptr[k] == -1 && ed[k] > 0)
222 BNDInsert(nbnd, bndind, bndptr, k);
223 }
224 }
225
226 if (ctrl->dbglvl&DBG_REFINE) {
227 printf("\tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);
228 for (l=0; l<ncon; l++)
229 printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
230 printf("], LB: ");
231 Compute2WayHLoadImbalanceVec(ncon, npwgts, tpwgts, tvec);
232 for (i=0; i<ncon; i++)
233 printf("%.3f ", tvec[i]);
234 printf("\n");
235 }
236
237 graph->mincut = mincut;
238 graph->nbnd = nbnd;
239
240 if (mincutorder == -1 || mincut == initcut)
241 break;
242 }
243
244 for (i=0; i<ncon; i++) {
245 PQueueFree(ctrl, &parts[i][0]);
246 PQueueFree(ctrl, &parts[i][1]);
247 }
248
249 idxwspacefree(ctrl, nvtxs);
250 idxwspacefree(ctrl, nvtxs);
251 idxwspacefree(ctrl, nvtxs);
252 idxwspacefree(ctrl, nvtxs);
253 fwspacefree(ctrl, 2*ncon);
254 fwspacefree(ctrl, 2*ncon);
255
256 }
257
258
259 /*************************************************************************
260 * This function selects the partition number and the queue from which
261 * we will move vertices out
262 **************************************************************************/
SelectQueue2(int ncon,float * npwgts,float * tpwgts,int * from,int * cnum,PQueueType queues[MAXNCON][2],float * maxwgt)263 void SelectQueue2(int ncon, float *npwgts, float *tpwgts, int *from, int *cnum,
264 PQueueType queues[MAXNCON][2], float *maxwgt)
265 {
266 int i, j, maxgain=0;
267 float diff, max, maxdiff=0.0;
268
269 *from = -1;
270 *cnum = -1;
271
272 /* First determine the side and the queue, irrespective of the presence of nodes */
273 for (j=0; j<2; j++) {
274 for (i=0; i<ncon; i++) {
275 diff = npwgts[j*ncon+i]-maxwgt[j*ncon+i];
276 if (diff >= maxdiff) {
277 maxdiff = diff;
278 *from = j;
279 *cnum = i;
280 }
281 }
282 }
283
284 if (*from != -1 && PQueueGetSize(&queues[*cnum][*from]) == 0) {
285 /* The desired queue is empty, select a node from that side anyway */
286 for (i=0; i<ncon; i++) {
287 if (PQueueGetSize(&queues[i][*from]) > 0) {
288 max = (npwgts[(*from)*ncon+i] - maxwgt[(*from)*ncon+i]);
289 *cnum = i;
290 break;
291 }
292 }
293
294 for (i++; i<ncon; i++) {
295 diff = npwgts[(*from)*ncon+i] - maxwgt[(*from)*ncon+i];
296 if (diff > max && PQueueGetSize(&queues[i][*from]) > 0) {
297 max = diff;
298 *cnum = i;
299 }
300 }
301 }
302
303 /* Check to see if you can focus on the cut */
304 if (maxdiff <= 0.0 || *from == -1) {
305 maxgain = -100000;
306
307 for (j=0; j<2; j++) {
308 for (i=0; i<ncon; i++) {
309 if (PQueueGetSize(&queues[i][j]) > 0 && PQueueGetKey(&queues[i][j]) > maxgain) {
310 maxgain = PQueueGetKey(&queues[i][j]);
311 *from = j;
312 *cnum = i;
313 }
314 }
315 }
316
317 /* printf("(%2d %2d) %3d\n", *from, *cnum, maxgain); */
318 }
319 }
320
321
322 /*************************************************************************
323 * This function checks if the newbal is better than oldbal given the
324 * ubvector ubvec
325 **************************************************************************/
IsBetter2wayBalance(int ncon,float * newbal,float * oldbal,float * ubvec)326 int IsBetter2wayBalance(int ncon, float *newbal, float *oldbal, float *ubvec)
327 {
328 int i, j;
329 float max1=0.0, max2=0.0, sum1=0.0, sum2=0.0, tmp;
330
331 for (i=0; i<ncon; i++) {
332 tmp = (newbal[i]-1)/(ubvec[i]-1);
333 max1 = (max1 < tmp ? tmp : max1);
334 sum1 += tmp;
335
336 tmp = (oldbal[i]-1)/(ubvec[i]-1);
337 max2 = (max2 < tmp ? tmp : max2);
338 sum2 += tmp;
339 }
340
341 if (max1 < max2)
342 return 1;
343 else if (max1 > max2)
344 return 0;
345 else
346 return sum1 <= sum2;
347 }
348
349
350