// Copyright 2002 - 2008, 2010, 2011 National Technology Engineering // Solutions of Sandia, LLC (NTESS). Under the terms of Contract // DE-NA0003525 with NTESS, the U.S. Government retains certain rights // in this software. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are // met: // // * Redistributions of source code must retain the above copyright // notice, this list of conditions and the following disclaimer. // // * Redistributions in binary form must reproduce the above // copyright notice, this list of conditions and the following // disclaimer in the documentation and/or other materials provided // with the distribution. // // * Neither the name of NTESS nor the names of its contributors // may be used to endorse or promote products derived from this // software without specific prior written permission. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // #include "gtest/gtest.h" #include "stk_util/environment/WallTime.hpp" // for wall_time #include "stk_util/parallel/DistributedIndex.hpp" // for DistributedIndex::KeyTypeVector #include "stk_util/parallel/GenerateParallelUniqueIDs.hpp" // for generate_parallel_unique_ids #include "stk_util/parallel/MPI.hpp" // for Datatype #include "stk_util/parallel/Parallel.hpp" // for MPI_Bcast, MPI_Comm, MPI_Reduce #include "stk_util/stk_config.h" // for STK_HAS_MPI #include "stk_util/util/ReportHandler.hpp" // for ThrowRequireMsg #include // for size_t #include // for binary_search, sort, copy #include // for uint64_t #include // for operator<<, basic_ostream, endl #include // for allocator_traits<>::value_type #include // for string #include // for vector, vector<>::iterator #if defined(STK_HAS_MPI) // means that MPI is available namespace { typedef int INTMPI; class MpiInfo { public: MpiInfo(MPI_Comm comm) : mProcId(-1), mNumProcs(-1), mComm(comm) { MPI_Comm_rank(mComm, &mProcId); MPI_Comm_size(mComm, &mNumProcs); } ~MpiInfo() {} INTMPI getProcId() const { return mProcId; } INTMPI getNumProcs() const { return mNumProcs; } MPI_Comm getMpiComm() const { return mComm; } private: INTMPI mProcId; INTMPI mNumProcs; MPI_Comm mComm; }; INTMPI whichProcOwnsId(const uint64_t maxId, const uint64_t id, INTMPI numProcs); void distributeIds(std::vector &myIds, const MpiInfo& mpiInfo); uint64_t getNumIdsPerProc(const uint64_t maxId, const INTMPI numProcs); void getIdUsageAcrossAllProcs(std::vector< std::vector > &idsToComm, std::vector &idsInUseAcrossAllProcsInMyRange, const MpiInfo& mpiInfo); void retrieveIds(const INTMPI root, uint64_t id, MPI_Comm comm, uint64_t numIdsToGetPerProc, std::vector& areIdsBeingUsed); void respondToRootProcessorAboutIdsOwnedOnThisProc(const int root, const uint64_t maxId, const std::vector &idsInUse, MPI_Comm comm); bool sendIdToCheck(const INTMPI root, uint64_t id, MPI_Comm comm); void receiveIdAndCheck(const int root, const std::vector &idsInUse, MPI_Comm comm); void checkUniqueIds(const std::vector &myIds, const std::vector &uniqueIds, const MpiInfo& mpiInfo); void writeIdsToFile(const std::string &filename, const INTMPI myProcId, const std::vector& myIds, const std::vector &uniqueIds); void generate_ids(const uint64_t maxId, const std::vector &idsInUse, std::vector &uniqueIds, const MpiInfo& mpiInfo); void getBatchesOfIdsFromOtherProcessorsUntilRequestOnThisProcIsFulfilled(INTMPI root, uint64_t &startingIdToSearchForNewIds, std::vector &idsObtained, uint64_t numIdsNeeded, int scaleFactorForNumIds, std::vector &sortedIds, const uint64_t maxId, const MpiInfo& mpiInfo); void terminateIdRequestForThisProc(INTMPI root, MPI_Comm comm); void getAvailableIds(const std::vector &myIds, uint64_t numIdsNeeded, std::vector &idsObtained, uint64_t &startingIdToSearchForNewIds, const uint64_t maxId, const MpiInfo& mpiInfo); void getAvailableIds_exp(const std::vector &myIds, uint64_t numIdsNeeded, std::vector &idsObtained, uint64_t &startingIdToSearchForNewIds, const uint64_t maxId, const MpiInfo& mpiInfo); //////////////////////////////////////////////////////////////////// TEST(GeneratedIds, whichProcOwnsId) { uint64_t maxId=10; INTMPI numProcs=3; uint64_t ids[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; INTMPI procOwner[] = { 0, 0, 0, 1, 1, 1, 2, 2, 2, 3}; for (int i=0;i<10;i++) { EXPECT_EQ(procOwner[i], whichProcOwnsId(maxId, ids[i], numProcs)); } } TEST(GeneratedIds, distributeIds) { MpiInfo mpiInfo(MPI_COMM_WORLD); int numIdsPerProc = 10; std::vector myIds(numIdsPerProc); distributeIds(myIds, mpiInfo); uint64_t offsetForProc = numIdsPerProc*mpiInfo.getProcId(); for (size_t i=0;i > idsToComm(mpiInfo.getNumProcs()); INTMPI procToSendId = 0; uint64_t madeUpId = static_cast(mpiInfo.getProcId()); idsToComm[procToSendId].push_back(madeUpId); std::vector idsInUseAcrossAllProcsInMyRange; getIdUsageAcrossAllProcs(idsToComm, idsInUseAcrossAllProcsInMyRange, mpiInfo); if ( mpiInfo.getProcId() == 0 ) { for (uint64_t id=0;id myIds(numIdsThisProc,0); distributeIds(myIds, mpiInfo); uint64_t startingIdToSearchForNewIds = 1; uint64_t numIdsNeeded = 100; std::vector idsObtained; uint64_t maxId = 10000000; double startTime = stk::wall_time(); getAvailableIds(myIds, numIdsNeeded, idsObtained, startingIdToSearchForNewIds, maxId, mpiInfo); double endTime = stk::wall_time(); if ( mpiInfo.getProcId() == 0 ) { std::cerr << "Took " << endTime-startTime << " seconds." << std::endl; } checkUniqueIds(myIds, idsObtained, mpiInfo); for (size_t i=0;i myIds(numIdsThisProc,0); distributeIds(myIds, mpiInfo); uint64_t startingIdToSearchForNewIds = 1; uint64_t numIdsNeeded = 100; std::vector idsObtained; uint64_t maxId = 72057594037927935; double startTime = stk::wall_time(); getAvailableIds_exp(myIds, numIdsNeeded, idsObtained, startingIdToSearchForNewIds, maxId, mpiInfo); double endTime = stk::wall_time(); if ( mpiInfo.getProcId() == 0 ) { std::cerr << "Took " << endTime-startTime << " seconds." << std::endl; } checkUniqueIds(myIds, idsObtained, mpiInfo); writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, idsObtained); for (size_t i=0;i myIds(numIdsThisProc,0); distributeIds(myIds, mpiInfo); uint64_t startingIdToSearchForNewIds = 1; uint64_t numIdsNeeded = 1000; std::vector idsObtained; uint64_t maxId = 100000000000; double startTime = stk::wall_time(); getAvailableIds(myIds, numIdsNeeded, idsObtained, startingIdToSearchForNewIds, maxId, mpiInfo); double endTime = stk::wall_time(); if ( mpiInfo.getProcId() == 0 ) { std::cerr << "Took " << endTime-startTime << " seconds." << std::endl; } checkUniqueIds(myIds, idsObtained, mpiInfo); writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, idsObtained); for (size_t i=0;i myIds(numIdsThisProc,0); distributeIds(myIds, mpiInfo); uint64_t numIdsNeeded = 10000; std::vector uniqueIds(numIdsNeeded,0); MPI_Barrier(mpiInfo.getMpiComm()); double startTime = stk::wall_time(); generate_ids(maxId, myIds, uniqueIds, mpiInfo); double endTime = stk::wall_time(); if ( mpiInfo.getProcId() == 0 ) { std::cerr << "Took " << endTime-startTime << " seconds." << std::endl; } EXPECT_EQ(numIdsNeeded, uniqueIds.size()); checkUniqueIds(myIds, uniqueIds, mpiInfo); writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, uniqueIds); } } // 2^56 = 72, 057, 594, 037, 927, 936 --> 72 quadrillion, 57 trillion, 594 billion, 37 million, 927 thousand, 936 ids! TEST(GeneratedIds, numIdsInUseConstantNumIdsNeededConstant) { MpiInfo mpiInfo(MPI_COMM_WORLD); if ( mpiInfo.getNumProcs() <= 10 ) { uint64_t totalIdsInUse = 362880; uint64_t numIdsThisProc = totalIdsInUse/mpiInfo.getNumProcs(); std::vector myIds(numIdsThisProc,0); distributeIds(myIds, mpiInfo); uint64_t maxId = 10000000; uint64_t numIdsNeeded = 10000; if ( mpiInfo.getProcId() != 0 ) { numIdsNeeded = 0; } std::vector uniqueIds(numIdsNeeded,0); MPI_Barrier(mpiInfo.getMpiComm()); double startTime = stk::wall_time(); generate_ids(maxId, myIds, uniqueIds, mpiInfo); double endTime = stk::wall_time(); if ( mpiInfo.getProcId() == 0 ) { std::cerr << "Took " << endTime-startTime << " seconds." << std::endl; } EXPECT_EQ(numIdsNeeded, uniqueIds.size()); checkUniqueIds(myIds, uniqueIds, mpiInfo); writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, uniqueIds); } } TEST(GeneratedIds, numIdsInUseConstantNumIdsNeededVariesWithNumberProcessors) { MpiInfo mpiInfo(MPI_COMM_WORLD); if ( mpiInfo.getNumProcs() <= 10 ) { uint64_t totalIdsInUse = 362880; uint64_t numIdsThisProc = totalIdsInUse/mpiInfo.getNumProcs(); std::vector myIds(numIdsThisProc,0); distributeIds(myIds, mpiInfo); uint64_t maxId = 10000000; uint64_t numIdsNeeded = 10000*mpiInfo.getNumProcs(); if ( mpiInfo.getProcId() != 0 ) { numIdsNeeded = 0; } std::vector uniqueIds(numIdsNeeded,0); MPI_Barrier(mpiInfo.getMpiComm()); double startTime = stk::wall_time(); generate_ids(maxId, myIds, uniqueIds, mpiInfo); double endTime = stk::wall_time(); if ( mpiInfo.getProcId() == 0 ) { std::cerr << "Took " << endTime-startTime << " seconds." << std::endl; } EXPECT_EQ(numIdsNeeded, uniqueIds.size()); checkUniqueIds(myIds, uniqueIds, mpiInfo); writeIdsToFile("ids_", mpiInfo.getProcId(), myIds, uniqueIds); } } TEST(GeneratedIds, distributed_index_vs_generate_parallel_unique_ids) { typedef stk::parallel::DistributedIndex PDIndex ; stk::ParallelMachine comm = MPI_COMM_WORLD ; PDIndex::KeySpanVector partition_spans(1) ; partition_spans[0].first = 1; partition_spans[0].second = 10000; PDIndex di( comm , partition_spans ); size_t numIdsNeeded = 1; std::vector requests( partition_spans.size() , numIdsNeeded ); std::vector< PDIndex::KeyTypeVector > generated_ids_from_di ; di.generate_new_keys( requests , generated_ids_from_di ); uint64_t maxAllowedId = 10000; std::vector existingIds; std::vector ids_from_gi = stk::generate_parallel_unique_ids(maxAllowedId, existingIds, numIdsNeeded, comm); ASSERT_EQ(ids_from_gi.size(), generated_ids_from_di[0].size()); } //////////////////////////////////////////////////////////////////// void distributeIds(std::vector &myIds, const MpiInfo &mpiInfo) { uint64_t offset = myIds.size(); for (uint64_t i=0;i > &idsToComm, std::vector &idsInUseAcrossAllProcsInMyRange, const MpiInfo &mpiInfo) { for (INTMPI i=0;i::type(), j, mpiInfo.getNumProcs()*i+j, mpiInfo.getMpiComm()); if ( numItemsToComm > 0 ) { MPI_Send(idsToComm[j].data(), numItemsToComm, sierra::MPI::Datatype::type(), j, mpiInfo.getNumProcs() * i + j, mpiInfo.getMpiComm()); } } } } else { uint64_t numItemsToReceive=0; MPI_Status status1; MPI_Recv(&numItemsToReceive, 1, sierra::MPI::Datatype::type(), i, mpiInfo.getNumProcs()*i+mpiInfo.getProcId(), mpiInfo.getMpiComm(), &status1); if ( numItemsToReceive > 0 ) { std::vector idsFromOtherProc(numItemsToReceive,0); MPI_Request request; MPI_Irecv(idsFromOtherProc.data(), numItemsToReceive, sierra::MPI::Datatype::type(), i, mpiInfo.getNumProcs() * i + mpiInfo.getProcId(), mpiInfo.getMpiComm(), &request); MPI_Status status2; MPI_Wait(&request, &status2); idsInUseAcrossAllProcsInMyRange.insert(idsInUseAcrossAllProcsInMyRange.end(), idsFromOtherProc.begin(), idsFromOtherProc.end()); } } } idsInUseAcrossAllProcsInMyRange.insert(idsInUseAcrossAllProcsInMyRange.end(), idsToComm[mpiInfo.getProcId()].begin(), idsToComm[mpiInfo.getProcId()].end()); std::sort(idsInUseAcrossAllProcsInMyRange.begin(), idsInUseAcrossAllProcsInMyRange.end()); } //////////////////////////////////////////////////////////////////// void checkUniqueIds(const std::vector &myIds, const std::vector &uniqueIds, const MpiInfo &mpiInfo) { std::vector sortedIds(uniqueIds.begin(), uniqueIds.end()); std::sort(sortedIds.begin(), sortedIds.end()); for (INTMPI i=0;i0, "Id generation error. Please contact sierra-help for support."); EXPECT_FALSE(std::binary_search(myIds.begin(), myIds.end(), uniqueIds[j])); EXPECT_EQ(true, sendIdToCheck(i, uniqueIds[j], mpiInfo.getMpiComm())); } terminateIdRequestForThisProc(i, mpiInfo.getMpiComm()); } else { receiveIdAndCheck(i, sortedIds, mpiInfo.getMpiComm()); } } } //////////////////////////////////////////////////////////////////// void writeIdsToFile(const std::string & /*filename*/, [[maybe_unused]] const INTMPI myProcId, [[maybe_unused]] const std::vector& myIds, [[maybe_unused]] const std::vector &uniqueIds) { #ifdef DEBUG_THIS_ std::ostringstream os; os << "ids_" << myProcId << ".m"; std::ofstream out(os.str().c_str()); // for (size_t i=0;i0, "Invalid Id. Contact sierra-help for support."); uint64_t numIdsPerProc = getNumIdsPerProc(maxId, numProcs); INTMPI procOwner = (id-1)/numIdsPerProc; return procOwner; } //////////////////////////////////////////////////////////////////// bool sendIdToCheck(const INTMPI root, uint64_t id, MPI_Comm comm) { MPI_Bcast(&id, 1, sierra::MPI::Datatype::type(), root, comm); bool goodId = true; if ( id != 0 ) { uint64_t good = 0; uint64_t received = 0; MPI_Reduce(&good, &received, 1, sierra::MPI::Datatype::type(), MPI_SUM, root, comm); if ( received > 0 ) { goodId = false; } } return goodId; } //////////////////////////////////////////////////////////////////// void receiveIdAndCheck(const int root, const std::vector &idsInUse, MPI_Comm comm) { uint64_t id=0; while( true ) { MPI_Bcast(&id, 1, sierra::MPI::Datatype::type(), root, comm); if ( id == 0) break; bool found = std::binary_search(idsInUse.begin(), idsInUse.end(), id); uint64_t result = 0; if ( found ) { result = 1; } MPI_Reduce(&result, &result, 1, sierra::MPI::Datatype::type(), MPI_SUM, root, comm); } } //////////////////////////////////////////////////////////////////// void respondToRootProcessorAboutIdsOwnedOnThisProc(const int root, const uint64_t /*maxId*/, const std::vector &idsInUse, MPI_Comm comm) { uint64_t id=0; while( true ) { MPI_Bcast(&id, 1, sierra::MPI::Datatype::type(), root, comm); if ( id == 0) break; uint64_t numIdsToGet=0; MPI_Bcast(&numIdsToGet, 1, sierra::MPI::Datatype::type(), root, comm); std::vector areIdsBeingused(numIdsToGet,0); for (size_t i=0;i& areIdsBeingUsed) { MPI_Bcast(&id, 1, sierra::MPI::Datatype::type(), root, comm); if ( id != 0 ) { MPI_Bcast(&numIdsToGetPerProc, 1, sierra::MPI::Datatype::type(), root, comm); std::vector zeroids(numIdsToGetPerProc,0); MPI_Reduce(zeroids.data(), areIdsBeingUsed.data(), numIdsToGetPerProc, MPI_INT, MPI_SUM, root, comm); } } TEST(GeneratedIds, multiPerf) { #ifdef COMMENT_OUT // // Performance and scalability comparision of a number of id generation routines. // // 16384 ids per processor initially. // Add 1000 ids in each of ten steps // // Case 1: Ids initially densly packed // Case 2: Ids initially spread // int mpi_rank = stk::parallel_machine_rank(MPI_COMM_WORLD); int mpi_size = stk::parallel_machine_size(MPI_COMM_WORLD); MpiInfo mpiInfo(MPI_COMM_WORLD); unsigned numInit = 32768*mpi_size; unsigned numNew = 1000; { srand((unsigned)0); std::vector inUse32a; std::vector inUse32c; std::vector inUse64a; std::vector new32a; std::vector new32c; std::vector new64a; std::vector inUse32b; std::vector order32c; std::vector inUse64b; std::vector new32b; std::vector new64b; unsigned maxAllowableId32 = ~0U; uint64_t maxAllowableId64 = maxAllowableId32; for(unsigned i=1; i 0) { unsigned curNumToFill = numToFill/2; if(curNumToFill == 0) curNumToFill = 1; for(unsigned i=0; i requests( partition_spans.size() , 0u ); std::vector< PDIndex::KeyTypeVector > generated_keys ; PDIndex::KeyProcVector sharing_of_local_keys ; PDIndex::KeyTypeVector keys_to_add ; PDIndex::KeyTypeVector keys_to_remove ; //------------------------------ // Add 32768 odd keys per process // starting at the beginning of the partition. const size_t old_size_multiplier = 16 ; for ( size_t j = 0 ; j < partition_spans.size() ; ++j ) { PDIndex::KeyType key_first = partition_spans[j].first ; if ( 0 == key_first % 2 ) { ++key_first ; } // Make it odd key_first += old_size_multiplier * mpi_rank ; const size_t n = old_size_multiplier * 1024 ; for ( size_t i = 0 ; i < n ; ++i ) { PDIndex::KeyType key = key_first + 2 * i ; keys_to_add.push_back( key ); } } di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() ); for(int iter=0; iter<64; ++iter) { const size_t gen_count = 10 ; for ( size_t i = 0 ; i < requests.size() ; ++i ) { if ( i % 2 ) { requests[i] = gen_count ; } else { requests[i] = 0 ; } } MPI_Barrier(MPI_COMM_WORLD); double startTime = stk::wall_time(); di.generate_new_keys( requests , generated_keys ); MPI_Barrier(MPI_COMM_WORLD); double endTime = stk::wall_time(); timeDI += (endTime-startTime); } if(mpi_rank == 0) { std::cout<<"CASE 1: TIME 32 A: "< &idsInUse, std::vector &uniqueIds, const MpiInfo& mpiInfo) { std::vector< std::vector > idsToComm(mpiInfo.getNumProcs()); for (size_t i=0;i(procOwner) &idsObtained, uint64_t numIdsNeeded, int scaleFactorForNumIds, std::vector &sortedIds, const uint64_t maxId, const MpiInfo& mpiInfo) { while ( startingIdToSearchForNewIds < maxId && idsObtained.size() < numIdsNeeded ) { int requestNumIds = numIdsNeeded - idsObtained.size(); std::vector areIdsBeingUsed(scaleFactorForNumIds*requestNumIds,0); if ( !std::binary_search(sortedIds.begin(), sortedIds.end(), startingIdToSearchForNewIds) ) { retrieveIds(root, startingIdToSearchForNewIds, mpiInfo.getMpiComm(), scaleFactorForNumIds*requestNumIds, areIdsBeingUsed); int numIdsChecked=0; for (size_t i=0;i &myIds, uint64_t numIdsNeeded, std::vector &idsObtained, uint64_t &startingIdToSearchForNewIds, const uint64_t maxId, const MpiInfo& mpiInfo) { std::vector receivedInfo(mpiInfo.getNumProcs(),0); MPI_Allgather(&numIdsNeeded, 1, sierra::MPI::Datatype::type(), receivedInfo.data(), 1, sierra::MPI::Datatype::type(), mpiInfo.getMpiComm()); std::vector sortedIds(myIds.begin(), myIds.end()); std::sort(sortedIds.begin(), sortedIds.end()); int scaleFactorForNumIds = 10; for (INTMPI procIndex=0;procIndex::type(), procIndex, mpiInfo.getMpiComm()); } } } void getAvailableIds_exp(const std::vector &myIds, uint64_t numIdsNeeded, std::vector &idsObtained, uint64_t &startingIdToSearchForNewIds, const uint64_t maxId, const MpiInfo& mpiInfo) { INTMPI numprocs = mpiInfo.getNumProcs(); std::vector receivedInfo(numprocs,0); MPI_Allgather(&numIdsNeeded, 1, sierra::MPI::Datatype::type(), receivedInfo.data(), 1, sierra::MPI::Datatype::type(), mpiInfo.getMpiComm()); std::vector sortedIds(myIds.begin(), myIds.end()); std::sort(sortedIds.begin(), sortedIds.end()); uint64_t largestIdHere = sortedIds.back(); uint64_t largestIdEverywhere = 0; MPI_Allreduce(&largestIdHere, &largestIdEverywhere, 1, sierra::MPI::Datatype::type(), MPI_MAX, mpiInfo.getMpiComm()); uint64_t totalNumberOfIdsNeeded = 0; uint64_t offsetId=0; for (INTMPI i=0;i largestIdHere ) { startingIdToSearchForNewIds = largestIdHere; idsObtained.resize(numIdsNeeded); for (size_t i=0;i::type(), procIndex, mpiInfo.getMpiComm()); } } } } } #endif // STK_HAS_MPI