18#define DBM_MULTIPLY_COMM_MEMPOOL
28#if defined(DBM_MULTIPLY_COMM_MEMPOOL)
40#if defined(DBM_MULTIPLY_COMM_MEMPOOL)
51static int gcd(
const int a,
const int b) {
62static int lcm(
const int a,
const int b) {
return (a * b) /
gcd(a, b); }
71 assert(0 <= nelements);
72 assert(element_size <= INT_MAX);
73 assert(nelements <= INT_MAX / (
int)element_size);
74 return nelements * (int)element_size;
81static inline int isum(
const int n,
const int input[n]) {
83 for (
int i = 0;
i < n;
i++) {
93static inline void icumsum(
const int n,
const int input[n],
int output[n]) {
96 int oval = output[0] = 0, ival = input[0];
97 for (
int i = 1;
i < n;
i++) {
98 output[
i] = (oval += ival);
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[],
113 int data_recv_count[nranks]) {
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++) {
120 &blks_recv[blks_recv_displ[irank] +
i];
121 const int block_size =
123 assert(block_size >= 0);
124 assert(data_recv_count[irank] <= INT_MAX - block_size);
125 data_recv_count[irank] += block_size;
148 return ((
unsigned long long)sum_index * 1021ULL) % (
unsigned long long)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));
169 int nblks_mythread[npacks];
170 memset(nblks_mythread, 0, npacks *
sizeof(
int));
171#pragma omp for schedule(static) nowait
174 for (
int iblock = 0; iblock < shard->
nblocks; iblock++) {
176 const int sum_index = (trans_matrix) ? blk->
row : blk->
col;
178 const int ipack = itick64 / dist_ticks->
nranks;
179 nblks_mythread[ipack]++;
185 for (
int ipack = 0; ipack < npacks; ipack++) {
186 nblks_per_pack[ipack] += nblks_mythread[ipack];
187 nblks_mythread[ipack] = nblks_per_pack[ipack];
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);
198 int ndata_mythread[npacks];
199 memset(ndata_mythread, 0, npacks *
sizeof(
int));
200#pragma omp for schedule(static) nowait
203 for (
int iblock = 0; iblock < shard->
nblocks; iblock++) {
205 const int free_index = (trans_matrix) ? blk->
col : blk->
row;
206 const int sum_index = (trans_matrix) ? blk->
row : blk->
col;
208 const int ipack = itick64 / dist_ticks->
nranks;
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};
217 ndata_mythread[ipack] += row_size * col_size;
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;
227 for (
int ipack = 0; ipack < npacks; ipack++) {
228 ndata_per_pack[ipack] += ndata_mythread[ipack];
237 const int row_size,
const int col_size,
238 const double shard_data[],
double pack_data[],
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;
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;
261 pack_block->
norm = (float)norm;
262 pack_block->
offset = offset;
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],
275 memset(blks_send_count, 0, nranks *
sizeof(
int));
276 memset(data_send_count, 0, nranks *
sizeof(
int));
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;
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];
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]);
312#pragma omp for schedule(static) nowait
313 for (
int iblock = 0; iblock < nblks_send; iblock++) {
314 const plan_t *
const plan = &plans[iblock];
319 const int plan_size = row_size * col_size;
320 const int irank = plan->
rank;
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];
331 data_send, offset, &blks_send[jblock]);
334 blks_send[jblock].offset = offset - data_send_displ[irank];
354 const int nshards,
double *seconds_sort) {
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;
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));
375#pragma omp for schedule(static) nowait
380 const int free_index = trans_matrix ? blk->
col : blk->
row;
381 const int target = free_index % nshards;
387 memcpy(block_offsets + thread_start, blocks,
sizeof(blocks));
388 memcpy(data_offsets + thread_start, data,
sizeof(data));
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];
404 shard_start[nshards] = pack.
nblocks;
411 memcpy(blocks, block_offsets + thread_start,
sizeof(blocks));
412 memcpy(data, data_offsets + thread_start,
sizeof(data));
414#pragma omp for schedule(static)
419 const int free_index = trans_matrix ? blk->
col : blk->
row;
420 const int target = free_index % nshards;
424 pack.
data, data[target],
425 &pack.
blocks[blocks[target]++]);
426 data[target] += row_size * col_size;
431 sort_start = omp_get_wtime();
433#pragma omp for nowait
434 for (
int ishard = 0; ishard < nshards; ishard++) {
435 const int nblocks = shard_start[ishard + 1] - shard_start[ishard];
437 qsort(&pack.
blocks[shard_start[ishard]], nblocks,
443 *seconds_sort += omp_get_wtime() - sort_start;
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],
457 if (nblocks_recv == 0) {
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];
466 if (nblocks_recv > 1) {
473 int nblocks_per_shard[nshards], shard_start[nshards];
474 memset(nblocks_per_shard, 0, nshards *
sizeof(
int));
477 assert(blocks_tmp != NULL || nblocks_recv == 0);
482 int nblocks_mythread[nshards];
483 memset(nblocks_mythread, 0, nshards *
sizeof(
int));
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]) {
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]++;
496 for (
int ishard = 0; ishard < nshards; ishard++) {
497 nblocks_per_shard[ishard] += nblocks_mythread[ishard];
498 nblocks_mythread[ishard] = nblocks_per_shard[ishard];
502 icumsum(nshards, nblocks_per_shard, shard_start);
503#pragma omp for schedule(static)
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];
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],
528 const bool trans_dist,
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;
545 const int nsend_packs = nticks / dist_ticks->
nranks;
546 assert(nsend_packs * dist_ticks->
nranks == nticks);
552 assert(packed.
send_packs != NULL || nsend_packs == 0);
554 if (dist->nranks == 1) {
555 assert(nsend_packs == 1);
565 plan_t *plans_per_pack[nsend_packs];
566 int nblks_send_per_pack[nsend_packs], ndata_send_per_pack[nsend_packs];
568 dist_ticks, nticks, nsend_packs, plans_per_pack,
569 nblks_send_per_pack, ndata_send_per_pack);
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]);
582 for (
int ipack = 0; ipack < nsend_packs; ipack++) {
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];
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]);
594 double tick = omp_get_wtime();
595 int blks_recv_count[nranks], blks_recv_displ[nranks];
597 icumsum(nranks, blks_recv_count, blks_recv_displ);
598 const int nblocks_recv =
isum(nranks, blks_recv_count);
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++) {
606 blks_send_count_byte[
i] =
608 blks_send_displ_byte[
i] =
610 blks_recv_count_byte[
i] =
612 blks_recv_displ_byte[
i] =
615 for (
int i = 0;
i < nranks;
i++) {
617 (int64_t)data_send_count[
i] *
sizeof(
double);
620 blks_recv, blks_recv_count_byte, blks_recv_displ_byte,
624 int data_recv_count[nranks], data_recv_displ[nranks];
626 free_index_sizes, sum_index_sizes, blks_recv,
628 icumsum(nranks, data_recv_count, data_recv_displ);
629 const int ndata_recv =
isum(nranks, data_recv_count);
634 data_recv, data_recv_count, data_recv_displ,
638 const double tock = omp_get_wtime();
641 blks_recv_count, blks_recv_displ,
642 data_recv_displ, blks_recv);
655 int max_nblocks = 0, max_data_size = 0;
656 for (
int ipack = 0; ipack < packed.
nsend_packs; ipack++) {
660 const double tick = omp_get_wtime();
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);
691 const int recv_rank = itick % nranks;
692 const int recv_ipack = itick / nranks;
695 if (send_rank == my_rank) {
696 assert(send_rank == recv_rank && send_ipack == recv_ipack);
700 (int64_t)send_pack->
data_size *
sizeof(
double);
741 for (
int ipack = 0; ipack < packed->
nsend_packs; ipack++) {
758 assert(iter != NULL);
790 const int itick = (iter->
itick + shift) % iter->
nticks;
void cp_mpi_free_mem(void *mem)
Wrapper around MPI_Free_mem.
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.
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.
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.
int cp_mpi_cart_rank(const cp_mpi_comm_t comm, const int coords[])
Wrapper around MPI_Cart_rank.
void * cp_mpi_alloc_mem(size_t size)
Wrapper around MPI_Alloc_mem.
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.
bool cp_mpi_comms_are_similar(const cp_mpi_comm_t comm1, const cp_mpi_comm_t comm2)
Wrapper around MPI_Comm_compare.
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.
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.
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.
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.
static int dbm_get_num_shards(const dbm_matrix_t *matrix)
Internal routine that returns the number of shards for given matrix.
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.
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.
Internal struct for storing a two dimensional distribution.
Internal struct for storing a matrix.
dbm_distribution_t * dist
Internal struct for storing a dbm_block_t plus its norm.
Internal struct for storing a pack - essentially a shard for MPI.
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.
Private struct used for planing during pack_matrix.