Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
minitpart.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * minitpart.c
5  *
6  * This file contains code that performs the initial partition of the
7  * coarsest graph
8  *
9  * Started 7/23/97
10  * George
11  *
12  * $Id: minitpart.c,v 1.2 1998/11/30 15:08:37 karypis Exp $
13  *
14  */
15 
16 #include <metis.h>
17 
18 /*************************************************************************
19 * This function computes the initial bisection of the coarsest graph
20 **************************************************************************/
21 void MocInit2WayPartition(CtrlType *ctrl, GraphType *graph, float *tpwgts, float ubfactor)
22 {
23  int i, dbglvl;
24 
25  dbglvl = ctrl->dbglvl;
26  IFSET(ctrl->dbglvl, DBG_REFINE, ctrl->dbglvl -= DBG_REFINE);
27  IFSET(ctrl->dbglvl, DBG_MOVEINFO, ctrl->dbglvl -= DBG_MOVEINFO);
28 
29  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr));
30 
31  switch (ctrl->IType) {
32  case IPART_GGPKL:
33  MocGrowBisection(ctrl, graph, tpwgts, ubfactor);
34  break;
35  case IPART_RANDOM:
36  MocRandomBisection(ctrl, graph, tpwgts, ubfactor);
37  break;
38  default:
39  errexit("Unknown initial partition type: %d\n", ctrl->IType);
40  }
41 
42  IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial Cut: %d [%d]\n", graph->mincut, graph->where[0]));
43  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));
44  ctrl->dbglvl = dbglvl;
45 
46 }
47 
48 
49 
50 
51 
52 /*************************************************************************
53 * This function takes a graph and produces a bisection by using a region
54 * growing algorithm. The resulting partition is returned in
55 * graph->where
56 **************************************************************************/
57 void MocGrowBisection(CtrlType *ctrl, GraphType *graph, float *tpwgts, float ubfactor)
58 {
59  int i, j, k, nvtxs, ncon, from, bestcut, mincut, nbfs;
60  idxtype *bestwhere, *where;
61 
62  nvtxs = graph->nvtxs;
63 
64  MocAllocate2WayPartitionMemory(ctrl, graph);
65  where = graph->where;
66 
67  bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");
68  nbfs = 2*(nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
69  bestcut = idxsum(graph->nedges, graph->adjwgt);
70 
71  for (; nbfs>0; nbfs--) {
72  idxset(nvtxs, 1, where);
73  where[RandomInRange(nvtxs)] = 0;
74 
75  MocCompute2WayPartitionParams(ctrl, graph);
76 
77  MocInit2WayBalance(ctrl, graph, tpwgts);
78 
79  MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 4);
80 
81  MocBalance2Way(ctrl, graph, tpwgts, 1.02);
82  MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 4);
83 
84  if (bestcut >= graph->mincut) {
85  bestcut = graph->mincut;
86  idxcopy(nvtxs, where, bestwhere);
87  if (bestcut == 0)
88  break;
89  }
90  }
91 
92  graph->mincut = bestcut;
93  idxcopy(nvtxs, bestwhere, where);
94 
95  GKfree(&bestwhere, LTERM);
96 }
97 
98 
99 
100 /*************************************************************************
101 * This function takes a graph and produces a bisection by using a region
102 * growing algorithm. The resulting partition is returned in
103 * graph->where
104 **************************************************************************/
105 void MocRandomBisection(CtrlType *ctrl, GraphType *graph, float *tpwgts, float ubfactor)
106 {
107  int i, ii, j, k, nvtxs, ncon, from, bestcut, mincut, nbfs, qnum;
108  idxtype *bestwhere, *where, *perm;
109  int counts[MAXNCON];
110  float *nvwgt;
111 
112  nvtxs = graph->nvtxs;
113  ncon = graph->ncon;
114  nvwgt = graph->nvwgt;
115 
116  MocAllocate2WayPartitionMemory(ctrl, graph);
117  where = graph->where;
118 
119  bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");
120  nbfs = 2*(nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
121  bestcut = idxsum(graph->nedges, graph->adjwgt);
122  perm = idxmalloc(nvtxs, "BisectGraph: perm");
123 
124  for (; nbfs>0; nbfs--) {
125  for (i=0; i<ncon; i++)
126  counts[i] = 0;
127 
128  RandomPermute(nvtxs, perm, 1);
129 
130  /* Partition by spliting the queues randomly */
131  for (ii=0; ii<nvtxs; ii++) {
132  i = perm[ii];
133  qnum = samax(ncon, nvwgt+i*ncon);
134  where[i] = counts[qnum];
135  counts[qnum] = (counts[qnum]+1)%2;
136  }
137 
138  MocCompute2WayPartitionParams(ctrl, graph);
139 
140  MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 6);
141  MocBalance2Way(ctrl, graph, tpwgts, 1.02);
142  MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 6);
143  MocBalance2Way(ctrl, graph, tpwgts, 1.02);
144  MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 6);
145 
146  /*
147  printf("Edgecut: %6d, NPwgts: [", graph->mincut);
148  for (i=0; i<graph->ncon; i++)
149  printf("(%.3f %.3f) ", graph->npwgts[i], graph->npwgts[graph->ncon+i]);
150  printf("]\n");
151  */
152 
153  if (bestcut >= graph->mincut) {
154  bestcut = graph->mincut;
155  idxcopy(nvtxs, where, bestwhere);
156  if (bestcut == 0)
157  break;
158  }
159  }
160 
161  graph->mincut = bestcut;
162  idxcopy(nvtxs, bestwhere, where);
163 
164  GKfree(&bestwhere, &perm, LTERM);
165 }
166 
167 
168 
169 
170 /*************************************************************************
171 * This function balances two partitions by moving the highest gain
172 * (including negative gain) vertices to the other domain.
173 * It is used only when tha unbalance is due to non contigous
174 * subdomains. That is, the are no boundary vertices.
175 * It moves vertices from the domain that is overweight to the one that
176 * is underweight.
177 **************************************************************************/
178 void MocInit2WayBalance(CtrlType *ctrl, GraphType *graph, float *tpwgts)
179 {
180  int i, ii, j, k, l, kwgt, nvtxs, nbnd, ncon, nswaps, from, to, pass, me, cnum, tmp;
181  idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
182  idxtype *perm, *qnum;
183  float *nvwgt, *npwgts;
184  PQueueType parts[MAXNCON][2];
185  int higain, oldgain, mincut;
186 
187  nvtxs = graph->nvtxs;
188  ncon = graph->ncon;
189  xadj = graph->xadj;
190  adjncy = graph->adjncy;
191  nvwgt = graph->nvwgt;
192  adjwgt = graph->adjwgt;
193  where = graph->where;
194  id = graph->id;
195  ed = graph->ed;
196  npwgts = graph->npwgts;
197  bndptr = graph->bndptr;
198  bndind = graph->bndind;
199 
200  perm = idxwspacemalloc(ctrl, nvtxs);
201  qnum = idxwspacemalloc(ctrl, nvtxs);
202 
203  /* This is called for initial partitioning so we know from where to pick nodes */
204  from = 1;
205  to = (from+1)%2;
206 
207  if (ctrl->dbglvl&DBG_REFINE) {
208  printf("Parts: [");
209  for (l=0; l<ncon; l++)
210  printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
211  printf("] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: %.3f [B]\n", tpwgts[0], tpwgts[1],
212  graph->nvtxs, graph->nbnd, graph->mincut,
213  Compute2WayHLoadImbalance(ncon, npwgts, tpwgts));
214  }
215 
216  for (i=0; i<ncon; i++) {
217  PQueueInit(ctrl, &parts[i][0], nvtxs, PLUS_GAINSPAN+1);
218  PQueueInit(ctrl, &parts[i][1], nvtxs, PLUS_GAINSPAN+1);
219  }
220 
221  ASSERT(ComputeCut(graph, where) == graph->mincut);
222  ASSERT(CheckBnd(graph));
223  ASSERT(CheckGraph(graph));
224 
225  /* Compute the queues in which each vertex will be assigned to */
226  for (i=0; i<nvtxs; i++)
227  qnum[i] = samax(ncon, nvwgt+i*ncon);
228 
229  /* Insert the nodes of the proper partition in the appropriate priority queue */
230  RandomPermute(nvtxs, perm, 1);
231  for (ii=0; ii<nvtxs; ii++) {
232  i = perm[ii];
233  if (where[i] == from) {
234  if (ed[i] > 0)
235  PQueueInsert(&parts[qnum[i]][0], i, ed[i]-id[i]);
236  else
237  PQueueInsert(&parts[qnum[i]][1], i, ed[i]-id[i]);
238  }
239  }
240 
241 
242  mincut = graph->mincut;
243  nbnd = graph->nbnd;
244  for (nswaps=0; nswaps<nvtxs; nswaps++) {
245  if (AreAnyVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, nvwgt, tpwgts[from]))
246  break;
247 
248  if ((cnum = SelectQueueOneWay(ncon, npwgts, tpwgts, from, parts)) == -1)
249  break;
250 
251  if ((higain = PQueueGetMax(&parts[cnum][0])) == -1)
252  higain = PQueueGetMax(&parts[cnum][1]);
253 
254  mincut -= (ed[higain]-id[higain]);
255  saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
256  saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
257 
258  where[higain] = to;
259 
260  if (ctrl->dbglvl&DBG_MOVEINFO) {
261  printf("Moved %6d from %d(%d). [%5d] %5d, NPwgts: ", higain, from, cnum, ed[higain]-id[higain], mincut);
262  for (l=0; l<ncon; l++)
263  printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
264  printf(", LB: %.3f\n", Compute2WayHLoadImbalance(ncon, npwgts, tpwgts));
265  if (ed[higain] == 0 && id[higain] > 0)
266  printf("\t Pulled from the interior!\n");
267  }
268 
269 
270  /**************************************************************
271  * Update the id[i]/ed[i] values of the affected nodes
272  ***************************************************************/
273  SWAP(id[higain], ed[higain], tmp);
274  if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
275  BNDDelete(nbnd, bndind, bndptr, higain);
276  if (ed[higain] > 0 && bndptr[higain] == -1)
277  BNDInsert(nbnd, bndind, bndptr, higain);
278 
279  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
280  k = adjncy[j];
281  oldgain = ed[k]-id[k];
282 
283  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
284  INC_DEC(id[k], ed[k], kwgt);
285 
286  /* Update the queue position */
287  if (where[k] == from) {
288  if (ed[k] > 0 && bndptr[k] == -1) { /* It moves in boundary */
289  PQueueDelete(&parts[qnum[k]][1], k, oldgain);
290  PQueueInsert(&parts[qnum[k]][0], k, ed[k]-id[k]);
291  }
292  else { /* It must be in the boundary already */
293  if (bndptr[k] == -1)
294  printf("What you thought was wrong!\n");
295  PQueueUpdate(&parts[qnum[k]][0], k, oldgain, ed[k]-id[k]);
296  }
297  }
298 
299  /* Update its boundary information */
300  if (ed[k] == 0 && bndptr[k] != -1)
301  BNDDelete(nbnd, bndind, bndptr, k);
302  else if (ed[k] > 0 && bndptr[k] == -1)
303  BNDInsert(nbnd, bndind, bndptr, k);
304  }
305 
306  ASSERTP(ComputeCut(graph, where) == mincut, ("%d != %d\n", ComputeCut(graph, where), mincut));
307 
308  }
309 
310  if (ctrl->dbglvl&DBG_REFINE) {
311  printf("\tMincut: %6d, NBND: %6d, NPwgts: ", mincut, nbnd);
312  for (l=0; l<ncon; l++)
313  printf("(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
314  printf(", LB: %.3f\n", Compute2WayHLoadImbalance(ncon, npwgts, tpwgts));
315  }
316 
317  graph->mincut = mincut;
318  graph->nbnd = nbnd;
319 
320  for (i=0; i<ncon; i++) {
321  PQueueFree(ctrl, &parts[i][0]);
322  PQueueFree(ctrl, &parts[i][1]);
323  }
324 
325  ASSERT(ComputeCut(graph, where) == graph->mincut);
326  ASSERT(CheckBnd(graph));
327 
328  idxwspacefree(ctrl, nvtxs);
329  idxwspacefree(ctrl, nvtxs);
330 }
331 
332 
333 
334 
335 /*************************************************************************
336 * This function selects the partition number and the queue from which
337 * we will move vertices out
338 **************************************************************************/
339 int SelectQueueOneWay(int ncon, float *npwgts, float *tpwgts, int from, PQueueType queues[MAXNCON][2])
340 {
341  int i, cnum=-1;
342  float max=0.0;
343 
344  for (i=0; i<ncon; i++) {
345  if (npwgts[from*ncon+i]-tpwgts[from] >= max &&
346  PQueueGetSize(&queues[i][0]) + PQueueGetSize(&queues[i][1]) > 0) {
347  max = npwgts[from*ncon+i]-tpwgts[0];
348  cnum = i;
349  }
350  }
351 
352  return cnum;
353 }
354 
355 
#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
#define RandomInRange(u)
Definition: macros.h:23
idxtype * id
Definition: struct.h:181
#define MocGrowBisection
Definition: rename.h:205
#define Compute2WayHLoadImbalance
Definition: rename.h:185
#define AreAnyVwgtsBelow
Definition: rename.h:280
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: macros.h:102
int IType
Definition: struct.h:218
int mincut
Definition: struct.h:175
#define DBG_MOVEINFO
Definition: defs.h:159
idxtype * bndptr
Definition: struct.h:178
#define IPART_GGPKL
Definition: defs.h:108
#define idxwspacemalloc
Definition: rename.h:164
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
float * npwgts
Definition: struct.h:196
int SelectQueueOneWay(int ncon, float *npwgts, float *tpwgts, int from, PQueueType queues[MAXNCON][2])
Definition: minitpart.c:339
int idxtype
Definition: struct.h:19
#define SMALLNIPARTS
Definition: defs.h:139
#define IPART_RANDOM
Definition: defs.h:110
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define MocFM_2WayEdgeRefine
Definition: rename.h:182
#define MocCompute2WayPartitionParams
Definition: rename.h:270
int PQueueGetSize(PQueueType *queue)
Definition: pqueue.c:129
#define DBG_IPART
Definition: defs.h:158
#define LARGENIPARTS
Definition: defs.h:138
#define CheckBnd
Definition: rename.h:44
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxcopy(n, a, b)
Definition: macros.h:44
int CoarsenTo
Definition: struct.h:215
void GKfree(void **ptr1,...)
Definition: util.c:121
#define ASSERTP(expr, msg)
Definition: macros.h:142
int ncon
Definition: struct.h:194
#define BNDDelete(nbnd, bndind, bndptr, vtx)
Definition: macros.h:109
#define MAXNCON
Definition: defs.h:20
idxtype * bndind
Definition: struct.h:178
#define errexit
Definition: rename.h:379
#define MocInit2WayBalance
Definition: rename.h:207
timer InitPartTmr
Definition: struct.h:230
#define MocInit2WayPartition
Definition: rename.h:204
#define INC_DEC(a, b, val)
Definition: macros.h:39
#define PLUS_GAINSPAN
Definition: defs.h:23
#define MocRandomBisection
Definition: rename.h:206
#define samax
Definition: rename.h:395
#define PQueueGetMax
Definition: rename.h:322
#define DBG_TIME
Definition: defs.h:154
int nedges
Definition: struct.h:161
#define idxmalloc
Definition: rename.h:383
int CheckGraph(GraphType *)
#define PQueueInsert
Definition: rename.h:318
int nvtxs
Definition: struct.h:161
#define MocAllocate2WayPartitionMemory
Definition: rename.h:269
#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
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define PQueueInit
Definition: rename.h:315
#define starttimer(tmr)
Definition: macros.h:53
#define MocBalance2Way
Definition: rename.h:146