Debian Codegraph @

packages/stk/stk_unit_tests/stk_util/parallel/UnitTestGenerateIds.cpp

raw
1 // Copyright 2002 - 2008, 2010, 2011 National Technology Engineering
2 // Solutions of Sandia, LLC (NTESS). Under the terms of Contract
3 // DE-NA0003525 with NTESS, the U.S. Government retains certain rights
4 // in this software.
5 //
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are
8 // met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 //
13 // * Redistributions in binary form must reproduce the above
14 // copyright notice, this list of conditions and the following
15 // disclaimer in the documentation and/or other materials provided
16 // with the distribution.
17 //
18 // * Neither the name of NTESS nor the names of its contributors
19 // may be used to endorse or promote products derived from this
20 // software without specific prior written permission.
21 //
22 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 //
34
35 #include "gtest/gtest.h"
36 #include "stk_util/environment/WallTime.hpp" // for wall_time
37 #include "stk_util/parallel/DistributedIndex.hpp" // for DistributedIndex::KeyTypeVector
38 #include "stk_util/parallel/GenerateParallelUniqueIDs.hpp" // for generate_parallel_unique_ids
39 #include "stk_util/parallel/MPI.hpp" // for Datatype
40 #include "stk_util/parallel/Parallel.hpp" // for MPI_Bcast, MPI_Comm, MPI_Reduce
41 #include "stk_util/stk_config.h" // for STK_HAS_MPI
42 #include "stk_util/util/ReportHandler.hpp" // for ThrowRequireMsg
43 #include <cstddef> // for size_t
44 #include <algorithm> // for binary_search, sort, copy
45 #include <cstdint> // for uint64_t
46 #include <iostream> // for operator<<, basic_ostream, endl
47 #include <memory> // for allocator_traits<>::value_type
48 #include <string> // for string
49 #include <vector> // for vector, vector<>::iterator
50
51 #if defined(STK_HAS_MPI) // means that MPI is available
52
53 namespace {
54
55 typedef int INTMPI;
56
57 class MpiInfo
58 {
59 public:
60 MpiInfo(MPI_Comm comm) : mProcId(-1), mNumProcs(-1), mComm(comm)
61 {
62 MPI_Comm_rank(mComm, &mProcId);
63 MPI_Comm_size(mComm, &mNumProcs);
64 }
65 ~MpiInfo() {}
66
67 INTMPI getProcId() const { return mProcId; }
68 INTMPI getNumProcs() const { return mNumProcs; }
69 MPI_Comm getMpiComm() const { return mComm; }
70
71 private:
72 INTMPI mProcId;
73 INTMPI mNumProcs;
74 MPI_Comm mComm;
75 };
76
77 INTMPI whichProcOwnsId(const uint64_t maxId, const uint64_t id, INTMPI numProcs);
78 void distributeIds(std::vector<uint64_t> &myIds, const MpiInfo& mpiInfo);
79 uint64_t getNumIdsPerProc(const uint64_t maxId, const INTMPI numProcs);
80 void getIdUsageAcrossAllProcs(std::vector< std::vector<uint64_t> > &idsToComm, std::vector<uint64_t> &idsInUseAcrossAllProcsInMyRange, const MpiInfo& mpiInfo);
81
82 void retrieveIds(const INTMPI root, uint64_t id, MPI_Comm comm, uint64_t numIdsToGetPerProc, std::vector<int>& areIdsBeingUsed);
83 void respondToRootProcessorAboutIdsOwnedOnThisProc(const int root, const uint64_t maxId, const std::vector<uint64_t> &idsInUse, MPI_Comm comm);
84
85 bool sendIdToCheck(const INTMPI root, uint64_t id, MPI_Comm comm);
86 void receiveIdAndCheck(const int root, const std::vector<uint64_t> &idsInUse, MPI_Comm comm);
87 void checkUniqueIds(const std::vector<uint64_t> &myIds, const std::vector<uint64_t> &uniqueIds, const MpiInfo& mpiInfo);
88 void writeIdsToFile(const std::string &filename, const INTMPI myProcId, const std::vector<uint64_t>& myIds, const std::vector<uint64_t> &uniqueIds);
89 void generate_ids(const uint64_t maxId, const std::vector<uint64_t> &idsInUse, std::vector<uint64_t> &uniqueIds, const MpiInfo& mpiInfo);
90 void getBatchesOfIdsFromOtherProcessorsUntilRequestOnThisProcIsFulfilled(INTMPI root, uint64_t &startingIdToSearchForNewIds, std::vector<uint64_t> &idsObtained, uint64_t numIdsNeeded, int scaleFactorForNumIds,
91 std::vector<uint64_t> &sortedIds, const uint64_t maxId, const MpiInfo& mpiInfo);
92 void terminateIdRequestForThisProc(INTMPI root, MPI_Comm comm);
93 void getAvailableIds(const std::vector<uint64_t> &myIds, uint64_t numIdsNeeded, std::vector<uint64_t> &idsObtained, uint64_t &startingIdToSearchForNewIds, const uint64_t maxId, const MpiInfo& mpiInfo);
94 void getAvailableIds_exp(const std::vector<uint64_t> &myIds, uint64_t numIdsNeeded, std::vector<uint64_t> &idsObtained, uint64_t &startingIdToSearchForNewIds, const uint64_t maxId, const MpiInfo& mpiInfo);
95
96 ////////////////////////////////////////////////////////////////////
97
98
99 TEST(GeneratedIds, whichProcOwnsId)
100 {
101 uint64_t maxId=10;
102 INTMPI numProcs=3;
103
104 uint64_t ids[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
105 INTMPI procOwner[] = { 0, 0, 0, 1, 1, 1, 2, 2, 2, 3};
106 for (int i=0;i<10;i++)
107 {
108 EXPECT_EQ(procOwner[i], whichProcOwnsId(maxId, ids[i], numProcs));
109 }
110 }
111
112 TEST(GeneratedIds, distributeIds)
113 {
114 MpiInfo mpiInfo(MPI_COMM_WORLD);
115
116 int numIdsPerProc = 10;
117 std::vector<uint64_t> myIds(numIdsPerProc);
118 distributeIds(myIds, mpiInfo);
119
120 uint64_t offsetForProc = numIdsPerProc*mpiInfo.getProcId();
121 for (size_t i=0;i<myIds.size();i++)
122 {
123 uint64_t oneBasedId = i+1;
124 EXPECT_EQ(oneBasedId+offsetForProc, myIds[i]);
125 }
126 }
127
128 TEST(GeneratedIds, getNumIdsPerProc)
129 {
130 INTMPI numProcs = 10;
131 uint64_t findIdsLessThan = 1000;
132
133 uint64_t numIdsOneOneProc = getNumIdsPerProc(findIdsLessThan, numProcs);
134 EXPECT_EQ(findIdsLessThan/numProcs, numIdsOneOneProc);
135 }
136
137 TEST(GeneratedIds, getIdUsageAcrossAllProcs)
138 {
139 MpiInfo mpiInfo(MPI_COMM_WORLD);
140
141 if ( mpiInfo.getNumProcs() != 1 )
142 {
143 std::vector< std::vector<uint64_t> > idsToComm(mpiInfo.getNumProcs());
144 INTMPI procToSendId = 0;
145 uint64_t madeUpId = static_cast<uint64_t>(mpiInfo.getProcId());
146 idsToComm[procToSendId].push_back(madeUpId);
147 std::vector<uint64_t> idsInUseAcrossAllProcsInMyRange;
148 getIdUsageAcrossAllProcs(idsToComm, idsInUseAcrossAllProcsInMyRange, mpiInfo);
149 if ( mpiInfo.getProcId() == 0 )
150 {
151 for (uint64_t id=0;id<idsInUseAcrossAllProcsInMyRange.size();id++)
152 {
153 EXPECT_EQ(id, idsInUseAcrossAllProcsInMyRange[id]);
154 }
155 }
156 else
157 {
158 EXPECT_EQ(0u, idsInUseAcrossAllProcsInMyRange.size());
159 }
160 }
161 }
162
163 TEST(GeneratedIds, findUniqueIdAcrossProcs)
164 {
165 MpiInfo mpiInfo(MPI_COMM_WORLD);
166
167 uint64_t totalIdsInUse = 362880;
168 uint64_t numIdsThisProc = totalIdsInUse/mpiInfo.getNumProcs();
169
170 std::vector<uint64_t> myIds(numIdsThisProc,0);
171 distributeIds(myIds, mpiInfo);
172
173 uint64_t startingIdToSearchForNewIds = 1;
174 uint64_t numIdsNeeded = 100;
175 std::vector<uint64_t> idsObtained;
176 uint64_t maxId = 10000000;
177
178 double startTime = stk::wall_time();
179
180 getAvailableIds(myIds, numIdsNeeded, idsObtained, startingIdToSearchForNewIds, maxId, mpiInfo);
181
182 double endTime = stk::wall_time();
183
184 if ( mpiInfo.getProcId() == 0 )
185 {
186 std::cerr << "Took " << endTime-startTime << " seconds." << std::endl;
187 }
188
189 checkUniqueIds(myIds, idsObtained, mpiInfo);
190
191 for (size_t i=0;i<idsObtained.size();i++)
192 {
193 uint64_t goldId = totalIdsInUse + numIdsNeeded*mpiInfo.getProcId()+1 + i;
194 EXPECT_EQ(goldId, idsObtained[i]);
195 }
196 }
197
198 TEST(GeneratedIds, findUniqueIdAcrossProcsApproach1)
199 {
200 MpiInfo mpiInfo(MPI_COMM_WORLD);
201
202 uint64_t numIdsThisProc = 50000;
203 uint64_t totalIdsInUse = numIdsThisProc*mpiInfo.getNumProcs();
204
205 std::vector<uint64_t> myIds(numIdsThisProc,0);
206 distributeIds(myIds, mpiInfo);
207
208 uint64_t startingIdToSearchForNewIds = 1;
209 uint64_t numIdsNeeded = 100;
210 std::vector<uint64_t> idsObtained;
211 uint64_t maxId = 72057594037927935;
212
213 double startTime = stk::wall_time();
214
215 getAvailableIds_exp(myIds, numIdsNeeded, idsObtained, startingIdToSearchForNewIds, maxId, mpiInfo);
216
217 double endTime = stk::wall_time();
218
219 if ( mpiInfo.getProcId() == 0 )
220 {
221 std::cerr << "Took " << endTime-startTime << " seconds." << std::endl;
222 }
223
224 checkUniqueIds(myIds, idsObtained, mpiInfo);
225 writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, idsObtained);
226
227 for (size_t i=0;i<idsObtained.size();i++)
228 {
229 uint64_t goldId = totalIdsInUse + numIdsNeeded*mpiInfo.getProcId()+1 + i;
230 EXPECT_EQ(goldId, idsObtained[i]);
231 }
232 }
233
234 TEST(GeneratedIds, findUniqueIdAcrossProcsVaryingNumIdsInUse)
235 {
236 MpiInfo mpiInfo(MPI_COMM_WORLD);
237
238 uint64_t numIdsThisProc = 50000;
239 uint64_t totalIdsInUse = numIdsThisProc*mpiInfo.getNumProcs();
240
241 std::vector<uint64_t> myIds(numIdsThisProc,0);
242 distributeIds(myIds, mpiInfo);
243
244 uint64_t startingIdToSearchForNewIds = 1;
245 uint64_t numIdsNeeded = 1000;
246 std::vector<uint64_t> idsObtained;
247 uint64_t maxId = 100000000000;
248
249 double startTime = stk::wall_time();
250
251 getAvailableIds(myIds, numIdsNeeded, idsObtained, startingIdToSearchForNewIds, maxId, mpiInfo);
252
253 double endTime = stk::wall_time();
254
255 if ( mpiInfo.getProcId() == 0 )
256 {
257 std::cerr << "Took " << endTime-startTime << " seconds." << std::endl;
258 }
259
260 checkUniqueIds(myIds, idsObtained, mpiInfo);
261 writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, idsObtained);
262
263 for (size_t i=0;i<idsObtained.size();i++)
264 {
265 uint64_t goldId = totalIdsInUse + numIdsNeeded*mpiInfo.getProcId()+1 + i;
266 EXPECT_EQ(goldId, idsObtained[i]);
267 }
268 }
269
270 TEST(GeneratedIds, numIdsInUseVariesWithNumberProcessorsNumIdsNeededVariesWithNumberProcessors)
271 {
272 MpiInfo mpiInfo(MPI_COMM_WORLD);
273
274 if ( mpiInfo.getNumProcs() < 10 )
275 {
276 uint64_t maxId = 10000000;
277 uint64_t numIdsThisProc = 100000;
278
279 std::vector<uint64_t> myIds(numIdsThisProc,0);
280 distributeIds(myIds, mpiInfo);
281
282 uint64_t numIdsNeeded = 10000;
283 std::vector<uint64_t> uniqueIds(numIdsNeeded,0);
284
285 MPI_Barrier(mpiInfo.getMpiComm());
286
287 double startTime = stk::wall_time();
288
289 generate_ids(maxId, myIds, uniqueIds, mpiInfo);
290
291 double endTime = stk::wall_time();
292
293 if ( mpiInfo.getProcId() == 0 )
294 {
295 std::cerr << "Took " << endTime-startTime << " seconds." << std::endl;
296 }
297
298 EXPECT_EQ(numIdsNeeded, uniqueIds.size());
299 checkUniqueIds(myIds, uniqueIds, mpiInfo);
300
301 writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, uniqueIds);
302 }
303 }
304
305 // 2^56 = 72, 057, 594, 037, 927, 936 --> 72 quadrillion, 57 trillion, 594 billion, 37 million, 927 thousand, 936 ids!
306
307 TEST(GeneratedIds, numIdsInUseConstantNumIdsNeededConstant)
308 {
309 MpiInfo mpiInfo(MPI_COMM_WORLD);
310
311 if ( mpiInfo.getNumProcs() <= 10 )
312 {
313 uint64_t totalIdsInUse = 362880;
314 uint64_t numIdsThisProc = totalIdsInUse/mpiInfo.getNumProcs();
315
316 std::vector<uint64_t> myIds(numIdsThisProc,0);
317 distributeIds(myIds, mpiInfo);
318
319 uint64_t maxId = 10000000;
320
321 uint64_t numIdsNeeded = 10000;
322 if ( mpiInfo.getProcId() != 0 )
323 {
324 numIdsNeeded = 0;
325 }
326
327 std::vector<uint64_t> uniqueIds(numIdsNeeded,0);
328
329 MPI_Barrier(mpiInfo.getMpiComm());
330
331 double startTime = stk::wall_time();
332
333 generate_ids(maxId, myIds, uniqueIds, mpiInfo);
334
335 double endTime = stk::wall_time();
336
337 if ( mpiInfo.getProcId() == 0 )
338 {
339 std::cerr << "Took " << endTime-startTime << " seconds." << std::endl;
340 }
341
342 EXPECT_EQ(numIdsNeeded, uniqueIds.size());
343 checkUniqueIds(myIds, uniqueIds, mpiInfo);
344
345 writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, uniqueIds);
346 }
347 }
348
349 TEST(GeneratedIds, numIdsInUseConstantNumIdsNeededVariesWithNumberProcessors)
350 {
351 MpiInfo mpiInfo(MPI_COMM_WORLD);
352
353 if ( mpiInfo.getNumProcs() <= 10 )
354 {
355 uint64_t totalIdsInUse = 362880;
356 uint64_t numIdsThisProc = totalIdsInUse/mpiInfo.getNumProcs();
357
358 std::vector<uint64_t> myIds(numIdsThisProc,0);
359 distributeIds(myIds, mpiInfo);
360
361 uint64_t maxId = 10000000;
362
363 uint64_t numIdsNeeded = 10000*mpiInfo.getNumProcs();
364 if ( mpiInfo.getProcId() != 0 )
365 {
366 numIdsNeeded = 0;
367 }
368
369 std::vector<uint64_t> uniqueIds(numIdsNeeded,0);
370
371 MPI_Barrier(mpiInfo.getMpiComm());
372
373 double startTime = stk::wall_time();
374
375 generate_ids(maxId, myIds, uniqueIds, mpiInfo);
376
377 double endTime = stk::wall_time();
378
379 if ( mpiInfo.getProcId() == 0 )
380 {
381 std::cerr << "Took " << endTime-startTime << " seconds." << std::endl;
382 }
383
384 EXPECT_EQ(numIdsNeeded, uniqueIds.size());
385 checkUniqueIds(myIds, uniqueIds, mpiInfo);
386
387 writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, uniqueIds);
388 }
389 }
390
391 TEST(GeneratedIds, distributed_index_vs_generate_parallel_unique_ids)
392 {
393 typedef stk::parallel::DistributedIndex PDIndex ;
394
395 stk::ParallelMachine comm = MPI_COMM_WORLD ;
396
397 PDIndex::KeySpanVector partition_spans(1) ;
398
399 partition_spans[0].first = 1;
400 partition_spans[0].second = 10000;
401
402 PDIndex di( comm , partition_spans );
403
404 size_t numIdsNeeded = 1;
405 std::vector<size_t> requests( partition_spans.size() , numIdsNeeded );
406
407 std::vector< PDIndex::KeyTypeVector > generated_ids_from_di ;
408 di.generate_new_keys( requests , generated_ids_from_di );
409
410 uint64_t maxAllowedId = 10000;
411 std::vector<uint64_t> existingIds;
412 std::vector<uint64_t> ids_from_gi = stk::generate_parallel_unique_ids(maxAllowedId, existingIds, numIdsNeeded, comm);
413
414 ASSERT_EQ(ids_from_gi.size(), generated_ids_from_di[0].size());
415 }
416
417 ////////////////////////////////////////////////////////////////////
418
419 void distributeIds(std::vector<uint64_t> &myIds, const MpiInfo &mpiInfo)
420 {
421 uint64_t offset = myIds.size();
422
423 for (uint64_t i=0;i<myIds.size();i++)
424 {
425 myIds[i] = offset*mpiInfo.getProcId() + i + 1;
426 }
427 }
428
429 ////////////////////////////////////////////////////////////////////
430
431 void getIdUsageAcrossAllProcs(std::vector< std::vector<uint64_t> > &idsToComm, std::vector<uint64_t> &idsInUseAcrossAllProcsInMyRange, const MpiInfo &mpiInfo)
432 {
433 for (INTMPI i=0;i<mpiInfo.getNumProcs();i++)
434 {
435 if ( i == mpiInfo.getProcId() )
436 {
437 for (INTMPI j=0;j<mpiInfo.getNumProcs();j++)
438 {
439 if ( j != mpiInfo.getProcId() )
440 {
441 uint64_t numItemsToComm = idsToComm[j].size();
442 MPI_Send(&numItemsToComm, 1, sierra::MPI::Datatype<uint64_t>::type(), j, mpiInfo.getNumProcs()*i+j, mpiInfo.getMpiComm());
443 if ( numItemsToComm > 0 )
444 {
445 MPI_Send(idsToComm[j].data(), numItemsToComm, sierra::MPI::Datatype<uint64_t>::type(), j,
446 mpiInfo.getNumProcs() * i + j, mpiInfo.getMpiComm());
447 }
448 }
449 }
450 }
451 else
452 {
453 uint64_t numItemsToReceive=0;
454 MPI_Status status1;
455 MPI_Recv(&numItemsToReceive, 1, sierra::MPI::Datatype<uint64_t>::type(), i, mpiInfo.getNumProcs()*i+mpiInfo.getProcId(), mpiInfo.getMpiComm(), &status1);
456 if ( numItemsToReceive > 0 )
457 {
458 std::vector<uint64_t> idsFromOtherProc(numItemsToReceive,0);
459 MPI_Request request;
460 MPI_Irecv(idsFromOtherProc.data(), numItemsToReceive, sierra::MPI::Datatype<uint64_t>::type(), i,
461 mpiInfo.getNumProcs() * i + mpiInfo.getProcId(), mpiInfo.getMpiComm(), &request);
462 MPI_Status status2;
463 MPI_Wait(&request, &status2);
464 idsInUseAcrossAllProcsInMyRange.insert(idsInUseAcrossAllProcsInMyRange.end(), idsFromOtherProc.begin(), idsFromOtherProc.end());
465 }
466 }
467 }
468
469 idsInUseAcrossAllProcsInMyRange.insert(idsInUseAcrossAllProcsInMyRange.end(), idsToComm[mpiInfo.getProcId()].begin(), idsToComm[mpiInfo.getProcId()].end());
470 std::sort(idsInUseAcrossAllProcsInMyRange.begin(), idsInUseAcrossAllProcsInMyRange.end());
471 }
472
473 ////////////////////////////////////////////////////////////////////
474
475 void checkUniqueIds(const std::vector<uint64_t> &myIds, const std::vector<uint64_t> &uniqueIds, const MpiInfo &mpiInfo)
476 {
477 std::vector<uint64_t> sortedIds(uniqueIds.begin(), uniqueIds.end());
478 std::sort(sortedIds.begin(), sortedIds.end());
479
480 for (INTMPI i=0;i<mpiInfo.getNumProcs();i++)
481 {
482 if (mpiInfo.getNumProcs() == i)
483 {
484 for (size_t j=0;j<uniqueIds.size();j++)
485 {
486 STK_ThrowRequireMsg(uniqueIds[j]>0, "Id generation error. Please contact sierra-help for support.");
487 EXPECT_FALSE(std::binary_search(myIds.begin(), myIds.end(), uniqueIds[j]));
488 EXPECT_EQ(true, sendIdToCheck(i, uniqueIds[j], mpiInfo.getMpiComm()));
489 }
490 terminateIdRequestForThisProc(i, mpiInfo.getMpiComm());
491 }
492 else
493 {
494 receiveIdAndCheck(i, sortedIds, mpiInfo.getMpiComm());
495 }
496 }
497 }
498
499 ////////////////////////////////////////////////////////////////////
500
501 void writeIdsToFile(const std::string & /*filename*/, [[maybe_unused]] const INTMPI myProcId,
502 [[maybe_unused]] const std::vector<uint64_t>& myIds,
503 [[maybe_unused]] const std::vector<uint64_t> &uniqueIds)
504 {
505 #ifdef DEBUG_THIS_
506 std::ostringstream os;
507 os << "ids_" << myProcId << ".m";
508 std::ofstream out(os.str().c_str());
509 // for (size_t i=0;i<myIds.size();i++)
510 // {
511 // out << "myids(" << i+1 << ") = " << myIds[i] << ";" << std::endl;
512 // }
513 for (size_t i=0;i<uniqueIds.size();i++)
514 {
515 out << "unique_ids(" << i+1 << ") = " << uniqueIds[i] << ";" << std::endl;
516 }
517 out.close();
518 #endif
519 }
520
521 ////////////////////////////////////////////////////////////////////
522
523 uint64_t getNumIdsPerProc(const uint64_t maxId, const INTMPI numProcs)
524 {
525 return maxId/numProcs;
526 }
527
528 ////////////////////////////////////////////////////////////////////
529
530 INTMPI whichProcOwnsId(const uint64_t maxId, const uint64_t id, INTMPI numProcs)
531 {
532 STK_ThrowRequireMsg(id>0, "Invalid Id. Contact sierra-help for support.");
533 uint64_t numIdsPerProc = getNumIdsPerProc(maxId, numProcs);
534 INTMPI procOwner = (id-1)/numIdsPerProc;
535 return procOwner;
536 }
537
538 ////////////////////////////////////////////////////////////////////
539
540 bool sendIdToCheck(const INTMPI root, uint64_t id, MPI_Comm comm)
541 {
542 MPI_Bcast(&id, 1, sierra::MPI::Datatype<uint64_t>::type(), root, comm);
543 bool goodId = true;
544 if ( id != 0 )
545 {
546 uint64_t good = 0;
547 uint64_t received = 0;
548 MPI_Reduce(&good, &received, 1, sierra::MPI::Datatype<uint64_t>::type(), MPI_SUM, root, comm);
549
550 if ( received > 0 )
551 {
552 goodId = false;
553 }
554 }
555 return goodId;
556 }
557
558 ////////////////////////////////////////////////////////////////////
559
560 void receiveIdAndCheck(const int root, const std::vector<uint64_t> &idsInUse, MPI_Comm comm)
561 {
562 uint64_t id=0;
563
564 while( true )
565 {
566 MPI_Bcast(&id, 1, sierra::MPI::Datatype<uint64_t>::type(), root, comm);
567 if ( id == 0) break;
568
569 bool found = std::binary_search(idsInUse.begin(), idsInUse.end(), id);
570 uint64_t result = 0;
571 if ( found )
572 {
573 result = 1;
574 }
575 MPI_Reduce(&result, &result, 1, sierra::MPI::Datatype<uint64_t>::type(), MPI_SUM, root, comm);
576 }
577 }
578
579 ////////////////////////////////////////////////////////////////////
580
581
582 void respondToRootProcessorAboutIdsOwnedOnThisProc(const int root, const uint64_t /*maxId*/, const std::vector<uint64_t> &idsInUse, MPI_Comm comm)
583 {
584 uint64_t id=0;
585
586 while( true )
587 {
588 MPI_Bcast(&id, 1, sierra::MPI::Datatype<uint64_t>::type(), root, comm);
589 if ( id == 0) break;
590 uint64_t numIdsToGet=0;
591 MPI_Bcast(&numIdsToGet, 1, sierra::MPI::Datatype<uint64_t>::type(), root, comm);
592
593 std::vector<int> areIdsBeingused(numIdsToGet,0);
594 for (size_t i=0;i<areIdsBeingused.size();i++)
595 {
596 if ( std::binary_search(idsInUse.begin(), idsInUse.end(), id+i) )
597 {
598 areIdsBeingused[i] = 1;
599 }
600 }
601 int *rbuff = 0;
602 MPI_Reduce(areIdsBeingused.data(), rbuff, numIdsToGet, MPI_INT, MPI_SUM, root, comm);
603 }
604 }
605
606 ////////////////////////////////////////////////////////////////////
607
608 void retrieveIds(const INTMPI root, uint64_t id, MPI_Comm comm, uint64_t numIdsToGetPerProc, std::vector<int>& areIdsBeingUsed)
609 {
610 MPI_Bcast(&id, 1, sierra::MPI::Datatype<uint64_t>::type(), root, comm);
611 if ( id != 0 )
612 {
613 MPI_Bcast(&numIdsToGetPerProc, 1, sierra::MPI::Datatype<uint64_t>::type(), root, comm);
614 std::vector<uint64_t> zeroids(numIdsToGetPerProc,0);
615 MPI_Reduce(zeroids.data(), areIdsBeingUsed.data(), numIdsToGetPerProc, MPI_INT, MPI_SUM, root, comm);
616 }
617 }
618
619
620 TEST(GeneratedIds, multiPerf) {
621 #ifdef COMMENT_OUT
622 //
623 // Performance and scalability comparision of a number of id generation routines.
624 //
625 // 16384 ids per processor initially.
626 // Add 1000 ids in each of ten steps
627 //
628 // Case 1: Ids initially densly packed
629 // Case 2: Ids initially spread
630 //
631
632 int mpi_rank = stk::parallel_machine_rank(MPI_COMM_WORLD);
633 int mpi_size = stk::parallel_machine_size(MPI_COMM_WORLD);
634 MpiInfo mpiInfo(MPI_COMM_WORLD);
635
636 unsigned numInit = 32768*mpi_size;
637 unsigned numNew = 1000;
638
639
640 {
641 srand((unsigned)0);
642
643
644 std::vector<unsigned> inUse32a;
645 std::vector<unsigned> inUse32c;
646 std::vector<uint64_t> inUse64a;
647 std::vector<unsigned> new32a;
648 std::vector<unsigned> new32c;
649 std::vector<uint64_t> new64a;
650 std::vector<unsigned> inUse32b;
651 std::vector<unsigned> order32c;
652 std::vector<uint64_t> inUse64b;
653 std::vector<unsigned> new32b;
654 std::vector<uint64_t> new64b;
655
656 unsigned maxAllowableId32 = ~0U;
657 uint64_t maxAllowableId64 = maxAllowableId32;
658
659 for(unsigned i=1; i<numInit+1; ++i) {
660 unsigned targetRank = rand()%mpi_size;
661 if(targetRank == (unsigned)mpi_rank) {
662 inUse32a.push_back(i);
663 inUse64a.push_back(i);
664 }
665 }
666
667 unsigned numToFill = numInit;
668 unsigned firstIndex = 1;
669
670 unsigned maxIndex = 0;
671
672 while(numToFill > 0) {
673 unsigned curNumToFill = numToFill/2;
674 if(curNumToFill == 0) curNumToFill = 1;
675
676 for(unsigned i=0; i<curNumToFill; ++i) {
677
678 unsigned targetRank = rand()%mpi_size;
679
680 maxIndex = std::max(maxIndex, firstIndex+1);
681
682 if(targetRank == (unsigned)mpi_rank) {
683 inUse32b.push_back(firstIndex + i);
684 inUse32c.push_back(firstIndex + i);
685 inUse64b.push_back(firstIndex + i);
686 }
687 }
688 numToFill -= curNumToFill;
689 firstIndex = firstIndex + (maxAllowableId32 - firstIndex)/1.8;
690 }
691 order32c.resize(numNew);
692 for(unsigned i=0; i<numNew; ++i) {
693 order32c[i] = mpi_rank*numNew + i;
694 }
695
696
697 double timeGenerateParallelUniqueA = 0.0;
698 double timeGenerateA = 0.0;
699 double timeGenerateParallelUniqueB = 0.0;
700 double timeGenerateParallelUniqueC = 0.0;
701 double timeGenerateB = 0.0;
702 double timeDI = 0.0;
703 double timeRED = 0.0;
704
705 {
706 MPI_Barrier(MPI_COMM_WORLD);
707 double startTime = stk::wall_time();
708
709
710 for(int iter=0; iter<512; ++iter) {
711 unsigned globalSubDivCount[16];
712 unsigned localSubDivCount[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
713 int mpiResult = MPI_Scan(localSubDivCount, globalSubDivCount, 16, MPI_UNSIGNED, MPI_SUM, MPI_COMM_WORLD);
714 }
715 MPI_Barrier(MPI_COMM_WORLD);
716 double endTime = stk::wall_time();
717 timeRED += (endTime-startTime);
718
719 }
720
721 for(int iter=0; iter<64; ++iter) {
722 MPI_Barrier(MPI_COMM_WORLD);
723 double startTime = stk::wall_time();
724 new32a = stk::generate_parallel_unique_ids(maxAllowableId32, inUse32a, numNew, MPI_COMM_WORLD, inUse32a.back());
725 MPI_Barrier(MPI_COMM_WORLD);
726 double endTime = stk::wall_time();
727 timeGenerateParallelUniqueA += (endTime-startTime);
728 for(unsigned inew=0; inew<new32a.size(); ++inew) {
729 inUse32a.push_back(new32a[inew]);
730 }
731 }
732
733 for(int iter=0; iter<64; ++iter) {
734 MPI_Barrier(MPI_COMM_WORLD);
735 double startTime = stk::wall_time();
736 new32b = stk::generate_parallel_unique_ids(maxAllowableId32, inUse32b, numNew, MPI_COMM_WORLD);
737 MPI_Barrier(MPI_COMM_WORLD);
738 double endTime = stk::wall_time();
739 timeGenerateParallelUniqueB += (endTime-startTime);
740 for(unsigned inew=0; inew<new32b.size(); ++inew) {
741 inUse32b.push_back(new32b[inew]);
742 }
743 }
744
745 for(int iter=0; iter<64; ++iter) {
746 MPI_Barrier(MPI_COMM_WORLD);
747 double startTime = stk::wall_time();
748 new32c = stk::generate_parallel_consistent_ids(maxAllowableId32, inUse32c, order32c, MPI_COMM_WORLD);
749 MPI_Barrier(MPI_COMM_WORLD);
750 double endTime = stk::wall_time();
751 timeGenerateParallelUniqueC += (endTime-startTime);
752 for(unsigned inew=0; inew<new32c.size(); ++inew) {
753 inUse32c.push_back(new32c[inew]);
754 //order32c.push_back(mpi_size*numNew + iter*mpi_size*);
755 }
756 }
757
758 if(mpi_rank == 0) {
759 std::cout<<"CASE 1: TIME 32 A: "<<timeGenerateParallelUniqueA<<std::endl;
760 std::cout<<"CASE 1: TIME 64 A: "<<timeGenerateA<<std::endl;
761 std::cout<<"CASE 1: TIME 32 B: "<<timeGenerateParallelUniqueB<<std::endl;
762 std::cout<<"CASE 1: TIME 32 C: "<<timeGenerateParallelUniqueC<<std::endl;
763 std::cout<<"CASE 1: TIME 64 B: "<<timeGenerateB<<std::endl;
764 std::cout<<"CASE 1: TIME DI: "<<timeDI<<std::endl;
765 std::cout<<"CASE 1: TIME RED: "<<timeRED<<std::endl;
766 }
767
768
769 for(int iter=0; iter<64; ++iter) {
770 new64a.resize(numNew);
771 MPI_Barrier(MPI_COMM_WORLD);
772 double startTime = stk::wall_time();
773 generate_ids(maxAllowableId64, inUse64a, new64a, mpiInfo);
774 MPI_Barrier(MPI_COMM_WORLD);
775 double endTime = stk::wall_time();
776 timeGenerateA += (endTime-startTime);
777 for(unsigned inew=0; inew<new64a.size(); ++inew) {
778 inUse64a.push_back(new64a[inew]);
779 }
780 }
781 for(int iter=0; iter<64; ++iter) {
782 new64b.resize(numNew);
783 MPI_Barrier(MPI_COMM_WORLD);
784 double startTime = stk::wall_time();
785 generate_ids(maxAllowableId64, inUse64b, new64b, mpiInfo);
786 MPI_Barrier(MPI_COMM_WORLD);
787 double endTime = stk::wall_time();
788 timeGenerateB += (endTime-startTime);
789 for(unsigned inew=0; inew<new64b.size(); ++inew) {
790 inUse64b.push_back(new64b[inew]);
791 }
792 }
793
794
795 if(mpi_rank == 0) {
796 std::cout<<"CASE 1: TIME 32 A: "<<timeGenerateParallelUniqueA<<std::endl;
797 std::cout<<"CASE 1: TIME 64 A: "<<timeGenerateA<<std::endl;
798 std::cout<<"CASE 1: TIME 32 B: "<<timeGenerateParallelUniqueB<<std::endl;
799 std::cout<<"CASE 1: TIME 64 B: "<<timeGenerateB<<std::endl;
800 std::cout<<"CASE 1: TIME DI: "<<timeDI<<std::endl;
801 }
802
803
804 typedef stk::parallel::DistributedIndex PDIndex;
805 PDIndex::KeySpanVector partition_spans;
806 enum { test_spans_count = 100 };
807 enum { test_spans_size = 1000000 };
808
809 partition_spans.resize( test_spans_count );
810
811 for ( unsigned i = 0 ; i < test_spans_count ; ++i ) {
812 partition_spans[i].first = 1 + test_spans_size * i * 2 ;
813 partition_spans[i].second = test_spans_size * ( i * 2 + 1 );
814 }
815 PDIndex di( MPI_COMM_WORLD , partition_spans );
816 std::vector<size_t> requests( partition_spans.size() , 0u );
817 std::vector< PDIndex::KeyTypeVector > generated_keys ;
818 PDIndex::KeyProcVector sharing_of_local_keys ;
819
820 PDIndex::KeyTypeVector keys_to_add ;
821 PDIndex::KeyTypeVector keys_to_remove ;
822
823 //------------------------------
824 // Add 32768 odd keys per process
825 // starting at the beginning of the partition.
826
827 const size_t old_size_multiplier = 16 ;
828
829 for ( size_t j = 0 ; j < partition_spans.size() ; ++j ) {
830 PDIndex::KeyType key_first = partition_spans[j].first ;
831 if ( 0 == key_first % 2 ) { ++key_first ; } // Make it odd
832 key_first += old_size_multiplier * mpi_rank ;
833
834 const size_t n = old_size_multiplier * 1024 ;
835 for ( size_t i = 0 ; i < n ; ++i ) {
836 PDIndex::KeyType key = key_first + 2 * i ;
837 keys_to_add.push_back( key );
838 }
839 }
840
841 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
842
843 for(int iter=0; iter<64; ++iter) {
844 const size_t gen_count = 10 ;
845 for ( size_t i = 0 ; i < requests.size() ; ++i ) {
846 if ( i % 2 ) {
847 requests[i] = gen_count ;
848 }
849 else {
850 requests[i] = 0 ;
851 }
852 }
853 MPI_Barrier(MPI_COMM_WORLD);
854 double startTime = stk::wall_time();
855
856 di.generate_new_keys( requests , generated_keys );
857
858 MPI_Barrier(MPI_COMM_WORLD);
859 double endTime = stk::wall_time();
860 timeDI += (endTime-startTime);
861 }
862
863
864 if(mpi_rank == 0) {
865 std::cout<<"CASE 1: TIME 32 A: "<<timeGenerateParallelUniqueA<<std::endl;
866 std::cout<<"CASE 1: TIME 64 A: "<<timeGenerateA<<std::endl;
867 std::cout<<"CASE 1: TIME 32 B: "<<timeGenerateParallelUniqueB<<std::endl;
868 std::cout<<"CASE 1: TIME 64 B: "<<timeGenerateB<<std::endl;
869 std::cout<<"CASE 1: TIME DI: "<<timeDI<<std::endl;
870 }
871 }
872 #endif
873 }
874
875
876 ////////////////////////////////////////////////////////////////////
877
878 void generate_ids(const uint64_t maxId, const std::vector<uint64_t> &idsInUse, std::vector<uint64_t> &uniqueIds, const MpiInfo& mpiInfo)
879 {
880 std::vector< std::vector<uint64_t> > idsToComm(mpiInfo.getNumProcs());
881
882 for (size_t i=0;i<idsInUse.size();i++)
883 {
884 INTMPI procOwner = whichProcOwnsId(maxId, idsInUse[i], mpiInfo.getNumProcs());
885 STK_ThrowRequireMsg(static_cast<int>(procOwner)<mpiInfo.getNumProcs(), "Id generation error. Please contact sierra-help. procOwner = " << procOwner << ", maxId = " << maxId << ", and id = " << idsInUse[i] << std::endl);
886 idsToComm[procOwner].push_back(idsInUse[i]);
887 }
888
889 std::vector<uint64_t> idsInUseAcrossAllProcsInMyRange;
890 getIdUsageAcrossAllProcs(idsToComm, idsInUseAcrossAllProcsInMyRange, mpiInfo);
891
892 std::vector<uint64_t> uniqueIdsFound;
893
894 uint64_t myIndexStart = getNumIdsPerProc(maxId, mpiInfo.getNumProcs())*mpiInfo.getProcId()+1;
895 uint64_t myIndexEnd = getNumIdsPerProc(maxId, mpiInfo.getNumProcs())*(mpiInfo.getProcId()+1)+1;
896
897 size_t numIdsNeeded = uniqueIds.size();
898 size_t numIdsAvailableThisProc = getNumIdsPerProc(maxId, mpiInfo.getNumProcs()) - idsInUseAcrossAllProcsInMyRange.size();
899 STK_ThrowRequireMsg(numIdsNeeded <= numIdsAvailableThisProc, "Not enough unique ids available (Id generation error). Plrease contact sierra-help for support. Number of ids needed: "
900 << numIdsNeeded << " and num available ids: " << numIdsAvailableThisProc);
901
902 if ( !uniqueIds.empty() )
903 {
904 uniqueIdsFound.reserve(numIdsNeeded);
905 for (uint64_t i=myIndexStart;i<myIndexEnd;i++)
906 {
907 if ( !std::binary_search(idsInUseAcrossAllProcsInMyRange.begin(), idsInUseAcrossAllProcsInMyRange.end(), i) )
908 {
909 uniqueIdsFound.push_back(i);
910 if ( uniqueIdsFound.size() == uniqueIds.size() )
911 {
912 break;
913 }
914 }
915 }
916 }
917
918 STK_ThrowRequireMsg(uniqueIdsFound.size() == uniqueIds.size(), "Id generation error. Could not obtain needed ids. Please contact sierra-help for support.");
919 std::copy(uniqueIdsFound.begin(), uniqueIdsFound.end(), uniqueIds.begin());
920 }
921
922 ////////////////////////////////////////////////////////////////////
923
924 void getBatchesOfIdsFromOtherProcessorsUntilRequestOnThisProcIsFulfilled(INTMPI root, uint64_t &startingIdToSearchForNewIds, std::vector<uint64_t> &idsObtained, uint64_t numIdsNeeded, int scaleFactorForNumIds,
925 std::vector<uint64_t> &sortedIds, const uint64_t maxId, const MpiInfo& mpiInfo)
926 {
927 while ( startingIdToSearchForNewIds < maxId && idsObtained.size() < numIdsNeeded )
928 {
929 int requestNumIds = numIdsNeeded - idsObtained.size();
930 std::vector<int> areIdsBeingUsed(scaleFactorForNumIds*requestNumIds,0);
931 if ( !std::binary_search(sortedIds.begin(), sortedIds.end(), startingIdToSearchForNewIds) )
932 {
933 retrieveIds(root, startingIdToSearchForNewIds, mpiInfo.getMpiComm(), scaleFactorForNumIds*requestNumIds, areIdsBeingUsed);
934 int numIdsChecked=0;
935 for (size_t i=0;i<areIdsBeingUsed.size();i++)
936 {
937 numIdsChecked=i;
938 if ( areIdsBeingUsed[i] == 0 )
939 {
940 idsObtained.push_back(startingIdToSearchForNewIds+i);
941 if ( idsObtained.size() == numIdsNeeded ) break;
942 }
943 }
944 startingIdToSearchForNewIds += numIdsChecked+1;
945 }
946 else
947 {
948 startingIdToSearchForNewIds++;
949 }
950 }
951 }
952
953 ////////////////////////////////////////////////////////////////////
954
955 void terminateIdRequestForThisProc(INTMPI root, MPI_Comm comm)
956 {
957 sendIdToCheck(root, 0, comm); // a zero terminates communication
958 }
959
960 ////////////////////////////////////////////////////////////////////
961
962 void getAvailableIds(const std::vector<uint64_t> &myIds, uint64_t numIdsNeeded, std::vector<uint64_t> &idsObtained, uint64_t &startingIdToSearchForNewIds, const uint64_t maxId, const MpiInfo& mpiInfo)
963 {
964 std::vector<uint64_t> receivedInfo(mpiInfo.getNumProcs(),0);
965 MPI_Allgather(&numIdsNeeded, 1, sierra::MPI::Datatype<uint64_t>::type(), receivedInfo.data(), 1,
966 sierra::MPI::Datatype<uint64_t>::type(), mpiInfo.getMpiComm());
967
968 std::vector<uint64_t> sortedIds(myIds.begin(), myIds.end());
969 std::sort(sortedIds.begin(), sortedIds.end());
970
971 int scaleFactorForNumIds = 10;
972
973 for (INTMPI procIndex=0;procIndex<mpiInfo.getNumProcs();procIndex++)
974 {
975 if ( receivedInfo[procIndex] != 0 )
976 {
977 if ( procIndex == mpiInfo.getProcId() )
978 {
979 getBatchesOfIdsFromOtherProcessorsUntilRequestOnThisProcIsFulfilled(procIndex, startingIdToSearchForNewIds, idsObtained, numIdsNeeded, scaleFactorForNumIds, sortedIds, maxId, mpiInfo);
980 STK_ThrowRequireMsg(idsObtained.size()==numIdsNeeded, "Id generation error. Ran out of ids. Please contact sierra-help for support.");
981 terminateIdRequestForThisProc(procIndex, mpiInfo.getMpiComm());
982 }
983 else
984 {
985 respondToRootProcessorAboutIdsOwnedOnThisProc(procIndex, maxId, sortedIds, mpiInfo.getMpiComm());
986 }
987 // updated starting id across all procs
988 MPI_Bcast(&startingIdToSearchForNewIds, 1, sierra::MPI::Datatype<uint64_t>::type(), procIndex, mpiInfo.getMpiComm());
989 }
990 }
991 }
992
993 void getAvailableIds_exp(const std::vector<uint64_t> &myIds, uint64_t numIdsNeeded, std::vector<uint64_t> &idsObtained, uint64_t &startingIdToSearchForNewIds, const uint64_t maxId, const MpiInfo& mpiInfo)
994 {
995 INTMPI numprocs = mpiInfo.getNumProcs();
996 std::vector<uint64_t> receivedInfo(numprocs,0);
997 MPI_Allgather(&numIdsNeeded, 1, sierra::MPI::Datatype<uint64_t>::type(), receivedInfo.data(), 1,
998 sierra::MPI::Datatype<uint64_t>::type(), mpiInfo.getMpiComm());
999
1000 std::vector<uint64_t> sortedIds(myIds.begin(), myIds.end());
1001 std::sort(sortedIds.begin(), sortedIds.end());
1002
1003 uint64_t largestIdHere = sortedIds.back();
1004 uint64_t largestIdEverywhere = 0;
1005
1006 MPI_Allreduce(&largestIdHere, &largestIdEverywhere, 1, sierra::MPI::Datatype<uint64_t>::type(), MPI_MAX, mpiInfo.getMpiComm());
1007
1008 uint64_t totalNumberOfIdsNeeded = 0;
1009 uint64_t offsetId=0;
1010 for (INTMPI i=0;i<numprocs;i++)
1011 {
1012 totalNumberOfIdsNeeded += receivedInfo[i];
1013 if ( i < mpiInfo.getProcId() )
1014 {
1015 offsetId += receivedInfo[i];
1016 }
1017 }
1018
1019 if ( maxId - totalNumberOfIdsNeeded > largestIdHere )
1020 {
1021 startingIdToSearchForNewIds = largestIdHere;
1022 idsObtained.resize(numIdsNeeded);
1023 for (size_t i=0;i<idsObtained.size();i++)
1024 {
1025 idsObtained[i] = largestIdEverywhere + offsetId + i + 1;
1026 }
1027 }
1028 else
1029 {
1030 int scaleFactorForNumIds = 1;
1031
1032 for (INTMPI procIndex=0;procIndex<numprocs;procIndex++)
1033 {
1034 if ( receivedInfo[procIndex] != 0 )
1035 {
1036 if ( procIndex == mpiInfo.getProcId() )
1037 {
1038 getBatchesOfIdsFromOtherProcessorsUntilRequestOnThisProcIsFulfilled(procIndex, startingIdToSearchForNewIds, idsObtained, numIdsNeeded, scaleFactorForNumIds, sortedIds, maxId, mpiInfo);
1039 STK_ThrowRequireMsg(idsObtained.size()==numIdsNeeded, "Id generation error. Ran out of ids. Please contact sierra-help for support.");
1040 terminateIdRequestForThisProc(procIndex, mpiInfo.getMpiComm());
1041 }
1042 else
1043 {
1044 respondToRootProcessorAboutIdsOwnedOnThisProc(procIndex, maxId, sortedIds, mpiInfo.getMpiComm());
1045 }
1046 // updated starting id across all procs
1047 MPI_Bcast(&startingIdToSearchForNewIds, 1, sierra::MPI::Datatype<uint64_t>::type(), procIndex, mpiInfo.getMpiComm());
1048 }
1049 }
1050 }
1051 }
1052
1053 }
1054
1055 #endif // STK_HAS_MPI
1056