Zoltan2
Loading...
Searching...
No Matches
ddirectoryTest.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 that demonstrates how to emulate distributed directories that
47// can sum-up entries using Tpetra classes (Map, Vector).
48// Similar functionality (but, of course, without the sum) using a Zoltan_DD
49// is also written.
50// It would be fair to compare the runtimes of the Tpetra version with the
51// Zoltan version, even without the sum operation. And if/when we implement
52// the sum operation, we could add a test of it to this program.
53
54#include <Teuchos_RCP.hpp>
55#include <Teuchos_ArrayView.hpp>
56
57#include <unordered_map>
58
59#include <Tpetra_Map.hpp>
60#include <Tpetra_Vector.hpp>
61
62#include <Zoltan2_TPLTraits.hpp>
63
64#include <zoltan_dd_cpp.h>
65#include <unordered_set>
66
67
68static const size_t TOOMANY = 100;
69
71// Functions for debugging
72template <typename T>
73void printTpetraThing(T &thing, const std::string &msg,
74 std::ostream &ostr = std::cout)
75{
76 ostr << msg << std::endl;
77 Teuchos::FancyOStream fancy(Teuchos::rcpFromRef(ostr));
78 thing.describe(fancy, Teuchos::VERB_EXTREME);
79}
80
81template <typename vector_t>
82void printVector(vector_t &vec, const std::string &msg,
83 std::ostream &ostr = std::cout)
84{
85 if (vec.getGlobalLength() > TOOMANY) return;
86 printTpetraThing<vector_t>(vec, msg, ostr);
87}
88
89template <typename map_t>
90void printMap(map_t &map, const std::string &msg,
91 std::ostream &ostr = std::cout)
92{
93 if (map.getGlobalNumElements() > TOOMANY) return;
94 printTpetraThing<map_t>(map, msg, ostr);
95}
96
98// Class to generate input IDs based on input values
99template <typename id_t>
100class IDs {
101public:
102
103 IDs(size_t nIds_, float fracShared_, id_t idBase_, int idStride_,
104 Teuchos::RCP<const Teuchos::Comm<int> > &comm_) :
105 nIds(nIds_),
106 nShared(std::ceil(nIds * fracShared_)),
107 nUnique(nIds - nShared),
108 idBase(idBase_),
109 idStride(idStride_),
110 contiguous(idStride_ == 1),
111 ids(nIds, 0), comm(comm_)
112 {
113 int me = comm->getRank();
114 int np = comm->getSize();
115
116 // Generate the uniquely owned IDs;
117 size_t cnt = 0;
118 for (size_t i = 0; i < nUnique; i++)
119 ids[cnt++] = idBase + ((me * nUnique + i) * idStride);
120
121 // Generate the shared IDs; they are the highest-numbered IDs
122 size_t gnUnique = nUnique * np;
123 std::srand(me);
124
125 for (size_t i = 0; i < nShared; i++) {
126 size_t r = rand() % nShared;
127 ids[cnt++] = idBase + ((gnUnique + r) * idStride);
128 }
129
130 print();
131 }
132
133 void print()
134 {
135 if (nIds > TOOMANY) return;
136
137 int me = comm->getRank();
138
139 std::cout << me << " nIds = " << nIds << "; nUnique = " << nUnique
140 << "; nShared = " << nShared << std::endl;
141
142 std::cout << me << " Unique: ";
143 for (size_t i = 0; i < nUnique; i++) std::cout << ids[i] << " ";
144 std::cout << std::endl;
145
146 std::cout << me << " Shared: ";
147 for (size_t i = 0; i < nShared; i++) std::cout << ids[nUnique+i] << " ";
148 std::cout << std::endl;
149 }
150
151 bool TpetraDDTest();
152
153 bool ZoltanDDTest();
154
155private:
156
157 typedef int scalar_t; // use int since we are counting occurrences
158
159
160 size_t nIds; // Number of IDs per processor
161 size_t nShared; // Number of shared IDs per processor
162 size_t nUnique; // Number of unique IDs per processor
163
164 id_t idBase; // Smallest possible ID
165 int idStride; // Offset between IDs; 1 provides contiguous
166 bool contiguous; // Flag indicating whether IDs are contiguous
167
168 std::vector<id_t> ids; // Ids generated on this proc
169
170 Teuchos::RCP<const Teuchos::Comm<int> > comm;
171};
172
173
175// Test of DDirectory-like functionality using Tpetra
176// Basic steps:
177// T1: Create an overlapped map M1 and a vector V1 that uses it;
178// V1[i] = number of local occurrencts of ID i
179// T2: Call createOneToOne to create a one-to-one map M2;
180// create a vector M2 that uses it.
181// T3: Create an Import object between the overlapped map and
182// the one-to-one map.
183// T4: Import with Tpetra::ADD from V1 to V2 to count the occurrences
184// T5: Import with Tpetra::REPLACE from V2 to V1 to return the
185// result to the original processors
186
187
188template <typename id_t>
190{
191 typedef typename Tpetra::Map<int, id_t> map_t;
192 typedef typename Teuchos::RCP<const map_t> rcpmap_t;
193
194 typedef typename Tpetra::Vector<scalar_t, int, id_t> vector_t;
195 typedef typename Teuchos::ArrayRCP<scalar_t> vectordata_t;
196
197 // Step T1
198
199 // Find unique IDs numbers and indexBase on this processor for
200 // constructing overlapping Tpetra::Map for IDs.
201
202 id_t minId = std::numeric_limits<id_t>::max();
203
204 std::unordered_map<id_t, size_t> uniqueIds;
205 uniqueIds.reserve(nIds); // Worst case
206
207 for (size_t i = 0; i < nIds; i++) {
208 id_t id = ids[i];
209 if (id < minId) minId = id;
210 if (uniqueIds.find(id) == uniqueIds.end())
211 uniqueIds[id] = 1;
212 else
213 uniqueIds[id]++;
214 }
215
216 // Compute global indexBase
217
218 id_t indexBase;
219 Teuchos::reduceAll(*comm, Teuchos::REDUCE_MIN, 1, &minId, &indexBase);
220
221 // Create list of locally unique IDs to use in Tpetra::Map creation
222
223 size_t nUniqueIds = uniqueIds.size();
224 Teuchos::Array<id_t> uniqueIdsList(nUniqueIds);
225
226 size_t cnt = 0;
227 for (auto it = uniqueIds.begin(); it != uniqueIds.end(); it++)
228 uniqueIdsList[cnt++] = it->first;
229
230 // Build Tpetra::Map for the given local ids
231
232 size_t dummy = Teuchos::OrdinalTraits<Tpetra::global_size_t>::invalid();
233
234 rcpmap_t idMap = Teuchos::rcp(new map_t(dummy, uniqueIdsList(), indexBase,
235 comm), true);
236
237 // Create Vector using this map.
238 // This vector will store number of occurrences of each id across procs
239
240 vector_t idVec(idMap, 0.);
241
242 // Use the multivector for counting number of occurrences of each id
243
244 {
245 vectordata_t idData = idVec.getDataNonConst();
246 for (auto it = uniqueIds.begin(); it != uniqueIds.end(); it++) {
247 id_t idx = idMap->getLocalElement(it->first);
248 idData[idx] = it->second;
249 }
250 }
251
252 printMap(*idMap, "idMap ");
253
254 printVector(idVec, "idVec before ");
255
256 // Step T2
257
258 // Create a one-to-one map and a vector that uses it
259
260 rcpmap_t oto_idMap;
261 if (contiguous) {
262 // For contigous ids, can use Tpetra default Map
263 id_t gnUnique = idMap->getMaxAllGlobalIndex() - indexBase + 1;
264 oto_idMap = Teuchos::rcp(new map_t(gnUnique, indexBase, comm));
265 }
266 else {
267 // Since ids may not be contiguous, cannot use default Tpetra Map
268 oto_idMap = Tpetra::createOneToOne(idMap);
269 }
270
271 vector_t oto_idVec(oto_idMap);
272
273 // Step T3
274
275 // Create an exporter between the two maps
276
277 typedef Tpetra::Export<int, id_t> export_t;
278
279 export_t idExporter(idMap, oto_idMap);
280
281 printTpetraThing(idExporter, "exporter ");
282
283 // Step T4
284
285 // Compute the number of occurrences of shared ids
286 printMap(*oto_idMap, "oto_idMap ");
287
288 printVector(oto_idVec, "oto_idVec BEFORE EXPORT");
289
290 oto_idVec.doExport(idVec, idExporter, Tpetra::ADD);
291
292 printVector(oto_idVec, "oto_idVec AFTER EXPORT");
293
294 // Step T5
295
296 // Send the result back to orig processors
297 // so that we can identify shared IDs in orig procs
298
299 idVec.doImport(oto_idVec, idExporter, Tpetra::REPLACE);
300
301 printVector(idVec, "idVec after ");
302
303 // Check the result
304 size_t cntShared = 0;
305 {
306 auto idData = idVec.getDataNonConst();
307 for (size_t i = 0; i < idVec.getLocalLength(); i++)
308 if (idData[i] > 1) cntShared++;
309 }
310
311 std::cout << comm->getRank() << " cntShared = " << cntShared
312 << "; nShared = " << nShared << std::endl;
313
314 return (cntShared == nShared);
315}
316
318// Perform nearly same operations using Zoltan DD.
319// Note that Zoltan cannot current do Tpetra::ADD; it will do Tpetra::REPLACE.
320// (That is why we are doing this study!)
321// Thus, the computed results will not be correct, but except for the addition,
322// the mechanics are all the same.
323
324template <typename id_t>
326{
327
328 if (nIds > size_t(std::numeric_limits<int>::max()))
329 throw std::runtime_error("Problem too large for Zoltan_DD");
330
331 int inIds = int(nIds);
332
333 // Build a Zoltan directory for the IDs; don't care about local IDs
334
335#ifdef HAVE_MPI
336 MPI_Comm mpicomm = Teuchos::getRawMpiComm(*comm);
337#else
338 { // Use siMPI from Zoltan here; make sure it is initialized
339 int flag;
340 MPI_Initialized(&flag);
341 if (!flag) {
342 int narg = 0;
343 char **argv = NULL;
344 MPI_Init(&narg, &argv);
345 }
346 }
347 MPI_Comm mpicomm = MPI_COMM_WORLD;
348#endif
349
351
352 Zoltan_DD zz(mpicomm, nIdEnt, 0, sizeof(scalar_t), inIds, 0);
353
354 // TODO: Can think about appropriate hash functions here.
355 // To match Tpetra's default map, we could use something like DD_Hash_Fn1.
356
357 // Allocate space for user data.
358 // In this case, the user data is occurrence counts that we would like to
359 // add up in the directory.
360 std::vector<scalar_t> user(nIds, 1.);
361
362 // Depending on size of id_t, may need to copy IDs to array of ZOLTAN_ID_TYPE
363 // TODO: Add TPL_Traits that don't require ArrayView. Doh.
364
365 ZOLTAN_ID_PTR zgids = NULL;
366 if (nIds) {
367 Teuchos::ArrayView<id_t> av(&(ids[0]), nIds);
369 }
370
371 // To do the summation, we'd need this function to be UpdateAdd or
372 // Update with an operator argument like Tpetra::ADD.
373 // For now, we'll just do the update (which does a replace-like operation).
374 zz.Update(zgids, NULL, (char*)(nIds ? &(user[0]) : NULL), NULL, inIds);
375
376 // Retrieve the result for all local IDs.
377 zz.Find(zgids, NULL, (char*)(nIds ? &(user[0]) : NULL), NULL, inIds, NULL);
378
379 // The following step is needed only to test the results;
380 // for general use, if user[i] > 1 in the summation, id[i] is shared.
381 size_t cntShared = 0;
382 std::unordered_set<id_t> alreadyCounted;
383 for (size_t i = 0; i < nIds; i++) {
384 if (user[i] > 1) {
385 // Id is shared; have we already counted it locally?
386 if (alreadyCounted.find(ids[i]) == alreadyCounted.end()) {
387 alreadyCounted.insert(ids[i]);
388 cntShared++;
389 }
390 }
391 }
392
393 if ((nIds * comm->getSize()) <= TOOMANY) zz.Print();
394
395 return (cntShared == nShared);
396}
397
399int main(int narg, char **arg)
400{
401 Tpetra::ScopeGuard tscope(&narg, &arg);
402 Teuchos::RCP<const Teuchos::Comm<int> > comm = Tpetra::getDefaultComm();
403
404 // Test with contiguous IDs of default Tpetra GO type
405 {
406 size_t nIds = 5; // Number of IDs per processor
407 float fracShared = 0.2; // Fraction of IDs that should be shared
408 size_t idBase = 0; // Smallest possible ID
409 int idStride = 1; // Offset between IDs; 1 gives contiguous numbering
410
411 typedef Tpetra::Map<>::global_ordinal_type gno_t;
412 IDs<gno_t> myIds(nIds, fracShared, idBase, idStride, comm);
413
414 myIds.TpetraDDTest();
415
416 myIds.ZoltanDDTest();
417 }
418
419 // Test with non-contiguous IDs of default Tpetra GO starting at 20
420 {
421 size_t nIds = 5; // Number of IDs per processor
422 float fracShared = 0.2; // Fraction of IDs that should be shared
423 size_t idBase = 20; // Smallest possible ID
424 int idStride = 3; // Offset between IDs; 1 gives contiguous numbering
425
426 typedef Tpetra::Map<>::global_ordinal_type gno_t;
427 IDs<gno_t> myIds(nIds, fracShared, idBase, idStride, comm);
428
429 myIds.TpetraDDTest();
430
431 myIds.ZoltanDDTest();
432 }
433
434#ifdef HAVE_TPETRA_INT_INT
435 // Test with contiguous integer IDs
436 {
437 size_t nIds = 5; // Number of IDs per processor
438 float fracShared = 0.2; // Fraction of IDs that should be shared
439 size_t idBase = 0; // Smallest possible ID
440 int idStride = 1; // Offset between IDs; 1 gives contiguous numbering
441
442 IDs<int> myIds(nIds, fracShared, idBase, idStride, comm);
443
444 myIds.TpetraDDTest();
445
446 myIds.ZoltanDDTest();
447 }
448
449 // Test with non-contiguous integer IDs starting at 20
450 {
451 size_t nIds = 5; // Number of IDs per processor
452 float fracShared = 0.2; // Fraction of IDs that should be shared
453 size_t idBase = 20; // Smallest possible ID
454 int idStride = 3; // Offset between IDs; 1 gives contiguous numbering
455
456 IDs<int> myIds(nIds, fracShared, idBase, idStride, comm);
457
458 myIds.TpetraDDTest();
459
460 myIds.ZoltanDDTest();
461 }
462#endif
463
464#ifdef HAVE_TPETRA_INT_LONG_LONG
465 // Test with non-contiguous long long IDs starting at 200
466 {
467 size_t nIds = 5; // Number of IDs per processor
468 float fracShared = 0.4; // Fraction of IDs that should be shared
469 size_t idBase = 200; // Smallest possible ID
470 int idStride = 4; // Offset between IDs; 1 gives contiguous numbering
471
472 IDs<long long> myIds(nIds, fracShared, idBase, idStride, comm);
473
474 myIds.TpetraDDTest();
475
476 myIds.ZoltanDDTest();
477 }
478#endif
479}
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS's idx_t,...
int main()
IDs(size_t nIds_, float fracShared_, id_t idBase_, int idStride_, Teuchos::RCP< const Teuchos::Comm< int > > &comm_)
bool TpetraDDTest()
void print()
bool ZoltanDDTest()
void printTpetraThing(T &thing, const std::string &msg, std::ostream &ostr=std::cout)
void printMap(map_t &map, const std::string &msg, std::ostream &ostr=std::cout)
void printVector(vector_t &vec, const std::string &msg, std::ostream &ostr=std::cout)
static const size_t TOOMANY
map_t::global_ordinal_type gno_t
Definition: mapRemotes.cpp:18
Tpetra::Map map_t
Definition: mapRemotes.cpp:16
static void ASSIGN_ARRAY(first_t **a, ArrayView< second_t > &b)