Nektar++
MeshPartitionScotch.cpp
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 // File MeshPartitionScotch.cpp
4 //
5 // For more information, please see: http://www.nektar.info
6 //
7 // The MIT License
8 //
9 // Copyright (c) 2006 Division of Applied Mathematics, Brown University (USA),
10 // Department of Aeronautics, Imperial College London (UK), and Scientific
11 // Computing and Imaging Institute, University of Utah (USA).
12 //
13 // License for the specific language governing rights and limitations under
14 // Permission is hereby granted, free of charge, to any person obtaining a
15 // copy of this software and associated documentation files (the "Software"),
16 // to deal in the Software without restriction, including without limitation
17 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
18 // and/or sell copies of the Software, and to permit persons to whom the
19 // Software is furnished to do so, subject to the following conditions:
20 //
21 // The above copyright notice and this permission notice shall be included
22 // in all copies or substantial portions of the Software.
23 //
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
25 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
27 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
29 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
30 // DEALINGS IN THE SOFTWARE.
31 //
32 // Description: Scotch partitioner interface
33 //
34 ///////////////////////////////////////////////////////////////////////////////
35 
38 
39 #include "MeshPartitionScotch.h"
40 
41 namespace Nektar
42 {
43 namespace LibUtilities
44 {
45 
48  "Scotch",
50  "Partitioning using the Scotch library.");
51 
53  = SessionReader::RegisterCmdLineFlag("use-scotch","","Use Scotch for mesh partitioning.");
54 
56  : MeshPartition(pSession)
57  {
58 
59  }
60 
62  {
63 
64  }
65 
67  int& nVerts,
68  int& nVertConds,
73  int& nparts,
74  int& volume,
76  {
77  int wgtflag = 0;
78  int *vwgt = 0;
79  int *vsize = 0;
80  if (vertWgt.num_elements() > 0)
81  {
82  wgtflag += 1;
83  vwgt = &vertWgt[0];
84  }
85  if (vertSize.num_elements() > 0)
86  {
87  wgtflag += 2;
88  vsize = &vertSize[0];
89  }
90  int numflag = 0;
91  // number of balancing conditions (size of vertex multi-weight)
92  int options[5];
93  options[0] = 0;
94 
95  PartGraphVKway(&nVerts, &xadj[0], &adjcy[0], vwgt, vsize,
96  &wgtflag, &numflag, &nparts, options, &volume,
97  &part[0]);
98  }
99 
100 
102  const SCOTCH_Num * const n,
103  const SCOTCH_Num * const xadj,
104  const SCOTCH_Num * const adjncy,
105  const SCOTCH_Num * const vwgt,
106  const SCOTCH_Num * const vsize,
107  const SCOTCH_Num * const wgtflag,
108  const SCOTCH_Num * const numflag,
109  const SCOTCH_Num * const nparts,
110  const SCOTCH_Num * const options,
111  SCOTCH_Num * const volume,
112  SCOTCH_Num * const part)
113  {
114  SCOTCH_Num baseval;
115  const SCOTCH_Num * vwgt2;
116  const SCOTCH_Num * vsize2;
117  SCOTCH_Num vsizval; /// Communication volume of current vertex
118  SCOTCH_Num vertnbr;
119  SCOTCH_Num vertnum;
120  SCOTCH_Num edgenum;
121  const SCOTCH_Num * edgetax;
122  const SCOTCH_Num * parttax;
123  SCOTCH_Num * nghbtab;
124  SCOTCH_Num commvol;
125 
126  vsize2 = ((*wgtflag & 1) != 0) ? vsize : NULL;
127  vwgt2 = ((*wgtflag & 2) != 0) ? vwgt : NULL;
128  baseval = *numflag;
129  vertnbr = *n;
130  edgetax = adjncy - baseval;
131 
132  // If no communication load data provided
133  if (vsize2 == NULL) {
134  if (PartGraph2 (n, xadj, adjncy, vwgt2, NULL, numflag, nparts,
135  part, SCOTCH_STRATDEFAULT, 0.01) != 0)
136  return;
137  }
138 
139  // Will have to turn communication volumes into edge loads
140  else {
141  const SCOTCH_Num * vsiztax;
142  SCOTCH_Num edgenbr;
143  SCOTCH_Num * edlotax;
144  int o;
145 
146  edgenbr = xadj[vertnbr] - baseval;
147  if ((edlotax =
148  (SCOTCH_Num*) malloc (edgenbr * sizeof (SCOTCH_Num))) == NULL)
149  {
150  return;
151  }
152 
153  edlotax -= baseval; // Base access to edlotax
154  vsiztax = vsize2 - baseval;
155 
156  // Un-based scan of vertex array xadj
157  for (vertnum = 0, edgenum = baseval;
158  vertnum < vertnbr; vertnum ++) {
159  SCOTCH_Num vsizval; // Communication size of current vertex
160  SCOTCH_Num edgennd;
161 
162  vsizval = vsize2[vertnum];
163  // Based traversal of edge array adjncy
164  for (edgennd = xadj[vertnum + 1];
165  edgenum < edgennd;
166  edgenum ++) {
167 
168  SCOTCH_Num vertend; // Based end vertex number
169 
170  vertend = edgetax[edgenum];
171  edlotax[edgenum] = vsizval + vsiztax[vertend];
172  }
173  }
174 
175  o = PartGraph2 (n, xadj, adjncy, vwgt2, edlotax + baseval, numflag,
176  nparts, part, SCOTCH_STRATDEFAULT, 0.01);
177 
178  free (edlotax + baseval);
179 
180  if (o != 0)
181  return;
182  }
183 
184  if ((nghbtab =
185  (SCOTCH_Num*) malloc (*nparts * sizeof (SCOTCH_Num))) == NULL)
186  {
187  return;
188  }
189 
190  memset (nghbtab, ~0, *nparts * sizeof (SCOTCH_Num));
191 
192  parttax = part - baseval;
193  vsizval = 1; // Assume no vertex communication sizes
194 
195  // Un-based scan of vertex array xadj
196  for (vertnum = 0, edgenum = baseval, commvol = 0;
197  vertnum < vertnbr; vertnum ++) {
198  SCOTCH_Num partval;
199  SCOTCH_Num edgennd;
200 
201  partval = part[vertnum];
202  nghbtab[partval] = vertnum; // Do not count local neighbors in
203  // communication volume
204  if (vsize2 != NULL)
205  vsizval = vsize2[vertnum];
206 
207  // Based traversal of edge array adjncy
208  for (edgennd = xadj[vertnum + 1]; edgenum < edgennd; edgenum ++) {
209  SCOTCH_Num vertend; // Based end vertex number
210  SCOTCH_Num partend;
211 
212  vertend = edgetax[edgenum];
213  partend = parttax[vertend];
214 
215  // If first neighbor in this part set part as accounted for
216  if (nghbtab[partend] != vertnum) {
217  nghbtab[partend] = vertnum;
218  commvol += vsizval;
219  }
220  }
221  }
222  *volume = commvol;
223 
224  free (nghbtab);
225  }
226 
228  const SCOTCH_Num * const n,
229  const SCOTCH_Num * const xadj,
230  const SCOTCH_Num * const adjncy,
231  const SCOTCH_Num * const vwgt,
232  const SCOTCH_Num * const adjwgt,
233  const SCOTCH_Num * const numflag,
234  const SCOTCH_Num * const nparts,
235  SCOTCH_Num * const part,
236  SCOTCH_Num flagval,
237  double kbalval)
238  {
239  // Scotch graph object to interface with libScotch
240  SCOTCH_Graph grafdat;
241  SCOTCH_Strat stradat;
242  SCOTCH_Num baseval;
243  SCOTCH_Num vertnbr;
244  int o;
245 
246  SCOTCH_graphInit (&grafdat);
247 
248  baseval = *numflag;
249  vertnbr = *n;
250 
251  o = 1; // Assume something will go wrong
252  if (SCOTCH_graphBuild (&grafdat, baseval, vertnbr, xadj, xadj + 1,
253  vwgt, NULL, xadj[vertnbr] - baseval, adjncy,
254  adjwgt) == 0) {
255  SCOTCH_stratInit (&stradat);
256  SCOTCH_stratGraphMapBuild (&stradat, flagval, *nparts, kbalval);
257 #ifdef SCOTCH_DEBUG_ALL
258  // TRICK: next instruction called only if graph is consistent
259  if (SCOTCH_graphCheck (&grafdat) == 0)
260 #endif /* SCOTCH_DEBUG_ALL */
261  o = SCOTCH_graphPart (&grafdat, *nparts, &stradat, part);
262  SCOTCH_stratExit (&stradat);
263  }
264  SCOTCH_graphExit (&grafdat);
265 
266  if (o != 0)
267  return (1);
268 
269  if (baseval != 0) { // MeTiS part array is based, Scotch is not
270  SCOTCH_Num vertnum;
271 
272  for (vertnum = 0; vertnum < vertnbr; vertnum ++)
273  part[vertnum] += baseval;
274  }
275 
276  return (0);
277  }
278 
279 }
280 }
static std::string RegisterCmdLineFlag(const std::string &pName, const std::string &pShortName, const std::string &pDescription)
Registers a command-line flag with the session reader.
static MeshPartitionSharedPtr create(const SessionReaderSharedPtr &pSession)
Creates an instance of this class.
boost::shared_ptr< SessionReader > SessionReaderSharedPtr
Definition: MeshPartition.h:50
MeshPartitionScotch(const SessionReaderSharedPtr &pSession)
int PartGraph2(const SCOTCH_Num *const n, const SCOTCH_Num *const xadj, const SCOTCH_Num *const adjncy, const SCOTCH_Num *const vwgt, const SCOTCH_Num *const adjwgt, const SCOTCH_Num *const numflag, const SCOTCH_Num *const nparts, SCOTCH_Num *const part, SCOTCH_Num flagval, double kbalval)
virtual void PartitionGraphImpl(int &nVerts, int &nVertConds, Nektar::Array< Nektar::OneD, int > &xadj, Nektar::Array< Nektar::OneD, int > &adjcy, Nektar::Array< Nektar::OneD, int > &vertWgt, Nektar::Array< Nektar::OneD, int > &vertSize, int &nparts, int &volume, Nektar::Array< Nektar::OneD, int > &part)
static std::string className
Name of class.
void PartGraphVKway(const SCOTCH_Num *const n, const SCOTCH_Num *const xadj, const SCOTCH_Num *const adjncy, const SCOTCH_Num *const vwgt, const SCOTCH_Num *const vsize, const SCOTCH_Num *const wgtflag, const SCOTCH_Num *const numflag, const SCOTCH_Num *const nparts, const SCOTCH_Num *const options, SCOTCH_Num *const volume, SCOTCH_Num *const part)
MeshPartitionFactory & GetMeshPartitionFactory()
tKey RegisterCreatorFunction(tKey idKey, CreatorFunction classCreator, tDescription pDesc="")
Register a class with the factory.
Definition: NekFactory.hpp:215