1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * kwayrefine.c
5 *
6 * This file contains the driving routines for multilevel k-way refinement
7 *
8 * Started 7/28/97
9 * George
10 *
11 * $Id: kwayrefine.c,v 1.1 1998/11/27 17:59:17 karypis Exp $
12 */
13
14 #include "metis.h"
15
16
17 /*************************************************************************
18 * This function is the entry point of refinement
19 **************************************************************************/
RefineKWay(CtrlType * ctrl,GraphType * orggraph,GraphType * graph,int nparts,float * tpwgts,float ubfactor)20 void RefineKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
21 {
22 int i, nlevels, mustfree=0;
23 GraphType *ptr;
24
25 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
26
27 /* Compute the parameters of the coarsest graph */
28 ComputeKWayPartitionParams(ctrl, graph, nparts);
29
30 /* Take care any non-contiguity */
31 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr1));
32 if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
33 EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
34 EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
35 EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
36 }
37 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr1));
38
39 /* Determine how many levels are there */
40 for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++);
41
42 for (i=0; ;i++) {
43 /* PrintSubDomainGraph(graph, nparts, graph->where); */
44 if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN && (i == nlevels/2 || i == nlevels/2+1))
45 EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
46
47 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
48
49 if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
50 ComputeKWayBalanceBoundary(ctrl, graph, nparts);
51 if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN)
52 Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1);
53 else
54 Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1);
55 ComputeKWayBoundary(ctrl, graph, nparts);
56 }
57
58 switch (ctrl->RType) {
59 case RTYPE_KWAYRANDOM:
60 Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1);
61 break;
62 case RTYPE_KWAYGREEDY:
63 Greedy_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10);
64 break;
65 case RTYPE_KWAYRANDOM_MCONN:
66 Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1);
67 break;
68 }
69 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
70
71 if (graph == orggraph)
72 break;
73
74 GKfree((void**) &graph->gdata, LTERM); /* Deallocate the graph related arrays */
75
76 graph = graph->finer;
77
78 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
79 if (graph->vwgt == NULL) {
80 graph->vwgt = idxsmalloc(graph->nvtxs, 1, "RefineKWay: graph->vwgt");
81 graph->adjwgt = idxsmalloc(graph->nedges, 1, "RefineKWay: graph->adjwgt");
82 mustfree = 1;
83 }
84 ProjectKWayPartition(ctrl, graph, nparts);
85 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
86 }
87
88 if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
89 ComputeKWayBalanceBoundary(ctrl, graph, nparts);
90 if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
91 Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8);
92 Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
93 }
94 else {
95 Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8);
96 Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
97 }
98 }
99
100 /* Take care any trivial non-contiguity */
101 IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr2));
102 EliminateComponents(ctrl, graph, nparts, tpwgts, ubfactor);
103 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr2));
104
105 if (mustfree)
106 GKfree((void**) &graph->vwgt, (void**) &graph->adjwgt, LTERM);
107
108 IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
109 }
110
111
112 /*************************************************************************
113 * This function allocates memory for k-way edge refinement
114 **************************************************************************/
AllocateKWayPartitionMemory(CtrlType * ctrl,GraphType * graph,int nparts)115 void AllocateKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
116 {
117 int nvtxs, pad64;
118
119 nvtxs = graph->nvtxs;
120
121 pad64 = (3*nvtxs+nparts)%2;
122
123 graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(RInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateKWayPartitionMemory: rdata");
124 graph->pwgts = graph->rdata;
125 graph->where = graph->rdata + nparts;
126 graph->bndptr = graph->rdata + nvtxs + nparts;
127 graph->bndind = graph->rdata + 2*nvtxs + nparts;
128 graph->rinfo = (RInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
129
130 /*
131 if (ctrl->wspace.edegrees != NULL)
132 free(ctrl->wspace.edegrees);
133 ctrl->wspace.edegrees = (EDegreeType *)GKmalloc(graph->nedges*sizeof(EDegreeType), "AllocateKWayPartitionMemory: edegrees");
134 */
135 }
136
137
138 /*************************************************************************
139 * This function computes the initial id/ed
140 **************************************************************************/
ComputeKWayPartitionParams(CtrlType * ctrl,GraphType * graph,int nparts)141 void ComputeKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
142 {
143 int i, j, k, l, nvtxs, nbnd, mincut, me, other;
144 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
145 RInfoType *rinfo, *myrinfo;
146 EDegreeType *myedegrees;
147
148 nvtxs = graph->nvtxs;
149 xadj = graph->xadj;
150 vwgt = graph->vwgt;
151 adjncy = graph->adjncy;
152 adjwgt = graph->adjwgt;
153
154 where = graph->where;
155 pwgts = idxset(nparts, 0, graph->pwgts);
156 bndind = graph->bndind;
157 bndptr = idxset(nvtxs, -1, graph->bndptr);
158 rinfo = graph->rinfo;
159
160
161 /*------------------------------------------------------------
162 / Compute now the id/ed degrees
163 /------------------------------------------------------------*/
164 ctrl->wspace.cdegree = 0;
165 nbnd = mincut = 0;
166 for (i=0; i<nvtxs; i++) {
167 me = where[i];
168 pwgts[me] += vwgt[i];
169
170 myrinfo = rinfo+i;
171 myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
172 myrinfo->edegrees = NULL;
173
174 for (j=xadj[i]; j<xadj[i+1]; j++) {
175 if (me != where[adjncy[j]])
176 myrinfo->ed += adjwgt[j];
177 }
178 myrinfo->id = graph->adjwgtsum[i] - myrinfo->ed;
179
180 if (myrinfo->ed > 0)
181 mincut += myrinfo->ed;
182
183 if (myrinfo->ed-myrinfo->id >= 0)
184 BNDInsert(nbnd, bndind, bndptr, i);
185
186 /* Time to compute the particular external degrees */
187 if (myrinfo->ed > 0) {
188 myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
189 ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
190
191 for (j=xadj[i]; j<xadj[i+1]; j++) {
192 other = where[adjncy[j]];
193 if (me != other) {
194 for (k=0; k<myrinfo->ndegrees; k++) {
195 if (myedegrees[k].pid == other) {
196 myedegrees[k].ed += adjwgt[j];
197 break;
198 }
199 }
200 if (k == myrinfo->ndegrees) {
201 myedegrees[myrinfo->ndegrees].pid = other;
202 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
203 }
204 }
205 }
206
207 ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
208 }
209 }
210
211 graph->mincut = mincut/2;
212 graph->nbnd = nbnd;
213
214 }
215
216
217
218 /*************************************************************************
219 * This function projects a partition, and at the same time computes the
220 * parameters for refinement.
221 **************************************************************************/
ProjectKWayPartition(CtrlType * ctrl,GraphType * graph,int nparts)222 void ProjectKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
223 {
224 int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
225 idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
226 idxtype *cmap, *where, *bndptr, *bndind;
227 idxtype *cwhere;
228 GraphType *cgraph;
229 RInfoType *crinfo, *rinfo, *myrinfo;
230 EDegreeType *myedegrees;
231 idxtype *htable;
232
233 cgraph = graph->coarser;
234 cwhere = cgraph->where;
235 crinfo = cgraph->rinfo;
236
237 nvtxs = graph->nvtxs;
238 cmap = graph->cmap;
239 xadj = graph->xadj;
240 adjncy = graph->adjncy;
241 adjwgt = graph->adjwgt;
242 adjwgtsum = graph->adjwgtsum;
243
244 AllocateKWayPartitionMemory(ctrl, graph, nparts);
245 where = graph->where;
246 rinfo = graph->rinfo;
247 bndind = graph->bndind;
248 bndptr = idxset(nvtxs, -1, graph->bndptr);
249
250 /* Go through and project partition and compute id/ed for the nodes */
251 for (i=0; i<nvtxs; i++) {
252 k = cmap[i];
253 where[i] = cwhere[k];
254 cmap[i] = crinfo[k].ed; /* For optimization */
255 }
256
257 htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
258
259 ctrl->wspace.cdegree = 0;
260 for (nbnd=0, i=0; i<nvtxs; i++) {
261 me = where[i];
262
263 myrinfo = rinfo+i;
264 myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
265 myrinfo->edegrees = NULL;
266
267 myrinfo->id = adjwgtsum[i];
268
269 if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
270 istart = xadj[i];
271 iend = xadj[i+1];
272
273 myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
274 ctrl->wspace.cdegree += iend-istart;
275
276 ndegrees = 0;
277 for (j=istart; j<iend; j++) {
278 other = where[adjncy[j]];
279 if (me != other) {
280 myrinfo->ed += adjwgt[j];
281 if ((k = htable[other]) == -1) {
282 htable[other] = ndegrees;
283 myedegrees[ndegrees].pid = other;
284 myedegrees[ndegrees++].ed = adjwgt[j];
285 }
286 else {
287 myedegrees[k].ed += adjwgt[j];
288 }
289 }
290 }
291 myrinfo->id -= myrinfo->ed;
292
293 /* Remove space for edegrees if it was interior */
294 if (myrinfo->ed == 0) {
295 myrinfo->edegrees = NULL;
296 ctrl->wspace.cdegree -= iend-istart;
297 }
298 else {
299 if (myrinfo->ed-myrinfo->id >= 0)
300 BNDInsert(nbnd, bndind, bndptr, i);
301
302 myrinfo->ndegrees = ndegrees;
303
304 for (j=0; j<ndegrees; j++)
305 htable[myedegrees[j].pid] = -1;
306 }
307 }
308 }
309
310 idxcopy(nparts, cgraph->pwgts, graph->pwgts);
311 graph->mincut = cgraph->mincut;
312 graph->nbnd = nbnd;
313
314 FreeGraph(graph->coarser);
315 graph->coarser = NULL;
316
317 idxwspacefree(ctrl, nparts);
318
319 ASSERT(CheckBnd2(graph));
320
321 }
322
323
324
325 /*************************************************************************
326 * This function checks if the partition weights are within the balance
327 * contraints
328 **************************************************************************/
IsBalanced(idxtype * pwgts,int nparts,float * tpwgts,float ubfactor)329 int IsBalanced(idxtype *pwgts, int nparts, float *tpwgts, float ubfactor)
330 {
331 int i, j, tvwgt;
332
333 tvwgt = idxsum(nparts, pwgts);
334 for (i=0; i<nparts; i++) {
335 if (pwgts[i] > tpwgts[i]*tvwgt*(ubfactor+0.005))
336 return 0;
337 }
338
339 return 1;
340 }
341
342
343 /*************************************************************************
344 * This function computes the boundary definition for balancing
345 **************************************************************************/
ComputeKWayBoundary(CtrlType * ctrl,GraphType * graph,int nparts)346 void ComputeKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
347 {
348 int i, nvtxs, nbnd;
349 idxtype *bndind, *bndptr;
350
351 nvtxs = graph->nvtxs;
352 bndind = graph->bndind;
353 bndptr = idxset(nvtxs, -1, graph->bndptr);
354
355
356 /*------------------------------------------------------------
357 / Compute the new boundary
358 /------------------------------------------------------------*/
359 nbnd = 0;
360 for (i=0; i<nvtxs; i++) {
361 if (graph->rinfo[i].ed-graph->rinfo[i].id >= 0)
362 BNDInsert(nbnd, bndind, bndptr, i);
363 }
364
365 graph->nbnd = nbnd;
366 }
367
368 /*************************************************************************
369 * This function computes the boundary definition for balancing
370 **************************************************************************/
ComputeKWayBalanceBoundary(CtrlType * ctrl,GraphType * graph,int nparts)371 void ComputeKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
372 {
373 int i, nvtxs, nbnd;
374 idxtype *bndind, *bndptr;
375
376 nvtxs = graph->nvtxs;
377 bndind = graph->bndind;
378 bndptr = idxset(nvtxs, -1, graph->bndptr);
379
380
381 /*------------------------------------------------------------
382 / Compute the new boundary
383 /------------------------------------------------------------*/
384 nbnd = 0;
385 for (i=0; i<nvtxs; i++) {
386 if (graph->rinfo[i].ed > 0)
387 BNDInsert(nbnd, bndind, bndptr, i);
388 }
389
390 graph->nbnd = nbnd;
391 }
392
393