From 99bde1993c8efb16eb5718d6bcbea17a06126d97 Mon Sep 17 00:00:00 2001 From: Peter Munch Date: Mon, 15 Feb 2021 12:19:32 +0100 Subject: [PATCH] Improve complexity of compute_set_union --- include/deal.II/base/mpi.templates.h | 39 +++++++++++++++++----------- 1 file changed, 24 insertions(+), 15 deletions(-) diff --git a/include/deal.II/base/mpi.templates.h b/include/deal.II/base/mpi.templates.h index e429a076b4..0cb0fa0f4d 100644 --- a/include/deal.II/base/mpi.templates.h +++ b/include/deal.II/base/mpi.templates.h @@ -424,12 +424,21 @@ namespace Utilities // 1) collect vector entries and create union std::vector result = vec; - if (this_mpi_process(comm) == 0) + const unsigned int rank = this_mpi_process(comm); + const unsigned int nproc = n_mpi_processes(comm); + + for (unsigned int stride = 1; stride < nproc; stride *= 2) { - for (unsigned int i = 1; i < n_mpi_processes(comm); i++) + const unsigned int rank_recv = (2 * stride) * (rank / (2 * stride)); + const unsigned int rank_send = rank_recv + stride; + + if (rank_send >= nproc) // nothing to do + continue; + + if (rank_recv == rank) // process receives data { MPI_Status status; - const auto ierr_1 = MPI_Probe(MPI_ANY_SOURCE, + const auto ierr_1 = MPI_Probe(rank_send, internal::Tags::compute_union, comm, &status); @@ -438,7 +447,7 @@ namespace Utilities int amount; const auto ierr_2 = MPI_Get_count(&status, - internal::mpi_type_id(vec.data()), + internal::mpi_type_id(result.data()), &amount); AssertThrowMPI(ierr_2); @@ -447,7 +456,7 @@ namespace Utilities const auto ierr_3 = MPI_Recv(result.data() + old_size, amount, - internal::mpi_type_id(vec.data()), + internal::mpi_type_id(result.data()), status.MPI_SOURCE, status.MPI_TAG, comm, @@ -458,16 +467,16 @@ namespace Utilities result.erase(std::unique(result.begin(), result.end()), result.end()); } - } - else - { - const auto ierr = MPI_Send(vec.data(), - vec.size(), - internal::mpi_type_id(vec.data()), - 0, - internal::Tags::compute_union, - comm); - AssertThrowMPI(ierr); + else if (rank_send == rank) // process sends data + { + const auto ierr = MPI_Send(result.data(), + result.size(), + internal::mpi_type_id(result.data()), + rank_recv, + internal::Tags::compute_union, + comm); + AssertThrowMPI(ierr); + } } // 2) broadcast result -- 2.39.5