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 **************************************************************************/
MocInit2WayPartition(CtrlType * ctrl,GraphType * graph,float * tpwgts,float ubfactor)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 graclus_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 **************************************************************************/
MocGrowBisection(CtrlType * ctrl,GraphType * graph,float * tpwgts,float ubfactor)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((void**) &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 **************************************************************************/
MocRandomBisection(CtrlType * ctrl,GraphType * graph,float * tpwgts,float ubfactor)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((void**) &bestwhere, (void**) &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 **************************************************************************/
MocInit2WayBalance(CtrlType * ctrl,GraphType * graph,float * tpwgts)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 **************************************************************************/
SelectQueueOneWay(int ncon,float * npwgts,float * tpwgts,int from,PQueueType queues[MAXNCON][2])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
356