Zoltan2
rcb_C.cpp
Go to the documentation of this file.
1 // @HEADER
2 //
3 // ***********************************************************************
4 //
5 // Zoltan2: A package of combinatorial algorithms for scientific computing
6 // Copyright 2012 Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact Karen Devine (kddevin@sandia.gov)
39 // Erik Boman (egboman@sandia.gov)
40 // Siva Rajamanickam (srajama@sandia.gov)
41 //
42 // ***********************************************************************
43 //
44 // @HEADER
45 
53 #include <Zoltan2_InputTraits.hpp>
54 #include <Tpetra_Map.hpp>
55 #include <vector>
56 #include <cstdlib>
57 
58 using namespace std;
59 using std::vector;
60 
65 int main(int argc, char *argv[])
66 {
67 #ifdef HAVE_ZOLTAN2_MPI
68  MPI_Init(&argc, &argv);
69  int rank, nprocs;
70  MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
71  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
72 #else
73  int rank=0, nprocs=1;
74 #endif
75 
76  // For convenience, we'll use the Tpetra defaults for local/global ID types
77  // Users can substitute their preferred local/global ID types
78  typedef Tpetra::Map<> Map_t;
79  typedef Map_t::local_ordinal_type localId_t;
80  typedef Map_t::global_ordinal_type globalId_t;
81 
82  typedef double scalar_t;
84 
85  // TODO explain
86  typedef Zoltan2::BasicVectorAdapter<myTypes> inputAdapter_t;
87  typedef inputAdapter_t::part_t part_t;
88 
90  // Create input data.
91 
92  size_t localCount = 40;
93  int dim = 3;
94 
95  scalar_t *coords = new scalar_t [dim * localCount];
96 
97  scalar_t *x = coords;
98  scalar_t *y = x + localCount;
99  scalar_t *z = y + localCount;
100 
101  // Create coordinates that range from 0 to 10.0
102 
103  srand(rank);
104  scalar_t scalingFactor = 10.0 / RAND_MAX;
105 
106  for (size_t i=0; i < localCount*dim; i++){
107  coords[i] = scalar_t(rand()) * scalingFactor;
108  }
109 
110  // Create global ids for the coordinates.
111 
112  globalId_t *globalIds = new globalId_t [localCount];
113  globalId_t offset = rank * localCount;
114 
115  for (size_t i=0; i < localCount; i++)
116  globalIds[i] = offset++;
117 
119  // Create parameters for an RCB problem
120 
121  double tolerance = 1.1;
122 
123  if (rank == 0)
124  std::cout << "Imbalance tolerance is " << tolerance << std::endl;
125 
126  Teuchos::ParameterList params("test params");
127  params.set("debug_level", "basic_status");
128  params.set("debug_procs", "0");
129  params.set("error_check_level", "debug_mode_assertions");
130 
131  params.set("compute_metrics", "true");
132  params.set("algorithm", "rcb");
133  params.set("imbalance_tolerance", tolerance );
134  params.set("num_global_parts", nprocs);
135 
136  params.set("bisection_num_test_cuts", 1);
137 
140  // A simple problem with no weights.
143 
144  // Create a Zoltan2 input adapter for this geometry. TODO explain
145 
146  inputAdapter_t ia1(localCount, globalIds, x, y, z, 1, 1, 1);
147 
148  // Create a Zoltan2 partitioning problem
149 
152 
153  // Solve the problem
154 
155  problem1->solve();
156 
157  // Check the solution.
158 
159  if (rank == 0)
160  problem1->printMetrics(cout);
161 
162  if (rank == 0){
163  scalar_t imb = problem1->getWeightImbalance();
164  if (imb <= tolerance)
165  std::cout << "pass: " << imb << std::endl;
166  else
167  std::cout << "fail: " << imb << std::endl;
168  std::cout << std::endl;
169  }
170 
173  // Try a problem with weights
176 
177  scalar_t *weights = new scalar_t [localCount];
178  for (size_t i=0; i < localCount; i++){
179  weights[i] = 1.0 + scalar_t(rank) / scalar_t(nprocs);
180  }
181 
182  // Create a Zoltan2 input adapter that includes weights.
183 
184  vector<const scalar_t *>coordVec(2);
185  vector<int> coordStrides(2);
186 
187  coordVec[0] = x; coordStrides[0] = 1;
188  coordVec[1] = y; coordStrides[1] = 1;
189 
190  vector<const scalar_t *>weightVec(1);
191  vector<int> weightStrides(1);
192 
193  weightVec[0] = weights; weightStrides[0] = 1;
194 
195  inputAdapter_t ia2(
196  localCount, globalIds,
197  coordVec, coordStrides,
198  weightVec, weightStrides);
199 
200  // Create a Zoltan2 partitioning problem
201 
204 
205  // Solve the problem
206 
207  problem2->solve();
208 
209  // Check the solution.
210 
211  if (rank == 0)
212  problem2->printMetrics(cout);
213 
214  if (rank == 0){
215  scalar_t imb = problem2->getWeightImbalance();
216  if (imb <= tolerance)
217  std::cout << "pass: " << imb << std::endl;
218  else
219  std::cout << "fail: " << imb << std::endl;
220  std::cout << std::endl;
221  }
222 
223  if (localCount > 0){
224  delete [] weights;
225  weights = NULL;
226  }
227 
230  // Try a problem with multiple weights.
233 
234  // Add to the parameters the multicriteria objective.
235 
236  params.set("partitioning_objective", "multicriteria_minimize_total_weight");
237 
238  // Create the new weights.
239 
240  weights = new scalar_t [localCount*3];
241  srand(rank);
242 
243  for (size_t i=0; i < localCount*3; i+=3){
244  weights[i] = 1.0 + rank / nprocs; // weight idx 1
245  weights[i+1] = rank<nprocs/2 ? 1 : 2; // weight idx 2
246  weights[i+2] = rand()/RAND_MAX +.5; // weight idx 3
247  }
248 
249  // Create a Zoltan2 input adapter with these weights.
250 
251  weightVec.resize(3);
252  weightStrides.resize(3);
253 
254  weightVec[0] = weights; weightStrides[0] = 3;
255  weightVec[1] = weights+1; weightStrides[1] = 3;
256  weightVec[2] = weights+2; weightStrides[2] = 3;
257 
258  inputAdapter_t ia3(
259  localCount, globalIds,
260  coordVec, coordStrides,
261  weightVec, weightStrides);
262 
263  // Create a Zoltan2 partitioning problem.
264 
267 
268  // Solve the problem
269 
270  problem3->solve();
271 
272  // Check the solution.
273 
274  if (rank == 0)
275  problem3->printMetrics(cout);
276 
277  if (rank == 0){
278  scalar_t imb = problem3->getWeightImbalance();
279  if (imb <= tolerance)
280  std::cout << "pass: " << imb << std::endl;
281  else
282  std::cout << "fail: " << imb << std::endl;
283  std::cout << std::endl;
284  }
285 
287  // Try the other multicriteria objectives.
288 
289  bool dataHasChanged = false; // default is true
290 
291  params.set("partitioning_objective", "multicriteria_minimize_maximum_weight");
292  problem3->resetParameters(&params);
293  problem3->solve(dataHasChanged);
294  if (rank == 0){
295  problem3->printMetrics(cout);
296  scalar_t imb = problem3->getWeightImbalance();
297  if (imb <= tolerance)
298  std::cout << "pass: " << imb << std::endl;
299  else
300  std::cout << "fail: " << imb << std::endl;
301  std::cout << std::endl;
302  }
303 
304  params.set("partitioning_objective", "multicriteria_balance_total_maximum");
305  problem3->resetParameters(&params);
306  problem3->solve(dataHasChanged);
307  if (rank == 0){
308  problem3->printMetrics(cout);
309  scalar_t imb = problem3->getWeightImbalance();
310  if (imb <= tolerance)
311  std::cout << "pass: " << imb << std::endl;
312  else
313  std::cout << "fail: " << imb << std::endl;
314  std::cout << std::endl;
315  }
316 
317  if (localCount > 0){
318  delete [] weights;
319  weights = NULL;
320  }
321 
324  // Using part sizes, ask for some parts to be empty.
327 
328  // Change the number of parts to twice the number of processes to
329  // ensure that we have more than one global part.
330 
331  params.set("num_global_parts", nprocs*2);
332 
333  // Using the initial problem that did not have any weights, reset
334  // parameter list, and give it some part sizes.
335 
336  problem1->resetParameters(&params);
337 
338  part_t partIds[2];
339  scalar_t partSizes[2];
340 
341  partIds[0] = rank*2; partSizes[0] = 0;
342  partIds[1] = rank*2+1; partSizes[1] = 1;
343 
344  problem1->setPartSizes(2, partIds, partSizes);
345 
346  // Solve the problem. The argument "dataHasChanged" indicates
347  // that we have not changed the input data, which allows the problem
348  // so skip some work when re-solving.
349 
350  dataHasChanged = false;
351 
352  problem1->solve(dataHasChanged);
353 
354  // Obtain the solution
355 
357  problem1->getSolution();
358 
359  // Check it. Part sizes should all be odd.
360 
361  const part_t *partAssignments = solution4.getPartListView();
362 
363  int numInEmptyParts = 0;
364  for (size_t i=0; i < localCount; i++){
365  if (partAssignments[i] % 2 == 0)
366  numInEmptyParts++;
367  }
368 
369  if (rank == 0)
370  std::cout << "Request that " << nprocs << " parts be empty." <<std::endl;
371 
372  // Check the solution.
373 
374  if (rank == 0)
375  problem1->printMetrics(cout);
376 
377  if (rank == 0){
378  scalar_t imb = problem1->getWeightImbalance();
379  if (imb <= tolerance)
380  std::cout << "pass: " << imb << std::endl;
381  else
382  std::cout << "fail: " << imb << std::endl;
383  std::cout << std::endl;
384  }
385 
386  if (coords)
387  delete [] coords;
388 
389  if (globalIds)
390  delete [] globalIds;
391 
392  delete problem1;
393  delete problem2;
394  delete problem3;
395 
396 #ifdef HAVE_ZOLTAN2_MPI
397  MPI_Finalize();
398 #endif
399 
400  if (rank == 0)
401  std::cout << "PASS" << std::endl;
402 }
403 
const scalar_t getWeightImbalance(int idx=0) const
Returns the imbalance of the solution.
void setPartSizes(int len, part_t *partIds, scalar_t *partSizes, bool makeCopy=true)
Set or reset relative sizes for the parts that Zoltan2 will create.
A simple class that can be the User template argument for an InputAdapter.
static ArrayRCP< ArrayRCP< zscalar_t > > weights
Defines the PartitioningSolution class.
void resetParameters(ParameterList *params)
Reset the list of parameters.
A PartitioningSolution is a solution to a partitioning problem.
const part_t * getPartListView() const
Returns the part list corresponding to the global ID list.
void printMetrics(std::ostream &os) const
Print the array of metrics.
BasicVectorAdapter represents a vector (plus optional weights) supplied by the user as pointers to st...
Traits for application input objects.
const PartitioningSolution< Adapter > & getSolution()
Get the solution to the problem.
PartitioningProblem sets up partitioning problems for the user.
Defines the PartitioningProblem class.
Defines the BasicVectorAdapter class.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
int main(int argc, char *argv[])
Definition: rcb_C.cpp:65