Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
mbalance.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * mbalance.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: mbalance.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 MocBalance2Way(CtrlType *ctrl, GraphType *graph, float *tpwgts, float lbfactor)
23 {
24 
25  if (Compute2WayHLoadImbalance(graph->ncon, graph->npwgts, tpwgts) < lbfactor)
26  return;
27 
28  MocGeneral2WayBalance(ctrl, graph, tpwgts, lbfactor);
29 
30 }
31 
32 
33 /*************************************************************************
34 * This function performs an edge-based FM refinement
35 **************************************************************************/
36 void MocGeneral2WayBalance(CtrlType *ctrl, GraphType *graph, float *tpwgts, float lbfactor)
37 {
38  int i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, me, limit, tmp, cnum;
39  idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
40  idxtype *moved, *swaps, *perm, *qnum;
41  float *nvwgt, *npwgts, mindiff[MAXNCON], origbal, minbal, newbal;
42  PQueueType parts[MAXNCON][2];
43  int higain, oldgain, mincut, newcut, mincutorder;
44  int qsizes[MAXNCON][2];
45 
46  nvtxs = graph->nvtxs;
47  ncon = graph->ncon;
48  xadj = graph->xadj;
49  nvwgt = graph->nvwgt;
50  adjncy = graph->adjncy;
51  adjwgt = graph->adjwgt;
52  where = graph->where;
53  id = graph->id;
54  ed = graph->ed;
55  npwgts = graph->npwgts;
56  bndptr = graph->bndptr;
57  bndind = graph->bndind;
58 
59  moved = idxwspacemalloc(ctrl, nvtxs);
60  swaps = idxwspacemalloc(ctrl, nvtxs);
61  perm = idxwspacemalloc(ctrl, nvtxs);
62  qnum = idxwspacemalloc(ctrl, nvtxs);
63 
64  limit = amin(amax(0.01*nvtxs, 15), 100);
65 
66  /* Initialize the queues */
67  for (i=0; i<ncon; i++) {
68  PQueueInit(ctrl, &parts[i][0], nvtxs, PLUS_GAINSPAN+1);
69  PQueueInit(ctrl, &parts[i][1], nvtxs, PLUS_GAINSPAN+1);
70  qsizes[i][0] = qsizes[i][1] = 0;
71  }
72 
73  for (i=0; i<nvtxs; i++) {
74  qnum[i] = samax(ncon, nvwgt+i*ncon);
75  qsizes[qnum[i]][where[i]]++;
76  }
77 
78 /*
79  printf("Weight Distribution: \t");
80  for (i=0; i<ncon; i++)
81  printf(" [%d %d]", qsizes[i][0], qsizes[i][1]);
82  printf("\n");
83 */
84 
85  for (from=0; from<2; from++) {
86  for (j=0; j<ncon; j++) {
87  if (qsizes[j][from] == 0) {
88  for (i=0; i<nvtxs; i++) {
89  if (where[i] != from)
90  continue;
91 
92  k = samax2(ncon, nvwgt+i*ncon);
93  if (k == j && qsizes[qnum[i]][from] > qsizes[j][from] && nvwgt[i*ncon+qnum[i]] < 1.3*nvwgt[i*ncon+j]) {
94  qsizes[qnum[i]][from]--;
95  qsizes[j][from]++;
96  qnum[i] = j;
97  }
98  }
99  }
100  }
101  }
102 
103 /*
104  printf("Weight Distribution (after):\t ");
105  for (i=0; i<ncon; i++)
106  printf(" [%d %d]", qsizes[i][0], qsizes[i][1]);
107  printf("\n");
108 */
109 
110 
111 
112  for (i=0; i<ncon; i++)
113  mindiff[i] = fabs(tpwgts[0]-npwgts[i]);
114  minbal = origbal = Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
115  newcut = mincut = graph->mincut;
116  mincutorder = -1;
117 
118  if (ctrl->dbglvl&DBG_REFINE) {
119  printf("Parts: [");
120  for (l=0; l<ncon; l++)
121  printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
122  printf("] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: %.3f [B]\n", tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut, origbal);
123  }
124 
125  idxset(nvtxs, -1, moved);
126 
127  ASSERT(ComputeCut(graph, where) == graph->mincut);
128  ASSERT(CheckBnd(graph));
129 
130  /* Insert all nodes in the priority queues */
131  nbnd = graph->nbnd;
132  RandomPermute(nvtxs, perm, 1);
133  for (ii=0; ii<nvtxs; ii++) {
134  i = perm[ii];
135  PQueueInsert(&parts[qnum[i]][where[i]], i, ed[i]-id[i]);
136  }
137 
138  for (nswaps=0; nswaps<nvtxs; nswaps++) {
139  if (minbal < lbfactor)
140  break;
141 
142  SelectQueue(ncon, npwgts, tpwgts, &from, &cnum, parts);
143  to = (from+1)%2;
144 
145  if (from == -1 || (higain = PQueueGetMax(&parts[cnum][from])) == -1)
146  break;
147 
148  saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
149  saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
150  newcut -= (ed[higain]-id[higain]);
151  newbal = Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
152 
153  if (newbal < minbal || (newbal == minbal &&
154  (newcut < mincut || (newcut == mincut && BetterBalance(ncon, npwgts, tpwgts, mindiff))))) {
155  mincut = newcut;
156  minbal = newbal;
157  mincutorder = nswaps;
158  for (i=0; i<ncon; i++)
159  mindiff[i] = fabs(tpwgts[0]-npwgts[i]);
160  }
161  else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
162  newcut += (ed[higain]-id[higain]);
163  saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
164  saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
165  break;
166  }
167 
168  where[higain] = to;
169  moved[higain] = nswaps;
170  swaps[nswaps] = higain;
171 
172  if (ctrl->dbglvl&DBG_MOVEINFO) {
173  printf("Moved %6d from %d(%d). Gain: %5d, Cut: %5d, NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);
174  for (l=0; l<ncon; l++)
175  printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
176  printf(", %.3f LB: %.3f\n", minbal, newbal);
177  }
178 
179 
180  /**************************************************************
181  * Update the id[i]/ed[i] values of the affected nodes
182  ***************************************************************/
183  SWAP(id[higain], ed[higain], tmp);
184  if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
185  BNDDelete(nbnd, bndind, bndptr, higain);
186  if (ed[higain] > 0 && bndptr[higain] == -1)
187  BNDInsert(nbnd, bndind, bndptr, higain);
188 
189  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
190  k = adjncy[j];
191  oldgain = ed[k]-id[k];
192 
193  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
194  INC_DEC(id[k], ed[k], kwgt);
195 
196  /* Update the queue position */
197  if (moved[k] == -1)
198  PQueueUpdate(&parts[qnum[k]][where[k]], k, oldgain, ed[k]-id[k]);
199 
200  /* Update its boundary information */
201  if (ed[k] == 0 && bndptr[k] != -1)
202  BNDDelete(nbnd, bndind, bndptr, k);
203  else if (ed[k] > 0 && bndptr[k] == -1)
204  BNDInsert(nbnd, bndind, bndptr, k);
205  }
206  }
207 
208 
209 
210  /****************************************************************
211  * Roll back computations
212  *****************************************************************/
213  for (nswaps--; nswaps>mincutorder; nswaps--) {
214  higain = swaps[nswaps];
215 
216  to = where[higain] = (where[higain]+1)%2;
217  SWAP(id[higain], ed[higain], tmp);
218  if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
219  BNDDelete(nbnd, bndind, bndptr, higain);
220  else if (ed[higain] > 0 && bndptr[higain] == -1)
221  BNDInsert(nbnd, bndind, bndptr, higain);
222 
223  saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
224  saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
225  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
226  k = adjncy[j];
227 
228  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
229  INC_DEC(id[k], ed[k], kwgt);
230 
231  if (bndptr[k] != -1 && ed[k] == 0)
232  BNDDelete(nbnd, bndind, bndptr, k);
233  if (bndptr[k] == -1 && ed[k] > 0)
234  BNDInsert(nbnd, bndind, bndptr, k);
235  }
236  }
237 
238  if (ctrl->dbglvl&DBG_REFINE) {
239  printf("\tMincut: %6d at %5d, NBND: %6d, NPwgts: [", mincut, mincutorder, nbnd);
240  for (l=0; l<ncon; l++)
241  printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
242  printf("], LB: %.3f\n", Compute2WayHLoadImbalance(ncon, npwgts, tpwgts));
243  }
244 
245  graph->mincut = mincut;
246  graph->nbnd = nbnd;
247 
248 
249  for (i=0; i<ncon; i++) {
250  PQueueFree(ctrl, &parts[i][0]);
251  PQueueFree(ctrl, &parts[i][1]);
252  }
253 
254  idxwspacefree(ctrl, nvtxs);
255  idxwspacefree(ctrl, nvtxs);
256  idxwspacefree(ctrl, nvtxs);
257  idxwspacefree(ctrl, nvtxs);
258 
259 }
260 
#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
#define samax2
Definition: rename.h:396
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
float * npwgts
Definition: struct.h:196
int idxtype
Definition: struct.h:19
int dbglvl
Definition: struct.h:216
#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 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 PQueueFree
Definition: rename.h:317
#define MocGeneral2WayBalance
Definition: rename.h:147
#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
#define MocBalance2Way
Definition: rename.h:146