Debian Codegraph @

packages/stk/stk_unit_tests/stk_util/parallel/UnitTestGenerateParallelConsistentIDs.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/parallel/GenerateParallelConsistentIDs.hpp" // for generate_parallel_consist...
37 #include "stk_util/parallel/Parallel.hpp" // for MPI_COMM_WORLD, MPI_Allre...
38 #include "stk_util/parallel/ParallelVectorConcat.hpp" // for parallel_vector_concat
39 #include "stk_util/util/ReportHandler.hpp" // for ThrowRequireMsg
40 #include <algorithm> // for sort, binary_search
41 #include <cstdint> // for uint64_t
42 #include <memory> // for allocator_traits<>::value...
43 #include <utility> // for pair
44 #include <vector> // for vector
45
46
47 //-------------------------------------------------------------------------------------------------------------------
48 // Helper functions for test error checking, consolidate pairs of local order and resultant ids into a single
49 // global sorted list.
50
51 std::vector<std::pair<uint64_t, uint64_t> > GenerateGlobalPairedList(std::vector<uint64_t>& localOrderArray, std::vector<uint64_t>& newIdsLocal, stk::ParallelMachine comm) {
52
53 STK_ThrowRequireMsg(localOrderArray.size() == newIdsLocal.size(),"Inconsistent Sizes in GenerateGlobalPairedList");
54
55 std::vector<std::pair<uint64_t, uint64_t> > idOrderPairsLocal;
56 std::vector<std::pair<uint64_t, uint64_t> > idOrderPairsGlobal;
57 for(uint64_t i = 0; i < localOrderArray.size(); ++i) {
58 idOrderPairsLocal.emplace_back(localOrderArray[i], newIdsLocal[i]);
59 }
60
61 stk::parallel_vector_concat(comm, idOrderPairsLocal, idOrderPairsGlobal);
62
63 std::sort(idOrderPairsGlobal.begin(), idOrderPairsGlobal.end());
64
65 return idOrderPairsGlobal;
66 }
67
68 //-------------------------------------------------------------------------------------------------------------------
69 // Verify that a result generated from the consistent ids function meets all properties nessecary of consistent ids
70 void VerifyConsistentIds(uint64_t maxAllowableId,
71 std::vector<uint64_t>& existingIdsLocal,
72 std::vector<uint64_t>& localOrderArray,
73 std::vector<uint64_t>& newIdsLocal,
74 stk::ParallelMachine comm) {
75
76 EXPECT_EQ(localOrderArray.size(), newIdsLocal.size());
77 //
78 // Generate a global list of all ids created matched with and sorted by their order array entry
79 //
80 std::vector<std::pair<uint64_t, uint64_t> > idOrderPairsGlobal = GenerateGlobalPairedList(localOrderArray, newIdsLocal, comm);
81
82 std::vector<uint64_t> existingIdsGlobal;
83 stk::parallel_vector_concat(comm, existingIdsLocal, existingIdsGlobal);
84 std::sort(existingIdsGlobal.begin(), existingIdsGlobal.end());
85 //
86 // Verify properties of the returned ids
87 //
88 for(uint64_t i=0; i<idOrderPairsGlobal.size(); ++i) {
89 uint64_t curNewID = idOrderPairsGlobal[i].second;
90 // 1) Verify all ids must be less than or equal to maxAllowableId
91 EXPECT_LE(curNewID, maxAllowableId);
92 // 2) Verify no overlap between existing and new id set
93 EXPECT_FALSE(std::binary_search(existingIdsGlobal.begin(), existingIdsGlobal.end(), curNewID));
94 // 3) Verify ids come back in order dictated by the ordering array
95 if(i > 0) {
96 uint64_t oldNewID = idOrderPairsGlobal[i-1].second;
97 EXPECT_LT(oldNewID, curNewID);
98 EXPECT_LT(idOrderPairsGlobal[i-1].first, idOrderPairsGlobal[i].first);
99 }
100 }
101
102 }
103
104 //------------------------------------------------------------------------------
105 //
106 // Test the generate_parallel_consistent_ids function in stk_util/parallel
107 //
108 TEST(UnitTestParallel, testGenerateParallelConsistentIDs) {
109 int mpi_rank = stk::parallel_machine_rank(MPI_COMM_WORLD);
110 int mpi_size = stk::parallel_machine_size(MPI_COMM_WORLD);
111 //
112 // Test 1, nominal element death case
113 // Each processor starts with 1000 unique densly packed ids ordered 1->N. Add 10 new ids per processor
114 // produced by kill every 100th element creating 10 new elements per processor.
115 //
116 uint64_t maxAllowableId = ~0U;
117
118 std::vector<uint64_t> newIds1;
119 std::vector<uint64_t> localOrderArray1;
120
121 {
122 std::vector<uint64_t> existingIds(1000);
123 uint64_t firstId = mpi_rank*1000;
124
125
126 for(uint64_t i=0; i<1000; ++i) {
127 uint64_t currentElemId = firstId+i;
128 existingIds[i] = currentElemId;
129 if(i%100 == 0) {
130 // local order array is the 'source element' which provides a unique repeatable ordering
131 localOrderArray1.push_back(currentElemId);
132 }
133 }
134 newIds1 = stk::generate_parallel_consistent_ids(maxAllowableId, existingIds, localOrderArray1, MPI_COMM_WORLD);
135
136 uint64_t localSize = newIds1.size();
137 uint64_t globalSize;
138 MPI_Allreduce(&localSize, &globalSize, 1, MPI_UNSIGNED_LONG, MPI_SUM, MPI_COMM_WORLD);
139 EXPECT_EQ(globalSize, (uint64_t)mpi_size*10);
140 VerifyConsistentIds(maxAllowableId, existingIds, localOrderArray1, newIds1, MPI_COMM_WORLD);
141 }
142 //
143 // Test 2, same total source data as case 1, but source data scattered among processors
144 //
145 std::vector<uint64_t> newIds2;
146 std::vector<uint64_t> localOrderArray2;
147 {
148 std::vector<uint64_t> existingIds;
149 uint64_t destProc = mpi_size/2;
150 for(int i=0; i<1000*mpi_size; ++i) {
151 destProc += i;
152 if(destProc >= (uint64_t)mpi_size) {
153 destProc = destProc%mpi_size;
154 }
155 if(destProc == (uint64_t)mpi_rank) {
156 existingIds.push_back(i);
157 if(i%100 == 0) {
158 localOrderArray2.push_back(i);
159 }
160 }
161 }
162 newIds2 = stk::generate_parallel_consistent_ids(maxAllowableId, existingIds, localOrderArray2, MPI_COMM_WORLD);
163
164 uint64_t localSize = newIds2.size();
165 uint64_t globalSize;
166 MPI_Allreduce(&localSize, &globalSize, 1, MPI_UNSIGNED_LONG, MPI_SUM, MPI_COMM_WORLD);
167 EXPECT_EQ(globalSize, (uint64_t)mpi_size*10);
168 VerifyConsistentIds(maxAllowableId, existingIds, localOrderArray2, newIds2, MPI_COMM_WORLD);
169 }
170 //
171 // Test 3, verify test 2 and test 3 generate the same ids in identical order, confirming the id generation scheme is decomposition independent
172 //
173 std::vector<std::pair<uint64_t, uint64_t> > idOrderPairsGlobal1 = GenerateGlobalPairedList(localOrderArray1, newIds1, MPI_COMM_WORLD);
174 std::vector<std::pair<uint64_t, uint64_t> > idOrderPairsGlobal2 = GenerateGlobalPairedList(localOrderArray2, newIds2, MPI_COMM_WORLD);
175 EXPECT_EQ(idOrderPairsGlobal1.size(), idOrderPairsGlobal2.size());
176 for(uint64_t i=0; i < idOrderPairsGlobal1.size(); ++i) {
177 EXPECT_EQ(idOrderPairsGlobal1[i].first, idOrderPairsGlobal2[i].first);
178 EXPECT_EQ(idOrderPairsGlobal1[i].second, idOrderPairsGlobal2[i].second);
179 }
180 //
181 // Test 4, sparse fill
182 //
183 {
184 std::vector<uint64_t> newIds;
185 std::vector<uint64_t> existingIds(1000);
186 std::vector<uint64_t> localOrderArray;
187
188 uint64_t firstId = mpi_rank*1000;
189
190 for(uint64_t i=0; i<1000; ++i) {
191 uint64_t currentElemId = firstId+i;
192 existingIds[i] = currentElemId;
193 }
194
195 if(mpi_rank == 0) {
196 existingIds.push_back(~0U);
197 }
198
199
200 for(int i=0; i<10; ++i) {
201 localOrderArray.push_back(mpi_rank*10 + i);
202 }
203
204
205 newIds = stk::generate_parallel_consistent_ids(maxAllowableId, existingIds, localOrderArray, MPI_COMM_WORLD);
206
207
208 uint64_t localSize = newIds.size();
209 uint64_t globalSize;
210 MPI_Allreduce(&localSize, &globalSize, 1, MPI_UNSIGNED_LONG, MPI_SUM, MPI_COMM_WORLD);
211 EXPECT_EQ(globalSize, (uint64_t)mpi_size*10);
212 VerifyConsistentIds(maxAllowableId, existingIds, localOrderArray, newIds, MPI_COMM_WORLD);
213 }
214
215 }