src/smpi/colls/bcast/bcast-ompi-split-bintree.cpp

   1 /* Copyright (c) 2013-2023. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 /*
   8  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   9  *                         University Research and Technology
  10  *                         Corporation.  All rights reserved.
  11  * Copyright (c) 2004-2009 The University of Tennessee and The University
  12  *                         of Tennessee Research Foundation.  All rights
  13  *                         reserved.
  14  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
  15  *                         University of Stuttgart.  All rights reserved.
  16  * Copyright (c) 2004-2005 The Regents of the University of California.
  17  *                         All rights reserved.
  18  * Copyright (c) 2009      University of Houston. All rights reserved.
  19  *
  20  * Additional copyrights may follow
  21  *
  22  *  Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions are
  24  * met:
  25
  26  * - Redistributions of source code must retain the above copyright
  27  *   notice, this list of conditions and the following disclaimer.
  28
  29  * - Redistributions in binary form must reproduce the above copyright
  30  *   notice, this list of conditions and the following disclaimer listed
  31  *   in this license in the documentation and/or other materials
  32  *   provided with the distribution.
  33
  34  * - Neither the name of the copyright holders nor the names of its
  35  *   contributors may be used to endorse or promote products derived from
  36  *   this software without specific prior written permission.
  37
  38  * The copyright holders provide no reassurances that the source code
  39  * provided does not infringe any patent, copyright, or any other
  40  * intellectual property rights of third parties.  The copyright holders
  41  * disclaim any liability to any recipient for claims brought against
  42  * recipient by any third party for infringement of that parties
  43  * intellectual property rights.
  44
  45  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  46  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  47  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  48  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  49  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  50  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  51  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  52  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  53  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  54  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  55  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  56  */
  57
  58 #include "../coll_tuned_topo.hpp"
  59 #include "../colls_private.hpp"
  60 #define MAXTREEFANOUT 32
  61 namespace simgrid::smpi {
  62
  63 int bcast__ompi_split_bintree( void* buffer,
  64                                int count,
  65                                MPI_Datatype datatype,
  66                                int root,
  67                                MPI_Comm comm)
  68 {
  69     unsigned int segsize ;
  70     int rank, size;
  71     int segindex, i, lr, pair;
  72     int segcount[2];       /* Number ompi_request_wait_allof elements sent with each segment */
  73     uint32_t counts[2];
  74     int num_segments[2];   /* Number of segments */
  75     int sendcount[2];      /* the same like segcount, except for the last segment */
  76     size_t realsegsize[2];
  77     char *tmpbuf[2];
  78     size_t type_size;
  79     ptrdiff_t type_extent;
  80
  81
  82     MPI_Request base_req, new_req;
  83     ompi_coll_tree_t *tree;
  84 //    mca_coll_tuned_module_t *tuned_module = (mca_coll_tuned_module_t*) module;
  85 //    mca_coll_tuned_comm_t *data = tuned_module->tuned_data;
  86
  87     size = comm->size();
  88     rank = comm->rank();
  89
  90
  91     //compute again segsize
  92     const size_t intermediate_message_size = 370728;
  93     size_t message_size = datatype->size() * (unsigned long)count;
  94     if(message_size < intermediate_message_size)
  95       segsize = 1024 ;
  96     else
  97       segsize = 1024 << 3;
  98
  99     XBT_DEBUG("ompi_coll_tuned_bcast_intra_split_bintree rank %d root %d ss %5u", rank, root, segsize);
 100
 101     if (size == 1) {
 102         return MPI_SUCCESS;
 103     }
 104
 105     /* setup the binary tree topology. */
 106     tree = ompi_coll_tuned_topo_build_tree(2,comm,root);
 107
 108     type_size = datatype->size();
 109
 110     /* Determine number of segments and number of elements per segment */
 111     counts[0] = count/2;
 112     if (count % 2 != 0) counts[0]++;
 113     counts[1] = count - counts[0];
 114
 115     /* Note that ompi_datatype_type_size() will never return a negative
 116        value in typelng; it returns an int [vs. an unsigned type]
 117        because of the MPI spec. */
 118     if (segsize < ((uint32_t)type_size)) {
 119       segsize = type_size; /* push segsize up to hold one type */
 120     }
 121     segcount[0] = segcount[1] = segsize / type_size;
 122     num_segments[0]           = counts[0] / segcount[0];
 123     if ((counts[0] % segcount[0]) != 0)
 124       num_segments[0]++;
 125     num_segments[1] = counts[1] / segcount[1];
 126     if ((counts[1] % segcount[1]) != 0)
 127       num_segments[1]++;
 128
 129     /* if the message is too small to be split into segments */
 130     if( (counts[0] == 0 || counts[1] == 0) ||
 131         (segsize > counts[0] * type_size) ||
 132         (segsize > counts[1] * type_size) ) {
 133         /* call linear version here ! */
 134         return bcast__SMP_linear( buffer, count, datatype, root, comm);
 135     }
 136     type_extent = datatype->get_extent();
 137
 138
 139     /* Determine real segment size */
 140     realsegsize[0] = segcount[0] * type_extent;
 141     realsegsize[1] = segcount[1] * type_extent;
 142
 143     /* set the buffer pointers */
 144     tmpbuf[0] = (char *) buffer;
 145     tmpbuf[1] = (char *) buffer+counts[0] * type_extent;
 146
 147     /* Step 1:
 148        Root splits the buffer in 2 and sends segmented message down the branches.
 149        Left subtree of the tree receives first half of the buffer, while right
 150        subtree receives the remaining message.
 151     */
 152
 153     /* determine if I am left (0) or right (1), (root is right) */
 154     lr = ((rank + size - root)%size + 1)%2;
 155
 156     /* root code */
 157     if( rank == root ) {
 158         /* determine segment count */
 159         sendcount[0] = segcount[0];
 160         sendcount[1] = segcount[1];
 161         /* for each segment */
 162         for (segindex = 0; segindex < num_segments[0]; segindex++) {
 163             /* for each child */
 164             for( i = 0; i < tree->tree_nextsize && i < 2; i++ ) {
 165                 if (segindex >= num_segments[i]) { /* no more segments */
 166                     continue;
 167                 }
 168                 /* determine how many elements are being sent in this round */
 169                 if(segindex == (num_segments[i] - 1))
 170                     sendcount[i] = counts[i] - segindex*segcount[i];
 171                 /* send data */
 172                 Request::send(tmpbuf[i], sendcount[i], datatype,
 173                                   tree->tree_next[i], COLL_TAG_BCAST, comm);
 174                 /* update tmp buffer */
 175                 tmpbuf[i] += realsegsize[i];
 176             }
 177         }
 178     }
 179
 180     /* intermediate nodes code */
 181     else if( tree->tree_nextsize > 0 ) {
 182       /* Intermediate nodes:
 183        * It will receive segments only from one half of the data.
 184        * Which one is determined by whether the node belongs to the "left" or "right"
 185        * subtree. Topology building function builds binary tree such that
 186        * odd "shifted ranks" ((rank + size - root)%size) are on the left subtree,
 187        * and even on the right subtree.
 188        *
 189        * Create the pipeline. We first post the first receive, then in the loop we
 190        * post the next receive and after that wait for the previous receive to complete
 191        * and we disseminating the data to all children.
 192        */
 193       sendcount[lr] = segcount[lr];
 194       base_req      = Request::irecv(tmpbuf[lr], sendcount[lr], datatype, tree->tree_prev, COLL_TAG_BCAST, comm);
 195
 196       for (segindex = 1; segindex < num_segments[lr]; segindex++) {
 197         /* determine how many elements to expect in this round */
 198         if (segindex == (num_segments[lr] - 1))
 199           sendcount[lr] = counts[lr] - segindex * segcount[lr];
 200         /* post new irecv */
 201         new_req = Request::irecv(tmpbuf[lr] + realsegsize[lr], sendcount[lr], datatype, tree->tree_prev, COLL_TAG_BCAST,
 202                                  comm);
 203
 204         /* wait for and forward current segment */
 205         Request::waitall(1, &base_req, MPI_STATUSES_IGNORE);
 206         for (i = 0; i < tree->tree_nextsize; i++) { /* send data to children (segcount[lr]) */
 207           Request::send(tmpbuf[lr], segcount[lr], datatype, tree->tree_next[i], COLL_TAG_BCAST, comm);
 208         } /* end of for each child */
 209
 210         /* update the base request */
 211         base_req = new_req;
 212         /* go to the next buffer (ie. the one corresponding to the next recv) */
 213         tmpbuf[lr] += realsegsize[lr];
 214         } /* end of for segindex */
 215
 216         /* wait for the last segment and forward current segment */
 217         Request::waitall( 1, &base_req, MPI_STATUSES_IGNORE );
 218         for( i = 0; i < tree->tree_nextsize; i++ ) {  /* send data to children */
 219             Request::send(tmpbuf[lr], sendcount[lr], datatype,
 220                               tree->tree_next[i], COLL_TAG_BCAST, comm);
 221         } /* end of for each child */
 222     }
 223
 224     /* leaf nodes */
 225     else {
 226         /* Just consume segments as fast as possible */
 227         sendcount[lr] = segcount[lr];
 228         for (segindex = 0; segindex < num_segments[lr]; segindex++) {
 229             /* determine how many elements to expect in this round */
 230             if (segindex == (num_segments[lr] - 1)) sendcount[lr] = counts[lr] - segindex*segcount[lr];
 231             /* receive segments */
 232             Request::recv(tmpbuf[lr], sendcount[lr], datatype,
 233                               tree->tree_prev, COLL_TAG_BCAST,
 234                               comm, MPI_STATUS_IGNORE);
 235             /* update the initial pointer to the buffer */
 236             tmpbuf[lr] += realsegsize[lr];
 237         }
 238     }
 239
 240     /* reset the buffer pointers */
 241     tmpbuf[0] = (char *) buffer;
 242     tmpbuf[1] = (char *) buffer+counts[0] * type_extent;
 243
 244     /* Step 2:
 245        Find your immediate pair (identical node in opposite subtree) and SendRecv
 246        data buffer with them.
 247        The tree building function ensures that
 248        if (we are not root)
 249        if we are in the left subtree (lr == 0) our pair is (rank+1)%size.
 250        if we are in the right subtree (lr == 1) our pair is (rank-1)%size
 251        If we have even number of nodes the rank (size-1) will pair up with root.
 252     */
 253     if (lr == 0) {
 254         pair = (rank+1)%size;
 255     } else {
 256         pair = (rank+size-1)%size;
 257     }
 258
 259     if ( (size%2) != 0 && rank != root) {
 260
 261         Request::sendrecv( tmpbuf[lr], counts[lr], datatype,
 262                                         pair, COLL_TAG_BCAST,
 263                                         tmpbuf[(lr+1)%2], counts[(lr+1)%2], datatype,
 264                                         pair, COLL_TAG_BCAST,
 265                                         comm, MPI_STATUS_IGNORE);
 266     } else if ( (size%2) == 0 ) {
 267         /* root sends right buffer to the last node */
 268         if( rank == root ) {
 269             Request::send(tmpbuf[1], counts[1], datatype,
 270                               (root+size-1)%size, COLL_TAG_BCAST, comm);
 271
 272         }
 273         /* last node receives right buffer from the root */
 274         else if (rank == (root+size-1)%size) {
 275             Request::recv(tmpbuf[1], counts[1], datatype,
 276                               root, COLL_TAG_BCAST,
 277                               comm, MPI_STATUS_IGNORE);
 278         }
 279         /* everyone else exchanges buffers */
 280         else {
 281             Request::sendrecv( tmpbuf[lr], counts[lr], datatype,
 282                                             pair, COLL_TAG_BCAST,
 283                                             tmpbuf[(lr+1)%2], counts[(lr+1)%2], datatype,
 284                                             pair, COLL_TAG_BCAST,
 285                                             comm, MPI_STATUS_IGNORE);
 286         }
 287     }
 288     ompi_coll_tuned_topo_destroy_tree(&tree);
 289     return (MPI_SUCCESS);
 290
 291
 292 }
 293
 294 } // namespace simgrid::smpi