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// Permission is hereby granted, free of charge, to any person obtaining a
14// copy of this software and associated documentation files (the "Software"),
15// to deal in the Software without restriction, including without limitation
16// the rights to use, copy, modify, merge, publish, distribute, sublicense,
17// and/or sell copies of the Software, and to permit persons to whom the
18// Software is furnished to do so, subject to the following conditions:
19//
20// The above copyright notice and this permission notice shall be included
21// in all copies or substantial portions of the Software.
22//
23// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
24// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
26// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
28// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
29// DEALINGS IN THE SOFTWARE.
30//
31// Description: Scotch partitioner interface
32//
33///////////////////////////////////////////////////////////////////////////////
34
36
38{
39
43 "Partitioning using the Scotch library.");
44
47 "use-scotch", "", "Use Scotch for mesh partitioning.");
48
51 LibUtilities::CommSharedPtr comm, int meshDim,
52 std::map<int, MeshEntity> element, CompositeDescriptor compMap)
53 : MeshPartition(session, comm, meshDim, element, compMap)
54{
55}
56
58 int &nVerts, [[maybe_unused]] int &nVertConds,
63 [[maybe_unused]] Nektar::Array<Nektar::OneD, int> &edgeWgt, int &nparts,
64 int &volume, Nektar::Array<Nektar::OneD, int> &part)
65{
66 int wgtflag = 0;
67 int *vwgt = nullptr;
68 int *vsize = nullptr;
69 if (vertWgt.size() > 0)
70 {
71 wgtflag += 1;
72 vwgt = &vertWgt[0];
73 }
74 if (vertSize.size() > 0)
75 {
76 wgtflag += 2;
77 vsize = &vertSize[0];
78 }
79 int numflag = 0;
80
81 PartGraphVKway(&nVerts, &xadj[0], &adjcy[0], vwgt, vsize, &wgtflag,
82 &numflag, &nparts, &volume, &part[0]);
83}
84
86 const SCOTCH_Num *const n, const SCOTCH_Num *const xadj,
87 const SCOTCH_Num *const adjncy, const SCOTCH_Num *const vwgt,
88 const SCOTCH_Num *const vsize, const SCOTCH_Num *const wgtflag,
89 const SCOTCH_Num *const numflag, const SCOTCH_Num *const nparts,
90 SCOTCH_Num *const volume, SCOTCH_Num *const part)
91{
92 SCOTCH_Num baseval;
93 const SCOTCH_Num *vwgt2;
94 const SCOTCH_Num *vsize2;
95 SCOTCH_Num vsizval; /// Communication volume of current vertex
96 SCOTCH_Num vertnbr;
97 SCOTCH_Num vertnum;
98 SCOTCH_Num edgenum;
99 const SCOTCH_Num *edgetax;
100 const SCOTCH_Num *parttax;
101 SCOTCH_Num *nghbtab;
102 SCOTCH_Num commvol;
103
104 vsize2 = ((*wgtflag & 1) != 0) ? vsize : nullptr;
105 vwgt2 = ((*wgtflag & 2) != 0) ? vwgt : nullptr;
106 baseval = *numflag;
107 vertnbr = *n;
108 edgetax = adjncy - baseval;
109
110 // If no communication load data provided
111 if (vsize2 == nullptr)
112 {
113 if (PartGraph2(n, xadj, adjncy, vwgt2, nullptr, numflag, nparts, part,
114 SCOTCH_STRATQUALITY, 0.01) != 0)
115 {
116 return;
117 }
118 }
119
120 // Will have to turn communication volumes into edge loads
121 else
122 {
123 const SCOTCH_Num *vsiztax;
124 SCOTCH_Num edgenbr;
125 SCOTCH_Num *edlotax;
126 int o;
127
128 edgenbr = xadj[vertnbr] - baseval;
129 if ((edlotax = (SCOTCH_Num *)malloc(edgenbr * sizeof(SCOTCH_Num))) ==
130 nullptr)
131 {
132 return;
133 }
134
135 edlotax -= baseval; // Base access to edlotax
136 vsiztax = vsize2 - baseval;
137
138 // Un-based scan of vertex array xadj
139 for (vertnum = 0, edgenum = baseval; vertnum < vertnbr; vertnum++)
140 {
141 SCOTCH_Num vsizval; // Communication size of current vertex
142 SCOTCH_Num edgennd;
143
144 vsizval = vsize2[vertnum];
145 // Based traversal of edge array adjncy
146 for (edgennd = xadj[vertnum + 1]; edgenum < edgennd; edgenum++)
147 {
148
149 SCOTCH_Num vertend; // Based end vertex number
150
151 vertend = edgetax[edgenum];
152 edlotax[edgenum] = vsizval + vsiztax[vertend];
153 }
154 }
155
156 o = PartGraph2(n, xadj, adjncy, vwgt2, edlotax + baseval, numflag,
157 nparts, part, SCOTCH_STRATQUALITY, 0.01);
158
159 free(edlotax + baseval);
160
161 if (o != 0)
162 {
163 return;
164 }
165 }
166
167 if ((nghbtab = (SCOTCH_Num *)malloc(*nparts * sizeof(SCOTCH_Num))) ==
168 nullptr)
169 {
170 return;
171 }
172
173 memset(nghbtab, ~0, *nparts * sizeof(SCOTCH_Num));
174
175 parttax = part - baseval;
176 vsizval = 1; // Assume no vertex communication sizes
177
178 // Un-based scan of vertex array xadj
179 for (vertnum = 0, edgenum = baseval, commvol = 0; vertnum < vertnbr;
180 vertnum++)
181 {
182 SCOTCH_Num partval;
183 SCOTCH_Num edgennd;
184
185 partval = part[vertnum];
186 nghbtab[partval] = vertnum; // Do not count local neighbors in
187 // communication volume
188 if (vsize2 != nullptr)
189 {
190 vsizval = vsize2[vertnum];
191 }
192
193 // Based traversal of edge array adjncy
194 for (edgennd = xadj[vertnum + 1]; edgenum < edgennd; edgenum++)
195 {
196 SCOTCH_Num vertend; // Based end vertex number
197 SCOTCH_Num partend;
198
199 vertend = edgetax[edgenum];
200 partend = parttax[vertend];
201
202 // If first neighbor in this part set part as accounted for
203 if (nghbtab[partend] != vertnum)
204 {
205 nghbtab[partend] = vertnum;
206 commvol += vsizval;
207 }
208 }
209 }
210 *volume = commvol;
211
212 free(nghbtab);
213}
214
216 const SCOTCH_Num *const n, const SCOTCH_Num *const xadj,
217 const SCOTCH_Num *const adjncy, const SCOTCH_Num *const vwgt,
218 const SCOTCH_Num *const adjwgt, const SCOTCH_Num *const numflag,
219 const SCOTCH_Num *const nparts, SCOTCH_Num *const part, SCOTCH_Num flagval,
220 double kbalval)
221{
222 // Scotch graph object to interface with libScotch
223 SCOTCH_Graph *grafdat = SCOTCH_graphAlloc();
224 ASSERTL0(grafdat != nullptr,
225 "Failed to allocate Scotch graph for partitioning.");
226
227 SCOTCH_Strat stradat;
228 SCOTCH_Num baseval;
229 SCOTCH_Num vertnbr;
230 int o;
231
232 ASSERTL0(SCOTCH_graphInit(grafdat) == 0,
233 "Failed to initialise Scotch graph for partitioning.");
234
235 baseval = *numflag;
236 vertnbr = *n;
237
238 o = 1; // Assume something will go wrong
239 if (SCOTCH_graphBuild(grafdat, baseval, vertnbr, xadj, xadj + 1, vwgt,
240 nullptr, xadj[vertnbr] - baseval, adjncy,
241 adjwgt) == 0)
242 {
243 SCOTCH_stratInit(&stradat);
244 SCOTCH_stratGraphMapBuild(&stradat, flagval, *nparts, kbalval);
245#ifdef SCOTCH_DEBUG_ALL
246 // TRICK: next instruction called only if graph is consistent
247 if (SCOTCH_graphCheck(grafdat) == 0)
248#endif /* SCOTCH_DEBUG_ALL */
249 o = SCOTCH_graphPart(grafdat, *nparts, &stradat, part);
250 SCOTCH_stratExit(&stradat);
251 }
252 SCOTCH_graphExit(grafdat);
253
254 if (o != 0)
255 {
256 return (1);
257 }
258
259 if (baseval != 0)
260 { // MeTiS part array is based, Scotch is not
261 SCOTCH_Num vertnum;
262
263 for (vertnum = 0; vertnum < vertnbr; vertnum++)
264 {
265 part[vertnum] += baseval;
266 }
267 }
268
269 return (0);
270}
271
272} // namespace Nektar::SpatialDomains
#define ASSERTL0(condition, msg)
Definition: ErrorUtil.hpp:208
tKey RegisterCreatorFunction(tKey idKey, CreatorFunction classCreator, std::string pDesc="")
Register a class with the factory.
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 LibUtilities::SessionReaderSharedPtr session, LibUtilities::CommSharedPtr comm, int meshDim, std::map< int, MeshEntity > element, CompositeDescriptor compMap)
Creates an instance of this class.
void v_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, Nektar::Array< Nektar::OneD, int > &edgeWgt, int &nparts, int &volume, Nektar::Array< Nektar::OneD, int > &part) final
static std::string className
Name of class.
MeshPartitionScotch(const LibUtilities::SessionReaderSharedPtr session, LibUtilities::CommSharedPtr comm, int meshDim, std::map< int, MeshEntity > element, CompositeDescriptor compMap)
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)
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, SCOTCH_Num *const volume, SCOTCH_Num *const part)
std::shared_ptr< SessionReader > SessionReaderSharedPtr
std::shared_ptr< Comm > CommSharedPtr
Pointer to a Communicator object.
Definition: Comm.h:55
std::map< int, std::pair< LibUtilities::ShapeType, std::vector< int > > > CompositeDescriptor
Definition: MeshGraph.h:61
MeshPartitionFactory & GetMeshPartitionFactory()