Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
parmetis.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * parmetis.c
5  *
6  * This file contains top level routines that are used by ParMETIS
7  *
8  * Started 10/14/97
9  * George
10  *
11  * $Id: parmetis.c,v 1.1 1998/11/27 17:59:27 karypis Exp $
12  *
13  */
14 
15 #include <metis.h>
16 
17 
18 /*************************************************************************
19 * This function is the entry point for KMETIS with seed specification
20 * in options[7]
21 **************************************************************************/
22 void METIS_PartGraphKway2(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
23  idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts,
24  int *options, int *edgecut, idxtype *part)
25 {
26  int i;
27  float *tpwgts;
28 
29  tpwgts = fmalloc(*nparts, "KMETIS: tpwgts");
30  for (i=0; i<*nparts; i++)
31  tpwgts[i] = 1.0/(1.0*(*nparts));
32 
33  METIS_WPartGraphKway2(nvtxs, xadj, adjncy, vwgt, adjwgt, wgtflag, numflag, nparts,
34  tpwgts, options, edgecut, part);
35 
36  free(tpwgts);
37 }
38 
39 
40 /*************************************************************************
41 * This function is the entry point for KWMETIS with seed specification
42 * in options[7]
43 **************************************************************************/
44 void METIS_WPartGraphKway2(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
45  idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts,
46  float *tpwgts, int *options, int *edgecut, idxtype *part)
47 {
48  int i, j;
50  CtrlType ctrl;
51 
52  if (*numflag == 1)
53  Change2CNumbering(*nvtxs, xadj, adjncy);
54 
55  SetUpGraph(&graph, OP_KMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, *wgtflag);
56 
57  if (options[0] == 0) { /* Use the default parameters */
58  ctrl.CType = KMETIS_CTYPE;
59  ctrl.IType = KMETIS_ITYPE;
60  ctrl.RType = KMETIS_RTYPE;
61  ctrl.dbglvl = KMETIS_DBGLVL;
62  }
63  else {
64  ctrl.CType = options[OPTION_CTYPE];
65  ctrl.IType = options[OPTION_ITYPE];
66  ctrl.RType = options[OPTION_RTYPE];
67  ctrl.dbglvl = options[OPTION_DBGLVL];
68  }
69  ctrl.optype = OP_KMETIS;
70  ctrl.CoarsenTo = 20*(*nparts);
71  ctrl.maxvwgt = 1.5*((graph.vwgt ? idxsum(*nvtxs, graph.vwgt) : (*nvtxs))/ctrl.CoarsenTo);
72 
73  InitRandom(options[7]);
74 
75  AllocateWorkSpace(&ctrl, &graph, *nparts);
76 
77  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
78  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
79 
80  *edgecut = MlevelKWayPartitioning(&ctrl, &graph, *nparts, part, tpwgts, 1.03);
81 
82  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
83  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
84 
85  FreeWorkSpace(&ctrl, &graph);
86 
87  if (*numflag == 1)
88  Change2FNumbering(*nvtxs, xadj, adjncy, part);
89 }
90 
91 
92 /*************************************************************************
93 * This function is the entry point for the node ND code for ParMETIS
94 **************************************************************************/
95 void METIS_NodeNDP(int nvtxs, idxtype *xadj, idxtype *adjncy, int npes,
96  int *options, idxtype *perm, idxtype *iperm, idxtype *sizes)
97 {
98  int i, ii, j, l, wflag, nflag;
100  CtrlType ctrl;
101  idxtype *cptr, *cind;
102 
103  if (options[0] == 0) { /* Use the default parameters */
104  ctrl.CType = ONMETIS_CTYPE;
105  ctrl.IType = ONMETIS_ITYPE;
106  ctrl.RType = ONMETIS_RTYPE;
107  ctrl.dbglvl = ONMETIS_DBGLVL;
108  ctrl.oflags = ONMETIS_OFLAGS;
109  ctrl.pfactor = ONMETIS_PFACTOR;
110  ctrl.nseps = ONMETIS_NSEPS;
111  }
112  else {
113  ctrl.CType = options[OPTION_CTYPE];
114  ctrl.IType = options[OPTION_ITYPE];
115  ctrl.RType = options[OPTION_RTYPE];
116  ctrl.dbglvl = options[OPTION_DBGLVL];
117  ctrl.oflags = options[OPTION_OFLAGS];
118  ctrl.pfactor = options[OPTION_PFACTOR];
119  ctrl.nseps = options[OPTION_NSEPS];
120  }
121  if (ctrl.nseps < 1)
122  ctrl.nseps = 1;
123 
124  ctrl.optype = OP_ONMETIS;
125  ctrl.CoarsenTo = 100;
126 
127  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
128  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
129 
130  InitRandom(-1);
131 
132  if (ctrl.oflags&OFLAG_COMPRESS) {
133  /*============================================================
134  * Compress the graph
135  ==============================================================*/
136  cptr = idxmalloc(nvtxs+1, "ONMETIS: cptr");
137  cind = idxmalloc(nvtxs, "ONMETIS: cind");
138 
139  CompressGraph(&ctrl, &graph, nvtxs, xadj, adjncy, cptr, cind);
140 
141  if (graph.nvtxs >= COMPRESSION_FRACTION*(nvtxs)) {
142  ctrl.oflags--; /* We actually performed no compression */
143  GKfree(&cptr, &cind, LTERM);
144  }
145  else if (2*graph.nvtxs < nvtxs && ctrl.nseps == 1)
146  ctrl.nseps = 2;
147  }
148  else {
149  SetUpGraph(&graph, OP_ONMETIS, nvtxs, 1, xadj, adjncy, NULL, NULL, 0);
150  }
151 
152 
153  /*=============================================================
154  * Do the nested dissection ordering
155  --=============================================================*/
156  ctrl.maxvwgt = 1.5*(idxsum(graph.nvtxs, graph.vwgt)/ctrl.CoarsenTo);
157  AllocateWorkSpace(&ctrl, &graph, 2);
158 
159  idxset(2*npes-1, 0, sizes);
160  MlevelNestedDissectionP(&ctrl, &graph, iperm, graph.nvtxs, npes, 0, sizes);
161 
162  FreeWorkSpace(&ctrl, &graph);
163 
164  if (ctrl.oflags&OFLAG_COMPRESS) { /* Uncompress the ordering */
165  if (graph.nvtxs < COMPRESSION_FRACTION*(nvtxs)) {
166  /* construct perm from iperm */
167  for (i=0; i<graph.nvtxs; i++)
168  perm[iperm[i]] = i;
169  for (l=ii=0; ii<graph.nvtxs; ii++) {
170  i = perm[ii];
171  for (j=cptr[i]; j<cptr[i+1]; j++)
172  iperm[cind[j]] = l++;
173  }
174  }
175 
176  GKfree(&cptr, &cind, LTERM);
177  }
178 
179 
180  for (i=0; i<nvtxs; i++)
181  perm[iperm[i]] = i;
182 
183  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
184  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
185 
186 }
187 
188 
189 
190 /*************************************************************************
191 * This function takes a graph and produces a bisection of it
192 **************************************************************************/
193 void MlevelNestedDissectionP(CtrlType *ctrl, GraphType *graph, idxtype *order, int lastvtx,
194  int npes, int cpos, idxtype *sizes)
195 {
196  int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2];
197  idxtype *label, *bndind;
198  GraphType lgraph, rgraph;
199  float ubfactor;
200 
201  nvtxs = graph->nvtxs;
202 
203  if (nvtxs == 0) {
204  GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
205  return;
206  }
207 
208  /* Determine the weights of the partitions */
209  tvwgt = idxsum(nvtxs, graph->vwgt);
210  tpwgts2[0] = tvwgt/2;
211  tpwgts2[1] = tvwgt-tpwgts2[0];
212 
213  if (cpos >= npes-1)
214  ubfactor = ORDER_UNBALANCE_FRACTION;
215  else
216  ubfactor = 1.05;
217 
218 
219  MlevelNodeBisectionMultiple(ctrl, graph, tpwgts2, ubfactor);
220 
221  IFSET(ctrl->dbglvl, DBG_SEPINFO, printf("Nvtxs: %6d, [%6d %6d %6d]\n", graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
222 
223  if (cpos < npes-1) {
224  sizes[2*npes-2-cpos] = graph->pwgts[2];
225  sizes[2*npes-2-(2*cpos+1)] = graph->pwgts[1];
226  sizes[2*npes-2-(2*cpos+2)] = graph->pwgts[0];
227  }
228 
229  /* Order the nodes in the separator */
230  nbnd = graph->nbnd;
231  bndind = graph->bndind;
232  label = graph->label;
233  for (i=0; i<nbnd; i++)
234  order[label[bndind[i]]] = --lastvtx;
235 
236  SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
237 
238  /* Free the memory of the top level graph */
239  GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
240 
241  if (rgraph.nvtxs > MMDSWITCH || 2*cpos+1 < npes-1)
242  MlevelNestedDissectionP(ctrl, &rgraph, order, lastvtx, npes, 2*cpos+1, sizes);
243  else {
244  MMDOrder(ctrl, &rgraph, order, lastvtx);
245  GKfree(&rgraph.gdata, &rgraph.rdata, &rgraph.label, LTERM);
246  }
247  if (lgraph.nvtxs > MMDSWITCH || 2*cpos+2 < npes-1)
248  MlevelNestedDissectionP(ctrl, &lgraph, order, lastvtx-rgraph.nvtxs, npes, 2*cpos+2, sizes);
249  else {
250  MMDOrder(ctrl, &lgraph, order, lastvtx-rgraph.nvtxs);
251  GKfree(&lgraph.gdata, &lgraph.rdata, &lgraph.label, LTERM);
252  }
253 }
254 
255 
256 
257 
258 /*************************************************************************
259 * This function is the entry point for ONWMETIS. It requires weights on the
260 * vertices. It is for the case that the matrix has been pre-compressed.
261 **************************************************************************/
262 void METIS_NodeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
263  idxtype *adjwgt, int *options, int *sepsize, idxtype *part)
264 {
265  int i, j, tvwgt, tpwgts[2];
267  CtrlType ctrl;
268 
269  SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);
270  tvwgt = idxsum(*nvtxs, graph.vwgt);
271 
272  if (options[0] == 0) { /* Use the default parameters */
273  ctrl.CType = ONMETIS_CTYPE;
274  ctrl.IType = ONMETIS_ITYPE;
275  ctrl.RType = ONMETIS_RTYPE;
276  ctrl.dbglvl = ONMETIS_DBGLVL;
277  }
278  else {
279  ctrl.CType = options[OPTION_CTYPE];
280  ctrl.IType = options[OPTION_ITYPE];
281  ctrl.RType = options[OPTION_RTYPE];
282  ctrl.dbglvl = options[OPTION_DBGLVL];
283  }
284 
285  ctrl.oflags = 0;
286  ctrl.pfactor = 0;
287  ctrl.nseps = 1;
288  ctrl.optype = OP_ONMETIS;
289  ctrl.CoarsenTo = amin(100, *nvtxs-1);
290  ctrl.maxvwgt = 1.5*tvwgt/ctrl.CoarsenTo;
291 
292  InitRandom(options[7]);
293 
294  AllocateWorkSpace(&ctrl, &graph, 2);
295 
296  /*============================================================
297  * Perform the bisection
298  *============================================================*/
299  tpwgts[0] = tvwgt/2;
300  tpwgts[1] = tvwgt-tpwgts[0];
301 
302  MlevelNodeBisectionMultiple(&ctrl, &graph, tpwgts, 1.05);
303 
304  *sepsize = graph.pwgts[2];
305  idxcopy(*nvtxs, graph.where, part);
306 
307  GKfree(&graph.gdata, &graph.rdata, &graph.label, LTERM);
308 
309 
310  FreeWorkSpace(&ctrl, &graph);
311 
312 }
313 
314 
315 
316 /*************************************************************************
317 * This function is the entry point for ONWMETIS. It requires weights on the
318 * vertices. It is for the case that the matrix has been pre-compressed.
319 **************************************************************************/
320 void METIS_EdgeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
321  idxtype *adjwgt, int *options, int *sepsize, idxtype *part)
322 {
323  int i, j, tvwgt, tpwgts[2];
325  CtrlType ctrl;
326 
327  SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);
328  tvwgt = idxsum(*nvtxs, graph.vwgt);
329 
330  if (options[0] == 0) { /* Use the default parameters */
331  ctrl.CType = ONMETIS_CTYPE;
332  ctrl.IType = ONMETIS_ITYPE;
333  ctrl.RType = ONMETIS_RTYPE;
334  ctrl.dbglvl = ONMETIS_DBGLVL;
335  }
336  else {
337  ctrl.CType = options[OPTION_CTYPE];
338  ctrl.IType = options[OPTION_ITYPE];
339  ctrl.RType = options[OPTION_RTYPE];
340  ctrl.dbglvl = options[OPTION_DBGLVL];
341  }
342 
343  ctrl.oflags = 0;
344  ctrl.pfactor = 0;
345  ctrl.nseps = 1;
346  ctrl.optype = OP_OEMETIS;
347  ctrl.CoarsenTo = amin(100, *nvtxs-1);
348  ctrl.maxvwgt = 1.5*tvwgt/ctrl.CoarsenTo;
349 
350  InitRandom(options[7]);
351 
352  AllocateWorkSpace(&ctrl, &graph, 2);
353 
354  /*============================================================
355  * Perform the bisection
356  *============================================================*/
357  tpwgts[0] = tvwgt/2;
358  tpwgts[1] = tvwgt-tpwgts[0];
359 
360  MlevelEdgeBisection(&ctrl, &graph, tpwgts, 1.05);
361  ConstructMinCoverSeparator(&ctrl, &graph, 1.05);
362 
363  *sepsize = graph.pwgts[2];
364  idxcopy(*nvtxs, graph.where, part);
365 
366  GKfree(&graph.gdata, &graph.rdata, &graph.label, LTERM);
367 
368 
369  FreeWorkSpace(&ctrl, &graph);
370 
371 }
#define OP_OEMETIS
Definition: defs.h:91
#define KMETIS_RTYPE
Definition: defs.h:51
int pfactor
Definition: struct.h:223
int * sizes
Definition: refMPIluBack.c:104
timer TotalTmr
Definition: struct.h:230
#define ONMETIS_OFLAGS
Definition: defs.h:65
void METIS_EdgeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *options, int *sepsize, idxtype *part)
Definition: parmetis.c:320
#define SplitGraphOrder
Definition: rename.h:298
#define ONMETIS_NSEPS
Definition: defs.h:67
#define COMPRESSION_FRACTION
Definition: defs.h:145
#define ConstructMinCoverSeparator
Definition: rename.h:337
idxtype * pwgts
Definition: struct.h:176
int optype
Definition: struct.h:222
int nbnd
Definition: struct.h:177
#define ONMETIS_DBGLVL
Definition: defs.h:64
#define SetUpGraph
Definition: rename.h:72
#define fmalloc
Definition: rename.h:384
#define OPTION_NSEPS
Definition: defs.h:36
#define ONMETIS_PFACTOR
Definition: defs.h:66
#define KMETIS_ITYPE
Definition: defs.h:50
#define DBG_SEPINFO
Definition: defs.h:161
#define OPTION_CTYPE
Definition: defs.h:30
int IType
Definition: struct.h:218
int oflags
Definition: struct.h:225
idxtype * rdata
Definition: struct.h:157
#define OPTION_OFLAGS
Definition: defs.h:34
#define MlevelNodeBisectionMultiple
Definition: rename.h:296
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
HitTile_Vector graph
int CType
Definition: struct.h:217
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
void METIS_PartGraphKway2(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, int *options, int *edgecut, idxtype *part)
Definition: parmetis.c:22
int idxtype
Definition: struct.h:19
#define InitRandom
Definition: rename.h:412
#define AllocateWorkSpace
Definition: rename.h:161
#define OPTION_PFACTOR
Definition: defs.h:35
#define ONMETIS_RTYPE
Definition: defs.h:63
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define InitTimers
Definition: rename.h:373
#define Change2CNumbering
Definition: rename.h:62
idxtype * label
Definition: struct.h:170
#define MMDSWITCH
Definition: defs.h:149
#define OPTION_RTYPE
Definition: defs.h:32
void METIS_NodeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *options, int *sepsize, idxtype *part)
Definition: parmetis.c:262
#define OFLAG_COMPRESS
Definition: defs.h:38
#define KMETIS_DBGLVL
Definition: defs.h:52
#define ONMETIS_ITYPE
Definition: defs.h:62
#define idxset
Definition: rename.h:390
#define idxcopy(n, a, b)
Definition: macros.h:44
int CoarsenTo
Definition: struct.h:215
void GKfree(void **ptr1,...)
Definition: util.c:121
void METIS_WPartGraphKway2(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, float *tpwgts, int *options, int *edgecut, idxtype *part)
Definition: parmetis.c:44
#define OP_ONMETIS
Definition: defs.h:92
idxtype * bndind
Definition: struct.h:178
#define MlevelNestedDissectionP
Definition: rename.h:304
#define ONMETIS_CTYPE
Definition: defs.h:61
#define OP_KMETIS
Definition: defs.h:90
#define PrintTimers
Definition: rename.h:374
#define FreeWorkSpace
Definition: rename.h:162
#define KMETIS_CTYPE
Definition: defs.h:49
idxtype * vwgt
Definition: struct.h:163
#define DBG_TIME
Definition: defs.h:154
int RType
Definition: struct.h:219
#define idxmalloc
Definition: rename.h:383
int nseps
Definition: struct.h:224
idxtype * gdata
Definition: struct.h:157
#define MMDOrder
Definition: rename.h:299
int maxvwgt
Definition: struct.h:220
#define OPTION_ITYPE
Definition: defs.h:31
#define MlevelKWayPartitioning
Definition: rename.h:92
int nvtxs
Definition: struct.h:161
#define CompressGraph
Definition: rename.h:38
#define MlevelEdgeBisection
Definition: rename.h:309
void METIS_NodeNDP(int nvtxs, idxtype *xadj, idxtype *adjncy, int npes, int *options, idxtype *perm, idxtype *iperm, idxtype *sizes)
Definition: parmetis.c:95
#define amin(a, b)
Definition: macros.h:30
#define Change2FNumbering
Definition: rename.h:63
#define ORDER_UNBALANCE_FRACTION
Definition: defs.h:147
#define OPTION_DBGLVL
Definition: defs.h:33
#define starttimer(tmr)
Definition: macros.h:53