Yet Another eXchange Tool  0.9.0
xt_xmap_all2all.c
Go to the documentation of this file.
1 
12 /*
13  * Keywords:
14  * Maintainer: Jörg Behrens <behrens@dkrz.de>
15  * Moritz Hanke <hanke@dkrz.de>
16  * Thomas Jahns <jahns@dkrz.de>
17  * URL: https://doc.redmine.dkrz.de/yaxt/html/
18  *
19  * Redistribution and use in source and binary forms, with or without
20  * modification, are permitted provided that the following conditions are
21  * met:
22  *
23  * Redistributions of source code must retain the above copyright notice,
24  * this list of conditions and the following disclaimer.
25  *
26  * Redistributions in binary form must reproduce the above copyright
27  * notice, this list of conditions and the following disclaimer in the
28  * documentation and/or other materials provided with the distribution.
29  *
30  * Neither the name of the DKRZ GmbH nor the names of its contributors
31  * may be used to endorse or promote products derived from this software
32  * without specific prior written permission.
33  *
34  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
35  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
36  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
37  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
38  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
39  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
40  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
41  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
42  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
43  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
44  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45  */
46 #ifdef HAVE_CONFIG_H
47 #include <config.h>
48 #endif
49 
50 #include <stdlib.h>
51 #include <stdio.h>
52 #include <string.h>
53 #include <assert.h>
54 #include <limits.h>
55 
56 #include <mpi.h>
57 
58 #include "xt/xt_idxlist.h"
59 #include "xt/xt_idxvec.h"
60 #include "xt/xt_xmap.h"
61 #include "xt/xt_mpi.h"
62 #include "xt_mpi_internal.h"
63 #include "core/core.h"
64 #include "core/ppm_xfuncs.h"
65 #include "xt/xt_xmap_all2all.h"
67 #include "xt_idxlist_internal.h"
68 #include "instr.h"
69 
70 static void exchange_idxlists(struct Xt_com_list **src_intersections,
71  size_t *num_src_intersections,
72  struct Xt_com_list **dst_intersections,
73  size_t *num_dst_intersections,
74  int * stripify,
75  Xt_idxlist src_idxlist_local,
76  Xt_idxlist dst_idxlist_local,
77  MPI_Comm comm)
78 {
79 
80  /*
81  Note: The meaning of source (src) and destination (dst) points can already be understood by
82  looking at the serial case, where it is just a transformation of sequences of integers
83  (called indices). The starting state (source sequence) is transformed into an end state
84  (dst sequence). The transformation does not have to be bijective. For each position dpos of
85  the dst sequence we have at least one position spos in the src sequence with:
86  dst(dpos) = src(spos)
87  */
88 
89  int comm_size, rank, is_inter;
90  xt_mpi_call(MPI_Comm_rank(comm, &rank), comm);
91  xt_mpi_call(MPI_Comm_test_inter(comm, &is_inter), comm);
92  int (*get_comm_size)(MPI_Comm, int *)
93  = is_inter ? MPI_Comm_remote_size : MPI_Comm_size;
94  xt_mpi_call(get_comm_size(comm, &comm_size), comm);
95 
96  // allocate memory for intersections
97  struct Xt_com_list *dsti = xmalloc((size_t)comm_size * sizeof (*dsti));
98  struct Xt_com_list *srci = xmalloc((size_t)comm_size * sizeof (*srci));
99 
100  // compute size of local index lists
101  size_t src_pack_size = xt_idxlist_get_pack_size(src_idxlist_local, comm);
102  size_t dst_pack_size = xt_idxlist_get_pack_size(dst_idxlist_local, comm);
103  size_t size_sum = src_pack_size + dst_pack_size;
104 
105  if (size_sum >= INT_MAX || size_sum < src_pack_size
106  || size_sum < dst_pack_size)
107  die("local src+dst index lists are too large");
108 
109  int send_buffer_size = (int)size_sum;
110 
111  // exchange buffer sizes
112  int *restrict pack_sizes
113  = xmalloc((size_t)comm_size * sizeof(*pack_sizes) * 2);
114 
115  xt_mpi_call(MPI_Allgather(&send_buffer_size, 1, MPI_INT,
116  pack_sizes, 1, MPI_INT, comm), comm);
117 
118  int *restrict displ = pack_sizes + comm_size;
119  displ[0] = 0;
120  unsigned recv_buffer_size = (unsigned)pack_sizes[0];
121  unsigned size_overflow = 0;
122  for (size_t i = 1; i < (size_t)comm_size; ++i) {
123 
124  displ[i] = (int)recv_buffer_size;
125  recv_buffer_size += (unsigned)pack_sizes[i];
126  size_overflow |= recv_buffer_size & (1U << (sizeof(int) * CHAR_BIT - 1));
127  }
128  if (size_overflow)
129  die("accumulated buffer sizes too big,"
130  " use distributed directory (xt_xmap_dist_dir_new)!");
131  void *recv_buffer = xmalloc((size_t)recv_buffer_size + size_sum),
132  *send_buffer = (unsigned char *)recv_buffer + (size_t)recv_buffer_size;
133  // pack local index lists
134  {
135  int position = 0;
136  xt_idxlist_pack(src_idxlist_local, send_buffer, send_buffer_size,
137  &position, comm);
138  xt_idxlist_pack(dst_idxlist_local, send_buffer, send_buffer_size,
139  &position, comm);
140  }
141  // exchange buffers
142  xt_mpi_call(MPI_Allgatherv(send_buffer, send_buffer_size, MPI_PACKED,
143  recv_buffer, pack_sizes, displ, MPI_PACKED,
144  comm), comm);
145 
146  size_t dst_isect_count = 0, src_isect_count = 0;
147  int large_list_seen = 0;
148  // compute intersections
149  for (int i = 0; i < comm_size; ++i) {
150 
151  int position = 0;
152  // unpack buffers unless local
153  Xt_idxlist src, dst;
154  if (is_inter || i != rank) {
155  src = xt_idxlist_unpack((unsigned char *)recv_buffer + displ[i],
156  pack_sizes[i], &position, comm);
157  dst = xt_idxlist_unpack((unsigned char *)recv_buffer + displ[i],
158  pack_sizes[i], &position, comm);
159  } else {
160  src = src_idxlist_local;
161  dst = dst_idxlist_local;
162  }
163  large_list_seen
166  Xt_idxlist intersect = xt_idxlist_get_intersection(src, dst_idxlist_local);
167  if (xt_idxlist_get_num_indices(intersect) > 0) {
168 
169  dsti[dst_isect_count].list = intersect;
170  dsti[dst_isect_count].rank = i;
171  ++dst_isect_count;
172  }
173  else
174  xt_idxlist_delete(intersect);
175 
176  intersect = xt_idxlist_get_intersection(src_idxlist_local, dst);
177  if (xt_idxlist_get_num_indices(intersect) > 0) {
178 
179  srci[src_isect_count].list = intersect;
180  srci[src_isect_count].rank = i;
181  ++src_isect_count;
182  }
183  else
184  xt_idxlist_delete(intersect);
185  if (is_inter || i != rank) {
186  xt_idxlist_delete(src);
187  xt_idxlist_delete(dst);
188  }
189  }
190 
191  *stripify = large_list_seen;
192 
193  free(recv_buffer);
194  free(pack_sizes);
195 
196  /* minimize memory use of tables */
197  *num_src_intersections = src_isect_count;
198  srci = xrealloc(srci, src_isect_count * sizeof (**src_intersections));
199  *src_intersections = srci;
200 
201  *num_dst_intersections = dst_isect_count;
202  dsti = xrealloc(dsti, dst_isect_count * sizeof (**dst_intersections));
203  *dst_intersections = dsti;
204 }
205 
206 Xt_xmap xt_xmap_all2all_new(Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist, MPI_Comm comm) {
207  INSTR_DEF(t_xt_xmap_all2all_new,"xt_xmap_all2all_new")
208  INSTR_START(t_xt_xmap_all2all_new);
209 
210  // ensure that yaxt is initialized
211  assert(xt_initialized());
212 
213  int tag_offset;
214  MPI_Comm newcomm = xt_mpi_comm_smart_dup(comm, &tag_offset);
215 
216  struct Xt_com_list * src_intersections = NULL, * dst_intersections = NULL;
217  size_t num_src_intersections, num_dst_intersections;
218 
219  int stripify;
220  // exchange index lists between all processes in comm
221  exchange_idxlists(&src_intersections, &num_src_intersections,
222  &dst_intersections, &num_dst_intersections,
223  &stripify, src_idxlist, dst_idxlist, newcomm);
224 
225  Xt_xmap (*xmap_new)(int num_src_intersections,
226  const struct Xt_com_list *src_com,
227  int num_dst_intersections,
228  const struct Xt_com_list *dst_com,
229  Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist,
230  MPI_Comm comm)
232 
233  Xt_xmap xmap = xmap_new((int)num_src_intersections, src_intersections,
234  (int)num_dst_intersections, dst_intersections,
235  src_idxlist, dst_idxlist, newcomm);
236 
237  xt_mpi_comm_smart_dedup(&newcomm, tag_offset);
238  for (size_t i = 0; i < num_src_intersections; ++i)
239  if (src_intersections[i].list != NULL)
240  xt_idxlist_delete(src_intersections[i].list);
241  for (size_t i = 0; i < num_dst_intersections; ++i)
242  if (dst_intersections[i].list != NULL)
243  xt_idxlist_delete(dst_intersections[i].list);
244  free(src_intersections);
245  free(dst_intersections);
246  INSTR_STOP(t_xt_xmap_all2all_new);
247  return xmap;
248 }
249 
250 /*
251  * Local Variables:
252  * c-basic-offset: 2
253  * coding: utf-8
254  * indent-tabs-mode: nil
255  * show-trailing-whitespace: t
256  * require-trailing-newline: t
257  * End:
258  */
int MPI_Comm
Definition: core.h:64
#define die(msg)
Definition: core.h:131
#define INSTR_STOP(T)
Definition: instr.h:69
#define INSTR_DEF(T, S)
Definition: instr.h:66
#define INSTR_START(T)
Definition: instr.h:68
add versions of standard API functions not returning on error
#define xrealloc(ptr, size)
Definition: ppm_xfuncs.h:71
#define xmalloc(size)
Definition: ppm_xfuncs.h:70
int xt_initialized(void)
Definition: xt_init.c:107
struct Xt_xmap_ * Xt_xmap
Definition: xt_core.h:81
index list declaration
int xt_idxlist_get_num_indices(Xt_idxlist idxlist)
Definition: xt_idxlist.c:98
Xt_idxlist xt_idxlist_unpack(void *buffer, int buffer_size, int *position, MPI_Comm comm)
void xt_idxlist_pack(Xt_idxlist idxlist, void *buffer, int buffer_size, int *position, MPI_Comm comm)
Definition: xt_idxlist.c:85
size_t xt_idxlist_get_pack_size(Xt_idxlist idxlist, MPI_Comm comm)
Definition: xt_idxlist.c:79
Xt_idxlist xt_idxlist_get_intersection(Xt_idxlist idxlist_src, Xt_idxlist idxlist_dst)
void xt_idxlist_delete(Xt_idxlist idxlist)
Definition: xt_idxlist.c:74
Provide non-public declarations common to all index lists.
@ CHEAP_VECTOR_SIZE
MPI_Comm xt_mpi_comm_smart_dup(MPI_Comm comm, int *tag_offset)
Definition: xt_mpi.c:813
void xt_mpi_comm_smart_dedup(MPI_Comm *comm, int tag_offset)
Definition: xt_mpi.c:864
utility routines for MPI
#define xt_mpi_call(call, comm)
Definition: xt_mpi.h:68
exchange map declarations
Xt_xmap xt_xmap_all2all_new(Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist, MPI_Comm comm)
static void exchange_idxlists(struct Xt_com_list **src_intersections, size_t *num_src_intersections, struct Xt_com_list **dst_intersections, size_t *num_dst_intersections, int *stripify, Xt_idxlist src_idxlist_local, Xt_idxlist dst_idxlist_local, MPI_Comm comm)
Xt_xmap xt_xmap_intersection_ext_new(int num_src_intersections, const struct Xt_com_list src_com[num_src_intersections], int num_dst_intersections, const struct Xt_com_list dst_com[num_dst_intersections], Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist, MPI_Comm comm)
Xt_xmap xt_xmap_intersection_new(int num_src_intersections, const struct Xt_com_list src_com[num_src_intersections], int num_dst_intersections, const struct Xt_com_list dst_com[num_dst_intersections], Xt_idxlist src_idxlist, Xt_idxlist dst_idxlist, MPI_Comm comm)