Zoltan2
findUniqueGids.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 // Program to testing Zoltan2::findUniqueGids capability
47 // Input: Vector of keys: each key is an array with N entries
48 // Result vector to be filled by findUniqueGids
49 // Output: Filled result vector
50 
51 
52 #include <iostream>
53 #include <vector>
54 #include <array>
55 #include <unordered_set>
56 #include <string>
57 #include <typeinfo>
58 
59 #include <Teuchos_Comm.hpp>
60 #include <Teuchos_DefaultComm.hpp>
62 
63 template<typename T>
64 struct type_name
65 {
66  static const char* name() {
67  std::cout << "You are missing a DECL_TYPE_NAME" << std::endl;
68  return(NULL);
69  }
70 };
71 
72 #define DECL_TYPE_NAME(x) \
73  template<> struct type_name<x> { static const char* name() {return #x;} }
74 
75 DECL_TYPE_NAME(int);
76 DECL_TYPE_NAME(long long);
77 
79 // Tests for correctness
80 static const std::string fail = "FAIL ";
81 static const std::string pass = " ";
82 
83 // Test for correct number of unique Gids
84 void checkNUnique(std::string &name, size_t nUniqueGids, size_t nExpected)
85 {
86  if (nUniqueGids != nExpected)
87  std::cout << fail << name
88  << "nUniqueGids " << nUniqueGids << " != " << nExpected
89  << std::endl;
90 }
91 
92 // Test for correct maximum Gid
93 template <typename gno_t>
95  std::string &name,
96  std::vector<gno_t> &gids,
97  gno_t maxExpected,
98  const Teuchos::Comm<int> &comm
99 )
100 {
101  gno_t maxGid = 0, gmaxGid = 0;
102  size_t len = gids.size();
103  for (size_t i = 0; i < len; i++)
104  if (gids[i] > maxGid) maxGid = gids[i];
105 
106  Teuchos::reduceAll<int, gno_t>(comm, Teuchos::REDUCE_MAX, 1,
107  &maxGid, &gmaxGid);
108  if (gmaxGid != maxExpected)
109  std::cout << fail << name
110  << "max Gid " << gmaxGid << " != " << maxExpected
111  << std::endl;
112 }
113 
114 // Test for correct minimum Gid
115 template <typename gno_t>
117  std::string &name,
118  std::vector<gno_t> &gids,
119  gno_t minExpected,
120  const Teuchos::Comm<int> &comm
121 )
122 {
123  gno_t minGid = std::numeric_limits<gno_t>::max(), gminGid;
124  size_t len = gids.size();
125  for (size_t i = 0; i < len; i++)
126  if (gids[i] < minGid) minGid = gids[i];
127 
128  Teuchos::reduceAll<int, gno_t>(comm, Teuchos::REDUCE_MIN, 1,
129  &minGid, &gminGid);
130  if (gminGid != minExpected)
131  std::cout << fail << name
132  << "min Gid " << gminGid << " != " << minExpected
133  << std::endl;
134 }
135 
136 // Test for number of locally unique Gids
137 template <typename gno_t>
139  std::string &name,
140  std::vector<gno_t> &gids,
141  size_t nExpected)
142 {
143  size_t gidsLen = gids.size();
144  std::unordered_set<gno_t> gidsSet(gidsLen);
145 
146  size_t nDups = 0;
147  for (size_t i = 0; i < gidsLen; i++) {
148  if (gidsSet.find(gids[i]) != gidsSet.end()) {
149  // Gid is already found locally
150  nDups++;
151  }
152  else
153  gidsSet.insert(gids[i]);
154  }
155  size_t nUnique = gidsLen - nDups;
156  if (nUnique != nExpected)
157  std::cout << fail << name
158  << "num locally unique Gids " << nUnique << " != " << nExpected
159  << std::endl;
160 }
161 
163 
164 template <typename gno_t>
165 void test1(Teuchos::RCP<const Teuchos::Comm<int> > &comm)
166 {
167  // Test 1:
168  // Key has only one entry
169  // Each proc has me+1 keys
170  // Keys are in range [1,np]
171  int me = comm->getRank();
172  int np = comm->getSize();
173 
174  std::string name = std::string(" test1: ")
175  + std::string(type_name<gno_t>::name());
176  if (me == 0) std::cout << "--------\n Starting " << name << std::endl;
177 
178  typedef std::array<gno_t, 1> zkey_t;
179  typedef std::vector<zkey_t> keyvec_t;
180  typedef std::vector<gno_t> gidvec_t;
181 
182  const size_t nKeys = me+1;
183  keyvec_t keys(nKeys);
184  gidvec_t gids(nKeys);
185 
186  for (size_t i = 0; i < nKeys; i++) {
187  zkey_t k;
188  k[0] = i+1;
189  keys[i] = k;
190  }
191 
192  size_t nUniqueGids = Zoltan2::findUniqueGids<zkey_t, gno_t>(keys,gids,*comm);
193 
194  // Test for correctness
195  if (me == 0)
196  std::cout << " " << name << " nUniqueGids " << nUniqueGids << std::endl;
197 
198  checkNUnique(name, nUniqueGids, size_t(np));
199 
200  checkMaxGid(name, gids, gno_t(np-1), *comm);
201 
202  checkMinGid(name, gids, gno_t(0), *comm);
203 
204  checkNLocallyUnique(name, gids, nKeys);
205 }
206 
208 
209 template <typename gno_t>
210 void test2(Teuchos::RCP<const Teuchos::Comm<int> > &comm)
211 {
212  // Test 2:
213  // Key has two entries
214  // Each proc has six keys
215  // Three Keys are {rank, x} for x in {1, 2, 3}
216  // Three Keys are {(rank+x)%np, x} for x in {1, 2, 3}
217  // Each rank has three unique and three non-unique keys
218  int me = comm->getRank();
219  int np = comm->getSize();
220 
221  std::string name = std::string(" test2: ")
222  + std::string(type_name<gno_t>::name());
223  if (me == 0) std::cout << "--------\n Starting " << name << std::endl;
224 
225  typedef std::array<gno_t, 2> zkey_t;
226  typedef std::vector<zkey_t> keyvec_t;
227  typedef std::vector<gno_t> gidvec_t;
228 
229  const size_t nKeys = 6;
230  const size_t nKeysHalf = 3;
231  keyvec_t keys(nKeys);
232  gidvec_t gids(nKeys);
233 
234  for (size_t i = 0; i < nKeysHalf; i++) {
235  zkey_t k;
236  k[0] = gno_t(me);
237  k[1] = gno_t(i+1);
238  keys[i] = k;
239  }
240  for (size_t i = 0; i < nKeysHalf; i++) {
241  zkey_t k;
242  k[0] = gno_t((me+i+1)%np);
243  k[1] = gno_t(i+1);
244  keys[i+nKeysHalf] = k;
245  }
246 
247  size_t nUniqueGids = Zoltan2::findUniqueGids<zkey_t,gno_t>(keys,gids,*comm);
248 
249  // Test for correctness
250  if (me == 0)
251  std::cout << " " << name << " nUniqueGids " << nUniqueGids << std::endl;
252 
253  checkNUnique(name, nUniqueGids, size_t(nKeysHalf*np));
254 
255  checkMaxGid(name, gids, gno_t(nKeysHalf*np-1), *comm);
256 
257  checkMinGid(name, gids, gno_t(0), *comm);
258 
259 }
260 
262 template <typename gno_t>
263 void test3(Teuchos::RCP<const Teuchos::Comm<int> > &comm)
264 {
265  // Test 3:
266  // Key has three entries
267  // Each proc has 2*np keys
268  // np Keys are {x, x, x} for x in {0, 1, ..., np-1}
269  // np Keys are {rank, rank, x} for x in {0, 1, ..., np-1}
270  // Each proc has one locally duplicated key
271  // Each proc contributes np unique keys
272  int me = comm->getRank();
273  int np = comm->getSize();
274 
275  std::string name = std::string(" test3: ")
276  + std::string(type_name<gno_t>::name());
277  if (me == 0) std::cout << "--------\n Starting " << name << std::endl;
278 
279  typedef std::array<gno_t, 3> zkey_t;
280  typedef std::vector<zkey_t> keyvec_t;
281  typedef std::vector<gno_t> gidvec_t;
282 
283  const size_t nKeys = 2*np;
284  const size_t nKeysHalf = np;
285  keyvec_t keys(nKeys);
286  gidvec_t gids(nKeys);
287 
288  for (size_t i = 0; i < nKeysHalf; i++) {
289  zkey_t k;
290  k[0] = gno_t(me);
291  k[1] = gno_t(me);
292  k[2] = gno_t(i);
293  keys[i+nKeysHalf] = k;
294  }
295  for (size_t i = 0; i < nKeysHalf; i++) {
296  zkey_t k;
297  k[0] = gno_t(i);
298  k[1] = gno_t(i);
299  k[2] = gno_t(i);
300  keys[i] = k;
301  }
302 
303  size_t nUniqueGids = Zoltan2::findUniqueGids<zkey_t,gno_t>(keys,gids,*comm);
304 
305  // for (size_t i = 0; i < nKeys; i++)
306  // std::cout << me << " Key " << i << ": "
307  // << keys[i][0] << " " << keys[i][1] << " " << keys[i][2]
308  // << " GID " << gids[i]
309  // << std::endl;
310 
311  // Test for correctness
312  if (me == 0)
313  std::cout << " " << name << " nUniqueGids " << nUniqueGids << std::endl;
314 
315  checkNUnique(name, nUniqueGids, size_t(np*np));
316 
317  checkMaxGid(name, gids, gno_t(np*np-1), *comm);
318 
319  checkMinGid(name, gids, gno_t(0), *comm);
320 
321  checkNLocallyUnique(name, gids, size_t(nKeys-1));
322 }
323 
325 
326 template <typename gno_t>
327 void test4(Teuchos::RCP<const Teuchos::Comm<int> > &comm)
328 {
329  // Test 4:
330  // Key has four entries
331  // Each proc has (rank+1)%2 keys; odd-numbered ranks are empty
332  // Keys are all identical {0, 1, 2, 3}
333  int me = comm->getRank();
334 
335  std::string name = std::string(" test4: ")
336  + std::string(type_name<gno_t>::name());
337  if (me == 0) std::cout << "--------\n Starting " << name << std::endl;
338 
339  typedef std::array<gno_t, 4> zkey_t;
340  typedef std::vector<zkey_t> keyvec_t;
341  typedef std::vector<gno_t> gidvec_t;
342 
343  const size_t nKeys = (me+1)%2;
344  keyvec_t keys(nKeys);
345  gidvec_t gids(nKeys);
346 
347  for (size_t i = 0; i < nKeys; i++) {
348  zkey_t k;
349  k[0] = gno_t(0);
350  k[1] = gno_t(1);
351  k[2] = gno_t(2);
352  k[3] = gno_t(3);
353  keys[i] = k;
354  }
355 
356  size_t nUniqueGids = Zoltan2::findUniqueGids<zkey_t,gno_t>(keys,gids,*comm);
357 
358  // Test for correctness
359  if (me == 0)
360  std::cout << " " << name << " nUniqueGids " << nUniqueGids << std::endl;
361 
362  checkNUnique(name, nUniqueGids, size_t(1));
363 
364  checkMaxGid(name, gids, gno_t(0), *comm);
365 
366  checkMinGid(name, gids, gno_t(0), *comm);
367 
368  checkNLocallyUnique(name, gids, (nKeys ? size_t(1): size_t(0)));
369 }
370 
372 
373 template <typename gno_t>
374 void test5(Teuchos::RCP<const Teuchos::Comm<int> > &comm)
375 {
376  // Test 5: Same as Test 3 but using the Tpetra Multivector interface.
377  // Key has three entries
378  // Each proc has 2*np keys
379  // np Keys are {x, x, x} for x in {0, 1, ..., np-1}
380  // np Keys are {rank, rank, x} for x in {0, 1, ..., np-1}
381  // Each proc has one locally duplicated key
382  // Each proc contributes np unique keys
383  int me = comm->getRank();
384  int np = comm->getSize();
385 
386  std::string name = std::string(" test5: ")
387  + std::string(type_name<gno_t>::name());
388  if (me == 0) std::cout << "--------\n Starting " << name << std::endl;
389 
390  typedef int lno_t;
391 
392  const size_t nVecs = 3;
393  const size_t nKeys = 2*np;
394  const size_t nKeysHalf = np;
395 
396  Tpetra::global_size_t gNEntries =
397  Teuchos::OrdinalTraits<Tpetra::global_size_t>::invalid();
398 
399  typedef Tpetra::Map<lno_t, gno_t> map_t;
400  Teuchos::RCP<const map_t> map = rcp(new map_t(gNEntries, nKeys, 0, comm),
401  true);
402 
403  Tpetra::MultiVector<gno_t, lno_t, gno_t> keys(map, nVecs);
404  Tpetra::Vector<gno_t, lno_t, gno_t> gids(map);
405 
406  for (size_t i = 0; i < nKeysHalf; i++) {
407  keys.replaceLocalValue(i+nKeysHalf, 0, gno_t(me));
408  keys.replaceLocalValue(i+nKeysHalf, 1, gno_t(me));
409  keys.replaceLocalValue(i+nKeysHalf, 2, gno_t(i));
410  }
411  for (size_t i = 0; i < nKeysHalf; i++) {
412  keys.replaceLocalValue(i, 0, gno_t(i));
413  keys.replaceLocalValue(i, 1, gno_t(i));
414  keys.replaceLocalValue(i, 2, gno_t(i));
415  }
416 
417  size_t nUniqueGids = Zoltan2::findUniqueGids<lno_t,gno_t>(keys,gids);
418 
419  // Test for correctness
420  if (me == 0)
421  std::cout << " " << name << " nUniqueGids " << nUniqueGids << std::endl;
422 
423  checkNUnique(name, nUniqueGids, size_t(np*np));
424 
425  Teuchos::ArrayRCP<const gno_t> gidsData = gids.getData();
426  std::vector<gno_t> gidsVec(nKeys);
427  for (size_t i = 0; i < nKeys; i++) gidsVec[i] = gidsData[i];
428 
429  checkMaxGid(name, gidsVec, gno_t(np*np-1), *comm);
430 
431  checkMinGid(name, gidsVec, gno_t(0), *comm);
432 
433  checkNLocallyUnique(name, gidsVec, size_t(nKeys-1));
434 }
435 
437 
438 template <typename gno_t>
439 void test6(Teuchos::RCP<const Teuchos::Comm<int> > &comm)
440 {
441  // Test 6: Same as Test 4 but using the Tpetra Multivector interface.
442  // Key has four entries
443  // Each proc has (rank+1)%2 keys; odd-numbered ranks are empty
444  // Keys are all identical {0, 1, 2, 3}
445  int me = comm->getRank();
446 
447  std::string name = std::string(" test6: ")
448  + std::string(type_name<gno_t>::name());
449  if (me == 0) std::cout << "--------\n Starting " << name << std::endl;
450 
451  typedef int lno_t;
452 
453  const size_t nVecs = 4;
454  const size_t nKeys = (me+1)%2;
455 
456  Tpetra::global_size_t gNEntries =
457  Teuchos::OrdinalTraits<Tpetra::global_size_t>::invalid();
458 
459  typedef Tpetra::Map<lno_t, gno_t> map_t;
460  Teuchos::RCP<const map_t> map = rcp(new map_t(gNEntries, nKeys, 0, comm),
461  true);
462 
463  Tpetra::MultiVector<gno_t, lno_t, gno_t> keys(map, nVecs);
464  Tpetra::Vector<gno_t, lno_t, gno_t> gids(map);
465 
466  for (size_t i = 0; i < nKeys; i++) {
467  keys.replaceLocalValue(i, 0, gno_t(0));
468  keys.replaceLocalValue(i, 1, gno_t(1));
469  keys.replaceLocalValue(i, 2, gno_t(2));
470  keys.replaceLocalValue(i, 3, gno_t(3));
471  }
472 
473  size_t nUniqueGids = Zoltan2::findUniqueGids<lno_t,gno_t>(keys,gids);
474 
475  // Test for correctness
476  if (me == 0)
477  std::cout << " " << name << " nUniqueGids " << nUniqueGids << std::endl;
478 
479  checkNUnique(name, nUniqueGids, size_t(1));
480 
481  Teuchos::ArrayRCP<const gno_t> gidsData = gids.getData();
482  std::vector<gno_t> gidsVec(nKeys);
483  for (size_t i = 0; i < nKeys; i++) gidsVec[i] = gidsData[i];
484 
485  checkMaxGid(name, gidsVec, gno_t(0), *comm);
486 
487  checkMinGid(name, gidsVec, gno_t(0), *comm);
488 
489  checkNLocallyUnique(name, gidsVec, (nKeys ? size_t(1): size_t(0)));
490 }
491 
493 
494 int main(int argc, char *argv[])
495 {
496  Teuchos::GlobalMPISession session(&argc, &argv);
497  Teuchos::RCP<const Teuchos::Comm<int> > comm =
498  Teuchos::DefaultComm<int>::getComm();
499 
500 #ifdef HAVE_TPETRA_INT_INT
501  test1<int>(comm);
502  test2<int>(comm);
503  test3<int>(comm);
504  test4<int>(comm);
505  test5<int>(comm);
506  test6<int>(comm);
507 #else
508  if (comm->getRank() == 0)
509  std::cout << "Skipping int tests because Tpetra is not build with "
510  << "GO == int" << std::endl;
511 #endif
512 
513 #ifdef HAVE_TPETRA_INT_LONG_LONG
514  test1<long long>(comm);
515  test2<long long>(comm);
516  test3<long long>(comm);
517  test4<long long>(comm);
518  test5<long long>(comm);
519  test6<long long>(comm);
520 #else
521  if (comm->getRank() == 0)
522  std::cout << "Skipping long long tests because Tpetra is not build with "
523  << "GO == long long" << std::endl;
524 #endif
525 
526  return 0;
527 }
void checkNUnique(std::string &name, size_t nUniqueGids, size_t nExpected)
int main(int argc, char *argv[])
void test3(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
size_t global_size_t
void test6(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
#define DECL_TYPE_NAME(x)
void test2(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
void test5(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
static const char * name()
static const std::string fail
void test1(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
void checkNLocallyUnique(std::string &name, std::vector< gno_t > &gids, size_t nExpected)
static const std::string pass
void checkMaxGid(std::string &name, std::vector< gno_t > &gids, gno_t maxExpected, const Teuchos::Comm< int > &comm)
Convert keys stored in std::vector to unique Gids stored in std::vector.
void checkMinGid(std::string &name, std::vector< gno_t > &gids, gno_t minExpected, const Teuchos::Comm< int > &comm)
void test4(Teuchos::RCP< const Teuchos::Comm< int > > &comm)