Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Mapping.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 //
46 // Test the MappingProblem and MappingSolution classes.
47 //
48 
49 #include <Teuchos_ParameterList.hpp>
50 #include <Teuchos_CommHelpers.hpp>
51 
52 #include <Zoltan2_TestHelpers.hpp>
54 
57 
59 
61 template <typename User>
63 {
64 public:
65  // Defines an (np x nCoordPerRank) grid of points
66  // Total number of parts is np * nPartsPerRow;
67  // Half of each row of points belongs to a single part.
68  // Lowest part number is lowestPartNum.
73 
74  // Problem dimensions are fixed
75  static const int nCoordDim = 2;
76  static const int nCoordPerRank = 6;
77 
78  // Constructor
80  const Teuchos::Comm<int> &comm_,
81  int nPartsPerRow_,
82  int lowestPartNum_,
83  bool useInputParts_=false)
84  :
85  me(comm_.getRank()),
86  np(comm_.getSize()),
87  nPartsPerRow(nPartsPerRow_),
88  lowestPartNum(lowestPartNum_),
89  useInputParts(useInputParts_)
90  {
91  for (int j = 0; j < nCoordPerRank; j++)
92  ids[j] = me * nCoordPerRank + j;
93 
94  for (int i = 0, j = 0; i < nPartsPerRow; i++)
95  for (int k = 0; k < nCoordPerRank / nPartsPerRow; k++, j++)
96  inputparts[j] = lowestPartNum + i + me*nPartsPerRow;
97 
98  for (int j = 0; j < nCoordPerRank; j++) {
99  coords[0][j] = scalar_t(j);
100  coords[1][j] = scalar_t(me);
101  if (nCoordDim > 2) coords[2][j] = scalar_t(np);
102  }
103  }
104 
105  // Print the data as received by the methods.
106  void print(std::string hi) {
107  // print ids
108  const gno_t *mids;
109  getIDsView(mids);
110  std::cout << hi << " methods Rank " << me << " ids: ";
111  for (size_t j = 0; j < getLocalNumIDs(); j++) std::cout << mids[j] << " ";
112  std::cout << std::endl;
113 
114  // print coords
115  const scalar_t **mcoords = new const scalar_t*[getNumEntriesPerID()];
116  int *stride = new int[getNumEntriesPerID()];
117  for (int k = 0; k < getNumEntriesPerID(); k++)
118  getEntriesView(mcoords[k], stride[k], k);
119 
120  std::cout << hi << " methods Rank " << me << " coords: ";
121  for (size_t j = 0; j < getLocalNumIDs(); j++) {
122  std::cout << "(";
123  for (int k = 0; k < getNumEntriesPerID(); k++)
124  std::cout << mcoords[k][j*stride[k]] << ",";
125  std::cout << ") ";
126  }
127  std::cout << std::endl;
128  delete [] mcoords;
129  delete [] stride;
130 
131  // print inputparts
132  const part_t *minputparts;
133  getPartsView(minputparts);
134  std::cout << hi << " methods Rank " << me << " parts: ";
135  if (minputparts != NULL)
136  for (size_t j = 0; j < getLocalNumIDs(); j++)
137  std::cout << minputparts[j] << " ";
138  else
139  std::cout << "not provided";
140  std::cout << std::endl;
141  }
142 
143  // Return values given to the constructor
144  bool adapterUsesInputParts() { return useInputParts; }
145  int adapterNPartsPerRow() { return nPartsPerRow; }
146  int adapterLowestPartNum() { return lowestPartNum; }
147 
148  // Methods for the VectorAdapter interface
149  size_t getLocalNumIDs() const { return nCoordPerRank; }
150  void getIDsView(const gno_t *&Ids) const { Ids = ids; }
151 
152  int getNumEntriesPerID() const { return nCoordDim; }
153  void getEntriesView(const scalar_t *&Coords, int &Stride, int Idx) const
154  {
155  Coords = coords[Idx];
156  Stride = 1;
157  }
158 
159  void getPartsView(const part_t *&InputPart) const {
160  if (useInputParts)
161  InputPart = inputparts;
162  else
163  InputPart = NULL;
164  }
165 
166 private:
167  int me; // my rank
168  int np; // number of ranks
169  int nPartsPerRow; // number of parts created per row of the grid
170  int lowestPartNum; // lowest part number; not necessarily zero
171  bool useInputParts; // use the input partition in the tests? If not,
172  // Zoltan2 uses rank as default part number
173  gno_t ids[nCoordPerRank]; // IDs of this rank's grid points
174  part_t inputparts[nCoordPerRank]; // Input part for each local point
175  scalar_t coords[nCoordDim][nCoordPerRank]; // Coordinate for each local point
176 };
177 
179 // Validate a mapping solution obtained without a partitioning solution
180 template <typename Adapter>
183  Adapter &ia,
184  const Teuchos::Comm<int> &comm
185 )
186 {
187  // Correctness of a particular mapping algorithm is beyond the scope of
188  // this test.
189  typedef typename Adapter::part_t part_t;
190 
191  bool aok = true;
192 
193  // All returned processors must be in range [0,np-1].
194 
195  if (ia.adapterUsesInputParts()) {
196  // Adapter provided input parts
197  const part_t *inputParts;
198  ia.getPartsView(inputParts);
199 
200  aok = validMappingSolution(msoln, ia, inputParts, comm);
201  }
202  else {
203  // Adapter did not provide input parts; use default part = me for all IDs
204  int me = comm.getRank();
205 
206  part_t *defaultParts = new part_t[ia.getLocalNumIDs()];
207  for (size_t i = 0; i < ia.getLocalNumIDs(); i++)
208  defaultParts[i] = me;
209 
210  aok = validMappingSolution(msoln, ia, defaultParts, comm);
211 
212  delete [] defaultParts;
213  }
214 
215  return aok;
216 }
217 
219 // Validate a mapping solution obtained with a partitioning solution
220 template <typename Adapter>
223  Adapter &ia,
225  const Teuchos::Comm<int> &comm
226 )
227 {
228  typedef typename Adapter::part_t part_t;
229 
230  const part_t *assignedParts = psoln.getPartListView();
231 
232  return(validMappingSolution(msoln, ia, assignedParts, comm));
233 }
234 
236 // Validate a mapping solution.
237 // This test checks only whether the mapping solution is valid. Correctness
238 // of a particular mapping algorithm is beyond the scope of this test.
239 template <typename Adapter>
242  Adapter &ia,
243  const typename Adapter::part_t *useTheseParts,
244  // Parts to check for correct mapping to ranks;
245  // may be from Adapter,
246  // from PartitioningSolution, or
247  // default to current rank
248  const Teuchos::Comm<int> &comm
249 )
250 {
251  typedef typename Adapter::part_t part_t;
252 
253  int np = comm.getSize();
254 
255  bool aok = true;
256 
257  // Min and max part numbers in useTheseParts
258  part_t globalmin, localmin = std::numeric_limits<part_t>::max();
259  part_t globalmax, localmax = 0;
260 
261  for (size_t i = 0; i < ia.getLocalNumIDs(); i++) {
262 
263  // All returned processors must be in range [0,np-1].
264  int r = msoln.getRankForPart(useTheseParts[i]);
265  if (r < 0 || r >= np) {
266  aok = false;
267  std::cout << __FILE__ << ":" << __LINE__ << " "
268  << "Invalid rank " << r << " of " << np << " returned"
269  << std::endl;
270  }
271 
272  // Find local max/min part number
273  part_t p = useTheseParts[i];
274  if (p > localmax) localmax = p;
275  if (p < localmin) localmin = p;
276  }
277 
278  // Find global max/min part number
279  Teuchos::reduceAll<int, part_t>(comm, Teuchos::REDUCE_MAX, 1,
280  &localmax, &globalmax);
281  Teuchos::reduceAll<int, part_t>(comm, Teuchos::REDUCE_MIN, 1,
282  &localmin, &globalmin);
283 
284  part_t *parts;
285  part_t nParts;
286  msoln.getMyPartsView(nParts, parts);
287 
288  for (part_t i = 0; i < nParts; i++) {
289 
290  // All returned parts must at least be in the range of part numbers
291  // from useTheseParts
292  part_t p = parts[i];
293  if ((p < globalmin) || (p > globalmax)) {
294  aok = false;
295  std::cout << __FILE__ << ":" << __LINE__ << " "
296  << "Invalid part " << p << " of " << np << " returned"
297  << std::endl;
298  }
299  }
300 
301  // Test the error checking in mapping solution;
302  // each test should throw an error.
303 
304  part_t ret;
305  bool errorThrownCorrectly = false;
306  part_t sillyPart = globalmax+10;
307  try {
308  ret = msoln.getRankForPart(sillyPart);
309  }
310  catch (std::exception &e) {
311  errorThrownCorrectly = true;
312  }
313  if (errorThrownCorrectly == false) {
314  aok = false;
315  std::cout << __FILE__ << ":" << __LINE__ << " "
316  << "Mapping Solution accepted a too-high part number "
317  << sillyPart << " returned " << ret << std::endl;
318  }
319 
320  errorThrownCorrectly = false;
321  sillyPart = globalmin - 1;
322  try {
323  ret = msoln.getRankForPart(sillyPart);
324  }
325  catch (std::exception &e) {
326  errorThrownCorrectly = true;
327  }
328  if (errorThrownCorrectly == false) {
329  aok = false;
330  std::cout << __FILE__ << ":" << __LINE__ << " "
331  << "Mapping Solution accepted a too-low part number "
332  << sillyPart << " returned " << ret << std::endl;
333  }
334 
335  return aok;
336 }
337 
339 
340 template <typename Adapter>
341 bool runTest(
342  Adapter &ia,
343  const RCP<const Teuchos::Comm<int> > &comm,
344  std::string hi
345 )
346 {
347  typedef typename Adapter::part_t part_t;
348  typedef typename Adapter::scalar_t scalar_t;
349 
350  int me = comm->getRank();
351  int np = comm->getSize();
352 
353  bool allgood = true;
354 
355  Teuchos::ParameterList params;
356  params.set("mapping_algorithm", "block");
357 
358  // Test mapping using default machine
359  if (me == 0)
360  std::cout << "Testing Mapping using default machine" << std::endl;
361 
362  Zoltan2::MappingProblem<Adapter> mprob1(&ia, &params, comm);
363  mprob1.solve();
364 
366 
367  if (!validMappingSolution<Adapter>(*msoln1, ia, *comm)) {
368  allgood = false;
369  if (me == 0)
370  std::cout << hi << " FAILED: invalid mapping solution" << std::endl;
371  }
372 
373 
374  // Test mapping explicitly using default machine
376  machine_t defMachine(*comm);
377 
378 #ifdef KDD
379  if (me == 0)
380  std::cout << "Testing Mapping using explicit machine" << std::endl;
381 
382  Zoltan2::MappingProblem<Adapter, machine_t> mprob2(&ia, &params, comm,
383  NULL, &defMachine);
384  mprob2.solve();
385 
387 
388  if (!sameMappingSolution(*msoln1, *msoln2, *comm)) {
389  allgood = false;
390  if (me == 0)
391  std::cout << hi << " FAILED: solution with explicit machine "
392  "differs from default" << std::endl;
393  }
394 #endif
395 
396  // Test mapping with a partitioning solution
397  if (me == 0)
398  std::cout << "Testing Mapping using a partitioning solution" << std::endl;
399 
400  RCP<const Zoltan2::Environment> env = rcp(new Zoltan2::Environment(comm));
401  Zoltan2::PartitioningSolution<Adapter> psoln(env, comm, 0);
402 
403  ArrayRCP<part_t> partList(ia.getLocalNumIDs());
404  for (size_t i = 0; i < ia.getLocalNumIDs(); i++)
405  partList[i] = (me + 1) % np;
406 
407  psoln.setParts(partList);
408 
409 #ifdef HAVE_ZOLTAN2_MPI
410  // Use an MPI_Comm, just to exercise that bit of code
411  // In real life, no one should extract the MPI_Comm from the Teuchos::Comm;
412  // he should use the Teuchos::Comm. But for testing,
413  // we need to exercise the MPI_Comm interface.
414  MPI_Comm mpicomm = Teuchos::getRawMpiComm(*comm);
415  Zoltan2::MappingProblem<Adapter, machine_t> mprob3(&ia, &params, mpicomm,
416  NULL, &defMachine);
417 #else
418  Zoltan2::MappingProblem<Adapter, machine_t> mprob3(&ia, &params, comm,
419  NULL, &defMachine);
420 #endif
421 
422  mprob3.solve();
423 
425 
426  if (!validMappingSolution(*msoln3, ia, psoln, *comm)) {
427  allgood = false;
428  if (me == 0)
429  std::cout << hi << " FAILED: invalid mapping solution "
430  "from partitioning solution" << std::endl;
431  }
432  return allgood;
433 }
434 
436 
437 int main(int narg, char *arg[])
438 {
439  Tpetra::ScopeGuard tscope(&narg, &arg);
440  Teuchos::RCP<const Teuchos::Comm<int> > comm = Tpetra::getDefaultComm();
441 
442  int me = comm->getRank();
443  bool allgood = true;
444 
445  typedef VerySimpleVectorAdapter<zzuser_t> vecAdapter_t;
446  //typedef vecAdapter_t::part_t part_t;
447  //typedef vecAdapter_t::scalar_t scalar_t;
448 
449  // TEST 1
450  {
451  int nPartsPerRow = 1;
452  int firstPart = 0;
453  bool useInputParts = true;
454 
455  vecAdapter_t ia(*comm, nPartsPerRow, firstPart, useInputParts);
456  ia.print("test1");
457 
458  allgood = runTest(ia, comm, "test1");
459  }
460 
461 #ifdef KDD
462  // TEST 2
463  {
464  // Create a very simple input adapter.
465  int nPartsPerRow = 1;
466  int firstPart = 0;
467  bool useInputParts = false;
468  vecAdapter_t ia(*comm, nPartsPerRow, firstPart, useInputParts);
469  ia.print("test2");
470  }
471 
472  // TEST 3
473  {
474  // Create a very simple input adapter.
475  int nPartsPerRow = 2;
476  int firstPart = 4;
477  bool useInputParts = true;
478  vecAdapter_t ia(*comm, nPartsPerRow, firstPart, useInputParts);
479  ia.print("test3");
480  }
481 
482  // TEST 4
483  {
484  // Create a very simple input adapter.
485  int nPartsPerRow = 3;
486  int firstPart = 10;
487  bool useInputParts = true;
488  vecAdapter_t ia(*comm, nPartsPerRow, firstPart, useInputParts);
489  ia.print("test4");
490  }
491 #endif
492 
493  if (allgood && (me == 0))
494  std::cout << "PASS" << std::endl;
495 }
InputTraits< User >::scalar_t scalar_t
bool validMappingSolution(Zoltan2::MappingSolution< Adapter > &msoln, Adapter &ia, const Teuchos::Comm< int > &comm)
Definition: Mapping.cpp:181
#define nParts
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > zzuser_t
Definition: Mapping.cpp:58
InputTraits< User >::gno_t gno_t
PartitionMapping maps a solution or an input distribution to ranks.
VerySimpleVectorAdapter(const Teuchos::Comm< int > &comm_, int nPartsPerRow_, int lowestPartNum_, bool useInputParts_=false)
Definition: Mapping.cpp:79
int main(int narg, char *arg[])
void solve(bool updateInputData=true)
Direct the problem to create a solution.
bool runTest(Adapter &ia, const RCP< const Teuchos::Comm< int > > &comm, std::string hi)
Definition: Mapping.cpp:341
InputTraits< User >::lno_t lno_t
Defines the VectorAdapter interface.
void getEntriesView(const scalar_t *&Coords, int &Stride, int Idx) const
Definition: Mapping.cpp:153
common code used by tests
void print(std::string hi)
Definition: Mapping.cpp:106
mapsoln_t * getSolution()
Get the solution to the problem.
Zoltan2::VectorAdapter< User >::scalar_t scalar_t
Definition: Mapping.cpp:71
SparseMatrixAdapter_t::part_t part_t
A PartitioningSolution is a solution to a partitioning problem.
size_t getLocalNumIDs() const
Returns the number of objects on this process.
Definition: Mapping.cpp:149
const part_t * getPartListView() const
Returns the part list corresponding to the global ID list.
Zoltan2::VectorAdapter< User >::gno_t gno_t
Definition: Mapping.cpp:70
Zoltan2::VectorAdapter< User >::lno_t lno_t
Definition: Mapping.cpp:69
VectorAdapter defines the interface for vector input.
InputTraits< User >::part_t part_t
The user parameters, debug, timing and memory profiling output objects, and error checking methods...
MachineRepresentation Class Base class for representing machine coordinates, networks, etc.
static const int nCoordPerRank
Definition: Mapping.cpp:76
void setParts(ArrayRCP< part_t > &partList)
The algorithm uses setParts to set the solution.
int getRankForPart(part_t part)
Get the rank containing a part. Simplifying assumption: a part is wholy assigned to a rank; it is not...
Defines the MappingSolution class.
void getMyPartsView(part_t &numParts, part_t *&parts)
Get the parts belonging to this rank.
void getIDsView(const gno_t *&Ids) const
Definition: Mapping.cpp:150
int getNumEntriesPerID() const
Return the number of vectors.
Definition: Mapping.cpp:152
void getPartsView(const part_t *&InputPart) const
Definition: Mapping.cpp:159
static const int nCoordDim
Definition: Mapping.cpp:75
MappingProblem enables mapping of a partition (either computed or input) to MPI ranks.
Zoltan2::VectorAdapter< User >::part_t part_t
Definition: Mapping.cpp:72
Defines the MappingProblem class.