Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
mkwayrefine.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * mkwayrefine.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: mkwayrefine.c,v 1.2 1998/11/27 18:16:19 karypis Exp $
12  */
13 
14 #include <metis.h>
15 
16 
17 /*************************************************************************
18 * This function is the entry point of refinement
19 **************************************************************************/
20 void MocRefineKWayHorizontal(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts,
21  float *ubvec)
22 {
23 
25 
26  /* Compute the parameters of the coarsest graph */
27  MocComputeKWayPartitionParams(ctrl, graph, nparts);
28 
29  for (;;) {
30  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
31 
32  if (!MocIsHBalanced(graph->ncon, nparts, graph->npwgts, ubvec)) {
33  MocComputeKWayBalanceBoundary(ctrl, graph, nparts);
34  MCGreedy_KWayEdgeBalanceHorizontal(ctrl, graph, nparts, ubvec, 4);
35  ComputeKWayBoundary(ctrl, graph, nparts);
36  }
37 
38  MCRandom_KWayEdgeRefineHorizontal(ctrl, graph, nparts, ubvec, 10);
39 
40  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
41 
42  if (graph == orggraph)
43  break;
44 
45  graph = graph->finer;
46  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
47  MocProjectKWayPartition(ctrl, graph, nparts);
48  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
49  }
50 
51  if (!MocIsHBalanced(graph->ncon, nparts, graph->npwgts, ubvec)) {
52  MocComputeKWayBalanceBoundary(ctrl, graph, nparts);
53  MCGreedy_KWayEdgeBalanceHorizontal(ctrl, graph, nparts, ubvec, 4);
54  ComputeKWayBoundary(ctrl, graph, nparts);
55  MCRandom_KWayEdgeRefineHorizontal(ctrl, graph, nparts, ubvec, 10);
56  }
57 
58  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
59 }
60 
61 
62 
63 
64 /*************************************************************************
65 * This function allocates memory for k-way edge refinement
66 **************************************************************************/
68 {
69  int nvtxs, ncon, pad64;
70 
71  nvtxs = graph->nvtxs;
72  ncon = graph->ncon;
73 
74  pad64 = (3*nvtxs)%2;
75 
76  graph->rdata = idxmalloc(3*nvtxs+(sizeof(RInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateKWayPartitionMemory: rdata");
77  graph->where = graph->rdata;
78  graph->bndptr = graph->rdata + nvtxs;
79  graph->bndind = graph->rdata + 2*nvtxs;
80  graph->rinfo = (RInfoType *)(graph->rdata + 3*nvtxs + pad64);
81 
82  graph->npwgts = fmalloc(ncon*nparts, "MocAllocateKWayPartitionMemory: npwgts");
83 }
84 
85 
86 /*************************************************************************
87 * This function computes the initial id/ed
88 **************************************************************************/
90 {
91  int i, j, k, l, nvtxs, ncon, nbnd, mincut, me, other;
92  idxtype *xadj, *adjncy, *adjwgt, *where, *bndind, *bndptr;
93  RInfoType *rinfo, *myrinfo;
94  EDegreeType *myedegrees;
95  float *nvwgt, *npwgts;
96 
97  nvtxs = graph->nvtxs;
98  ncon = graph->ncon;
99  xadj = graph->xadj;
100  nvwgt = graph->nvwgt;
101  adjncy = graph->adjncy;
102  adjwgt = graph->adjwgt;
103 
104  where = graph->where;
105  npwgts = sset(ncon*nparts, 0.0, graph->npwgts);
106  bndind = graph->bndind;
107  bndptr = idxset(nvtxs, -1, graph->bndptr);
108  rinfo = graph->rinfo;
109 
110 
111  /*------------------------------------------------------------
112  / Compute now the id/ed degrees
113  /------------------------------------------------------------*/
114  ctrl->wspace.cdegree = 0;
115  nbnd = mincut = 0;
116  for (i=0; i<nvtxs; i++) {
117  me = where[i];
118  saxpy(ncon, 1.0, nvwgt+i*ncon, 1, npwgts+me*ncon, 1);
119 
120  myrinfo = rinfo+i;
121  myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
122  myrinfo->edegrees = NULL;
123 
124  for (j=xadj[i]; j<xadj[i+1]; j++) {
125  if (me != where[adjncy[j]])
126  myrinfo->ed += adjwgt[j];
127  }
128  myrinfo->id = graph->adjwgtsum[i] - myrinfo->ed;
129 
130  if (myrinfo->ed > 0)
131  mincut += myrinfo->ed;
132 
133  if (myrinfo->ed-myrinfo->id >= 0)
134  BNDInsert(nbnd, bndind, bndptr, i);
135 
136  /* Time to compute the particular external degrees */
137  if (myrinfo->ed > 0) {
138  myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
139  ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
140 
141  for (j=xadj[i]; j<xadj[i+1]; j++) {
142  other = where[adjncy[j]];
143  if (me != other) {
144  for (k=0; k<myrinfo->ndegrees; k++) {
145  if (myedegrees[k].pid == other) {
146  myedegrees[k].ed += adjwgt[j];
147  break;
148  }
149  }
150  if (k == myrinfo->ndegrees) {
151  myedegrees[myrinfo->ndegrees].pid = other;
152  myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
153  }
154  }
155  }
156 
157  ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
158  }
159  }
160 
161  graph->mincut = mincut/2;
162  graph->nbnd = nbnd;
163 
164 }
165 
166 
167 
168 /*************************************************************************
169 * This function projects a partition, and at the same time computes the
170 * parameters for refinement.
171 **************************************************************************/
173 {
174  int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
175  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
176  idxtype *cmap, *where, *bndptr, *bndind;
177  idxtype *cwhere;
178  GraphType *cgraph;
179  RInfoType *crinfo, *rinfo, *myrinfo;
180  EDegreeType *myedegrees;
181  idxtype *htable;
182 
183  cgraph = graph->coarser;
184  cwhere = cgraph->where;
185  crinfo = cgraph->rinfo;
186 
187  nvtxs = graph->nvtxs;
188  cmap = graph->cmap;
189  xadj = graph->xadj;
190  adjncy = graph->adjncy;
191  adjwgt = graph->adjwgt;
192  adjwgtsum = graph->adjwgtsum;
193 
194  MocAllocateKWayPartitionMemory(ctrl, graph, nparts);
195  where = graph->where;
196  rinfo = graph->rinfo;
197  bndind = graph->bndind;
198  bndptr = idxset(nvtxs, -1, graph->bndptr);
199 
200  /* Go through and project partition and compute id/ed for the nodes */
201  for (i=0; i<nvtxs; i++) {
202  k = cmap[i];
203  where[i] = cwhere[k];
204  cmap[i] = crinfo[k].ed; /* For optimization */
205  }
206 
207  htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
208 
209  ctrl->wspace.cdegree = 0;
210  for (nbnd=0, i=0; i<nvtxs; i++) {
211  me = where[i];
212 
213  myrinfo = rinfo+i;
214  myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
215  myrinfo->edegrees = NULL;
216 
217  myrinfo->id = adjwgtsum[i];
218 
219  if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
220  istart = xadj[i];
221  iend = xadj[i+1];
222 
223  myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
224  ctrl->wspace.cdegree += iend-istart;
225 
226  ndegrees = 0;
227  for (j=istart; j<iend; j++) {
228  other = where[adjncy[j]];
229  if (me != other) {
230  myrinfo->ed += adjwgt[j];
231  if ((k = htable[other]) == -1) {
232  htable[other] = ndegrees;
233  myedegrees[ndegrees].pid = other;
234  myedegrees[ndegrees++].ed = adjwgt[j];
235  }
236  else {
237  myedegrees[k].ed += adjwgt[j];
238  }
239  }
240  }
241  myrinfo->id -= myrinfo->ed;
242 
243  /* Remove space for edegrees if it was interior */
244  if (myrinfo->ed == 0) {
245  myrinfo->edegrees = NULL;
246  ctrl->wspace.cdegree -= iend-istart;
247  }
248  else {
249  if (myrinfo->ed-myrinfo->id >= 0)
250  BNDInsert(nbnd, bndind, bndptr, i);
251 
252  myrinfo->ndegrees = ndegrees;
253 
254  for (j=0; j<ndegrees; j++)
255  htable[myedegrees[j].pid] = -1;
256  }
257  }
258  }
259 
260  scopy(graph->ncon*nparts, cgraph->npwgts, graph->npwgts);
261  graph->mincut = cgraph->mincut;
262  graph->nbnd = nbnd;
263 
264  FreeGraph(graph->coarser);
265  graph->coarser = NULL;
266 
267  idxwspacefree(ctrl, nparts);
268 
269  ASSERT(CheckBnd2(graph));
270 
271 }
272 
273 
274 
275 /*************************************************************************
276 * This function computes the boundary definition for balancing
277 **************************************************************************/
279 {
280  int i, nvtxs, nbnd;
281  idxtype *bndind, *bndptr;
282 
283  nvtxs = graph->nvtxs;
284  bndind = graph->bndind;
285  bndptr = idxset(nvtxs, -1, graph->bndptr);
286 
287 
288  /* Compute the new boundary */
289  nbnd = 0;
290  for (i=0; i<nvtxs; i++) {
291  if (graph->rinfo[i].ed > 0)
292  BNDInsert(nbnd, bndind, bndptr, i);
293  }
294 
295  graph->nbnd = nbnd;
296 }
297 
EDegreeType * edegrees
Definition: struct.h:102
timer ProjectTmr
Definition: struct.h:230
timer RefTmr
Definition: struct.h:230
#define idxwspacefree
Definition: rename.h:165
int ndegrees
Definition: struct.h:121
#define MCGreedy_KWayEdgeBalanceHorizontal
Definition: rename.h:225
#define saxpy
Definition: rename.h:409
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
int nbnd
Definition: struct.h:177
#define scopy(n, a, b)
Definition: macros.h:43
idxtype ed
Definition: struct.h:79
idxtype pid
Definition: struct.h:78
#define FreeGraph
Definition: rename.h:169
#define fmalloc
Definition: rename.h:384
#define MocRefineKWayHorizontal
Definition: rename.h:235
#define MocAllocateKWayPartitionMemory
Definition: rename.h:236
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: macros.h:102
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
idxtype * rdata
Definition: struct.h:157
#define idxwspacemalloc
Definition: rename.h:164
struct graphdef * coarser
Definition: struct.h:198
#define stoptimer(tmr)
Definition: macros.h:54
struct graphdef * finer
Definition: struct.h:198
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define MocComputeKWayPartitionParams
Definition: rename.h:237
float * npwgts
Definition: struct.h:196
int idxtype
Definition: struct.h:19
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
int ed
Definition: struct.h:120
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
RInfoType * rinfo
Definition: struct.h:184
int cdegree
Definition: struct.h:104
#define MCRandom_KWayEdgeRefineHorizontal
Definition: rename.h:224
#define MocComputeKWayBalanceBoundary
Definition: rename.h:239
int ncon
Definition: struct.h:194
#define CheckBnd2
Definition: rename.h:45
idxtype * bndind
Definition: struct.h:178
timer UncoarsenTmr
Definition: struct.h:230
#define MocIsHBalanced
Definition: rename.h:229
#define MocProjectKWayPartition
Definition: rename.h:238
#define DBG_TIME
Definition: defs.h:154
EDegreeType * edegrees
Definition: struct.h:122
#define idxmalloc
Definition: rename.h:383
int nvtxs
Definition: struct.h:161
WorkSpaceType wspace
Definition: struct.h:227
#define sset
Definition: rename.h:391
#define ASSERT(expr)
Definition: macros.h:130
float * nvwgt
Definition: struct.h:195
#define ComputeKWayBoundary
Definition: rename.h:111
int id
Definition: struct.h:120
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define starttimer(tmr)
Definition: macros.h:53