1 /* Copyright 2008-2010,2012 IPB, Universite de Bordeaux, INRIA & CNRS
2 **
3 ** This file is part of the Scotch software package for static mapping,
4 ** graph partitioning and sparse matrix ordering.
5 **
6 ** This software is governed by the CeCILL-C license under French law
7 ** and abiding by the rules of distribution of free software. You can
8 ** use, modify and/or redistribute the software under the terms of the
9 ** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
10 ** URL: "http://www.cecill.info".
11 **
12 ** As a counterpart to the access to the source code and rights to copy,
13 ** modify and redistribute granted by the license, users are provided
14 ** only with a limited warranty and the software's author, the holder of
15 ** the economic rights, and the successive licensors have only limited
16 ** liability.
17 **
18 ** In this respect, the user's attention is drawn to the risks associated
19 ** with loading, using, modifying and/or developing or reproducing the
20 ** software by the user in light of its specific status of free software,
21 ** that may mean that it is complicated to manipulate, and that also
22 ** therefore means that it is reserved for developers and experienced
23 ** professionals having in-depth computer knowledge. Users are therefore
24 ** encouraged to load and test the software's suitability as regards
25 ** their requirements in conditions enabling the security of their
26 ** systems and/or data to be ensured and, more generally, to use and
27 ** operate it in the same conditions as regards security.
28 **
29 ** The fact that you are presently reading this means that you have had
30 ** knowledge of the CeCILL-C license and that you accept its terms.
31 */
32 /************************************************************/
33 /** **/
34 /** NAME : parmetis_dgraph_part.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module is the compatibility **/
39 /** library for the ParMeTiS ordering **/
40 /** routines. **/
41 /** **/
42 /** DATES : # Version 5.1 : from : 19 jun 2008 **/
43 /** to 30 jun 2010 **/
44 /** # Version 6.0 : from : 13 sep 2012 **/
45 /** to 13 sep 2012 **/
46 /** **/
47 /************************************************************/
48
49 /*
50 ** The defines and includes.
51 */
52
53 #define LIBRARY
54
55 #include "module.h"
56 #include "common.h"
57 #include "ptscotch.h"
58 #include "parmetis.h" /* Our "parmetis.h" file */
59
60 /************************************/
61 /* */
62 /* These routines are the C API for */
63 /* the ParMeTiS graph ordering */
64 /* routine. */
65 /* */
66 /************************************/
67
68 void
METISNAMEU(ParMETIS_V3_PartKway)69 METISNAMEU(ParMETIS_V3_PartKway) (
70 const SCOTCH_Num * const vtxdist,
71 SCOTCH_Num * const xadj,
72 SCOTCH_Num * const adjncy,
73 SCOTCH_Num * const vwgt,
74 SCOTCH_Num * const adjwgt,
75 const SCOTCH_Num * const wgtflag,
76 const SCOTCH_Num * const numflag,
77 const SCOTCH_Num * const ncon, /* Not used */
78 const SCOTCH_Num * const nparts,
79 const float * const tpwgts,
80 const float * const ubvec, /* Not used */
81 const SCOTCH_Num * const options, /* Not used */
82 SCOTCH_Num * const edgecut,
83 SCOTCH_Num * const part,
84 MPI_Comm * comm)
85 {
86 MPI_Comm proccomm;
87 int procglbnbr;
88 int proclocnum;
89 SCOTCH_Num baseval;
90 SCOTCH_Arch archdat;
91 SCOTCH_Dgraph grafdat; /* Scotch distributed graph object to interface with libScotch */
92 SCOTCH_Dmapping mappdat; /* Scotch distributed mapping object to interface with libScotch */
93 SCOTCH_Strat stradat;
94 SCOTCH_Num vertlocnbr;
95 SCOTCH_Num * veloloctab;
96 SCOTCH_Num edgelocnbr;
97 SCOTCH_Num * edloloctab;
98 SCOTCH_Num * velotab;
99 double * vwgttab;
100 SCOTCH_Num i;
101
102 if ((vwgttab = malloc (*nparts * sizeof (double))) == NULL)
103 return;
104 if ((velotab = malloc (*nparts * sizeof (SCOTCH_Num))) == NULL) {
105 free (vwgttab);
106 return;
107 }
108 for (i = 0; i < *nparts; i ++)
109 vwgttab[i] = (double) tpwgts[i] * (double) (*nparts);
110 for (i = 0; i < *nparts; i ++) {
111 double deltval;
112 deltval = fabs (vwgttab[i] - floor (vwgttab[i] + 0.5));
113 if (deltval > 0.01) {
114 SCOTCH_Num j;
115
116 deltval = 1.0 / deltval;
117 for (j = 0; j < *nparts; j ++)
118 vwgttab[j] *= deltval;
119 }
120 }
121 for (i = 0; i < *nparts; i ++)
122 velotab[i] = (SCOTCH_Num) (vwgttab[i] + 0.5);
123
124 proccomm = *comm;
125 if (SCOTCH_dgraphInit (&grafdat, proccomm) != 0)
126 return;
127
128 MPI_Comm_size (proccomm, &procglbnbr);
129 MPI_Comm_rank (proccomm, &proclocnum);
130 baseval = *numflag;
131 vertlocnbr = vtxdist[proclocnum + 1] - vtxdist[proclocnum];
132 edgelocnbr = xadj[vertlocnbr] - baseval;
133 veloloctab = ((vwgt != NULL) && ((*wgtflag & 2) != 0)) ? vwgt : NULL;
134 edloloctab = ((adjwgt != NULL) && ((*wgtflag & 1) != 0)) ? adjwgt : NULL;
135
136 if (SCOTCH_dgraphBuild (&grafdat, baseval,
137 vertlocnbr, vertlocnbr, xadj, xadj + 1, veloloctab, NULL,
138 edgelocnbr, edgelocnbr, adjncy, NULL, edloloctab) == 0) {
139 SCOTCH_stratInit (&stradat);
140 #ifdef SCOTCH_DEBUG_ALL
141 if (SCOTCH_dgraphCheck (&grafdat) == 0) /* TRICK: next instruction called only if graph is consistent */
142 #endif /* SCOTCH_DEBUG_ALL */
143 {
144 SCOTCH_archInit (&archdat);
145
146 if ((SCOTCH_archCmpltw (&archdat, *nparts, velotab) == 0) &&
147 (SCOTCH_dgraphMapInit (&grafdat, &mappdat, &archdat, part) == 0)) {
148 SCOTCH_dgraphMapCompute (&grafdat, &mappdat, &stradat);
149
150 SCOTCH_dgraphMapExit (&grafdat, &mappdat);
151 }
152 SCOTCH_archExit (&archdat);
153 }
154 SCOTCH_stratExit (&stradat);
155 }
156 SCOTCH_dgraphExit (&grafdat);
157
158 *edgecut = 0; /* TODO : compute real edge cut for people who might want it */
159
160 free (vwgttab);
161 free (velotab);
162
163 if (baseval != 0) { /* MeTiS part array is based, Scotch is not */
164 SCOTCH_Num vertlocnum;
165
166 for (vertlocnum = 0; vertlocnum < vertlocnbr; vertlocnum ++)
167 part[vertlocnum] += baseval;
168 }
169 }
170
171 /*
172 **
173 */
174
175 void
METISNAMEU(ParMETIS_V3_PartGeomKway)176 METISNAMEU(ParMETIS_V3_PartGeomKway) (
177 const SCOTCH_Num * const vtxdist,
178 SCOTCH_Num * const xadj,
179 SCOTCH_Num * const adjncy,
180 SCOTCH_Num * const vwgt,
181 SCOTCH_Num * const adjwgt,
182 const SCOTCH_Num * const wgtflag,
183 const SCOTCH_Num * const numflag,
184 const SCOTCH_Num * const ndims, /* Not used */
185 const float * const xyz, /* Not used */
186 const SCOTCH_Num * const ncon, /* Not used */
187 const SCOTCH_Num * const nparts,
188 const float * const tpwgts,
189 const float * const ubvec,
190 const SCOTCH_Num * const options, /* Not used */
191 SCOTCH_Num * const edgecut,
192 SCOTCH_Num * const part,
193 MPI_Comm * commptr)
194 {
195 METISNAMEU(ParMETIS_V3_PartKway) (vtxdist, xadj, adjncy, vwgt, adjwgt, wgtflag, numflag, ncon, nparts, tpwgts, ubvec, options, edgecut, part, commptr);
196 }
197