(git:27c966b)
Loading...
Searching...
No Matches
dbm_multiply_comm.c
Go to the documentation of this file.
1/*----------------------------------------------------------------------------*/
2/* CP2K: A general program to perform molecular dynamics simulations */
3/* Copyright 2000-2026 CP2K developers group <https://cp2k.org> */
4/* */
5/* SPDX-License-Identifier: BSD-3-Clause */
6/*----------------------------------------------------------------------------*/
7#include "dbm_multiply_comm.h"
8#include "../mpiwrap/cp_mpi.h"
10
11#include <assert.h>
12#include <limits.h>
13#include <omp.h>
14#include <stdlib.h>
15#include <string.h>
16
17#if 1
18#define DBM_MULTIPLY_COMM_MEMPOOL
19#endif
20
21/*******************************************************************************
22 * \brief Private routine for allocating a communication buffer, which is taken
23 * from the memory pool (DBM_MULTIPLY_COMM_MEMPOOL) rather than mapping
24 * fresh pages for every multiplication.
25 * \author Hans Pabst
26 ******************************************************************************/
27static void *allocate_comm_buffer(const size_t size) {
28#if defined(DBM_MULTIPLY_COMM_MEMPOOL)
29 return offload_mempool_host_malloc(size);
30#else
31 return cp_mpi_alloc_mem(size);
32#endif
33}
34
35/*******************************************************************************
36 * \brief Private routine for releasing a buffer from allocate_comm_buffer.
37 * \author Hans Pabst
38 ******************************************************************************/
39static void free_comm_buffer(void *mem) {
40#if defined(DBM_MULTIPLY_COMM_MEMPOOL)
42#else
43 cp_mpi_free_mem(mem);
44#endif
45}
46
47/*******************************************************************************
48 * \brief Private routine for computing greatest common divisor of two numbers.
49 * \author Ole Schuett
50 ******************************************************************************/
51static int gcd(const int a, const int b) {
52 if (a == 0) {
53 return b;
54 }
55 return gcd(b % a, a); // Euclid's algorithm.
56}
57
58/*******************************************************************************
59 * \brief Private routine for computing least common multiple of two numbers.
60 * \author Ole Schuett
61 ******************************************************************************/
62static int lcm(const int a, const int b) { return (a * b) / gcd(a, b); }
63
64/*******************************************************************************
65 * \brief Private routine for converting element counts to byte counts.
66 * \author Hans Pabst
67 ******************************************************************************/
68static int checked_byte_count(const int nelements, const size_t element_size) {
69 // MPI displacements/counts are int; unchecked multiplication could overflow
70 // silently and corrupt the alltoallv layout.
71 assert(0 <= nelements);
72 assert(element_size <= INT_MAX);
73 assert(nelements <= INT_MAX / (int)element_size);
74 return nelements * (int)element_size;
75}
76
77/*******************************************************************************
78 * \brief Private routine for computing the sum of the given integers.
79 * \author Ole Schuett
80 ******************************************************************************/
81static inline int isum(const int n, const int input[n]) {
82 int output = 0;
83 for (int i = 0; i < n; i++) {
84 output += input[i];
85 }
86 return output;
87}
88
89/*******************************************************************************
90 * \brief Private routine for computing the cumulative sums of given numbers.
91 * \author Ole Schuett and Hans Pabst
92 ******************************************************************************/
93static inline void icumsum(const int n, const int input[n], int output[n]) {
94 // Exclusive prefix sum using carried accumulators to avoid a load from
95 // output[i-1] each iteration (removes loop-carried memory dependency).
96 int oval = output[0] = 0, ival = input[0];
97 for (int i = 1; i < n; i++) {
98 output[i] = (oval += ival);
99 ival = input[i];
100 }
101}
102
103/*******************************************************************************
104 * \brief Private routine computing received data counts from block metadata.
105 * \author Hans Pabst
106 ******************************************************************************/
107static void compute_data_recv_count(const int nranks,
108 const int blks_recv_count[nranks],
109 const int blks_recv_displ[nranks],
110 const int free_index_sizes[],
111 const int sum_index_sizes[],
112 const dbm_pack_block_t blks_recv[],
113 int data_recv_count[nranks]) {
114 // Derives per-rank data counts locally from the already-received block
115 // metadata, eliminating a collective alltoall for exchanging data amounts.
116 memset(data_recv_count, 0, nranks * sizeof(int));
117 for (int irank = 0; irank < nranks; irank++) {
118 for (int i = 0; i < blks_recv_count[irank]; i++) {
119 const dbm_pack_block_t *const blk =
120 &blks_recv[blks_recv_displ[irank] + i];
121 const int block_size =
122 free_index_sizes[blk->free_index] * sum_index_sizes[blk->sum_index];
123 assert(block_size >= 0);
124 assert(data_recv_count[irank] <= INT_MAX - block_size);
125 data_recv_count[irank] += block_size;
126 }
127 }
128}
129
130/*******************************************************************************
131 * \brief Private struct used for planing during pack_matrix.
132 * \author Ole Schuett
133 ******************************************************************************/
134typedef struct {
135 const dbm_block_t *blk; // source block
136 int rank; // target mpi rank
139} plan_t;
140
141/*******************************************************************************
142 * \brief Private routine for calculating tick indices in pack plans.
143 * \author Maximilian Graml
144 ******************************************************************************/
145static inline unsigned long long calculate_tick_index(int sum_index,
146 int nticks) {
147 // 1021 is used as a random prime to scramble the index
148 return ((unsigned long long)sum_index * 1021ULL) % (unsigned long long)nticks;
149}
150
151/*******************************************************************************
152 * \brief Private routine for planing packs.
153 * \author Ole Schuett
154 ******************************************************************************/
155static void create_pack_plans(const bool trans_matrix, const bool trans_dist,
156 const dbm_matrix_t *matrix,
157 const cp_mpi_comm_t comm,
158 const dbm_dist_1d_t *dist_indices,
159 const dbm_dist_1d_t *dist_ticks, const int nticks,
160 const int npacks, plan_t *plans_per_pack[npacks],
161 int nblks_per_pack[npacks],
162 int ndata_per_pack[npacks]) {
163 memset(nblks_per_pack, 0, npacks * sizeof(int));
164 memset(ndata_per_pack, 0, npacks * sizeof(int));
165
166#pragma omp parallel
167 {
168 // 1st pass: Compute number of blocks that will be send in each pack.
169 int nblks_mythread[npacks];
170 memset(nblks_mythread, 0, npacks * sizeof(int));
171#pragma omp for schedule(static) nowait
172 for (int ishard = 0; ishard < dbm_get_num_shards(matrix); ishard++) {
173 dbm_shard_t *shard = &matrix->shards[ishard];
174 for (int iblock = 0; iblock < shard->nblocks; iblock++) {
175 const dbm_block_t *blk = &shard->blocks[iblock];
176 const int sum_index = (trans_matrix) ? blk->row : blk->col;
177 unsigned long long itick64 = calculate_tick_index(sum_index, nticks);
178 const int ipack = itick64 / dist_ticks->nranks;
179 nblks_mythread[ipack]++;
180 }
181 }
182
183 // Sum nblocks across threads and allocate arrays for plans.
184#pragma omp critical
185 for (int ipack = 0; ipack < npacks; ipack++) {
186 nblks_per_pack[ipack] += nblks_mythread[ipack];
187 nblks_mythread[ipack] = nblks_per_pack[ipack];
188 }
189#pragma omp barrier
190#pragma omp for
191 for (int ipack = 0; ipack < npacks; ipack++) {
192 const int nblks = nblks_per_pack[ipack];
193 plans_per_pack[ipack] = malloc(nblks * sizeof(plan_t));
194 assert(plans_per_pack[ipack] != NULL || nblks == 0);
195 }
196
197 // 2nd pass: Plan where to send each block.
198 int ndata_mythread[npacks];
199 memset(ndata_mythread, 0, npacks * sizeof(int));
200#pragma omp for schedule(static) nowait // Need static to match previous loop.
201 for (int ishard = 0; ishard < dbm_get_num_shards(matrix); ishard++) {
202 dbm_shard_t *shard = &matrix->shards[ishard];
203 for (int iblock = 0; iblock < shard->nblocks; iblock++) {
204 const dbm_block_t *blk = &shard->blocks[iblock];
205 const int free_index = (trans_matrix) ? blk->col : blk->row;
206 const int sum_index = (trans_matrix) ? blk->row : blk->col;
207 unsigned long long itick64 = calculate_tick_index(sum_index, nticks);
208 const int ipack = itick64 / dist_ticks->nranks;
209 // Compute rank to which this block should be sent.
210 const int coord_free_idx = dist_indices->index2coord[free_index];
211 const int coord_sum_idx = itick64 % dist_ticks->nranks;
212 const int coords[2] = {(trans_dist) ? coord_sum_idx : coord_free_idx,
213 (trans_dist) ? coord_free_idx : coord_sum_idx};
214 const int rank = cp_mpi_cart_rank(comm, coords);
215 const int row_size = matrix->row_sizes[blk->row];
216 const int col_size = matrix->col_sizes[blk->col];
217 ndata_mythread[ipack] += row_size * col_size;
218 // Create plan.
219 const int iplan = --nblks_mythread[ipack];
220 plans_per_pack[ipack][iplan].blk = blk;
221 plans_per_pack[ipack][iplan].rank = rank;
222 plans_per_pack[ipack][iplan].row_size = row_size;
223 plans_per_pack[ipack][iplan].col_size = col_size;
224 }
225 }
226#pragma omp critical
227 for (int ipack = 0; ipack < npacks; ipack++) {
228 ndata_per_pack[ipack] += ndata_mythread[ipack];
229 }
230 } // end of omp parallel region
231}
232
233/*******************************************************************************
234 * \brief Private routine for copying a block and computing its squared norm.
235 ******************************************************************************/
236static void copy_pack_block(const bool trans_matrix, const dbm_block_t *blk,
237 const int row_size, const int col_size,
238 const double shard_data[], double pack_data[],
239 const int offset, dbm_pack_block_t *pack_block) {
240 double norm = 0.0; // Compute norm as double, store as float.
241 if (trans_matrix) {
242 // Transpose block to allow for outer-product style multiplication.
243 for (int i = 0; i < row_size; i++) {
244 for (int j = 0; j < col_size; j++) {
245 const double element = shard_data[blk->offset + j * row_size + i];
246 pack_data[offset + i * col_size + j] = element;
247 norm += element * element;
248 }
249 }
250 pack_block->free_index = blk->col;
251 pack_block->sum_index = blk->row;
252 } else {
253 for (int i = 0; i < row_size * col_size; i++) {
254 const double element = shard_data[blk->offset + i];
255 pack_data[offset + i] = element;
256 norm += element * element;
257 }
258 pack_block->free_index = blk->row;
259 pack_block->sum_index = blk->col;
260 }
261 pack_block->norm = (float)norm;
262 pack_block->offset = offset;
263}
264
265/*******************************************************************************
266 * \brief Private routine for filling send buffers.
267 * \author Ole Schuett
268 ******************************************************************************/
270 const dbm_matrix_t *matrix, const bool trans_matrix, const int nblks_send,
271 const int ndata_send, plan_t plans[nblks_send], const int nranks,
272 int blks_send_count[nranks], int data_send_count[nranks],
273 int blks_send_displ[nranks], int data_send_displ[nranks],
274 dbm_pack_block_t blks_send[nblks_send], double data_send[ndata_send]) {
275 memset(blks_send_count, 0, nranks * sizeof(int));
276 memset(data_send_count, 0, nranks * sizeof(int));
277
278#pragma omp parallel
279 {
280 // 3th pass: Compute per rank nblks and ndata.
281 int nblks_mythread[nranks], ndata_mythread[nranks];
282 memset(nblks_mythread, 0, nranks * sizeof(int));
283 memset(ndata_mythread, 0, nranks * sizeof(int));
284#pragma omp for schedule(static) nowait
285 for (int iblock = 0; iblock < nblks_send; iblock++) {
286 const plan_t *plan = &plans[iblock];
287 nblks_mythread[plan->rank] += 1;
288 ndata_mythread[plan->rank] += plan->row_size * plan->col_size;
289 }
290
291 // Sum nblks and ndata across threads.
292#pragma omp critical
293 for (int irank = 0; irank < nranks; irank++) {
294 blks_send_count[irank] += nblks_mythread[irank];
295 data_send_count[irank] += ndata_mythread[irank];
296 nblks_mythread[irank] = blks_send_count[irank];
297 ndata_mythread[irank] = data_send_count[irank];
298 }
299#pragma omp barrier
300
301 // Compute send displacements.
302#pragma omp single
303 {
304 icumsum(nranks, blks_send_count, blks_send_displ);
305 icumsum(nranks, data_send_count, data_send_displ);
306 const int m = nranks - 1;
307 assert(nblks_send == blks_send_displ[m] + blks_send_count[m]);
308 assert(ndata_send == data_send_displ[m] + data_send_count[m]);
309 }
310
311 // 4th pass: Fill blks_send and data_send arrays.
312#pragma omp for schedule(static) nowait // Match the previous loop.
313 for (int iblock = 0; iblock < nblks_send; iblock++) {
314 const plan_t *const plan = &plans[iblock];
315 const dbm_block_t *const blk = plan->blk;
316 const int ishard = dbm_get_shard_index(matrix, blk->row, blk->col);
317 const dbm_shard_t *const shard = &matrix->shards[ishard];
318 const int row_size = plan->row_size, col_size = plan->col_size;
319 const int plan_size = row_size * col_size;
320 const int irank = plan->rank;
321
322 // The blk_send_data is ordered by rank, thread, and block.
323 // data_send_displ[irank]: Start of data for irank within blk_send_data.
324 // ndata_mythread[irank]: Current threads offset within data for irank.
325 nblks_mythread[irank] -= 1;
326 ndata_mythread[irank] -= plan_size;
327 const int offset = data_send_displ[irank] + ndata_mythread[irank];
328 const int jblock = blks_send_displ[irank] + nblks_mythread[irank];
329
330 copy_pack_block(trans_matrix, blk, row_size, col_size, shard->data,
331 data_send, offset, &blks_send[jblock]);
332
333 // After the block exchange data_recv_displ will be added to the offsets.
334 blks_send[jblock].offset = offset - data_send_displ[irank];
335 }
336 } // end of omp parallel region
337}
338
339/*******************************************************************************
340 * \brief Private comperator passed to qsort to compare two blocks by sum_index.
341 * \author Ole Schuett
342 ******************************************************************************/
343static int compare_pack_blocks_by_sum_index(const void *a, const void *b) {
344 const dbm_pack_block_t *blk_a = (const dbm_pack_block_t *)a;
345 const dbm_pack_block_t *blk_b = (const dbm_pack_block_t *)b;
346 return blk_a->sum_index - blk_b->sum_index;
347}
348
349/*******************************************************************************
350 * \brief Private routine for packing a local matrix directly by target shard.
351 ******************************************************************************/
352static dbm_pack_t pack_local_matrix(const bool trans_matrix,
353 const dbm_matrix_t *matrix,
354 const int nshards, double *seconds_sort) {
355 dbm_pack_t pack = {0};
356 if (dbm_get_num_blocks(matrix) == 0) {
357 return pack;
358 }
359 const int nthreads = omp_get_max_threads();
360 const size_t count = (size_t)nthreads * nshards;
361 int *const workspace = malloc(2 * count * sizeof(int));
362 assert(workspace != NULL);
363 int *const block_offsets = workspace;
364 int *const data_offsets = workspace + count;
365 int shard_start[nshards + 1];
366 double sort_start = 0.0;
367
368#pragma omp parallel
369 {
370 const size_t thread_start = (size_t)omp_get_thread_num() * nshards;
371 int blocks[nshards], data[nshards];
372 memset(blocks, 0, sizeof(blocks));
373 memset(data, 0, sizeof(data));
374 // Count directly by the output's free-index shard; input shards may differ.
375#pragma omp for schedule(static) nowait
376 for (int ishard = 0; ishard < dbm_get_num_shards(matrix); ishard++) {
377 const dbm_shard_t *const shard = &matrix->shards[ishard];
378 for (int i = 0; i < shard->nblocks; i++) {
379 const dbm_block_t *const blk = &shard->blocks[i];
380 const int free_index = trans_matrix ? blk->col : blk->row;
381 const int target = free_index % nshards;
382 blocks[target]++;
383 data[target] +=
384 matrix->row_sizes[blk->row] * matrix->col_sizes[blk->col];
385 }
386 }
387 memcpy(block_offsets + thread_start, blocks, sizeof(blocks));
388 memcpy(data_offsets + thread_start, data, sizeof(data));
389#pragma omp barrier
390
391#pragma omp master
392 {
393 for (int ishard = 0; ishard < nshards; ishard++) {
394 shard_start[ishard] = pack.nblocks;
395 for (int ithread = 0; ithread < omp_get_num_threads(); ithread++) {
396 const size_t i = (size_t)ithread * nshards + ishard;
397 const int nblocks = block_offsets[i], ndata = data_offsets[i];
398 block_offsets[i] = pack.nblocks;
399 data_offsets[i] = pack.data_size;
400 pack.nblocks += nblocks;
401 pack.data_size += ndata;
402 }
403 }
404 shard_start[nshards] = pack.nblocks;
405 pack.blocks =
407 pack.data = allocate_comm_buffer(pack.data_size * sizeof(double));
408 }
409#pragma omp barrier
410 // Keep the frequently updated cursors private to avoid false sharing.
411 memcpy(blocks, block_offsets + thread_start, sizeof(blocks));
412 memcpy(data, data_offsets + thread_start, sizeof(data));
413
414#pragma omp for schedule(static) // Match the counting pass.
415 for (int ishard = 0; ishard < dbm_get_num_shards(matrix); ishard++) {
416 const dbm_shard_t *const shard = &matrix->shards[ishard];
417 for (int i = 0; i < shard->nblocks; i++) {
418 const dbm_block_t *const blk = &shard->blocks[i];
419 const int free_index = trans_matrix ? blk->col : blk->row;
420 const int target = free_index % nshards;
421 const int row_size = matrix->row_sizes[blk->row];
422 const int col_size = matrix->col_sizes[blk->col];
423 copy_pack_block(trans_matrix, blk, row_size, col_size, shard->data,
424 pack.data, data[target],
425 &pack.blocks[blocks[target]++]);
426 data[target] += row_size * col_size;
427 }
428 }
429
430#pragma omp master
431 sort_start = omp_get_wtime();
432#pragma omp barrier
433#pragma omp for nowait
434 for (int ishard = 0; ishard < nshards; ishard++) {
435 const int nblocks = shard_start[ishard + 1] - shard_start[ishard];
436 if (nblocks > 1) {
437 qsort(&pack.blocks[shard_start[ishard]], nblocks,
439 }
440 }
441 }
442
443 *seconds_sort += omp_get_wtime() - sort_start;
444 free(workspace);
445 return pack;
446}
447
448/*******************************************************************************
449 * \brief Private routine for post-processing received blocks.
450 * \author Ole Schuett
451 ******************************************************************************/
453 const int nranks, const int nshards, const int nblocks_recv,
454 const int blks_recv_count[nranks], const int blks_recv_displ[nranks],
455 const int data_recv_displ[nranks],
456 dbm_pack_block_t blks_recv[nblocks_recv]) {
457 if (nblocks_recv == 0) {
458 return;
459 }
460 if (nshards == 1) {
461 for (int irank = 0; irank < nranks; irank++) {
462 for (int i = 0; i < blks_recv_count[irank]; i++) {
463 blks_recv[blks_recv_displ[irank] + i].offset += data_recv_displ[irank];
464 }
465 }
466 if (nblocks_recv > 1) {
467 qsort(blks_recv, nblocks_recv, sizeof(dbm_pack_block_t),
469 }
470 return;
471 }
472
473 int nblocks_per_shard[nshards], shard_start[nshards];
474 memset(nblocks_per_shard, 0, nshards * sizeof(int));
475 dbm_pack_block_t *blocks_tmp =
476 malloc(nblocks_recv * sizeof(dbm_pack_block_t));
477 assert(blocks_tmp != NULL || nblocks_recv == 0);
478
479#pragma omp parallel
480 {
481 // First use counting sort to group blocks by their free_index shard.
482 int nblocks_mythread[nshards];
483 memset(nblocks_mythread, 0, nshards * sizeof(int));
484 int irank = 0;
485#pragma omp for schedule(static) nowait
486 for (int iblock = 0; iblock < nblocks_recv; iblock++) {
487 while (iblock >= blks_recv_displ[irank] + blks_recv_count[irank]) {
488 irank++;
489 }
490 blocks_tmp[iblock] = blks_recv[iblock];
491 blocks_tmp[iblock].offset += data_recv_displ[irank];
492 const int ishard = blks_recv[iblock].free_index % nshards;
493 nblocks_mythread[ishard]++;
494 }
495#pragma omp critical
496 for (int ishard = 0; ishard < nshards; ishard++) {
497 nblocks_per_shard[ishard] += nblocks_mythread[ishard];
498 nblocks_mythread[ishard] = nblocks_per_shard[ishard];
499 }
500#pragma omp barrier
501#pragma omp single
502 icumsum(nshards, nblocks_per_shard, shard_start);
503#pragma omp for schedule(static) // Need static to match previous loop.
504 for (int iblock = 0; iblock < nblocks_recv; iblock++) {
505 const int ishard = blocks_tmp[iblock].free_index % nshards;
506 const int jblock = --nblocks_mythread[ishard] + shard_start[ishard];
507 blks_recv[jblock] = blocks_tmp[iblock];
508 }
509
510 // Then sort blocks within each shard by their sum_index.
511#pragma omp for nowait
512 for (int ishard = 0; ishard < nshards; ishard++) {
513 if (nblocks_per_shard[ishard] > 1) {
514 qsort(&blks_recv[shard_start[ishard]], nblocks_per_shard[ishard],
516 }
517 }
518 } // end of omp parallel region
519
520 free(blocks_tmp);
521}
522
523/*******************************************************************************
524 * \brief Private routine for redistributing a matrix along selected dimensions.
525 * \author Ole Schuett
526 ******************************************************************************/
527static dbm_packed_matrix_t pack_matrix(const bool trans_matrix,
528 const bool trans_dist,
529 const dbm_matrix_t *restrict matrix,
530 const dbm_distribution_t *restrict dist,
531 const int nticks,
532 dbm_comm_iterator_t *iter) {
533 assert(cp_mpi_comms_are_similar(matrix->dist->comm, dist->comm));
534
535 // The row/col indicies are distributed along one cart dimension and the
536 // ticks are distributed along the other cart dimension.
537 const dbm_dist_1d_t *dist_indices = (trans_dist) ? &dist->cols : &dist->rows;
538 const dbm_dist_1d_t *dist_ticks = (trans_dist) ? &dist->rows : &dist->cols;
539 const int *free_index_sizes =
540 (trans_matrix) ? matrix->col_sizes : matrix->row_sizes;
541 const int *sum_index_sizes =
542 (trans_matrix) ? matrix->row_sizes : matrix->col_sizes;
543
544 // Allocate packed matrix.
545 const int nsend_packs = nticks / dist_ticks->nranks;
546 assert(nsend_packs * dist_ticks->nranks == nticks);
547 dbm_packed_matrix_t packed;
548 packed.dist_indices = dist_indices;
549 packed.dist_ticks = dist_ticks;
550 packed.nsend_packs = nsend_packs;
551 packed.send_packs = malloc(nsend_packs * sizeof(dbm_pack_t));
552 assert(packed.send_packs != NULL || nsend_packs == 0);
553
554 if (dist->nranks == 1) {
555 assert(nsend_packs == 1);
556 packed.send_packs[0] = pack_local_matrix(
557 trans_matrix, matrix, dist_indices->nshards, &iter->seconds_sort);
558 packed.recv_pack = (dbm_pack_t){0};
559 packed.max_nblocks = packed.send_packs[0].nblocks;
560 packed.max_data_size = packed.send_packs[0].data_size;
561 return packed;
562 }
563
564 // Plan all packs.
565 plan_t *plans_per_pack[nsend_packs];
566 int nblks_send_per_pack[nsend_packs], ndata_send_per_pack[nsend_packs];
567 create_pack_plans(trans_matrix, trans_dist, matrix, dist->comm, dist_indices,
568 dist_ticks, nticks, nsend_packs, plans_per_pack,
569 nblks_send_per_pack, ndata_send_per_pack);
570
571 // Allocate send buffers for maximum number of blocks/data over all packs.
572 int nblks_send_max = 0, ndata_send_max = 0;
573 for (int ipack = 0; ipack < nsend_packs; ++ipack) {
574 nblks_send_max = imax(nblks_send_max, nblks_send_per_pack[ipack]);
575 ndata_send_max = imax(ndata_send_max, ndata_send_per_pack[ipack]);
576 }
577 dbm_pack_block_t *blks_send =
578 allocate_comm_buffer(nblks_send_max * sizeof(dbm_pack_block_t));
579 double *data_send = allocate_comm_buffer(ndata_send_max * sizeof(double));
580
581 // Cannot parallelize over packs (there might be too few of them).
582 for (int ipack = 0; ipack < nsend_packs; ipack++) {
583 // Fill send buffers according to plans.
584 const int nranks = dist->nranks;
585 int blks_send_count[nranks], data_send_count[nranks];
586 int blks_send_displ[nranks], data_send_displ[nranks];
587 fill_send_buffers(matrix, trans_matrix, nblks_send_per_pack[ipack],
588 ndata_send_per_pack[ipack], plans_per_pack[ipack], nranks,
589 blks_send_count, data_send_count, blks_send_displ,
590 data_send_displ, blks_send, data_send);
591 free(plans_per_pack[ipack]);
592
593 // 1st communication: Exchange block counts.
594 double tick = omp_get_wtime();
595 int blks_recv_count[nranks], blks_recv_displ[nranks];
596 cp_mpi_alltoall_int(blks_send_count, 1, blks_recv_count, 1, dist->comm);
597 icumsum(nranks, blks_recv_count, blks_recv_displ);
598 const int nblocks_recv = isum(nranks, blks_recv_count);
599
600 // 2nd communication: Exchange blocks.
601 dbm_pack_block_t *blks_recv =
602 allocate_comm_buffer(nblocks_recv * sizeof(dbm_pack_block_t));
603 int blks_send_count_byte[nranks], blks_send_displ_byte[nranks];
604 int blks_recv_count_byte[nranks], blks_recv_displ_byte[nranks];
605 for (int i = 0; i < nranks; i++) { // TODO: this is ugly!
606 blks_send_count_byte[i] =
607 checked_byte_count(blks_send_count[i], sizeof(dbm_pack_block_t));
608 blks_send_displ_byte[i] =
609 checked_byte_count(blks_send_displ[i], sizeof(dbm_pack_block_t));
610 blks_recv_count_byte[i] =
611 checked_byte_count(blks_recv_count[i], sizeof(dbm_pack_block_t));
612 blks_recv_displ_byte[i] =
613 checked_byte_count(blks_recv_displ[i], sizeof(dbm_pack_block_t));
614 }
615 for (int i = 0; i < nranks; i++) {
616 iter->bytes_alltoall += blks_send_count_byte[i] +
617 (int64_t)data_send_count[i] * sizeof(double);
618 }
619 cp_mpi_alltoallv_byte(blks_send, blks_send_count_byte, blks_send_displ_byte,
620 blks_recv, blks_recv_count_byte, blks_recv_displ_byte,
621 dist->comm);
622
623 // 3rd compute data counts from the received block metadata.
624 int data_recv_count[nranks], data_recv_displ[nranks];
625 compute_data_recv_count(nranks, blks_recv_count, blks_recv_displ,
626 free_index_sizes, sum_index_sizes, blks_recv,
627 data_recv_count);
628 icumsum(nranks, data_recv_count, data_recv_displ);
629 const int ndata_recv = isum(nranks, data_recv_count);
630
631 // 4th communication: Exchange data.
632 double *data_recv = allocate_comm_buffer(ndata_recv * sizeof(double));
633 cp_mpi_alltoallv_double(data_send, data_send_count, data_send_displ,
634 data_recv, data_recv_count, data_recv_displ,
635 dist->comm);
636
637 // 5th post-process received blocks and assemble them into a pack.
638 const double tock = omp_get_wtime();
639 iter->seconds_alltoall += tock - tick;
640 postprocess_received_blocks(nranks, dist_indices->nshards, nblocks_recv,
641 blks_recv_count, blks_recv_displ,
642 data_recv_displ, blks_recv);
643 iter->seconds_sort += omp_get_wtime() - tock;
644 packed.send_packs[ipack].nblocks = nblocks_recv;
645 packed.send_packs[ipack].data_size = ndata_recv;
646 packed.send_packs[ipack].blocks = blks_recv;
647 packed.send_packs[ipack].data = data_recv;
648 }
649
650 // Deallocate send buffers.
651 free_comm_buffer(blks_send);
652 free_comm_buffer(data_send);
653
654 // Allocate pack_recv.
655 int max_nblocks = 0, max_data_size = 0;
656 for (int ipack = 0; ipack < packed.nsend_packs; ipack++) {
657 max_nblocks = imax(max_nblocks, packed.send_packs[ipack].nblocks);
658 max_data_size = imax(max_data_size, packed.send_packs[ipack].data_size);
659 }
660 const double tick = omp_get_wtime();
661 cp_mpi_max_int(&max_nblocks, 1, packed.dist_ticks->comm);
662 cp_mpi_max_int(&max_data_size, 1, packed.dist_ticks->comm);
663 iter->seconds_alltoall += omp_get_wtime() - tick;
664 packed.max_nblocks = max_nblocks;
665 packed.max_data_size = max_data_size;
666 packed.recv_pack.blocks =
668 packed.recv_pack.data =
669 allocate_comm_buffer(packed.max_data_size * sizeof(double));
670
671 return packed; // Ownership of packed transfers to caller.
672}
673
674/*******************************************************************************
675 * \brief Private routine for sending and receiving the pack for the given tick.
676 * \author Ole Schuett
677 ******************************************************************************/
678static dbm_pack_t *sendrecv_pack(const int itick, const int nticks,
679 dbm_packed_matrix_t *packed, int64_t *bytes) {
680 const int nranks = packed->dist_ticks->nranks;
681 const int my_rank = packed->dist_ticks->my_rank;
682
683 // Compute send rank and pack.
684 const int itick_of_rank0 = (itick + nticks - my_rank) % nticks;
685 const int send_rank = (my_rank + nticks - itick_of_rank0) % nranks;
686 const int send_itick = (itick_of_rank0 + send_rank) % nticks;
687 const int send_ipack = send_itick / nranks;
688 assert(send_itick % nranks == my_rank);
689
690 // Compute receive rank and pack.
691 const int recv_rank = itick % nranks;
692 const int recv_ipack = itick / nranks;
693
694 dbm_pack_t *send_pack = &packed->send_packs[send_ipack];
695 if (send_rank == my_rank) {
696 assert(send_rank == recv_rank && send_ipack == recv_ipack);
697 return send_pack; // Local pack, no mpi needed.
698 } else {
699 *bytes += (int64_t)send_pack->nblocks * sizeof(dbm_pack_block_t) +
700 (int64_t)send_pack->data_size * sizeof(double);
701 // Exchange blocks.
702 const int nblocks_in_bytes = cp_mpi_sendrecv_byte(
703 /*sendbuf=*/send_pack->blocks,
704 /*sendcound=*/
705 checked_byte_count(send_pack->nblocks, sizeof(dbm_pack_block_t)),
706 /*dest=*/send_rank,
707 /*sendtag=*/send_ipack,
708 /*recvbuf=*/packed->recv_pack.blocks,
709 /*recvcount=*/
711 /*source=*/recv_rank,
712 /*recvtag=*/recv_ipack,
713 /*comm=*/packed->dist_ticks->comm);
714
715 assert(nblocks_in_bytes % sizeof(dbm_pack_block_t) == 0);
716 packed->recv_pack.nblocks = nblocks_in_bytes / sizeof(dbm_pack_block_t);
717
718 // Exchange data.
720 /*sendbuf=*/send_pack->data,
721 /*sendcound=*/send_pack->data_size,
722 /*dest=*/send_rank,
723 /*sendtag=*/send_ipack,
724 /*recvbuf=*/packed->recv_pack.data,
725 /*recvcount=*/packed->max_data_size,
726 /*source=*/recv_rank,
727 /*recvtag=*/recv_ipack,
728 /*comm=*/packed->dist_ticks->comm);
729
730 return &packed->recv_pack;
731 }
732}
733
734/*******************************************************************************
735 * \brief Private routine for releasing a packed matrix.
736 * \author Ole Schuett
737 ******************************************************************************/
741 for (int ipack = 0; ipack < packed->nsend_packs; ipack++) {
742 free_comm_buffer(packed->send_packs[ipack].blocks);
743 free_comm_buffer(packed->send_packs[ipack].data);
744 }
745 free(packed->send_packs);
746}
747
748/*******************************************************************************
749 * \brief Internal routine for creating a communication iterator.
750 * \author Ole Schuett
751 ******************************************************************************/
753 const bool transb,
754 const dbm_matrix_t *matrix_a,
755 const dbm_matrix_t *matrix_b,
756 const dbm_matrix_t *matrix_c) {
757 dbm_comm_iterator_t *iter = malloc(sizeof(dbm_comm_iterator_t));
758 assert(iter != NULL);
759 iter->dist = matrix_c->dist;
760
761 // During each communication tick we'll fetch a pack_a and pack_b.
762 // Since the cart might be non-squared, the number of communication ticks is
763 // chosen as the least common multiple of the cart's dimensions.
764 iter->nticks = lcm(iter->dist->rows.nranks, iter->dist->cols.nranks);
765 iter->itick = 0;
766 iter->seconds_alltoall = iter->seconds_sort = 0.0;
767 iter->bytes_alltoall = iter->bytes_shift = 0;
768
769 // 1.arg=source dimension, 2.arg=target dimension, false=rows, true=columns.
770 iter->packed_a =
771 pack_matrix(transa, false, matrix_a, iter->dist, iter->nticks, iter);
772 iter->packed_b =
773 pack_matrix(!transb, true, matrix_b, iter->dist, iter->nticks, iter);
774
775 return iter;
776}
777
778/*******************************************************************************
779 * \brief Internal routine for retrieving next pair of packs of given iterator.
780 * \author Ole Schuett
781 ******************************************************************************/
783 dbm_pack_t **pack_b) {
784 if (iter->itick >= iter->nticks) {
785 return false; // end of iterator reached
786 }
787
788 // Start each rank at a different tick to spread the load on the sources.
789 const int shift = iter->dist->rows.my_rank + iter->dist->cols.my_rank;
790 const int itick = (iter->itick + shift) % iter->nticks;
791 *pack_a =
792 sendrecv_pack(itick, iter->nticks, &iter->packed_a, &iter->bytes_shift);
793 *pack_b =
794 sendrecv_pack(itick, iter->nticks, &iter->packed_b, &iter->bytes_shift);
795
796 ++iter->itick;
797 return true;
798}
799
800/*******************************************************************************
801 * \brief Internal routine for releasing the given communication iterator.
802 * \author Ole Schuett
803 ******************************************************************************/
807 free(iter);
808}
809
810// EOF
void cp_mpi_free_mem(void *mem)
Wrapper around MPI_Free_mem.
Definition cp_mpi.c:638
void cp_mpi_max_int(int *values, const int count, const cp_mpi_comm_t comm)
Wrapper around MPI_Allreduce for op MPI_MAX and datatype MPI_INT.
Definition cp_mpi.c:343
int cp_mpi_sendrecv_byte(const void *sendbuf, const int sendcount, const int dest, const int sendtag, void *recvbuf, const int recvcount, const int source, const int recvtag, const cp_mpi_comm_t comm)
Wrapper around MPI_Sendrecv for datatype MPI_BYTE.
Definition cp_mpi.c:508
void cp_mpi_alltoallv_double(const double *sendbuf, const int *sendcounts, const int *sdispls, double *recvbuf, const int *recvcounts, const int *rdispls, const cp_mpi_comm_t comm)
Wrapper around MPI_Alltoallv for datatype MPI_DOUBLE.
Definition cp_mpi.c:603
int cp_mpi_cart_rank(const cp_mpi_comm_t comm, const int coords[])
Wrapper around MPI_Cart_rank.
Definition cp_mpi.c:279
void * cp_mpi_alloc_mem(size_t size)
Wrapper around MPI_Alloc_mem.
Definition cp_mpi.c:622
void cp_mpi_alltoall_int(const int *sendbuf, const int sendcount, int *recvbuf, const int recvcount, const cp_mpi_comm_t comm)
Wrapper around MPI_Alltoall for datatype MPI_INT.
Definition cp_mpi.c:568
bool cp_mpi_comms_are_similar(const cp_mpi_comm_t comm1, const cp_mpi_comm_t comm2)
Wrapper around MPI_Comm_compare.
Definition cp_mpi.c:326
void cp_mpi_alltoallv_byte(const void *sendbuf, const int *sendcounts, const int *sdispls, void *recvbuf, const int *recvcounts, const int *rdispls, const cp_mpi_comm_t comm)
Wrapper around MPI_Alltoallv for datatype MPI_BYTE.
Definition cp_mpi.c:584
int cp_mpi_sendrecv_double(const double *sendbuf, const int sendcount, const int dest, const int sendtag, double *recvbuf, const int recvcount, const int source, const int recvtag, const cp_mpi_comm_t comm)
Wrapper around MPI_Sendrecv for datatype MPI_DOUBLE.
Definition cp_mpi.c:538
int cp_mpi_comm_t
Definition cp_mpi.h:18
static int imax(int x, int y)
Returns the larger of two given integers (missing from the C standard).
int dbm_get_num_blocks(const dbm_matrix_t *matrix)
Returns the number of local blocks of the given matrix.
Definition dbm_matrix.c:746
static int dbm_get_shard_index(const dbm_matrix_t *matrix, const int row, const int col)
Internal routine for getting a block's shard index.
Definition dbm_matrix.h:253
static int dbm_get_num_shards(const dbm_matrix_t *matrix)
Internal routine that returns the number of shards for given matrix.
Definition dbm_matrix.h:245
static dbm_packed_matrix_t pack_matrix(const bool trans_matrix, const bool trans_dist, const dbm_matrix_t *restrict matrix, const dbm_distribution_t *restrict dist, const int nticks, dbm_comm_iterator_t *iter)
Private routine for redistributing a matrix along selected dimensions.
static void free_packed_matrix(dbm_packed_matrix_t *packed)
Private routine for releasing a packed matrix.
static void icumsum(const int n, const int input[n], int output[n])
Private routine for computing the cumulative sums of given numbers.
static void create_pack_plans(const bool trans_matrix, const bool trans_dist, const dbm_matrix_t *matrix, const cp_mpi_comm_t comm, const dbm_dist_1d_t *dist_indices, const dbm_dist_1d_t *dist_ticks, const int nticks, const int npacks, plan_t *plans_per_pack[npacks], int nblks_per_pack[npacks], int ndata_per_pack[npacks])
Private routine for planing packs.
static void postprocess_received_blocks(const int nranks, const int nshards, const int nblocks_recv, const int blks_recv_count[nranks], const int blks_recv_displ[nranks], const int data_recv_displ[nranks], dbm_pack_block_t blks_recv[nblocks_recv])
Private routine for post-processing received blocks.
dbm_comm_iterator_t * dbm_comm_iterator_start(const bool transa, const bool transb, const dbm_matrix_t *matrix_a, const dbm_matrix_t *matrix_b, const dbm_matrix_t *matrix_c)
Internal routine for creating a communication iterator.
static void fill_send_buffers(const dbm_matrix_t *matrix, const bool trans_matrix, const int nblks_send, const int ndata_send, plan_t plans[nblks_send], const int nranks, int blks_send_count[nranks], int data_send_count[nranks], int blks_send_displ[nranks], int data_send_displ[nranks], dbm_pack_block_t blks_send[nblks_send], double data_send[ndata_send])
Private routine for filling send buffers.
static int gcd(const int a, const int b)
Private routine for computing greatest common divisor of two numbers.
static int lcm(const int a, const int b)
Private routine for computing least common multiple of two numbers.
void dbm_comm_iterator_stop(dbm_comm_iterator_t *iter)
Internal routine for releasing the given communication iterator.
static void * allocate_comm_buffer(const size_t size)
Private routine for allocating a communication buffer, which is taken from the memory pool (DBM_MULTI...
static int compare_pack_blocks_by_sum_index(const void *a, const void *b)
Private comperator passed to qsort to compare two blocks by sum_index.
bool dbm_comm_iterator_next(dbm_comm_iterator_t *iter, dbm_pack_t **pack_a, dbm_pack_t **pack_b)
Internal routine for retrieving next pair of packs of given iterator.
static void free_comm_buffer(void *mem)
Private routine for releasing a buffer from allocate_comm_buffer.
static dbm_pack_t * sendrecv_pack(const int itick, const int nticks, dbm_packed_matrix_t *packed, int64_t *bytes)
Private routine for sending and receiving the pack for the given tick.
static dbm_pack_t pack_local_matrix(const bool trans_matrix, const dbm_matrix_t *matrix, const int nshards, double *seconds_sort)
Private routine for packing a local matrix directly by target shard.
static void copy_pack_block(const bool trans_matrix, const dbm_block_t *blk, const int row_size, const int col_size, const double shard_data[], double pack_data[], const int offset, dbm_pack_block_t *pack_block)
Private routine for copying a block and computing its squared norm.
static unsigned long long calculate_tick_index(int sum_index, int nticks)
Private routine for calculating tick indices in pack plans.
static void compute_data_recv_count(const int nranks, const int blks_recv_count[nranks], const int blks_recv_displ[nranks], const int free_index_sizes[], const int sum_index_sizes[], const dbm_pack_block_t blks_recv[], int data_recv_count[nranks])
Private routine computing received data counts from block metadata.
static int isum(const int n, const int input[n])
Private routine for computing the sum of the given integers.
static int checked_byte_count(const int nelements, const size_t element_size)
Private routine for converting element counts to byte counts.
static void const int const int i
void offload_mempool_host_free(const void *memory)
Internal routine for releasing memory back to the pool.
void * offload_mempool_host_malloc(const size_t size)
Internal routine for allocating host memory from the pool.
Internal struct for storing a block's metadata.
Definition dbm_shard.h:20
Internal struct for storing a communication iterator.
dbm_packed_matrix_t packed_a
dbm_distribution_t * dist
dbm_packed_matrix_t packed_b
Internal struct for storing a one dimensional distribution.
cp_mpi_comm_t comm
Internal struct for storing a two dimensional distribution.
Internal struct for storing a matrix.
Definition dbm_matrix.h:19
int * row_sizes
Definition dbm_matrix.h:24
int * col_sizes
Definition dbm_matrix.h:25
dbm_shard_t * shards
Definition dbm_matrix.h:27
dbm_distribution_t * dist
Definition dbm_matrix.h:20
Internal struct for storing a dbm_block_t plus its norm.
Internal struct for storing a pack - essentially a shard for MPI.
double * data
dbm_pack_block_t * blocks
Internal struct for storing a packed matrix.
const dbm_dist_1d_t * dist_ticks
const dbm_dist_1d_t * dist_indices
Internal struct for storing a matrix shard.
Definition dbm_shard.h:30
double * data
Definition dbm_shard.h:42
dbm_block_t * blocks
Definition dbm_shard.h:33
Private struct used for planing during pack_matrix.
const dbm_block_t * blk