Zoltan2
Loading...
Searching...
No Matches
Zoltan2_Directory_Impl.hpp
Go to the documentation of this file.
1/*
2 * @HEADER
3 *
4 * ***********************************************************************
5 *
6 * Zoltan2 Directory for Load-balancing, Partitioning, Ordering and Coloring
7 * Copyright 2012 Sandia Corporation
8 *
9 * Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
10 * the U.S. Government retains certain rights in this software.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions are
14 * met:
15 *
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * 2. Redistributions in binary form must reproduce the above copyright
20 * notice, this list of conditions and the following disclaimer in the
21 * documentation and/or other materials provided with the distribution.
22 *
23 * 3. Neither the name of the Corporation nor the names of theremove_local
24 * contributors may be used to endorse or promote products derived from
25 * this software without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
28 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
30 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
31 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
32 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
33 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
34 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
35 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
36 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
37 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 *
39 * Questions? Contact Karen Devine kddevin@sandia.gov
40 * Erik Boman egboman@sandia.gov
41 *
42 * ***********************************************************************
43 *
44 * @HEADER
45 */
46
47#ifndef ZOLTAN2_DIRECTORY_IMPL_H_
48#define ZOLTAN2_DIRECTORY_IMPL_H_
49
50#include "Zoltan2_Directory.hpp"
52
53namespace Zoltan2 {
54
55// These macros were rolled over from the original zoltan code. I've preserved
56// them for now until we have further discussion on how we want debug levels
57// and logging to work in the new code. This should just be debug related and
58// not impact the behavior of the code.
59#define ZOLTAN2_PRINT_INFO(proc,yo,str) \
60 printf("ZOLTAN2 (Processor %d) %s: %s\n", (proc), (yo), \
61 ((str) != NULL ? (char *)(str) : " "));
62
63#define ZOLTAN2_TRACE(proc,where,yo,str) \
64 printf("ZOLTAN (Processor %d) %s %s %s\n", (proc), (where), (yo), \
65 ((str) != NULL ? (char *)(str) : " "));
66
67#define ZOLTAN2_TRACE_IN(proc,yo,str) \
68 ZOLTAN2_TRACE((proc),"Entering",(yo),(str));
69
70#define ZOLTAN2_TRACE_OUT(proc,yo,str) \
71 ZOLTAN2_TRACE((proc),"Exiting",(yo),(str));
72
73// Tags for MPI communications. These need unique values. Arbitrary
74// These were rolled over from the original zoltan code and still used.
75#define ZOLTAN2_DD_FIND_MSG_TAG 29137 /* needs 3 consecutive values */
76#define ZOLTAN2_DD_UPDATE_MSG_TAG 29140 /* needs 2 consecutive values */
77#define ZOLTAN2_DD_REMOVE_MSG_TAG 29142 /* needs 2 consecutive values */
78#define ZOLTAN2_DD_RESIZE_MSG_TAG 29150 /* */
79
80template <typename gid_t,typename lid_t,typename user_t>
82{
83 const char * yo = "Zoltan2_Directory::allocate";
84
85 if (debug_level > 4) {
86 ZOLTAN2_TRACE_IN (comm->getRank(), yo, NULL);
87 }
88
89 /* insure all processors are using the same GID, LID, USER lengths */
90 size_t array[3], max_array[3], min_array[3];
91 array[0] = sizeof(lid_t);
92 array[1] = sizeof(gid_t);
93 array[2] = sizeof(user_t);
94 Teuchos::reduceAll<int,size_t>(
95 *comm, Teuchos::REDUCE_MAX, 3, array, max_array);
96 Teuchos::reduceAll<int,size_t>(
97 *comm, Teuchos::REDUCE_MIN, 3, array, min_array);
98 if (max_array[0] != min_array[0] || max_array[1] != min_array[1]
99 || max_array[2] != min_array[2]) {
100 throw std::invalid_argument(
101 "Zoltan2_Directory() LID, GID, USER data lengths differ globally");
102 }
103
104 // get the base size of the user data component
105 // for simple mode, this is going to just be the sizeof(user_t)
106 // for vector mode, this is sizeof(size_t) for the std::vector length
107 // the actual data will be variable
108 size_t user_base_size = is_Zoltan2_Directory_Vector() ? sizeof(size_t) :
109 size_of_value_type();
110
111 // set up the base size to include the gid and the lid (if used) + user size
112 size_t size = sizeof(gid_t) + (use_lid?sizeof(lid_t):0) + user_base_size;
113
114 // now calculate the full update msg size
115 update_msg_size = size + sizeof(Zoltan2_DD_Update_Msg<gid_t,lid_t>);
116
117 // for remove message we just need the gid, not any other info
118 size = sizeof(gid_t);
119 remove_msg_size = size + sizeof(Zoltan2_DD_Remove_Msg<gid_t,lid_t>);
120
121 // Current form of find_local is passed so gid_t is the input and
122 // lid_t is the output so this guarantees that ptr is sufficient to
123 // cover both (uses the max). This handling is consistent with the original
124 // zoltan code but I initially found it very confusing.
125 // I suggest searching for all of the places where max_id_size is used and
126 // that represents the relevant code. This may be the most optimal way of
127 // doing this. I did not get to assessing it in detail.
128 //
129 // NOTE: To really test this thoroughly we would want to play around with
130 // the values GID_SET_LENGTH and LID_SET_LENGTH in the directoryTest_Impl.hpp
131 // setup. I made sure this works for gid larger than lid and the opposite.
132 // Probably should extend the unit tests to cover all these cases at once as
133 // originally I had some bugs where this would work fine except when lid
134 // size was greater than gid size. Now this all should be ok.
135 max_id_size = std::max(sizeof(gid_t),sizeof(lid_t));
136
137 size = max_id_size + user_base_size;
138 find_msg_size = size + sizeof(Zoltan2_DD_Find_Msg<gid_t,lid_t>);
139
140 // TODO: Alignment is currently off for all of the modes for performance
141 // comparisons. I was not sure yet the implications of this and how it would
142 // best integrate if we have variable length user data
143/*
144 update_msg_size = align_size_t(update_msg_size);
145 remove_msg_size = align_size_t(remove_msg_size);
146 find_msg_size = align_size_t(find_msg_size);
147*/
148
149 if (debug_level > 4) {
150 ZOLTAN2_TRACE_OUT (comm->getRank(), yo, NULL);
151 }
152}
153
154// Copy Block
155template <typename gid_t,typename lid_t,typename user_t>
157 const Zoltan2_Directory<gid_t,lid_t,user_t> & src) {
158 node_map = src.node_map;
159 return 0;
160}
161
162template <typename gid_t,typename lid_t,typename user_t>
164 size_t count, const gid_t * gid, const lid_t * lid,
165 const user_t * user, const int * partition,
166 Update_Mode update_mode)
167{
168 // for conveniece store but maybe this should be a construct property
169 // should a directory allow mixed modes (Replace, then Aggregate... for ex)
170 this->mode = update_mode;
171
172 const char * yo = "Zoltan2_Directory::update";
173
174 if (debug_level > 4) {
175 ZOLTAN2_TRACE_IN(comm->getRank(), yo, NULL);
176 }
177
178 // part of initializing the error checking process
179 // for each linked list head, walk its list resetting errcheck
180 if(debug_level) {
181 for(size_t n = 0; n < node_map.size(); ++n) {
182 node_map.value_at(n).errcheck = -1; // not possible processor
183 }
184 }
185
186 if (debug_level > 6) {
187 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After reset errcheck");
188 }
189
190 int err = 0;
191
192 // allocate memory for list of processors to contact
193 Teuchos::ArrayRCP<int> procs;
194 if(count > 0) {
195 procs = Teuchos::arcp(new int[count], 0, count, true);
196 }
197
198 // set up the msg sizes for vector mode only
199 Teuchos::ArrayRCP<int> msg_sizes;
200 int sum_msg_size = 0;
201 if(is_Zoltan2_Directory_Vector() && count > 0) {
202 msg_sizes = Teuchos::arcp(new int[count], 0, count, true);
203 for (size_t i = 0; i < count; i++) {
204 size_t msg_size = get_update_msg_size(user[i]);
205 sum_msg_size += msg_size;
206 msg_sizes[i] = msg_size;
207 }
208 }
209 else {
210 sum_msg_size = update_msg_size * count; // simple case
211 }
212
213 Teuchos::ArrayRCP<char> sbuff;
214 if(sum_msg_size) {
215 sbuff = Teuchos::arcp(new char[sum_msg_size], 0, sum_msg_size, true);
216 }
217
218 typedef Zoltan2_DD_Update_Msg<gid_t,lid_t> msg_t;
219
220 // build update messages
221 int track_offset = 0;
222 char * trackptr = sbuff.getRawPtr();
223 for (size_t i = 0; i < count; i++) {
224 // hash the gid to determine which proc will own it
225 procs[i] = hash_proc(gid[i]);
226
227 // this ptr is the beginning of the message which can be different
228 // lengths for different gids if using Zoltan2_Directory_Vector
229 msg_t *ptr = reinterpret_cast<msg_t*>(trackptr);
230
231 // write in all my info
232 ptr->lid_flag = lid ? 1 : 0;
233 ptr->user_flag = user ? 1 : 0;
234 ptr->partition_flag = partition ? 1 : 0;
235 ptr->partition = partition ? partition[i] : -1;
236 ptr->owner = comm->getRank();
237
238 // now deal with the gid
239 gid_t * pgid = ptr->adjData;
240 *pgid = gid[i];
241
242 // optionally write the lid if we are using that
243 if(use_lid) {
244 if(!lid) {
245 throw std::logic_error(
246 "Did not pass lid values but directory was created to use them!");
247 }
248 lid_t * plid = reinterpret_cast<lid_t*>(ptr->adjData + 1);
249 *plid = lid[i];
250 }
251 else {
252 if(lid) {
253 throw std::logic_error(
254 "Passed lid values but directory was created not to use them!");
255 }
256 }
257
258 // find the spot where the user data begins
259 user_t * puser = reinterpret_cast<user_t*>(
260 reinterpret_cast<char*>(ptr->adjData) + sizeof(gid_t) +
261 (use_lid?sizeof(lid_t):0));
262
263 // write in the user data - for Zoltan2_Directory_Simple this is a trival
264 // copy but for Zoltan2_Directory_Vector we write length and then write all
265 // of the elements in the vector.
266 if (user) {
267 user_to_raw(user[i], puser);
268 }
269 else {
270 // The update msg contains space for the vector length (sizeof(size_t))
271 // if it's a Zoltan2_Directory_Vector
272 *puser = user_t(); // create an empty result
273 }
274
275 // vector will have different lengths but the simple mode will have all
276 // lengths just update_msg_size
277 size_t new_update_msg_size =
278 is_Zoltan2_Directory_Vector() ? msg_sizes[i] : update_msg_size;
279 track_offset += new_update_msg_size;
280 trackptr += new_update_msg_size;
281 }
282
283 // this check just makes sure our internal logic above is correct
284 // we should have looped to total size sum_msg_size
285 if(track_offset != sum_msg_size) {
286 throw std::logic_error("Bad summing!");
287 }
288
289 if (debug_level > 6) {
290 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After fill contact list");
291 }
292
293 // now create efficient communication plan
294
295 // Kokkos mode uses the new refactored C++ communicator class
296 Zoltan2_Directory_Comm directoryComm(count, procs, comm,
298 int nrec = directoryComm.getNRec();
299
300 if (err) {
301 throw std::logic_error("Zoltan2_Directory::update() Comm_Create error");
302 }
303
304 if (debug_level > 6) {
305 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After Comm_Create");
306 }
307
308 int sum_recv_sizes = 0;
309 if(is_Zoltan2_Directory_Vector()) {
310 // Only vector mode has to use the resizing options for getting receive info
311 err = directoryComm.resize(msg_sizes,
312 ZOLTAN2_DD_RESIZE_MSG_TAG, &sum_recv_sizes);
313 }
314 else {
315 sum_recv_sizes = update_msg_size * nrec;
316 }
317
318 if (err) {
319 throw std::logic_error("directoryComm.execute_resize error");
320 }
321
322 // If dd has no nodes allocated (e.g., first call to DD_Update;
323 // create the nodelist and freelist
324
325 // TODO upgrade nrec as size_t and all corresponding changes...
326 if(nrec && static_cast<int>(node_map.size()) < nrec) {
327 // some things to consider here if we will have multiple update calls in
328 // series... how will subsequent calls optimally manage this list since the
329 // new gid set may be partially overlapped with the original. Currently the
330 // update_local has a mechanism to rehash and increase this size if we run
331 // out so skipping this call would be logically ok (but not best performance)
332 rehash_node_map(nrec);
333 }
334
335 // allocate receive buffer for nrec DD_Update_Msg structures
336 Teuchos::ArrayRCP<char> rbuff;
337 if(sum_recv_sizes > 0) {
338 rbuff = Teuchos::arcp(
339 new char[sum_recv_sizes], 0, sum_recv_sizes, true); // receive buffer
340 }
341
342 // send my update messages & receive updates directed to me
343 //if resizing we send size 1 because the sizes will be built individually
344 const int nbytes = is_Zoltan2_Directory_Vector() ? 1 : update_msg_size;
345
346 err = directoryComm.do_forward(ZOLTAN2_DD_UPDATE_MSG_TAG+1,
347 sbuff, nbytes, rbuff);
348
349 if (err) {
350 throw std::logic_error("Zoltan2_Directory::update() Comm_Do error");
351 }
352
353 if (debug_level > 6) {
354 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After Comm_Do");
355 }
356
357 int errcount = 0;
358
359 // for each message rec'd, update local directory information
360 track_offset = 0;
361 trackptr = rbuff.getRawPtr();
362 for (int i = 0; i < nrec; i++) {
363 msg_t *ptr = reinterpret_cast<msg_t*>(trackptr);
364
365 user_t * puser = (ptr->user_flag) ?
366 (user_t*)(reinterpret_cast<char*>(ptr->adjData) +
367 sizeof(gid_t) + (use_lid?sizeof(lid_t):0)) : NULL;
368
369 err = update_local(ptr->adjData,
370 (ptr->lid_flag) ? reinterpret_cast<lid_t*>(ptr->adjData + 1) : NULL,
371 puser,
372 (ptr->partition_flag) ? (ptr->partition) : -1, // illegal partition
373 ptr->owner);
374
375 if (err)
376 ++errcount;
377
378 // in this case we are reading the raw data so we calculate the message
379 // size from it. For vector mode, this will find the length of the vector
380 // and calculate the full message size from that.
381 size_t delta_msg_size = get_update_msg_size(puser);
382 trackptr += delta_msg_size;
383 track_offset += delta_msg_size;
384 }
385
386 // safety check - if all this internal logic is correct the ptr offset should
387 // not be exactly at the end of the recv buffer.
388 if(track_offset != sum_recv_sizes) {
389 throw std::logic_error("Did not sum!");
390 }
391
392 if (debug_level > 6) {
393 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After Local update");
394 }
395
396 err = 0;
397
398 if (debug_level) { // overwrite error return if extra checking is on
399 err = (errcount) ? 1 : 0;
400 }
401
402 if (debug_level) {
403 char str[100]; // used to build message string
404 sprintf (str, "Processed %lu GIDs (%d local), %d GID errors", count,
405 directoryComm.getNRec(),
406 errcount);
407 ZOLTAN2_PRINT_INFO (comm->getRank(), yo, str);
408 }
409
410 if (debug_level > 4) {
411 ZOLTAN2_TRACE_OUT(comm->getRank(), yo, NULL);
412 }
413
414 return err;
415}
416
417template <typename gid_t,typename lid_t,typename user_t>
419 gid_t* gid, /* GID to update (in) */
420 lid_t* lid, /* gid's LID (in), NULL if not needed */
421 user_t *user, /* gid's user data (in), NULL if not needed */
422 int partition, /* gid's partition (in), -1 if not used */
423 int owner) /* gid's current owner (proc number) (in) */
424{
425 const char * yo = "Zoltan2_Directory::update_local";
426
427 // input sanity checking
428 if (owner < 0) {
429 throw std::logic_error(
430 "Zoltan2_Directory::update_local() owner < 0");
431 }
432 if (owner >= comm->getSize()) {
433 throw std::logic_error(
434 "Zoltan2_Directory::update_local() owner >= comm->getSize()");
435 }
436 if (gid == NULL) {
437 throw std::logic_error(
438 "Zoltan2_Directory::update_local() gid == NULL");
439 }
440
441 if (debug_level > 5) {
442 ZOLTAN2_TRACE_IN (comm->getRank(), yo, NULL);
443 }
444
445 // compute offset into hash table to find head of linked list
446 size_t node_index = node_map.find(*gid);
447 if(node_map.valid_at(node_index)) {
448 Zoltan2_Directory_Node<gid_t,lid_t,user_t> & node =
449 node_map.value_at(node_index);
450
451 // found match, update directory information
452 if (lid) {
453 node.lid = *lid;
454 }
455 if (user) {
456 update_local_user(user, node.userData);
457 }
458
459 node.owner = owner;
460 if (partition != -1) {
461 node.partition = partition;
462 }
463
464 // errcheck is reset to -1 at beginning of update for debug mode
465 // then it will get set to the provider of the data when the node is
466 // created or on the first call to be updated locally.
467 // So if errcheck -1, then we do nothing - it's the first action.
468 if(debug_level) {
469 // if node.errcheck is -1 we are detecting the first update to a node
470 // which already existed at the beginning of the update call so it's ok.
471 // if mode is not Replace then duplicate calls are ok (expected) since
472 // Add and Aggregate combine from many procs are the outcome is not
473 // order dependent.
474 if(node.errcheck != -1 && mode == Replace) {
475 // here we have detected two actions on a single node in the same
476 // update call for replace.
477 // The actions could have been: create node -> change node
478 // or if the node already existed: change node -> change node
479
480 // in Replace mode, two actions are potentially problematic.
481 // If two procs update the same gid with different data it will
482 // be order dependent.
483
484 // For performance testing it's convenient to allow
485 // Replace to be called from different procs but expect the data
486 // to always be identical. That means we can compare Replace and
487 // Aggregate more meaningfully since the gid setup for update is
488 // the same.
489
490 // To discuss - should one proc be allowed to submit duplicate
491 // gids in an update call using Replace mode. Should two different
492 // procs be allowed to submit duplicate gids with the same data
493 // for a replace call, in which case the outcome is determined
494 // regardless of order but we would be relying on the user to have
495 // accurate data submission. Then we might consider a debug check
496 // here to validate the data is coming in matches the local data.
497
498 // TODO: Probably add this throw in, but currently the testing
499 // framework will feed multiple Replace calls with the same data
500 // from different gids - so we would have to change the tests
501 // to guarantee Replace was a unique gid lists for each proc.
502 // That is easy to do but not ideal at the moment for performance
503 // testing reasons. I'd like the pattern of calls to be the same
504 // as Add and Aggregate as a reference.
505
506 // throw std::logic_error( "Two replace calls were detected on."
507 // " the same gid which can be an undefined results.");
508 }
509 }
510
511 node.errcheck = owner;
512
513 if (debug_level > 5) {
514 ZOLTAN2_TRACE_OUT (comm->getRank(), yo, NULL);
515 }
516
517 // TODO: Change logic flow to avoid this internal return
518 return 0; // ignore all errors
519 }
520
521 // gid not found.
522 // Create new Zoltan2_Directory_Node<gid_t,lid_t> and fill it in
523 Zoltan2_Directory_Node<gid_t,lid_t,user_t> node; // will add to hash at end
524 node.free = 0; // TODO - is this necessary - see notes in rehash_node_map
525 node.lid = lid ? (*lid) : lid_t();
526
527 // this is more or less doing what above relic commands did except for
528 // vector mode there is special handling to account for the variable length
529 // of the std::vector
530 if(user) {
531 raw_to_user(user, node.userData);
532 }
533 else {
534 node.userData = user_t();
535 }
536
537 node.partition = partition;
538 node.owner = owner;
539 node.errcheck = owner;
540
541 if(node_map.insert(*gid, node).failed()) {
542 // Need more nodes (that's the assumption here if we have failure)
543 // A new update has added more to our local list and we need more capacity.
544 // TODO: Decide most efficient scheme. Here we bump to at least 10 or if
545 // we're already at the level, increase by 10% increments. I think this will
546 // be less efficient for small scale problems, when we probably care less,
547 // but more efficient as we scale up.
548 size_t new_guess_size = (node_map.size() < 10) ? 10 :
549 ( node_map.size() + node_map.size()/10); // adds a minimum of 1
550 rehash_node_map(new_guess_size);
551 if(node_map.insert(*gid, node).failed()) {
552 throw std::logic_error("Hash insert failed. Mem sufficient?....");
553 }
554 }
555
556 if (debug_level > 6) {
557 ZOLTAN2_PRINT_INFO (comm->getRank(), yo, "Created new directory item");
558 }
559
560 if (debug_level > 5) {
561 ZOLTAN2_TRACE_OUT (comm->getRank(), yo, NULL);
562 }
563
564 return 0;
565}
566
567template <typename gid_t,typename lid_t,typename user_t>
569 size_t count,
570 const gid_t * gid, /* Incoming list of GIDs to get owners proc */
571 lid_t * lid, /* Outgoing corresponding list of LIDs */
572 user_t * user, /* Outgoing optional corresponding user data */
573 int * partition, /* Outgoing optional partition information */
574 int * owner, /* Outgoing optional list of data owners */
575 bool throw_if_missing) /* default true - throw if gid is not found. */
576{
577 const char * yo = "Zoltan2_Directory::find";
578
579 if (debug_level > 4) {
580 ZOLTAN2_TRACE_IN(comm->getRank(), yo, NULL);
581 }
582
583 int err = 0;
584
585 /* allocate memory for processors to contact for directory info */
586 Teuchos::ArrayRCP<int> procs;
587 if(count > 0) {
588 procs = Teuchos::arcp(
589 new int[count], 0, count, true); // processors to contact
590 }
591
592 /* Setup procs list */
593 for (size_t i = 0; i < count; i++) {
594 procs[i] = hash_proc(gid[i]); // determines the owner
595 }
596
597 // create efficient communication plan
598 Zoltan2_Directory_Comm directoryComm(count, procs, comm,
600 int nrec = directoryComm.getNRec();
601
602 if (debug_level > 6) {
603 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After Comm_Create");
604 }
605
606 if (err) {
607 throw std::logic_error("Zoltan2_Directory::find() error");
608 }
609
610 Teuchos::ArrayRCP<char> sbuff;
611 if(count > 0) {
612 sbuff = Teuchos::arcp(new char[find_msg_size*count],
613 0, find_msg_size*count, true); // send buffer
614 }
615
616 typedef Zoltan2_DD_Find_Msg<gid_t,lid_t> msg_t;
617
618 /* for each GID, fill DD_Find_Msg buffer and contact list */
619 char *trackptr = sbuff.getRawPtr();
620 for (size_t i = 0; i < count; i++) {
621 msg_t *ptr = reinterpret_cast<msg_t*>(trackptr);
622 ptr->index = i;
623 ptr->proc = procs[i];
624 *(ptr->adjData) = gid[i];
625 trackptr += find_msg_size;
626 }
627
628 if (debug_level > 6) {
629 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After fill");
630 }
631
632 if (err) {
633 throw std::logic_error("directoryComm.execute_resize error");
634 }
635
636 // allocate receive buffer
637 Teuchos::ArrayRCP<char> rbuff;
638 if(nrec > 0) {
639 rbuff = Teuchos::arcp(new char[nrec * find_msg_size],
640 0, nrec * find_msg_size, true);
641 }
642
643 const int nbytes = find_msg_size; // just getting length not full vector data
644
645 err = directoryComm.do_forward(ZOLTAN2_DD_FIND_MSG_TAG+1, sbuff,
646 nbytes, rbuff);
647
648 if (err) {
649 throw std::logic_error("Zoltan2_Directory::find() error");
650 }
651
652 if (debug_level > 6) {
653 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After Comm_Do");
654 }
655
656 // get find messages directed to me and determine total recv size
657 // and a list of individual sizes (rmsg_sizes_resized)
658 Teuchos::ArrayRCP<int> rmsg_sizes_resized;
659 if(nrec > 0) {
660 rmsg_sizes_resized = Teuchos::arcp(new int[nrec], 0, nrec, true);
661 }
662 Teuchos::ArrayRCP<int>::size_type sum_rmsg_sizes_resized = 0;
663
664 char *track_ptr = rbuff.getRawPtr();
665 for (int i = 0; i < nrec; i++) {
666 msg_t *msg = reinterpret_cast<msg_t*>(track_ptr);
667 track_ptr += find_msg_size;
668 size_t find_rmsg_size_resized = get_local_find_msg_size(msg->adjData,
669 throw_if_missing);
670 rmsg_sizes_resized[i] = find_rmsg_size_resized;
671 sum_rmsg_sizes_resized += find_rmsg_size_resized;
672 }
673
674 Teuchos::ArrayRCP<char>::size_type track_offset_resized = 0;
675
676 Teuchos::ArrayRCP<char> rbuff_resized_build;
677
678 if(is_Zoltan2_Directory_Vector()) {
679
680 if(sum_rmsg_sizes_resized > 0) {
681 rbuff_resized_build = Teuchos::arcp(new char[sum_rmsg_sizes_resized],
682 0, sum_rmsg_sizes_resized, true);
683 }
684
685 track_ptr = rbuff.getRawPtr();
686 char * track_ptr_resized = rbuff_resized_build.getRawPtr();
687 for (int i = 0; i < nrec; i++) {
688 memcpy(track_ptr_resized, track_ptr, find_msg_size);
689 track_ptr += find_msg_size;
690 track_ptr_resized += rmsg_sizes_resized[i];
691 }
692 }
693
694 // for performance, when not using variable sized we can optimize this step
695 // and use the original rbuff (there is no resizing to consider)
696 Teuchos::ArrayRCP<char> rbuff_resized = is_Zoltan2_Directory_Vector() ?
697 rbuff_resized_build : rbuff;
698
699 // Fill it with the true array data
700 track_offset_resized = 0; // for debugging
701 track_ptr = rbuff_resized.getRawPtr();
702 for (int i = 0; i < nrec; i++) {
703 typedef Zoltan2_DD_Find_Msg<gid_t,lid_t> find_msg_t;
704 find_msg_t *ptr = reinterpret_cast<find_msg_t*>(track_ptr);
705 user_t * puser = reinterpret_cast<user_t*>(
706 reinterpret_cast<char*>(ptr->adjData) + max_id_size);
707
708 // In original DD_Find_Local the first two values (gid and lid) are
709 // passed as the same, we send in gid and collect lid if it's used.
710 // that is why the find_msg_size is setup originally using max of
711 // sizeof(gid_t) and sizeof(lid_t)
712 err = find_local(ptr->adjData, (lid_t*)ptr->adjData,
713 puser, &ptr->partition, &ptr->proc, throw_if_missing);
714
715 const size_t & size_shift = rmsg_sizes_resized[i];
716 track_offset_resized += size_shift;
717 track_ptr += size_shift;
718 }
719
720 if(track_offset_resized != sum_rmsg_sizes_resized) {
721 throw std::logic_error("Bad sum!");
722 }
723
724 // This section is handled differently if it's variable sized array
725 size_t size_scale = is_Zoltan2_Directory_Vector() ? 1 : find_msg_size;
726
727 Teuchos::ArrayRCP<char> sbuff_resized;
728 if(!is_Zoltan2_Directory_Vector()) {
729 sbuff_resized = sbuff; // vector mode will set this and fill it
730 }
731
732 if(is_Zoltan2_Directory_Vector()) {
733 err = directoryComm.do_reverse(ZOLTAN2_DD_FIND_MSG_TAG+2,
734 rbuff_resized, size_scale, rmsg_sizes_resized, sbuff_resized);
735 }
736 else {
737 err = directoryComm.do_reverse(ZOLTAN2_DD_FIND_MSG_TAG+2,
738 rbuff_resized, size_scale, Teuchos::null, sbuff_resized);
739 }
740
741 if (err) {
742 throw std::logic_error("Zoltan2_Directory::find() do reverse failed");
743 }
744
745 if (debug_level > 6) {
746 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After Comm_Reverse");
747 }
748
749 // fill in user supplied lists with returned information
750 track_offset_resized = 0;
751
752 // it's not going to be in order... so don't use gid[i]
753 char * trackptr_resized = sbuff_resized.getRawPtr();
754 for (size_t i = 0; i < count; i++) {
755
756 if(track_offset_resized >= sbuff_resized.size()) {
757 printf(
758 "%d has gid.size() %d track_offset_resized: %d sbuff_resized: %d\n",
759 comm->getRank(),
760 (int) count, (int) track_offset_resized, (int) sbuff_resized.size());
761 throw std::logic_error("Bad buffer overflow! Internal error.");
762 }
763
764 msg_t *ptr = reinterpret_cast<msg_t*>(trackptr_resized);
765
766 if (owner)
767 owner[ptr->index] = ptr->proc;
768 if (partition)
769 partition[ptr->index] = ptr->partition ;
770 if (lid) {
771 memcpy (&lid[ptr->index], ptr->adjData, sizeof(lid_t));
772 }
773
774 user_t * pRead = reinterpret_cast<user_t*>(
775 reinterpret_cast<char*>(ptr->adjData) + max_id_size);
776
777 // if find_local failed proc is set to -1. Then we can leave the data
778 // untouched - the default behavior is to throw but the unit tests are
779 // set up to track and verify each remove id was properly taken out. To do
780 // this the test overrides with an optional flag on find() and says do not
781 // throw - and expects the data to remain untouched - then validates the
782 // data is not changed.
783 if(ptr->proc != -1 && user) {
784 raw_to_user(pRead, user[ptr->index]);
785 }
786
787 // don't use smsg_sizes_resized here because we don't get them back
788 // in the same order
789 size_t incoming_size = get_incoming_find_msg_size(ptr);
790 trackptr_resized += incoming_size;
791 track_offset_resized += incoming_size;
792 }
793
794 if(track_offset_resized != sbuff_resized.size()) {
795 throw std::logic_error("Bad buffer sum!");
796 }
797
798 if (debug_level > 6) {
799 ZOLTAN2_PRINT_INFO(comm->getRank(), yo, "After fill return lists");
800 }
801
802 int errcount = 0;
803 Teuchos::reduceAll<int>(*comm, Teuchos::REDUCE_SUM, 1, &errcount, &err);
804 err = (err) ? 1 : 0;
805
806 // if at least one GID was not found, potentially notify caller of error
807 if (debug_level > 0) {
808 char str[100]; /* diagnostic message string */
809 sprintf(str, "Processed %lu GIDs, GIDs not found: %d", count, errcount);
810 ZOLTAN2_PRINT_INFO (comm->getRank(), yo, str);
811 }
812
813 if (debug_level > 4) {
814 ZOLTAN2_TRACE_OUT(comm->getRank(), yo, NULL);
815 }
816
817 return err;
818}
819
820template <typename gid_t,typename lid_t,typename user_t>
822 gid_t* gid, /* incoming GID to locate (in) */
823 lid_t* lid, /* gid's LID (out) */
824 user_t *user, /* gid's user data (out) */
825 int *partition, /* gid's partition number (out) */
826 int *owner, /* gid's owner (processor number) (out) */
827 bool throw_if_missing) const
828{
829 const char * yo = "Zoltan2_Directory::find_local";
830
831 /* input sanity check */
832 if (owner == NULL || gid == NULL) {
833 throw std::logic_error("Zoltan2_Directory::find_local() Invalid input");
834 }
835
836 if (debug_level > 5) {
837 ZOLTAN2_TRACE_IN (comm->getRank(), yo, NULL);
838 }
839
840 /* compute offset into hash table to find head of linked list */
841 // Note performance is better if we first get index, then check valid_at,
842 // and use index to call value_at. Alternative is to call exists(*gid) and
843 // then node_map.value_at(node_map.find(*gid))) which is slower.
844 // TODO: Can this be optimized further?
845 size_t node_index = node_map.find(*gid);
846 if(node_map.valid_at(node_index))
847 {
848 const Zoltan2_Directory_Node<gid_t,lid_t,user_t> & node =
849 node_map.value_at(node_index);
850 /* matching global ID found! Return gid's information */
851 if(lid) {
852 *lid = node.lid;
853 }
854
855 if (user) {
856 user_to_raw(node.userData, user);
857 }
858
859 if (owner) *owner = node.owner;
860 if (partition) *partition = node.partition;
861
862 if (debug_level > 5) {
863 ZOLTAN2_TRACE_OUT (comm->getRank(), yo, NULL);
864 }
865 return 0; // success point
866 }
867
868 // failure point
869 if (owner != NULL)
870 *owner = -1; /* JDT Added -1 owner not found */
871
872 if (debug_level > 5) {
873 ZOLTAN2_TRACE_OUT (comm->getRank(), yo, NULL);
874 }
875
876 if(throw_if_missing) {
877 // TODO: This used to be linked to debug_level but wanted to discuss as it
878 // seems we would want an error always if this failed.
879 throw std::logic_error("find_local did not succeed");
880 }
881
882 return 0;
883}
884
885// Print block
886template <typename gid_t,typename lid_t,typename user_t>
888{
889 const char * yo = "Zoltan2_Directory::print";
890
891 if (debug_level > 4) {
892 ZOLTAN2_TRACE_IN (comm->getRank(), yo, NULL);
893 }
894
895 for (size_t i = 0; i < node_map.size(); i++) {
896 Zoltan2_Directory_Node<gid_t,lid_t,user_t> & node =
897 node_map.value_at(i);
898 printf ("ZOLTAN DD Print(%d): \tList, \tGID ", comm->getRank());
899 printf("(");
900 // the issue here is that gid could be a simple type (int/long) or it
901 // could be an arbitrary structure such as:
902 // struct some_type {
903 // int x[4];
904 // }
905 // Directory works for such arbitrary type but only knows sizeof,
906 // not details of the internal implementation. In the testing framework
907 // the length of above x array is stored so it can be printed.
908 // TODO: Decide how to handle this - if we want directory to be able to
909 // print nice output of the gid (and lid) then perhaps we need to require
910 // that such structs define a to_string() method.
911 printf( "TODO: Decide how to print gid of arbitrary type.");
912 printf(") ");
913 if (use_lid) {
914 printf("\tLID (");
915 // see above note on the gid and printing
916 printf( "TODO: Decide how to print lid of arbitrary type.");
917 printf(") ");
918 }
919 printf ("\tPart %d\n", node.partition);
920 printf ("\tOwner %d\n", node.owner);
921 }
922
923 if (debug_level > 4) {
924 ZOLTAN2_TRACE_OUT (comm->getRank(), yo, NULL);
925 }
926 return 0;
927}
928
929// Stats block
930template <typename gid_t,typename lid_t,typename user_t>
932{
933 const char *yo = "Zoltan2_Directory::stats";
934
935 if (debug_level > 4) {
936 ZOLTAN2_TRACE_IN (comm->getRank(), yo, NULL);
937 }
938
939 char str[100]; // used to build message string
940 // not much to do here for equivalent to stats
941 // TODO: Consider removing stats()
942 sprintf(str, "Kokkos unordered map %d nodes.", node_map.size());
943 ZOLTAN2_PRINT_INFO (comm->getRank(), yo, str);
944 if (debug_level > 4) {
945 ZOLTAN2_TRACE_OUT (comm->getRank(), yo, NULL);
946 }
947}
948
949template <typename gid_t,typename lid_t,typename user_t>
951 size_t count,
952 const gid_t * gid) /* Incoming list of GIDs to remove */
953{
954 const char * yo = "Zoltan2_Directory::remove";
955
956 if (debug_level > 4) {
957 ZOLTAN2_TRACE_IN (comm->getRank(), yo, NULL);
958 }
959
960 int err = 0;
961
962 // allocate memory for processor contact list
963 Teuchos::ArrayRCP<int> procs;
964 Teuchos::ArrayRCP<char> sbuff;
965 if(count > 0) {
966 procs = Teuchos::arcp( // list of processors to contact
967 new int[count], 0, count, true);
968 sbuff = Teuchos::arcp( // send buffer
969 new char[count*remove_msg_size], 0, count*remove_msg_size, true);
970 }
971
972 typedef Zoltan2_DD_Remove_Msg<gid_t,lid_t> msg_t;
973
974 // for each GID, fill in contact list and then message structure
975 char * trackptr = sbuff.getRawPtr();
976 for (size_t i = 0; i < count; i++) {
977 procs[i] = hash_proc(gid[i]);
978 msg_t *ptr = reinterpret_cast<msg_t*>(trackptr);
979 ptr->owner = comm->getRank();
980 *(ptr->adjData) = gid[i];
981 trackptr += remove_msg_size;
982 }
983
984 // now create efficient communication plan
985 Zoltan2_Directory_Comm directoryComm(count, procs, comm,
987 int nrec = directoryComm.getNRec();
988
989 if (err) {
990 throw std::logic_error("Zoltan_Comm_Create failed");
991 }
992
993 if (debug_level > 6) {
994 ZOLTAN2_PRINT_INFO (comm->getRank(), yo, "After Zoltan_Comm_Create");
995 }
996
997 // allocate receive buffer for nrec DD_Remove_Msg structures
998 Teuchos::ArrayRCP<char> rbuff;
999 if(nrec > 0) {
1000 rbuff = Teuchos::arcp(new char[nrec*remove_msg_size],
1001 0, nrec*remove_msg_size, true); // receive buffer
1002 }
1003
1004 // send my update messages & receive updates directed to me
1005 err = directoryComm.do_forward(ZOLTAN2_DD_UPDATE_MSG_TAG+1,
1006 sbuff, remove_msg_size, rbuff);
1007
1008 if (err) {
1009 throw std::logic_error("Comm_Do error");
1010 }
1011
1012 if (debug_level > 6) {
1013 ZOLTAN2_PRINT_INFO (comm->getRank(), yo, "After Zoltan_Comm_Do");
1014 }
1015
1016 /* for each message rec'd, remove local directory info */
1017 int errcount = 0;
1018
1019 // Note calling begin_erase() and end_erase() without actually erasing
1020 // something leads to confusing seg faults. Hence nrec>0 check.
1021 // Pulling begin_erase and end_erase out of the loop is important for
1022 // performance. Since the actual erase is fairly simple we may consider
1023 // eliminating remove_local and just calling here but will keep for now to
1024 // keep symmetry with other modes.
1025 if(nrec > 0) {
1026 node_map.begin_erase();
1027 for (int i = 0; i < nrec; i++) {
1028 msg_t *ptr = reinterpret_cast<msg_t*>(&(rbuff[i*remove_msg_size]));
1029 err = remove_local(ptr->adjData);
1030 if (err == 1) { // TODO eliminate warns (1) make all errors
1031 ++errcount;
1032 }
1033 }
1034 node_map.end_erase();
1035 } // if nrec > 0
1036
1037 err = 0;
1038
1039 if (debug_level) {
1040 char str[100]; // used to build message string
1041 sprintf (str, "Processed %zu GIDs (%d local), %d GIDs not found",
1042 count, nrec, errcount);
1043 ZOLTAN2_PRINT_INFO (comm->getRank(), yo, str);
1044 err = (errcount) ? 1 : 0;
1045 }
1046
1047 return err;
1048}
1049
1050template <typename gid_t,typename lid_t,typename user_t>
1052 gid_t* gid) /* GID to be removed (in) */
1053{
1054 const char * yo = "Zoltan2_Directory::remove_local";
1055
1056 /* input sanity checking */
1057 if (gid == NULL) {
1058 throw std::logic_error("Invalid input argument");
1059 }
1060
1061 if (debug_level > 5) {
1062 ZOLTAN2_TRACE_IN (comm->getRank(), yo, NULL);
1063 }
1064
1065 if(node_map.exists(*gid)) {
1066 node_map.erase(*gid);
1067 return 0;
1068 }
1069
1070 /* We get here only if the global ID has not been found */
1071 if (debug_level > 5) {
1072 ZOLTAN2_TRACE_OUT (comm->getRank(), yo, NULL);
1073 }
1074
1075 return 1;
1076}
1077
1078template <typename gid_t,typename lid_t,typename user_t>
1080 const gid_t & gid) const
1081{
1082 uint32_t k;
1083
1084 // Copied from murmurc.3
1085 // TODO: Will be removed as Kokkos form develops
1086 #define ZOLTAN2_ROTL32(x,r) (uint32_t) \
1087 (((uint32_t)(x) << (int8_t)(r)) | ((uint32_t)(x) >> (32 - (int8_t)(r))))
1088
1089 const void * key = (void *)(&gid);
1090 int len = sizeof(gid_t);
1091 uint32_t seed = 14;
1092 void * out = (void *)&k;
1093
1094 const uint8_t * data = (const uint8_t*)key;
1095 const int nblocks = len / 4;
1096 int i;
1097 uint32_t h1 = seed;
1098 uint32_t c1 = 0xcc9e2d51;
1099 uint32_t c2 = 0x1b873593;
1100 const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
1101 for(i = -nblocks; i; i++)
1102 {
1103 uint32_t k1 = blocks[i];
1104 k1 *= c1;
1105 k1 = ZOLTAN2_ROTL32(k1,15);
1106 k1 *= c2;
1107 h1 ^= k1;
1108 h1 = ZOLTAN2_ROTL32(h1,13);
1109 h1 = h1*5+0xe6546b64;
1110 }
1111 const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
1112 uint32_t k1 = 0;
1113 switch(len & 3)
1114 {
1115 case 3: k1 ^= tail[2] << 16;
1116 case 2: k1 ^= tail[1] << 8;
1117 case 1: k1 ^= tail[0];
1118 k1 *= c1; k1 = ZOLTAN2_ROTL32(k1,15); k1 *= c2; h1 ^= k1;
1119 };
1120 h1 ^= len;
1121 h1 ^= h1 >> 16;
1122 h1 *= 0x85ebca6b;
1123 h1 ^= h1 >> 13;
1124 h1 *= 0xc2b2ae35;
1125 h1 ^= h1 >> 16;
1126 *(uint32_t*)out = h1;
1127
1128 return(k % comm->getSize());
1129}
1130
1131
1132/* TODO: Currently disabled - I need to review the benefits of this and see if
1133 we need this in the new version. Also how do we best handle this for variable
1134 sized data. */
1135/*
1136template <typename gid_t,typename lid_t,typename user_t>
1137size_t Zoltan2_Directory<gid_t,lid_t,user_t>::align_size_t(size_t a) const
1138{
1139 #define ZOLTAN2_ALIGN_VAL 7U
1140 return((ZOLTAN2_ALIGN_VAL + a) & ~ZOLTAN2_ALIGN_VAL);
1141}
1142*/
1143
1144} // end namespace Zoltan2
1145
1146#endif // ZOLTAN2_DIRECTORY_IMPL_H_
Zoltan2::BasicUserTypes< zscalar_t, zlno_t, zgno_t > user_t
Definition Metric.cpp:74
#define ZOLTAN2_TRACE_IN(proc, yo, str)
#define ZOLTAN2_DD_FIND_MSG_TAG
#define ZOLTAN2_DD_RESIZE_MSG_TAG
#define ZOLTAN2_PRINT_INFO(proc, yo, str)
#define ZOLTAN2_DD_UPDATE_MSG_TAG
#define ZOLTAN2_TRACE_OUT(proc, yo, str)
#define ZOLTAN2_ROTL32(x, r)
Update_Mode
Update_Mode determines how update executes.
int update_local(gid_t *gid, lid_t *lid, user_t *user, int partition, int owner)
int print() const
gids to remove.
int remove(size_t length, const gid_t *gid)
if true will throw if a gid is not found. This is used by the unit tests to properly assess if remove...
int update(size_t length, const gid_t *gid, const lid_t *lid, const user_t *user, const int *partition, Update_Mode update_mode)
update is called by user to submit new data.
int copy(const Zoltan2_Directory< gid_t, lid_t, user_t > &dd)
int find_local(gid_t *gid, lid_t *lid, user_t *user, int *partition, int *owner, bool throw_if_missing=true) const
void stats() const
stats. New Kokkos mode needs further development.
unsigned int hash_proc(const gid_t &gid) const
int find(size_t length, const gid_t *gid, lid_t *lid, user_t *user, int *partition, int *owner, bool throw_if_missing=true)
Can be Replace, Add, or Aggregate.
Created by mbenlioglu on Aug 31, 2020.