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 using Teuchos::RCP;
61 
66 int main(int argc, char *argv[])
67 {
68 #ifdef HAVE_ZOLTAN2_MPI
69  MPI_Init(&argc, &argv);
70  int rank, nprocs;
71  MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
72  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
73 #else
74  int rank=0, nprocs=1;
75 #endif
76 
77  // For convenience, we'll use the Tpetra defaults for local/global ID types
78  // Users can substitute their preferred local/global ID types
79  typedef Tpetra::Map<> Map_t;
80  typedef Map_t::local_ordinal_type localId_t;
81  typedef Map_t::global_ordinal_type globalId_t;
82 
83  typedef double scalar_t;
85 
86  // TODO explain
87  typedef Zoltan2::BasicVectorAdapter<myTypes> inputAdapter_t;
89  typedef inputAdapter_t::part_t part_t;
91 
93  // Create input data.
94 
95  size_t localCount = 40;
96  int dim = 3;
97 
98  scalar_t *coords = new scalar_t [dim * localCount];
99 
100  scalar_t *x = coords;
101  scalar_t *y = x + localCount;
102  scalar_t *z = y + localCount;
103 
104  // Create coordinates that range from 0 to 10.0
105 
106  srand(rank);
107  scalar_t scalingFactor = 10.0 / RAND_MAX;
108 
109  for (size_t i=0; i < localCount*dim; i++){
110  coords[i] = scalar_t(rand()) * scalingFactor;
111  }
112 
113  // Create global ids for the coordinates.
114 
115  globalId_t *globalIds = new globalId_t [localCount];
116  globalId_t offset = rank * localCount;
117 
118  for (size_t i=0; i < localCount; i++)
119  globalIds[i] = offset++;
120 
122  // Create parameters for an RCB problem
123 
124  double tolerance = 1.1;
125 
126  if (rank == 0)
127  std::cout << "Imbalance tolerance is " << tolerance << std::endl;
128 
129  Teuchos::ParameterList params("test params");
130  params.set("debug_level", "basic_status");
131  params.set("debug_procs", "0");
132  params.set("error_check_level", "debug_mode_assertions");
133 
134  params.set("algorithm", "rcb");
135  params.set("imbalance_tolerance", tolerance );
136  params.set("num_global_parts", nprocs);
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 = new inputAdapter_t(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  // create metric object where communicator is Teuchos default
158 
159  quality_t *metricObject1 = new quality_t(ia1, &params, //problem1->getComm(),
160  &problem1->getSolution());
161  // Check the solution.
162 
163  if (rank == 0) {
164  metricObject1->printMetrics(cout);
165  }
166 
167  if (rank == 0){
168  scalar_t imb = metricObject1->getObjectCountImbalance();
169  if (imb <= tolerance)
170  std::cout << "pass: " << imb << std::endl;
171  else
172  std::cout << "fail: " << imb << std::endl;
173  std::cout << std::endl;
174  }
175  delete metricObject1;
176 
179  // Try a problem with weights
182 
183  scalar_t *weights = new scalar_t [localCount];
184  for (size_t i=0; i < localCount; i++){
185  weights[i] = 1.0 + scalar_t(rank) / scalar_t(nprocs);
186  }
187 
188  // Create a Zoltan2 input adapter that includes weights.
189 
190  vector<const scalar_t *>coordVec(2);
191  vector<int> coordStrides(2);
192 
193  coordVec[0] = x; coordStrides[0] = 1;
194  coordVec[1] = y; coordStrides[1] = 1;
195 
196  vector<const scalar_t *>weightVec(1);
197  vector<int> weightStrides(1);
198 
199  weightVec[0] = weights; weightStrides[0] = 1;
200 
201  inputAdapter_t *ia2=new inputAdapter_t(localCount, globalIds, coordVec,
202  coordStrides,weightVec,weightStrides);
203 
204  // Create a Zoltan2 partitioning problem
205 
208 
209  // Solve the problem
210 
211  problem2->solve();
212 
213  // create metric object for MPI builds
214 
215 #ifdef HAVE_ZOLTAN2_MPI
216  quality_t *metricObject2 = new quality_t(ia2, &params, //problem2->getComm()
217  MPI_COMM_WORLD,
218  &problem2->getSolution());
219 #else
220  quality_t *metricObject2 = new quality_t(ia2, &params, problem2->getComm(),
221  &problem2->getSolution());
222 #endif
223  // Check the solution.
224 
225  if (rank == 0) {
226  metricObject2->printMetrics(cout);
227  }
228 
229  if (rank == 0){
230  scalar_t imb = metricObject2->getWeightImbalance(0);
231  if (imb <= tolerance)
232  std::cout << "pass: " << imb << std::endl;
233  else
234  std::cout << "fail: " << imb << std::endl;
235  std::cout << std::endl;
236  }
237  delete metricObject2;
238 
239  if (localCount > 0){
240  delete [] weights;
241  weights = NULL;
242  }
243 
246  // Try a problem with multiple weights.
249 
250  // Add to the parameters the multicriteria objective.
251 
252  params.set("partitioning_objective", "multicriteria_minimize_total_weight");
253 
254  // Create the new weights.
255 
256  weights = new scalar_t [localCount*3];
257  srand(rank);
258 
259  for (size_t i=0; i < localCount*3; i+=3){
260  weights[i] = 1.0 + rank / nprocs; // weight idx 1
261  weights[i+1] = rank<nprocs/2 ? 1 : 2; // weight idx 2
262  weights[i+2] = rand()/RAND_MAX +.5; // weight idx 3
263  }
264 
265  // Create a Zoltan2 input adapter with these weights.
266 
267  weightVec.resize(3);
268  weightStrides.resize(3);
269 
270  weightVec[0] = weights; weightStrides[0] = 3;
271  weightVec[1] = weights+1; weightStrides[1] = 3;
272  weightVec[2] = weights+2; weightStrides[2] = 3;
273 
274  inputAdapter_t *ia3=new inputAdapter_t(localCount, globalIds, coordVec,
275  coordStrides,weightVec,weightStrides);
276 
277  // Create a Zoltan2 partitioning problem.
278 
281 
282  // Solve the problem
283 
284  problem3->solve();
285 
286  // create metric object where Teuchos communicator is specified
287 
288  quality_t *metricObject3 = new quality_t(ia3, &params, problem3->getComm(),
289  &problem3->getSolution());
290  // Check the solution.
291 
292  if (rank == 0) {
293  metricObject3->printMetrics(cout);
294  }
295 
296  if (rank == 0){
297  scalar_t imb = metricObject3->getWeightImbalance(0);
298  if (imb <= tolerance)
299  std::cout << "pass: " << imb << std::endl;
300  else
301  std::cout << "fail: " << imb << std::endl;
302  std::cout << std::endl;
303  }
304  delete metricObject3;
305 
307  // Try the other multicriteria objectives.
308 
309  bool dataHasChanged = false; // default is true
310 
311  params.set("partitioning_objective", "multicriteria_minimize_maximum_weight");
312  problem3->resetParameters(&params);
313  problem3->solve(dataHasChanged);
314 
315  // Solution changed!
316 
317  metricObject3 = new quality_t(ia3, &params, problem3->getComm(),
318  &problem3->getSolution());
319  if (rank == 0){
320  metricObject3->printMetrics(cout);
321  scalar_t imb = metricObject3->getWeightImbalance(0);
322  if (imb <= tolerance)
323  std::cout << "pass: " << imb << std::endl;
324  else
325  std::cout << "fail: " << imb << std::endl;
326  std::cout << std::endl;
327  }
328  delete metricObject3;
329 
330  params.set("partitioning_objective", "multicriteria_balance_total_maximum");
331  problem3->resetParameters(&params);
332  problem3->solve(dataHasChanged);
333 
334  // Solution changed!
335 
336  metricObject3 = new quality_t(ia3, &params, problem3->getComm(),
337  &problem3->getSolution());
338  if (rank == 0){
339  metricObject3->printMetrics(cout);
340  scalar_t imb = metricObject3->getWeightImbalance(0);
341  if (imb <= tolerance)
342  std::cout << "pass: " << imb << std::endl;
343  else
344  std::cout << "fail: " << imb << std::endl;
345  std::cout << std::endl;
346  }
347  delete metricObject3;
348 
349  if (localCount > 0){
350  delete [] weights;
351  weights = NULL;
352  }
353 
356  // Using part sizes, ask for some parts to be empty.
359 
360  // Change the number of parts to twice the number of processes to
361  // ensure that we have more than one global part.
362 
363  params.set("num_global_parts", nprocs*2);
364 
365  // Using the initial problem that did not have any weights, reset
366  // parameter list, and give it some part sizes.
367 
368  problem1->resetParameters(&params);
369 
370  part_t partIds[2];
371  scalar_t partSizes[2];
372 
373  partIds[0] = rank*2; partSizes[0] = 0;
374  partIds[1] = rank*2+1; partSizes[1] = 1;
375 
376  problem1->setPartSizes(2, partIds, partSizes);
377 
378  // Solve the problem. The argument "dataHasChanged" indicates
379  // that we have not changed the input data, which allows the problem
380  // so skip some work when re-solving.
381 
382  dataHasChanged = false;
383 
384  problem1->solve(dataHasChanged);
385 
386  // Obtain the solution
387 
389  problem1->getSolution();
390 
391  // Check it. Part sizes should all be odd.
392 
393  const part_t *partAssignments = solution4.getPartListView();
394 
395  int numInEmptyParts = 0;
396  for (size_t i=0; i < localCount; i++){
397  if (partAssignments[i] % 2 == 0)
398  numInEmptyParts++;
399  }
400 
401  if (rank == 0)
402  std::cout << "Request that " << nprocs << " parts be empty." <<std::endl;
403 
404  // Solution changed!
405 
406  metricObject1 = new quality_t(ia1, &params, //problem1->getComm(),
407  &problem1->getSolution());
408  // Check the solution.
409 
410  if (rank == 0) {
411  metricObject1->printMetrics(cout);
412  }
413 
414  if (rank == 0){
415  scalar_t imb = metricObject1->getObjectCountImbalance();
416  if (imb <= tolerance)
417  std::cout << "pass: " << imb << std::endl;
418  else
419  std::cout << "fail: " << imb << std::endl;
420  std::cout << std::endl;
421  }
422  delete metricObject1;
423 
424  if (coords)
425  delete [] coords;
426 
427  if (globalIds)
428  delete [] globalIds;
429 
430  delete problem1;
431  delete ia1;
432  delete problem2;
433  delete ia2;
434  delete problem3;
435  delete ia3;
436 
437 #ifdef HAVE_ZOLTAN2_MPI
438  MPI_Finalize();
439 #endif
440 
441  if (rank == 0)
442  std::cout << "PASS" << std::endl;
443 }
444 
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
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
void resetParameters(ParameterList *params)
Reset the list of parameters.
Defines the PartitioningSolution class.
A PartitioningSolution is a solution to a partitioning problem.
RCP< const Comm< int > > getComm()
Return the communicator used by the problem.
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.
const part_t * getPartListView() const
Returns the part list corresponding to the global ID list.
Defines the PartitioningProblem class.
A class that computes and returns quality metrics.
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:66