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