Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
mfm2.c
Go to the documentation of this file.
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 **************************************************************************/
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 = 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 **************************************************************************/
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 **************************************************************************/
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 
#define idxwspacefree
Definition: rename.h:165
#define PQueueUpdate
Definition: rename.h:320
#define saxpy
Definition: rename.h:409
#define DBG_REFINE
Definition: defs.h:157
int nbnd
Definition: struct.h:177
idxtype * ed
Definition: struct.h:181
idxtype * id
Definition: struct.h:181
void fwspacefree(CtrlType *ctrl, int n)
Definition: memory.c:140
#define SelectQueue2
Definition: rename.h:191
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: macros.h:102
int mincut
Definition: struct.h:175
#define DBG_MOVEINFO
Definition: defs.h:159
idxtype * bndptr
Definition: struct.h:178
#define idxwspacemalloc
Definition: rename.h:164
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define MocFM_2WayEdgeRefine2
Definition: rename.h:190
float * npwgts
Definition: struct.h:196
int idxtype
Definition: struct.h:19
#define IsBetter2wayBalance
Definition: rename.h:192
#define PQueueReset
Definition: rename.h:316
int dbglvl
Definition: struct.h:216
#define fwspacemalloc
Definition: rename.h:166
int PQueueGetSize(PQueueType *queue)
Definition: pqueue.c:129
#define CheckBnd
Definition: rename.h:44
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
int ncon
Definition: struct.h:194
#define BNDDelete(nbnd, bndind, bndptr, vtx)
Definition: macros.h:109
#define MAXNCON
Definition: defs.h:20
#define amax(a, b)
Definition: macros.h:29
idxtype * bndind
Definition: struct.h:178
int PQueueGetKey(PQueueType *queue)
Definition: pqueue.c:530
#define INC_DEC(a, b, val)
Definition: macros.h:39
#define PLUS_GAINSPAN
Definition: defs.h:23
#define samax
Definition: rename.h:395
#define PQueueGetMax
Definition: rename.h:322
#define AreAllBelow
Definition: rename.h:283
#define PQueueInsert
Definition: rename.h:318
int nvtxs
Definition: struct.h:161
#define RandomPermute
Definition: rename.h:410
#define ASSERT(expr)
Definition: macros.h:130
#define SWAP(a, b, tmp)
Definition: macros.h:36
float * nvwgt
Definition: struct.h:195
#define ComputeCut
Definition: rename.h:43
#define max(a, b)
Definition: cannonAsync.c:47
#define PQueueDelete
Definition: rename.h:319
#define PQueueFree
Definition: rename.h:317
#define Compute2WayHLoadImbalanceVec
Definition: rename.h:186
#define amin(a, b)
Definition: macros.h:30
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define PQueueInit
Definition: rename.h:315