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