Debian Codegraph @

packages/stk/stk_unit_tests/stk_util/parallel/UnitTestDistributedIndex.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/DistributedIndex.hpp" // for DistributedIndex::KeyTypeVector, Distr...
37 #include "stk_util/parallel/Parallel.hpp" // for parallel_machine_rank, parallel_machin...
38 #include <cstddef> // for size_t
39 #include <memory> // for allocator_traits<>::value_type
40 #include <stdexcept> // for runtime_error
41 #include <utility> // for swap
42 #include <vector> // for vector, vector::size_type
43
44 class UnitTestSTKParallelDistributedIndex {
45 public:
46 static void test_ctor();
47 static void test_ctor_bad();
48 static void test_update();
49 static void test_update_bad();
50 static void test_generate();
51 static void test_generate_bad();
52 static void test_generate_big();
53 static void test_update_generate();
54 };
55
56 namespace {
57
58 TEST( UnitTestDistributedIndexConstructor , testUnit )
59 { UnitTestSTKParallelDistributedIndex::test_ctor(); }
60
61 TEST( UnitTestDistributedIndexConstructorBad , testUnit )
62 { UnitTestSTKParallelDistributedIndex::test_ctor_bad(); }
63
64 TEST( UnitTestDistributedIndexUpdate , testUnit )
65 { UnitTestSTKParallelDistributedIndex::test_update(); }
66
67 TEST( UnitTestDistributedIndexUpdateBad , testUnit )
68 { UnitTestSTKParallelDistributedIndex::test_update_bad(); }
69
70 TEST( UnitTestDistributedIndexGenerate , testUnit )
71 { UnitTestSTKParallelDistributedIndex::test_generate(); }
72
73 TEST( UnitTestDistributedIndexGenerateBad , testUnit )
74 { UnitTestSTKParallelDistributedIndex::test_generate_bad(); }
75
76 TEST( UnitTestDistributedIndexUpdateGenerate , testUnit )
77 { UnitTestSTKParallelDistributedIndex::test_update_generate(); }
78
79 TEST( UnitTestDistributedIndexGenerateBig , testUnit )
80 { UnitTestSTKParallelDistributedIndex::test_generate_big(); }
81
82 // Generate spans:
83 // [ 1..10000]
84 // [20001..30000]
85 // [40001..50000]
86 // [60001..70000]
87 // [80001..90000]
88 // etc.
89 void generate_test_spans_10x10000(
90 stk::parallel::DistributedIndex::KeySpanVector & partition_spans )
91 {
92 enum { test_spans_count = 10 };
93 enum { test_spans_size = 10000 };
94
95 partition_spans.resize( test_spans_count );
96
97 for ( unsigned i = 0 ; i < test_spans_count ; ++i ) {
98 partition_spans[i].first = 1 + test_spans_size * i * 2 ;
99 partition_spans[i].second = test_spans_size * ( i * 2 + 1 );
100 }
101 }
102
103 }
104
105 //----------------------------------------------------------------------
106
107 void UnitTestSTKParallelDistributedIndex::test_ctor()
108 {
109 typedef stk::parallel::DistributedIndex PDIndex ;
110 stk::ParallelMachine comm = MPI_COMM_WORLD ;
111
112 int mpi_rank = stk::parallel_machine_rank(comm);
113 int mpi_size = stk::parallel_machine_size(comm);
114
115 PDIndex::KeySpanVector partition_spans ;
116
117 generate_test_spans_10x10000( partition_spans );
118
119 PDIndex di( comm , partition_spans );
120
121 EXPECT_EQ( di.m_comm_rank , mpi_rank );
122 EXPECT_EQ( di.m_comm_size , mpi_size );
123 EXPECT_TRUE( di.m_key_usage.empty() );
124 ASSERT_EQ( di.m_key_span.size() , partition_spans.size() );
125 for ( size_t i = 0 ; i < di.m_key_span.size() ; ++i ) {
126 EXPECT_EQ( di.m_key_span[i].first , partition_spans[i].first );
127 EXPECT_EQ( di.m_key_span[i].second , partition_spans[i].second );
128 }
129
130 // All queries will be empty:
131
132 PDIndex::KeyTypeVector keys_to_query ;
133 PDIndex::KeyProcVector sharing_of_local_keys ;
134
135 di.query( sharing_of_local_keys );
136
137 EXPECT_TRUE( sharing_of_local_keys.empty() );
138
139 di.query( keys_to_query , sharing_of_local_keys );
140
141 EXPECT_TRUE( sharing_of_local_keys.empty() );
142
143 keys_to_query.push_back( 10 );
144
145 di.query( keys_to_query , sharing_of_local_keys );
146
147 EXPECT_TRUE( sharing_of_local_keys.empty() );
148 }
149
150 void UnitTestSTKParallelDistributedIndex::test_ctor_bad()
151 {
152 typedef stk::parallel::DistributedIndex PDIndex ;
153
154 stk::ParallelMachine comm = MPI_COMM_WORLD ;
155
156 {
157 // Throw for overlapping span
158 PDIndex::KeySpanVector partition_spans ;
159
160 generate_test_spans_10x10000( partition_spans );
161
162 // Corrupt this span to trigger an error
163 partition_spans[5].first = partition_spans[4].second ;
164
165 ASSERT_THROW( PDIndex di( comm , partition_spans ) , std::runtime_error );
166 }
167
168 {
169 // Throw for one bad span
170 PDIndex::KeySpanVector partition_spans ;
171
172 generate_test_spans_10x10000( partition_spans );
173
174 // Corrupt this span to trigger an error
175 std::swap( partition_spans[5].first , partition_spans[5].second );
176
177 ASSERT_THROW( PDIndex( comm , partition_spans ) , std::runtime_error );
178 }
179 }
180
181 //----------------------------------------------------------------------
182
183 void UnitTestSTKParallelDistributedIndex::test_update()
184 {
185 typedef stk::parallel::DistributedIndex PDIndex ;
186
187 stk::ParallelMachine comm = MPI_COMM_WORLD ;
188
189 int mpi_rank = stk::parallel_machine_rank(comm);
190 int mpi_size = stk::parallel_machine_size(comm);
191
192 PDIndex::KeySpanVector partition_spans ;
193
194 generate_test_spans_10x10000( partition_spans );
195
196 PDIndex di( comm , partition_spans );
197
198 PDIndex::KeyTypeVector keys_to_add ;
199 PDIndex::KeyTypeVector keys_to_remove ;
200 PDIndex::KeyProcVector sharing_of_local_keys ;
201
202 //------------------------------
203 // Update nothing:
204
205 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
206
207 EXPECT_TRUE( di.m_key_usage.empty() );
208
209 //------------------------------
210 // Update one key on all processes and
211 // one key unique to each process.
212
213 keys_to_add.push_back( partition_spans[0].first + 1 );
214 keys_to_add.push_back( partition_spans[1].first + 2 + mpi_rank );
215
216 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
217
218 di.query( sharing_of_local_keys );
219
220 // First key shared by all processes
221 // Second key shared just by this process
222 EXPECT_EQ( sharing_of_local_keys.size() , size_t(mpi_size + 1) );
223
224 di.query( keys_to_add , sharing_of_local_keys );
225
226 EXPECT_EQ( sharing_of_local_keys.size() , size_t(mpi_size + 1) );
227
228 //------------------------------
229 // Repeat the update, should result in no changes.
230
231 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
232
233 di.query( sharing_of_local_keys );
234
235 // First key shared by all processes
236 // Second key shared just by this process
237 EXPECT_EQ( sharing_of_local_keys.size() , size_t(mpi_size + 1) );
238
239 //------------------------------
240
241 keys_to_remove.clear();
242 keys_to_add.clear();
243
244 keys_to_remove.push_back( partition_spans[0].second );
245
246 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
247
248 di.query( sharing_of_local_keys );
249
250 EXPECT_EQ( sharing_of_local_keys.size() , size_t(mpi_size + 1) );
251
252 //------------------------------
253 // Remove shared key
254
255 keys_to_remove.clear();
256 keys_to_add.clear();
257
258 keys_to_remove.push_back( partition_spans[0].first + 1 );
259
260 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
261
262 di.query( sharing_of_local_keys );
263
264 EXPECT_EQ( sharing_of_local_keys.size() , size_t(1) );
265
266 //------------------------------
267 // Add two shared-by-all
268
269 keys_to_remove.clear();
270 keys_to_add.clear();
271
272 keys_to_add.push_back( partition_spans[0].first + 1 );
273 keys_to_add.push_back( partition_spans[0].first + 2 );
274
275 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
276
277 di.query( sharing_of_local_keys );
278
279 EXPECT_EQ( sharing_of_local_keys.size() , size_t(2*mpi_size + 1) );
280
281 di.query( keys_to_add , sharing_of_local_keys );
282
283 EXPECT_EQ( sharing_of_local_keys.size() , size_t(2*mpi_size) );
284
285 //------------------------------
286
287 keys_to_remove.clear();
288 keys_to_add.clear();
289
290 // Shared by even rank processes:
291 if ( 0 == mpi_rank % 2 ) {
292 keys_to_add.push_back( partition_spans[2].first );
293 }
294
295 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
296
297 di.query( sharing_of_local_keys );
298
299 {
300 size_t expected = 2 * mpi_size + 1 ;
301 if ( 0 == mpi_rank % 2 ) { expected += ( mpi_size + 1 ) / 2 ; }
302 EXPECT_EQ( sharing_of_local_keys.size() , expected );
303 }
304
305 }
306
307 //----------------------------------------------------------------------
308
309 void UnitTestSTKParallelDistributedIndex::test_update_bad()
310 {
311 typedef stk::parallel::DistributedIndex PDIndex ;
312
313 stk::ParallelMachine comm = MPI_COMM_WORLD ;
314
315 int mpi_rank = stk::parallel_machine_rank(comm);
316 int mpi_size = stk::parallel_machine_size(comm);
317
318 PDIndex::KeySpanVector partition_spans ;
319
320 generate_test_spans_10x10000( partition_spans );
321
322 PDIndex di( comm , partition_spans );
323
324 PDIndex::KeyTypeVector keys_to_add ;
325 PDIndex::KeyTypeVector keys_to_remove ;
326 PDIndex::KeyProcVector sharing_of_local_keys ;
327
328 //------------------------------
329 // Invalid key on every process
330
331 keys_to_add.push_back( partition_spans[0].second + 1 + mpi_rank );
332
333 ASSERT_THROW( di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() ), std::runtime_error );
334
335 //------------------------------
336
337 keys_to_add.clear();
338 if ( mpi_size == mpi_rank + 1 ) {
339 keys_to_add.push_back( partition_spans[0].second + 1 );
340 }
341
342 ASSERT_THROW( di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() ), std::runtime_error );
343 }
344
345 //----------------------------------------------------------------------
346
347 void UnitTestSTKParallelDistributedIndex::test_generate()
348 {
349 typedef stk::parallel::DistributedIndex PDIndex ;
350
351 stk::ParallelMachine comm = MPI_COMM_WORLD ;
352
353 int mpi_rank = stk::parallel_machine_rank(comm);
354 // int mpi_size = stk::parallel_machine_size(comm);
355
356 PDIndex::KeySpanVector partition_spans ;
357
358 generate_test_spans_10x10000( partition_spans );
359
360 PDIndex di( comm , partition_spans );
361
362 std::vector<size_t> requests( partition_spans.size() , 0u );
363 std::vector< PDIndex::KeyTypeVector > generated_keys ;
364 PDIndex::KeyProcVector sharing_of_local_keys ;
365
366 di.generate_new_keys( requests , generated_keys );
367
368 EXPECT_TRUE( di.m_key_usage.empty() );
369
370 ASSERT_EQ( generated_keys.size() , partition_spans.size() );
371
372 for ( size_t i = 0 ; i < generated_keys.size() ; ++i ) {
373 EXPECT_TRUE( generated_keys[i].empty() );
374 }
375
376 //----------------------------------------
377
378 size_t total = 0 ;
379 for ( size_t i = 0 ; i < requests.size() ; ++i ) {
380 requests[i] = i + mpi_rank ;
381 total += requests[i] ;
382 }
383
384 di.generate_new_keys( requests , generated_keys );
385
386 ASSERT_EQ( generated_keys.size() , partition_spans.size() );
387
388 for ( size_t i = 0 ; i < generated_keys.size() ; ++i ) {
389 EXPECT_EQ( generated_keys[i].size() , requests[i] );
390 for ( size_t j = 0 ; j < generated_keys[i].size() ; ++j ) {
391 EXPECT_TRUE( partition_spans[i].first <= generated_keys[i][j] );
392 EXPECT_TRUE( generated_keys[i][j] <= partition_spans[i].second );
393 if ( 0 < j ) {
394 EXPECT_TRUE( generated_keys[i][j-1] < generated_keys[i][j] );
395 }
396 }
397 }
398
399 //----------------------------------------
400
401 di.query( sharing_of_local_keys );
402
403 EXPECT_EQ( sharing_of_local_keys.size() , total );
404
405 // Confirm global uniqueness
406
407 for ( size_t i = 0 ; i < generated_keys.size() ; ++i ) {
408 di.query( generated_keys[i] , sharing_of_local_keys );
409 EXPECT_EQ( generated_keys[i].size() , sharing_of_local_keys.size() );
410 for ( size_t j = 0 ; j < sharing_of_local_keys.size() ; ++j ) {
411 EXPECT_EQ( sharing_of_local_keys[j].second , mpi_rank );
412 }
413 }
414
415 //----------------------------------------
416 // Double the number of keys
417
418 di.generate_new_keys( requests , generated_keys );
419
420 ASSERT_EQ( generated_keys.size() , partition_spans.size() );
421
422 for ( size_t i = 0 ; i < generated_keys.size() ; ++i ) {
423 EXPECT_EQ( generated_keys[i].size() , requests[i] );
424 for ( size_t j = 0 ; j < generated_keys[i].size() ; ++j ) {
425 EXPECT_TRUE( partition_spans[i].first <= generated_keys[i][j] );
426 EXPECT_TRUE( generated_keys[i][j] <= partition_spans[i].second );
427 if ( 0 < j ) {
428 EXPECT_TRUE( generated_keys[i][j-1] < generated_keys[i][j] );
429 }
430 }
431 }
432
433 di.query( sharing_of_local_keys );
434
435 EXPECT_EQ( sharing_of_local_keys.size() , total * 2 );
436 }
437
438 //----------------------------------------------------------------------
439
440 void UnitTestSTKParallelDistributedIndex::test_update_generate()
441 {
442 typedef stk::parallel::DistributedIndex PDIndex ;
443
444 stk::ParallelMachine comm = MPI_COMM_WORLD ;
445
446 int p_rank = stk::parallel_machine_rank(comm);
447 int p_size = stk::parallel_machine_size(comm);
448
449 PDIndex::KeySpanVector partition_spans ;
450
451 generate_test_spans_10x10000( partition_spans );
452
453 PDIndex di( comm , partition_spans );
454
455 std::vector<size_t> requests( partition_spans.size() , 0u );
456 std::vector< PDIndex::KeyTypeVector > generated_keys ;
457 PDIndex::KeyProcVector sharing_of_local_keys ;
458
459 PDIndex::KeyTypeVector keys_to_add ;
460 PDIndex::KeyTypeVector keys_to_remove ;
461
462 //------------------------------
463 // Add ( 5 * j ) odd keys per process
464 // starting at the beginning of the partition.
465
466 const size_t old_size_multiplier = 5 ;
467
468 for ( size_t j = 0 ; j < partition_spans.size() ; ++j ) {
469 PDIndex::KeyType key_first = partition_spans[j].first ;
470 if ( 0 == key_first % 2 ) { ++key_first ; } // Make it odd
471 key_first += old_size_multiplier * p_rank ;
472
473 const size_t n = old_size_multiplier * j ;
474 for ( size_t i = 0 ; i < n ; ++i ) {
475 PDIndex::KeyType key = key_first + 2 * i ;
476 keys_to_add.push_back( key );
477 }
478 }
479
480 di.update_keys( keys_to_add.begin(), keys_to_add.end() , keys_to_remove.begin(), keys_to_remove.end() );
481
482 //------------------------------
483 // Request 20 new keys per process per span
484 // The maximum new key will be larger than some spans
485 // and within the gaps of other spans.
486
487 const size_t gen_count = 20 ;
488 for ( size_t i = 0 ; i < requests.size() ; ++i ) {
489 if ( i % 2 ) {
490 requests[i] = gen_count ;
491 }
492 else {
493 requests[i] = 0 ;
494 }
495 }
496
497 di.generate_new_keys( requests , generated_keys );
498
499 for ( size_t i = 0 ; i < requests.size() ; ++i ) {
500 EXPECT_EQ( requests[i] , generated_keys[i].size() );
501
502 const size_t old_count = p_size * old_size_multiplier * i ;
503 const size_t tot_request = p_size * requests[i] ;
504
505 PDIndex::KeyType max_gen_key = partition_spans[i].first ;
506
507 if ( 0 == tot_request ) {
508 EXPECT_TRUE( generated_keys[i].size() == 0 );
509 }
510 else if ( tot_request < old_count ) {
511 // Will only fill in gaps between odd keys
512 max_gen_key += 2 * old_count ;
513
514 EXPECT_TRUE( max_gen_key > generated_keys[i][ requests[i] - 1 ] );
515 }
516 else {
517 // Will fill in gaps contiguously after the old max key
518 max_gen_key += old_count + tot_request - 1 ;
519
520 EXPECT_TRUE( max_gen_key >= generated_keys[i][ requests[i] - 1 ] );
521 }
522
523 // Sorted
524 for ( size_t j = 0 ; j < generated_keys[i].size() ; ++j ) {
525 if ( 0 < j ) {
526 EXPECT_TRUE( generated_keys[i][j-1] < generated_keys[i][j] );
527 }
528 }
529 }
530 }
531
532 //----------------------------------------------------------------------
533
534 void UnitTestSTKParallelDistributedIndex::test_generate_bad()
535 {
536 typedef stk::parallel::DistributedIndex PDIndex ;
537
538 stk::ParallelMachine comm = MPI_COMM_WORLD ;
539
540 int mpi_rank = stk::parallel_machine_rank(comm);
541 int mpi_size = stk::parallel_machine_size(comm);
542
543 PDIndex::KeySpanVector partition_spans ;
544
545 generate_test_spans_10x10000( partition_spans );
546
547 PDIndex di( comm , partition_spans );
548
549 std::vector<size_t> requests( partition_spans.size() , 0u );
550 std::vector< PDIndex::KeyTypeVector > generated_keys ;
551 //------------------------------
552
553 for ( size_t i = 0 ; i < requests.size() ; ++i ) {
554 requests[i] = 10 ;
555 }
556
557 if( mpi_rank == mpi_size -1 ) {
558 requests.clear();
559 }
560
561 ASSERT_THROW( di.generate_new_keys( requests , generated_keys ), std::runtime_error );
562
563 if( mpi_rank == mpi_size -1 ) {
564 requests.push_back(2*(partition_spans[0].second - partition_spans[0].first));
565 }
566
567 ASSERT_THROW( di.generate_new_keys( requests , generated_keys ), std::runtime_error );
568
569 for ( size_t i = 0 ; i < requests.size() ; ++i ) {
570 requests[i] = partition_spans[i].second - partition_spans[i].first ;
571 }
572
573 ASSERT_THROW( di.generate_new_keys( requests , generated_keys ), std::runtime_error );
574
575 }
576
577 //----------------------------------------------------------------------
578
579 void UnitTestSTKParallelDistributedIndex::test_generate_big()
580 {
581 typedef stk::parallel::DistributedIndex PDIndex ;
582
583 stk::ParallelMachine comm = MPI_COMM_WORLD ;
584
585 const int mpi_rank = stk::parallel_machine_rank(comm);
586 const int mpi_size = stk::parallel_machine_size(comm);
587
588 PDIndex::KeySpanVector partition_spans ;
589
590 generate_test_spans_10x10000( partition_spans );
591
592 PDIndex di( comm , partition_spans );
593
594 std::vector<size_t> requests( partition_spans.size() , 0u );
595
596 std::vector< PDIndex::KeyTypeVector > generated_keys ;
597
598 //----------------------------------------
599
600 if ( mpi_rank == mpi_size - 1 ) {
601 requests[5] = 5000 ; // Half
602 }
603 else {
604 requests[5] = 0 ;
605 }
606
607 di.generate_new_keys( requests , generated_keys );
608
609 ASSERT_EQ( generated_keys.size() , partition_spans.size() );
610
611 for ( size_t i = 0 ; i < generated_keys.size() ; ++i ) {
612 EXPECT_EQ( generated_keys[i].size() , requests[i] );
613 }
614
615 //----------------------------------------
616
617 if ( mpi_rank == mpi_size - 1 ) {
618 requests[5] = 4999 ; // Almost half again
619 }
620 else {
621 requests[5] = 0 ;
622 }
623
624 di.generate_new_keys( requests , generated_keys );
625
626 ASSERT_EQ( generated_keys.size() , partition_spans.size() );
627
628 for ( size_t i = 0 ; i < generated_keys.size() ; ++i ) {
629 EXPECT_EQ( generated_keys[i].size() , requests[i] );
630 }
631
632 //----------------------------------------
633 // This should request generation of one too many keys.
634
635 if ( mpi_rank == 0 ) {
636 requests[5] = 2 ; // Exceed the total
637 }
638 else {
639 requests[5] = 0 ;
640 }
641
642 ASSERT_THROW( di.generate_new_keys( requests , generated_keys ) , std::runtime_error );
643
644 }
645
646
647
648
649