| 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 |
|