From 99bde1993c8efb16eb5718d6bcbea17a06126d97 Mon Sep 17 00:00:00 2001
From: Peter Munch <peterrmuench@gmail.com>
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<T> 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