Debian Codegraph @

packages/stk/stk_unit_tests/stk_util/parallel/UnitTestIndexGapFinder.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/Parallel.hpp" // for MPI_COMM_WORLD, MPI_Scan, MPI_SUM
37 #include "stk_util/parallel/ParallelIndexGapFinder.hpp" // for parallel_index_gap_finder_global
38 #include "stk_util/parallel/ParallelVectorConcat.hpp" // for parallel_vector_concat
39 #include <algorithm> // for sort
40 #include <cstdint> // for uint64_t
41 #include <vector> // for vector<>::iterator, vector
42
43
44 //------------------------------------------------------------------------------
45 //
46 // Test the generate_parallel_unique_ids function in stk_util/parallel
47 //
48
49 TEST(UnitTestParallel, testParallelIndexGapFinder) {
50 int mpi_rank = stk::parallel_machine_rank(MPI_COMM_WORLD);
51 int mpi_size = stk::parallel_machine_size(MPI_COMM_WORLD);
52 //
53 // Test 1, dense filling of initially half full space
54 // First 500 of 1000 ids in use(0->500), return the remaining 500 (500->999)
55 //
56
57 {
58 std::vector<uint64_t> localIdsInUse;
59 uint64_t numLocalIdsRequested = 0;
60 int targetRank = 0;
61 for(uint64_t i=0; i < 500; ++i) {
62 if(mpi_rank == targetRank) {
63 localIdsInUse.push_back(i);
64 numLocalIdsRequested++;
65 }
66 targetRank++;
67 if(targetRank >= mpi_size) {
68 targetRank = 0;
69 }
70 }
71 std::vector<uint64_t> returnIds;
72 uint64_t myFirstNewId;
73
74 MPI_Scan(&numLocalIdsRequested, &myFirstNewId, 1, MPI_UNSIGNED_LONG, MPI_SUM, MPI_COMM_WORLD);
75
76 myFirstNewId-=numLocalIdsRequested;
77
78
79 int returnCode = stk::parallel_index_gap_finder_global(MPI_COMM_WORLD, 0, 1000, localIdsInUse,
80 numLocalIdsRequested, 500, myFirstNewId, returnIds);
81
82
83 std::vector<uint64_t> globalReturnIds;
84 stk::parallel_vector_concat(MPI_COMM_WORLD, returnIds, globalReturnIds);
85
86
87 std::sort(globalReturnIds.begin(), globalReturnIds.end());
88
89 EXPECT_EQ(returnCode, 0);
90
91 EXPECT_EQ(globalReturnIds.size(), (uint64_t)500);
92
93
94 for(int i=0; i<500; ++i) {
95 EXPECT_EQ(globalReturnIds[i], (uint64_t)(500+i));
96 }
97 }
98
99
100 //
101 // Test 2, dense filling of initial half full space.
102 // Initially all even ids in use. Note, this is likely the worst case for performance of this routine, but it should
103 // still return correct results.
104 //
105 {
106 std::vector<uint64_t> localIdsInUse;
107 uint64_t numLocalIdsRequested = 0;
108 int targetRank = 0;
109 for(uint64_t i=0; i < 1000; ++i) {
110 if(i%2 != 0) {
111 targetRank += 5;
112 continue;
113 }
114 if(targetRank >= mpi_size) {
115 targetRank = 0;
116 }
117 if(mpi_rank == targetRank) {
118 localIdsInUse.push_back(i);
119 numLocalIdsRequested++;
120 }
121 targetRank++;
122 }
123
124
125
126 std::vector<uint64_t> returnIds;
127
128
129
130
131 uint64_t myFirstNewId;
132 MPI_Scan(&numLocalIdsRequested, &myFirstNewId, 1, MPI_UNSIGNED_LONG, MPI_SUM, MPI_COMM_WORLD);
133 myFirstNewId-=numLocalIdsRequested;
134 int returnCode = stk::parallel_index_gap_finder_global(MPI_COMM_WORLD, 0, 1000, localIdsInUse,
135 numLocalIdsRequested, 500, myFirstNewId, returnIds);
136 std::vector<uint64_t> globalReturnIds;
137 stk::parallel_vector_concat(MPI_COMM_WORLD, returnIds, globalReturnIds);
138
139 EXPECT_EQ(returnCode, 0);
140 EXPECT_EQ(globalReturnIds.size(), (uint64_t)500);
141 std::sort(globalReturnIds.begin(), globalReturnIds.end());
142 for(uint64_t i=0; i<500; i++) {
143 EXPECT_EQ(globalReturnIds[i], i*2+1);
144 }
145 }
146
147
148 //
149 // Test 3,
150 // Boundary case, same as 3 but only 1 processor has any initial ids, only 1 processor will recieve any ids
151 //
152 {
153 std::vector<uint64_t> localIdsInUse;
154 int targetRank = mpi_size/2;
155 for(uint64_t i=0; i < 1000; ++i) {
156 if(i%2 != 0) {
157 continue;
158 }
159 if(mpi_rank == targetRank) {
160 localIdsInUse.push_back(i);
161 }
162 }
163 std::vector<uint64_t> returnIds;
164
165 uint64_t numLocalIdsRequested;
166 if(mpi_rank == mpi_size/3) {
167 numLocalIdsRequested = 500;
168 } else {
169 numLocalIdsRequested = 0;
170 }
171
172
173
174 uint64_t myFirstNewId;
175 MPI_Scan(&numLocalIdsRequested, &myFirstNewId, 1, MPI_UNSIGNED_LONG, MPI_SUM, MPI_COMM_WORLD);
176 myFirstNewId-=numLocalIdsRequested;
177 int returnCode = stk::parallel_index_gap_finder_global(MPI_COMM_WORLD, 0, 1000, localIdsInUse,
178 numLocalIdsRequested, 500, myFirstNewId, returnIds);
179 std::vector<uint64_t> globalReturnIds;
180 stk::parallel_vector_concat(MPI_COMM_WORLD, returnIds, globalReturnIds);
181
182
183 if(mpi_rank == mpi_size/3) {
184 EXPECT_EQ(returnIds.size(), (uint64_t)500);
185 } else {
186 EXPECT_EQ(returnIds.size(), (uint64_t)0);
187 }
188
189 EXPECT_EQ(returnCode, 0);
190 EXPECT_EQ(globalReturnIds.size(), (uint64_t)500);
191 std::sort(globalReturnIds.begin(), globalReturnIds.end());
192 for(uint64_t i=0; i<500; i++) {
193 EXPECT_EQ(globalReturnIds[i], i*2+1);
194 }
195 }
196
197
198 //
199 // Test 4,
200 // Sparse filling spread id in a logarithm fashion clumped at zero
201 //
202 {
203 uint64_t maxId = 1000000;
204 uint64_t numId = 1024;
205 uint64_t curStart = 0;
206 int targetRank = mpi_size/2;
207 std::vector<uint64_t> localIdsInUse;
208 while(numId > 0) {
209 numId = numId/2;
210 for(uint64_t i=0; i<numId; ++i) {
211 if(mpi_rank == targetRank) {
212 localIdsInUse.push_back(curStart+i);
213 }
214 targetRank++;
215 if(targetRank >= mpi_size){
216 targetRank = 0;
217 }
218 }
219 curStart = curStart + (maxId-curStart)/2;
220 }
221
222
223 uint64_t numLocalIdsRequested=0;
224 for(uint64_t i=0; i<10000; ++i) {
225 if(i%mpi_size == (uint64_t)mpi_rank) {
226 numLocalIdsRequested++;
227 }
228 }
229
230
231 //
232 // Successively fill to 10% capacity
233 //
234 for(int iter=0; iter<10; ++iter) {
235 std::vector<uint64_t> returnIds;
236
237
238
239
240 uint64_t myFirstNewId;
241 MPI_Scan(&numLocalIdsRequested, &myFirstNewId, 1, MPI_UNSIGNED_LONG, MPI_SUM, MPI_COMM_WORLD);
242 myFirstNewId-=numLocalIdsRequested;
243 int returnCode = stk::parallel_index_gap_finder_global(MPI_COMM_WORLD, 0, maxId, localIdsInUse,
244 numLocalIdsRequested, 10000, myFirstNewId, returnIds);
245 std::vector<uint64_t> globalReturnIds;
246 stk::parallel_vector_concat(MPI_COMM_WORLD, returnIds, globalReturnIds);
247
248
249
250
251
252 EXPECT_EQ(returnCode, 0);
253 EXPECT_EQ(globalReturnIds.size(), (uint64_t)10000);
254 std::vector<uint64_t> globalInUse;
255 stk::parallel_vector_concat(MPI_COMM_WORLD, localIdsInUse, globalInUse);
256 globalInUse.insert(globalInUse.end(), globalReturnIds.begin(), globalReturnIds.end());
257 std::sort(globalInUse.begin(), globalInUse.end());
258 for(uint64_t i=0; i<globalInUse.size() -1; ++i) {
259 EXPECT_NE(globalInUse[i], globalInUse[i+1]);
260 }
261 for(uint64_t iret=0; iret<globalReturnIds.size(); ++iret) {
262 if(mpi_rank == targetRank) {
263 localIdsInUse.push_back(globalReturnIds[iret]);
264 }
265 targetRank++;
266 }
267 }
268 }
269
270
271 }