src/smpi/colls/allgatherv-mpich-rdb.c

   1         /* Short or medium size message and power-of-two no. of processes. Use
   2          * recursive doubling algorithm */
   3 #include "colls_private.h"
   4 int smpi_coll_tuned_allgatherv_mpich_rdb (
   5   void *sendbuf,
   6   int sendcount,
   7   MPI_Datatype sendtype,
   8   void *recvbuf,
   9   int *recvcounts,
  10   int *displs,
  11   MPI_Datatype recvtype,
  12   MPI_Comm comm)
  13 {
  14   int        comm_size, rank, j, i;
  15   MPI_Status status;
  16   MPI_Aint  recvtype_extent, recvtype_true_extent, recvtype_true_lb;
  17   int curr_cnt, dst, total_count;
  18   void *tmp_buf;
  19   int mask, dst_tree_root, my_tree_root, position,
  20     send_offset, recv_offset, last_recv_cnt=0, nprocs_completed, k,
  21     offset, tmp_mask, tree_root;
  22
  23   comm_size = smpi_comm_size(comm);
  24   rank = smpi_comm_rank(comm);
  25
  26   total_count = 0;
  27   for (i=0; i<comm_size; i++)
  28     total_count += recvcounts[i];
  29
  30   if (total_count == 0) return MPI_ERR_COUNT;
  31
  32   recvtype_extent=smpi_datatype_get_extent( recvtype);
  33
  34   /* need to receive contiguously into tmp_buf because
  35      displs could make the recvbuf noncontiguous */
  36
  37   smpi_datatype_extent(recvtype, &recvtype_true_lb, &recvtype_true_extent);
  38
  39   tmp_buf= (void*)xbt_malloc(total_count*(max(recvtype_true_extent,recvtype_extent)));
  40
  41   /* adjust for potential negative lower bound in datatype */
  42   tmp_buf = (void *)((char*)tmp_buf - recvtype_true_lb);
  43
  44   /* copy local data into right location in tmp_buf */
  45   position = 0;
  46   for (i=0; i<rank; i++) position += recvcounts[i];
  47   if (sendbuf != MPI_IN_PLACE)
  48   {
  49     smpi_datatype_copy(sendbuf, sendcount, sendtype,
  50                        ((char *)tmp_buf + position*
  51                         recvtype_extent),
  52                        recvcounts[rank], recvtype);
  53   }
  54   else
  55   {
  56     /* if in_place specified, local data is found in recvbuf */
  57     smpi_datatype_copy(((char *)recvbuf +
  58                         displs[rank]*recvtype_extent),
  59                        recvcounts[rank], recvtype,
  60                        ((char *)tmp_buf + position*
  61                         recvtype_extent),
  62                        recvcounts[rank], recvtype);
  63   }
  64   curr_cnt = recvcounts[rank];
  65
  66   mask = 0x1;
  67   i = 0;
  68   while (mask < comm_size) {
  69     dst = rank ^ mask;
  70
  71     /* find offset into send and recv buffers. zero out
  72        the least significant "i" bits of rank and dst to
  73        find root of src and dst subtrees. Use ranks of
  74        roots as index to send from and recv into buffer */
  75
  76     dst_tree_root = dst >> i;
  77     dst_tree_root <<= i;
  78
  79     my_tree_root = rank >> i;
  80     my_tree_root <<= i;
  81
  82     if (dst < comm_size) {
  83       send_offset = 0;
  84       for (j=0; j<my_tree_root; j++)
  85         send_offset += recvcounts[j];
  86
  87       recv_offset = 0;
  88       for (j=0; j<dst_tree_root; j++)
  89         recv_offset += recvcounts[j];
  90
  91       smpi_mpi_sendrecv(((char *)tmp_buf + send_offset * recvtype_extent),
  92                         curr_cnt, recvtype, dst,
  93                         COLL_TAG_ALLGATHERV,
  94                         ((char *)tmp_buf + recv_offset * recvtype_extent),
  95                         total_count - recv_offset, recvtype, dst,
  96                         COLL_TAG_ALLGATHERV,
  97                         comm, &status);
  98       /* for convenience, recv is posted for a bigger amount
  99          than will be sent */
 100       last_recv_cnt=smpi_mpi_get_count(&status, recvtype);
 101       curr_cnt += last_recv_cnt;
 102     }
 103
 104     /* if some processes in this process's subtree in this step
 105        did not have any destination process to communicate with
 106        because of non-power-of-two, we need to send them the
 107        data that they would normally have received from those
 108        processes. That is, the haves in this subtree must send to
 109        the havenots. We use a logarithmic
 110        recursive-halfing algorithm for this. */
 111
 112     /* This part of the code will not currently be
 113        executed because we are not using recursive
 114        doubling for non power of two. Mark it as experimental
 115        so that it doesn't show up as red in the coverage
 116        tests. */
 117
 118     /* --BEGIN EXPERIMENTAL-- */
 119     if (dst_tree_root + mask > comm_size) {
 120       nprocs_completed = comm_size - my_tree_root - mask;
 121       /* nprocs_completed is the number of processes in this
 122          subtree that have all the data. Send data to others
 123          in a tree fashion. First find root of current tree
 124          that is being divided into two. k is the number of
 125          least-significant bits in this process's rank that
 126          must be zeroed out to find the rank of the root */
 127       j = mask;
 128       k = 0;
 129       while (j) {
 130         j >>= 1;
 131         k++;
 132       }
 133       k--;
 134
 135       tmp_mask = mask >> 1;
 136
 137       while (tmp_mask) {
 138         dst = rank ^ tmp_mask;
 139
 140         tree_root = rank >> k;
 141         tree_root <<= k;
 142
 143         /* send only if this proc has data and destination
 144            doesn't have data. at any step, multiple processes
 145            can send if they have the data */
 146         if ((dst > rank) &&
 147             (rank < tree_root + nprocs_completed)
 148             && (dst >= tree_root + nprocs_completed)) {
 149
 150           offset = 0;
 151           for (j=0; j<(my_tree_root+mask); j++)
 152             offset += recvcounts[j];
 153           offset *= recvtype_extent;
 154
 155           smpi_mpi_send(((char *)tmp_buf + offset),
 156                         last_recv_cnt,
 157                         recvtype, dst,
 158                         COLL_TAG_ALLGATHERV, comm);
 159           /* last_recv_cnt was set in the previous
 160              receive. that's the amount of data to be
 161              sent now. */
 162         }
 163         /* recv only if this proc. doesn't have data and sender
 164            has data */
 165         else if ((dst < rank) &&
 166                  (dst < tree_root + nprocs_completed) &&
 167                  (rank >= tree_root + nprocs_completed)) {
 168
 169           offset = 0;
 170           for (j=0; j<(my_tree_root+mask); j++)
 171             offset += recvcounts[j];
 172
 173           smpi_mpi_recv(((char *)tmp_buf + offset * recvtype_extent),
 174                         total_count - offset, recvtype,
 175                         dst, COLL_TAG_ALLGATHERV,
 176                         comm, &status);
 177           /* for convenience, recv is posted for a
 178              bigger amount than will be sent */
 179           last_recv_cnt=smpi_mpi_get_count(&status, recvtype);
 180           curr_cnt += last_recv_cnt;
 181         }
 182         tmp_mask >>= 1;
 183         k--;
 184       }
 185     }
 186     /* --END EXPERIMENTAL-- */
 187
 188     mask <<= 1;
 189     i++;
 190   }
 191
 192   /* copy data from tmp_buf to recvbuf */
 193   position = 0;
 194   for (j=0; j<comm_size; j++) {
 195     if ((sendbuf != MPI_IN_PLACE) || (j != rank)) {
 196       /* not necessary to copy if in_place and
 197          j==rank. otherwise copy. */
 198       smpi_datatype_copy(((char *)tmp_buf + position*recvtype_extent),
 199                          recvcounts[j], recvtype,
 200                          ((char *)recvbuf + displs[j]*recvtype_extent),
 201                          recvcounts[j], recvtype);
 202     }
 203     position += recvcounts[j];
 204   }
 205
 206   free(tmp_buf);
 207   return MPI_SUCCESS;
 208 }