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