Yet Another eXchange Tool 0.11.3
Loading...
Searching...
No Matches
xt_xmap_dist_dir_bucket_gen_cycl_stripe.c
Go to the documentation of this file.
1
15/*
16 * Keywords:
17 * Maintainer: Jörg Behrens <behrens@dkrz.de>
18 * Moritz Hanke <hanke@dkrz.de>
19 * Thomas Jahns <jahns@dkrz.de>
20 * URL: https://dkrz-sw.gitlab-pages.dkrz.de/yaxt/
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions are
24 * met:
25 *
26 * Redistributions of source code must retain the above copyright notice,
27 * this list of conditions and the following disclaimer.
28 *
29 * Redistributions in binary form must reproduce the above copyright
30 * notice, this list of conditions and the following disclaimer in the
31 * documentation and/or other materials provided with the distribution.
32 *
33 * Neither the name of the DKRZ GmbH nor the names of its contributors
34 * may be used to endorse or promote products derived from this software
35 * without specific prior written permission.
36 *
37 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
38 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
39 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
40 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
41 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
42 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
43 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
44 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
45 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
46 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
47 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
48 */
49#ifdef HAVE_CONFIG_H
50#include <config.h>
51#endif
52
53#include <string.h>
54#include <assert.h>
55
56#include <mpi.h>
57
61#include "xt_idxlist_internal.h"
63#include "xt_idxlist_unpack.h"
64#include "xt_config_internal.h"
65#include "core/ppm_xfuncs.h"
66#include "xt/xt_mpi.h"
67#include "xt_mpi_internal.h"
68#include "xt_arithmetic_util.h"
69#include "ensure_array_size.h"
71
72static int
74 void *gen_state_,
75 Xt_idxlist src_idxlist,
76 Xt_idxlist dst_idxlist,
77 Xt_config config,
78 struct Xt_xmdd_bucket_gen_comms *comms,
79 void *init_params);
80
81static struct Xt_com_list
82xt_xmdd_cycl_stripe_get_next_bucket(void *gen_state_, int type);
83
84static void
86
87static int
89
99
100
101static inline Xt_int
104 bool *stripify, MPI_Comm comm, int comm_size,
105 Xt_config config)
106{
107 unsigned long long local_vals[2], global_sums[2];
108
109 unsigned num_indices_src = (unsigned)xt_idxlist_get_num_indices(src);
110 local_vals[0] = num_indices_src;
111 local_vals[1] = xt_idxlist_is_stripe_conversion_profitable_(src, config)
113
114 xt_mpi_call(MPI_Allreduce(local_vals, global_sums, 2,
115 MPI_UNSIGNED_LONG_LONG, MPI_SUM, comm), comm);
116
117 *stripify = global_sums[1] > 0;
118 return (Xt_int)(MAX(((global_sums[0] + (unsigned)comm_size - 1)
119 / (unsigned)comm_size), 1) * (unsigned)comm_size);
120}
121
123
124 int num_a = xt_idxlist_get_num_indices(a),
126 Xt_int min_index_a = num_a ? xt_idxlist_get_min_index(a) : XT_INT_MAX,
127 min_index_b = num_b ? xt_idxlist_get_min_index(b) : XT_INT_MAX,
128 min_index = (Xt_int)MIN(min_index_a, min_index_b);
129 return min_index;
130}
131
133
134 int num_a = xt_idxlist_get_num_indices(a),
136 Xt_int max_index_a = num_a ? xt_idxlist_get_max_index(a) : XT_INT_MIN,
137 max_index_b = num_b ? xt_idxlist_get_max_index(b) : XT_INT_MIN,
138 max_index = MAX(max_index_a, max_index_b);
139 return max_index;
140}
141
142static struct bucket_params
145 Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist,
146 int comm_size)
147{
150 = get_min_idxlist_index(src_idxlist, dst_idxlist);
152 = get_max_idxlist_index(src_idxlist, dst_idxlist);
153 size_t first_overlapping_bucket = 0;
154 /* is it impossible for early buckets to overlap our lists? */
157 first_overlapping_bucket
159 }
160 /* is it impossible for later ranks to overlap our lists? */
161 size_t start_of_non_overlapping_bucket_suffix
162 = (size_t)(((long long)local_index_range_ubound + local_interval - 1)
163 / local_interval) + 1;
165 || start_of_non_overlapping_bucket_suffix > (size_t)comm_size)
166 start_of_non_overlapping_bucket_suffix = (size_t)comm_size;
167 /*
168 * size_t max_num_intersect
169 * = start_of_non_overlapping_bucket_suffix - first_overlapping_bucket;
170 */
171 return (struct bucket_params){
172 .global_interval = global_interval,
173 .local_interval = local_interval,
174 .local_index_range_lbound = local_index_range_lbound,
175 .local_index_range_ubound = local_index_range_ubound,
176 .most_recent_rank_generated = (int)first_overlapping_bucket - 1,
177 .max_rank_generated = (int)(start_of_non_overlapping_bucket_suffix-1),
178 };
179}
180
181/* unfortunately GCC 11 cannot handle the literal constants used for
182 * MPI_STATUSES_IGNORE by MPICH */
183#if __GNUC__ >= 11 && __GNUC__ <= 13 && defined MPICH
184#pragma GCC diagnostic push
185#pragma GCC diagnostic ignored "-Wstringop-overread"
186#pragma GCC diagnostic ignored "-Wstringop-overflow"
187#endif
188
189/* interval_size[0] and interval_size[1] are the global interval
190 * size for the local and remote group */
191
192static inline void
194 Xt_idxlist src, Xt_idxlist dst,
195 bool *stripify, Xt_int interval_size[2],
196 struct Xt_xmdd_bucket_gen_comms *comms,
197 int comm_size, int remote_size,
198 Xt_config config)
199{
200 /* global_sums[0] and [1] refer to the local and remote group of
201 * intercommunicator inter_comm */
202 unsigned long long local_vals[2], global_sums[2][2];
203
204 unsigned num_indices_src = (unsigned)xt_idxlist_get_num_indices(src);
205 local_vals[0] = num_indices_src;
206 local_vals[1] = (num_indices_src > (unsigned)config->idxv_cnv_size)
207 || (xt_idxlist_get_num_indices(dst) > config->idxv_cnv_size);
208
209 xt_mpi_call(MPI_Allreduce(local_vals, global_sums[0], 2,
210 MPI_UNSIGNED_LONG_LONG, MPI_SUM,
211 comms->intra_comm),
212 comms->intra_comm);
213 /* instead of sendrecv one might use hand-programmed multi-casts
214 * sending to each rank in a range from the remote group and
215 * receiving from the first rank in that group,
216 * the better choice probably depends on the asymmetry of the group
217 * sizes, i.e. use bcast from a very small to a very large group
218 * and few sends from a large to a small group */
219 int comm_rank;
220 xt_mpi_call(MPI_Comm_rank(comms->inter_comm, &comm_rank),
221 comms->inter_comm);
222 if (comm_rank == 0) {
224 xt_mpi_call(MPI_Sendrecv(global_sums[0], 2, MPI_UNSIGNED_LONG_LONG, 0, tag,
225 global_sums[1], 2, MPI_UNSIGNED_LONG_LONG, 0, tag,
226 comms->inter_comm, MPI_STATUS_IGNORE),
227 comms->inter_comm);
228 }
229 xt_mpi_call(MPI_Bcast(global_sums[1], 2, MPI_UNSIGNED_LONG_LONG,
230 0, comms->intra_comm), comms->intra_comm);
231 *stripify = (global_sums[0][1] > 0 || global_sums[1][1] > 0);
232 interval_size[0]
233 = (Xt_int)(((global_sums[0][0] + (unsigned)comm_size - 1)
234 / (unsigned)comm_size) * (unsigned)comm_size);
235 interval_size[1]
236 = (Xt_int)(((global_sums[1][0] + (unsigned)remote_size - 1)
237 / (unsigned)remote_size) * (unsigned)remote_size);
238}
239
240static inline Xt_int
242{
243 int num_idx = xt_idxlist_get_num_indices(l);
244 Xt_int min_index = num_idx ? xt_idxlist_get_min_index(l) : XT_INT_MAX;
245 return min_index;
246}
247
248static inline Xt_int
250{
251 int num_idx = xt_idxlist_get_num_indices(l);
252 Xt_int max_index = num_idx ? xt_idxlist_get_max_index(l) : XT_INT_MIN;
253 return max_index;
254}
255
256
257static struct bucket_params
259 Xt_int global_interval, int comm_size)
260{
261 /* guard vs. comm_size being larger than number of indices */
265 size_t first_overlapping_bucket = 0;
266 /* is it impossible for early buckets to overlap our lists? */
269 first_overlapping_bucket
271 }
272 /* is it impossible for later ranks to overlap our lists? */
273 size_t start_of_non_overlapping_bucket_suffix
274 = (size_t)(((long long)local_index_range_ubound + local_interval - 1)
275 / local_interval) + 1;
277 || start_of_non_overlapping_bucket_suffix > (size_t)comm_size)
278 start_of_non_overlapping_bucket_suffix = (size_t)comm_size;
279 return (struct bucket_params){
280 .global_interval = global_interval,
281 .local_interval = local_interval,
282 .local_index_range_lbound = local_index_range_lbound,
283 .local_index_range_ubound = local_index_range_ubound,
284 .most_recent_rank_generated = (int)first_overlapping_bucket - 1,
285 .max_rank_generated = (int)(start_of_non_overlapping_bucket_suffix-1),
286 };
287}
288
289static int
291 void *gen_state_,
292 Xt_idxlist src_idxlist,
293 Xt_idxlist dst_idxlist,
294 Xt_config config,
295 struct Xt_xmdd_bucket_gen_comms *comms,
296 void *init_params)
297{
298 (void)init_params;
299 struct Xt_xmdd_bucket_gen_cycl_stripe_state *gen_state = gen_state_;
300 bool stripify = false;
301 int comm_size;
302 xt_mpi_call(MPI_Comm_size(comms->intra_comm, &comm_size), comms->intra_comm);
303 if (comms->inter_comm == MPI_COMM_NULL) {
304 /* global_interval is a multiple of comm_size and has a size of at least
305 comm_size */
306 Xt_int global_interval_size
308 src_idxlist, dst_idxlist,
309 &stripify, comms->intra_comm, comm_size, config);
310 gen_state->dst
311 = get_intracomm_bucket_params(global_interval_size,
312 src_idxlist, dst_idxlist, comm_size);
313 } else {
314 Xt_int global_interval_size[2];
315 int remote_size;
316 xt_mpi_call(MPI_Comm_remote_size(comms->inter_comm, &remote_size),
317 comms->inter_comm);
319 src_idxlist, dst_idxlist,
320 &stripify, global_interval_size,
321 comms, comm_size, remote_size, config);
322 gen_state->src
323 = get_intercomm_bucket_params(src_idxlist, global_interval_size[0],
324 comm_size);
325 gen_state->dst
326 = get_intercomm_bucket_params(dst_idxlist, global_interval_size[1],
327 remote_size);
328 }
329 gen_state->last_list_generated = NULL;
330 gen_state->stripes = NULL;
331 gen_state->stripes_array_size = 0;
332 return stripify;
333}
334
335static void
337{
338 struct Xt_xmdd_bucket_gen_cycl_stripe_state *gen_state = gen_state_;
339 if (gen_state->last_list_generated)
341 free(gen_state->stripes);
342}
343
344static int
346{
347 int max_num_intersect = 0;
348 struct Xt_xmdd_bucket_gen_cycl_stripe_state *gen_state = gen_state_;
349 struct bucket_params *params = type == Xt_dist_dir_bucket_gen_type_send
350 ? &gen_state->src : &gen_state->dst;
353 max_num_intersect =
355 >= params->local_index_range_lbound
358 return max_num_intersect;
359}
360
361
400static Xt_idxlist
403 int dist_dir_rank)
404{
409 int num_stripes = 0;
410
411 /* find first index in bucket of dist_dir_rank
412 <= local_index_range_lbound */
413 Xt_int start = (Xt_int)(0 + dist_dir_rank * local_interval);
414 {
415 long long start_correction
416 = (long long)local_index_range_lbound - (long long)start;
417 Xt_int corr_steps
418 = (Xt_int)((start_correction
419 - (llsign_mask(start_correction)
420 & (long long)(global_interval - 1)))
421 / (long long)global_interval);
422 start = (Xt_int)(start + corr_steps * global_interval);
423 }
424 /* next find last stripe in bucket of dist_dir_rank
425 * <= local_index_range_ubound */
426 Xt_int end
427 = (Xt_int)(start
428 + (((long long)local_index_range_ubound - (long long)start)
430 Xt_int use_start_stripe
432 num_stripes = (int)(((long long)end - (long long)start)/global_interval)
433 + (int)use_start_stripe;
434 start = (Xt_int)(start
435 + ((Xt_int)((Xt_uint)use_start_stripe - (Xt_uint)1)
436 & global_interval));
437 if (!num_stripes)
438 return NULL;
439
440 struct Xt_stripe *restrict stripes = gen_state->stripes;
441 ENSURE_ARRAY_SIZE(stripes, gen_state->stripes_array_size, (size_t)num_stripes);
442 for (int j = 0; j < num_stripes; ++j) {
443 stripes[j].start = (Xt_int)(start + j * global_interval);
444 stripes[j].stride = 1;
445 stripes[j].nstrides = (int)local_interval;
446 }
447 gen_state->stripes = stripes;
448 return xt_idxstripes_prealloc_new(stripes, num_stripes);
449}
450
451static struct Xt_com_list
452xt_xmdd_cycl_stripe_get_next_bucket(void *gen_state_, int type)
453{
454 struct Xt_xmdd_bucket_gen_cycl_stripe_state *gen_state = gen_state_;
455 struct Xt_com_list bucket;
456 if (gen_state->last_list_generated)
458 struct bucket_params *params =
459 type == Xt_dist_dir_bucket_gen_type_send ? &gen_state->src
460 : &gen_state->dst;
461 int next_rank = params->most_recent_rank_generated,
462 max_rank = params->max_rank_generated;
463 bucket.list = NULL;
464 while (next_rank < max_rank
465 && !(bucket.list = xt_xmap_dist_dir_get_bucket(
466 gen_state, params, ++next_rank)))
467 ;
468 params->most_recent_rank_generated = bucket.rank = next_rank;
469 gen_state->last_list_generated = bucket.list;
470 return bucket;
471}
472
473
474
475
476
477/*
478 * Local Variables:
479 * c-basic-offset: 2
480 * coding: utf-8
481 * indent-tabs-mode: nil
482 * show-trailing-whitespace: t
483 * require-trailing-newline: t
484 * End:
485 */
@ MPI_COMM_NULL
Definition core.h:74
int MPI_Comm
Definition core.h:64
#define ENSURE_ARRAY_SIZE(arrayp, curr_array_size, req_size)
add versions of standard API functions not returning on error
Xt_idxlist list
Definition xt_core.h:154
Xt_int start
Definition xt_stripe.h:55
Xt_xmdd_bucket_gen_init_state_internal init
static long long llsign_mask(long long x)
implementation of configuration object
#define XT_INT_MIN
Definition xt_core.h:78
#define XT_INT_MAX
Definition xt_core.h:77
XT_INT Xt_int
Definition xt_core.h:72
unsigned XT_INT Xt_uint
Definition xt_core.h:74
#define MAX(a, b)
Definition xt_cuda.c:68
bool xt_idxlist_is_stripe_conversion_profitable_(Xt_idxlist idxlist, Xt_config config)
Definition xt_idxlist.c:479
Xt_int xt_idxlist_get_min_index(Xt_idxlist idxlist)
Definition xt_idxlist.c:349
Xt_int xt_idxlist_get_max_index(Xt_idxlist idxlist)
Definition xt_idxlist.c:354
void xt_idxlist_delete(Xt_idxlist idxlist)
Definition xt_idxlist.c:75
Provide non-public declarations common to all index lists.
#define xt_idxlist_get_num_indices(idxlist)
#define MIN(a, b)
Xt_idxlist xt_idxstripes_prealloc_new(const struct Xt_stripe *stripes, int num_stripes)
utility routines for MPI
#define xt_mpi_call(call, comm)
Definition xt_mpi.h:68
@ xt_mpi_tag_xmap_dist_dir_src_send
@ Xt_dist_dir_bucket_gen_type_send
static Xt_idxlist xt_xmap_dist_dir_get_bucket(struct Xt_xmdd_bucket_gen_cycl_stripe_state *gen_state, struct bucket_params *bucket_params, int dist_dir_rank)
generates the buckets of the distributed directory
static struct bucket_params get_intracomm_bucket_params(Xt_int global_interval, Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist, int comm_size)
static Xt_int get_intracomm_dist_dir_global_interval_size(Xt_idxlist src, Xt_idxlist dst, bool *stripify, MPI_Comm comm, int comm_size, Xt_config config)
static Xt_int get_intercomm_max_idxlist_index(Xt_idxlist l)
static void get_intercomm_dist_dir_global_interval_size(Xt_idxlist src, Xt_idxlist dst, bool *stripify, Xt_int interval_size[2], struct Xt_xmdd_bucket_gen_comms *comms, int comm_size, int remote_size, Xt_config config)
static Xt_int get_max_idxlist_index(Xt_idxlist a, Xt_idxlist b)
static struct bucket_params get_intercomm_bucket_params(Xt_idxlist idxlist, Xt_int global_interval, int comm_size)
static Xt_int get_min_idxlist_index(Xt_idxlist a, Xt_idxlist b)
const struct Xt_xmdd_bucket_gen_ Xt_xmdd_cycl_stripe_bucket_gen_desc
static void xt_xmdd_bucket_gen_cycl_stripe_destroy(void *gen_state)
static Xt_int get_intercomm_min_idxlist_index(Xt_idxlist l)
static int xt_xmdd_bucket_gen_cycl_stripe_init(void *gen_state_, Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist, Xt_config config, struct Xt_xmdd_bucket_gen_comms *comms, void *init_params)
static int xt_xmdd_bucket_gen_cycl_stripe_get_intersect_max_num(void *gen_state, int type)
static struct Xt_com_list xt_xmdd_cycl_stripe_get_next_bucket(void *gen_state_, int type)
Default bucket generator for creation of distributed directories.
Default bucket generator for creation of distributed directories.
int(* Xt_xmdd_bucket_gen_init_state_internal)(void *gen_state, Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist, Xt_config config, const struct Xt_xmdd_bucket_gen_comms *comms, void *init_params, const struct Xt_xmdd_bucket_gen_ *gen)
Utility functions for creation of distributed directories.