Zoltan2
Loading...
Searching...
No Matches
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
63template<typename T>
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
77DECL_TYPE_NAME(long long);
78
80// Tests for correctness
81static const std::string fail = "FAIL ";
82static const std::string pass = " ";
83
84// Test for correct number of unique Gids
85void 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
94template <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
116template <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
138template <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
165template <typename gno_t>
166void 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
210template <typename gno_t>
211void 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
263template <typename gno_t>
264void 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
327template <typename gno_t>
328void 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
374template <typename gno_t>
375void 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
439template <typename gno_t>
440void 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
495int 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}
Convert keys stored in std::vector to unique Gids stored in std::vector.
int main()
void checkNUnique(std::string &name, size_t nUniqueGids, size_t nExpected)
void test3(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
void checkMinGid(std::string &name, std::vector< gno_t > &gids, gno_t minExpected, const Teuchos::Comm< int > &comm)
void test6(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
void test2(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
void checkMaxGid(std::string &name, std::vector< gno_t > &gids, gno_t maxExpected, const Teuchos::Comm< int > &comm)
void checkNLocallyUnique(std::string &name, std::vector< gno_t > &gids, size_t nExpected)
void test5(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
void test4(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
void test1(Teuchos::RCP< const Teuchos::Comm< int > > &comm)
#define DECL_TYPE_NAME(x)
static const std::string fail
static const std::string pass
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:17
map_t::global_ordinal_type gno_t
Definition: mapRemotes.cpp:18
Tpetra::Map map_t
Definition: mapRemotes.cpp:16
static const char * name()