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

   1 /* Copyright (c) 2013-2021. 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 {
  62 namespace smpi {
  63
  64 int bcast__ompi_split_bintree( void* buffer,
  65                                int count,
  66                                MPI_Datatype datatype,
  67                                int root,
  68                                MPI_Comm comm)
  69 {
  70     unsigned int segsize ;
  71     int rank, size;
  72     int segindex, i, lr, pair;
  73     int segcount[2];       /* Number ompi_request_wait_allof elements sent with each segment */
  74     uint32_t counts[2];
  75     int num_segments[2];   /* Number of segments */
  76     int sendcount[2];      /* the same like segcount, except for the last segment */
  77     size_t realsegsize[2];
  78     char *tmpbuf[2];
  79     size_t type_size;
  80     ptrdiff_t type_extent;
  81
  82
  83     MPI_Request base_req, new_req;
  84     ompi_coll_tree_t *tree;
  85 //    mca_coll_tuned_module_t *tuned_module = (mca_coll_tuned_module_t*) module;
  86 //    mca_coll_tuned_comm_t *data = tuned_module->tuned_data;
  87
  88     size = comm->size();
  89     rank = comm->rank();
  90
  91
  92     //compute again segsize
  93     const size_t intermediate_message_size = 370728;
  94     size_t message_size = datatype->size() * (unsigned long)count;
  95     if(message_size < intermediate_message_size)
  96       segsize = 1024 ;
  97     else
  98       segsize = 1024 << 3;
  99
 100     XBT_DEBUG("ompi_coll_tuned_bcast_intra_split_bintree rank %d root %d ss %5u", rank, root, segsize);
 101
 102     if (size == 1) {
 103         return MPI_SUCCESS;
 104     }
 105
 106     /* setup the binary tree topology. */
 107     tree = ompi_coll_tuned_topo_build_tree(2,comm,root);
 108
 109     type_size = datatype->size();
 110
 111     /* Determine number of segments and number of elements per segment */
 112     counts[0] = count/2;
 113     if (count % 2 != 0) counts[0]++;
 114     counts[1] = count - counts[0];
 115
 116     /* Note that ompi_datatype_type_size() will never return a negative
 117        value in typelng; it returns an int [vs. an unsigned type]
 118        because of the MPI spec. */
 119     if (segsize < ((uint32_t)type_size)) {
 120       segsize = type_size; /* push segsize up to hold one type */
 121     }
 122     segcount[0] = segcount[1] = segsize / type_size;
 123     num_segments[0]           = counts[0] / segcount[0];
 124     if ((counts[0] % segcount[0]) != 0)
 125       num_segments[0]++;
 126     num_segments[1] = counts[1] / segcount[1];
 127     if ((counts[1] % segcount[1]) != 0)
 128       num_segments[1]++;
 129
 130     /* if the message is too small to be split into segments */
 131     if( (counts[0] == 0 || counts[1] == 0) ||
 132         (segsize > counts[0] * type_size) ||
 133         (segsize > counts[1] * type_size) ) {
 134         /* call linear version here ! */
 135         return bcast__SMP_linear( buffer, count, datatype, root, comm);
 136     }
 137     type_extent = datatype->get_extent();
 138
 139
 140     /* Determine real segment size */
 141     realsegsize[0] = segcount[0] * type_extent;
 142     realsegsize[1] = segcount[1] * type_extent;
 143
 144     /* set the buffer pointers */
 145     tmpbuf[0] = (char *) buffer;
 146     tmpbuf[1] = (char *) buffer+counts[0] * type_extent;
 147
 148     /* Step 1:
 149        Root splits the buffer in 2 and sends segmented message down the branches.
 150        Left subtree of the tree receives first half of the buffer, while right
 151        subtree receives the remaining message.
 152     */
 153
 154     /* determine if I am left (0) or right (1), (root is right) */
 155     lr = ((rank + size - root)%size + 1)%2;
 156
 157     /* root code */
 158     if( rank == root ) {
 159         /* determine segment count */
 160         sendcount[0] = segcount[0];
 161         sendcount[1] = segcount[1];
 162         /* for each segment */
 163         for (segindex = 0; segindex < num_segments[0]; segindex++) {
 164             /* for each child */
 165             for( i = 0; i < tree->tree_nextsize && i < 2; i++ ) {
 166                 if (segindex >= num_segments[i]) { /* no more segments */
 167                     continue;
 168                 }
 169                 /* determine how many elements are being sent in this round */
 170                 if(segindex == (num_segments[i] - 1))
 171                     sendcount[i] = counts[i] - segindex*segcount[i];
 172                 /* send data */
 173                 Request::send(tmpbuf[i], sendcount[i], datatype,
 174                                   tree->tree_next[i], COLL_TAG_BCAST, comm);
 175                 /* update tmp buffer */
 176                 tmpbuf[i] += realsegsize[i];
 177             }
 178         }
 179     }
 180
 181     /* intermediate nodes code */
 182     else if( tree->tree_nextsize > 0 ) {
 183       /* Intermediate nodes:
 184        * It will receive segments only from one half of the data.
 185        * Which one is determined by whether the node belongs to the "left" or "right"
 186        * subtree. Topology building function builds binary tree such that
 187        * odd "shifted ranks" ((rank + size - root)%size) are on the left subtree,
 188        * and even on the right subtree.
 189        *
 190        * Create the pipeline. We first post the first receive, then in the loop we
 191        * post the next receive and after that wait for the previous receive to complete
 192        * and we disseminating the data to all children.
 193        */
 194       sendcount[lr] = segcount[lr];
 195       base_req      = Request::irecv(tmpbuf[lr], sendcount[lr], datatype, tree->tree_prev, COLL_TAG_BCAST, comm);
 196
 197       for (segindex = 1; segindex < num_segments[lr]; segindex++) {
 198         /* determine how many elements to expect in this round */
 199         if (segindex == (num_segments[lr] - 1))
 200           sendcount[lr] = counts[lr] - segindex * segcount[lr];
 201         /* post new irecv */
 202         new_req = Request::irecv(tmpbuf[lr] + realsegsize[lr], sendcount[lr], datatype, tree->tree_prev, COLL_TAG_BCAST,
 203                                  comm);
 204
 205         /* wait for and forward current segment */
 206         Request::waitall(1, &base_req, MPI_STATUSES_IGNORE);
 207         for (i = 0; i < tree->tree_nextsize; i++) { /* send data to children (segcount[lr]) */
 208           Request::send(tmpbuf[lr], segcount[lr], datatype, tree->tree_next[i], COLL_TAG_BCAST, comm);
 209         } /* end of for each child */
 210
 211         /* update the base request */
 212         base_req = new_req;
 213         /* go to the next buffer (ie. the one corresponding to the next recv) */
 214         tmpbuf[lr] += realsegsize[lr];
 215         } /* end of for segindex */
 216
 217         /* wait for the last segment and forward current segment */
 218         Request::waitall( 1, &base_req, MPI_STATUSES_IGNORE );
 219         for( i = 0; i < tree->tree_nextsize; i++ ) {  /* send data to children */
 220             Request::send(tmpbuf[lr], sendcount[lr], datatype,
 221                               tree->tree_next[i], COLL_TAG_BCAST, comm);
 222         } /* end of for each child */
 223     }
 224
 225     /* leaf nodes */
 226     else {
 227         /* Just consume segments as fast as possible */
 228         sendcount[lr] = segcount[lr];
 229         for (segindex = 0; segindex < num_segments[lr]; segindex++) {
 230             /* determine how many elements to expect in this round */
 231             if (segindex == (num_segments[lr] - 1)) sendcount[lr] = counts[lr] - segindex*segcount[lr];
 232             /* receive segments */
 233             Request::recv(tmpbuf[lr], sendcount[lr], datatype,
 234                               tree->tree_prev, COLL_TAG_BCAST,
 235                               comm, MPI_STATUS_IGNORE);
 236             /* update the initial pointer to the buffer */
 237             tmpbuf[lr] += realsegsize[lr];
 238         }
 239     }
 240
 241     /* reset the buffer pointers */
 242     tmpbuf[0] = (char *) buffer;
 243     tmpbuf[1] = (char *) buffer+counts[0] * type_extent;
 244
 245     /* Step 2:
 246        Find your immediate pair (identical node in opposite subtree) and SendRecv
 247        data buffer with them.
 248        The tree building function ensures that
 249        if (we are not root)
 250        if we are in the left subtree (lr == 0) our pair is (rank+1)%size.
 251        if we are in the right subtree (lr == 1) our pair is (rank-1)%size
 252        If we have even number of nodes the rank (size-1) will pair up with root.
 253     */
 254     if (lr == 0) {
 255         pair = (rank+1)%size;
 256     } else {
 257         pair = (rank+size-1)%size;
 258     }
 259
 260     if ( (size%2) != 0 && rank != root) {
 261
 262         Request::sendrecv( tmpbuf[lr], counts[lr], datatype,
 263                                         pair, COLL_TAG_BCAST,
 264                                         tmpbuf[(lr+1)%2], counts[(lr+1)%2], datatype,
 265                                         pair, COLL_TAG_BCAST,
 266                                         comm, MPI_STATUS_IGNORE);
 267     } else if ( (size%2) == 0 ) {
 268         /* root sends right buffer to the last node */
 269         if( rank == root ) {
 270             Request::send(tmpbuf[1], counts[1], datatype,
 271                               (root+size-1)%size, COLL_TAG_BCAST, comm);
 272
 273         }
 274         /* last node receives right buffer from the root */
 275         else if (rank == (root+size-1)%size) {
 276             Request::recv(tmpbuf[1], counts[1], datatype,
 277                               root, COLL_TAG_BCAST,
 278                               comm, MPI_STATUS_IGNORE);
 279         }
 280         /* everyone else exchanges buffers */
 281         else {
 282             Request::sendrecv( tmpbuf[lr], counts[lr], datatype,
 283                                             pair, COLL_TAG_BCAST,
 284                                             tmpbuf[(lr+1)%2], counts[(lr+1)%2], datatype,
 285                                             pair, COLL_TAG_BCAST,
 286                                             comm, MPI_STATUS_IGNORE);
 287         }
 288     }
 289     ompi_coll_tuned_topo_destroy_tree(&tree);
 290     return (MPI_SUCCESS);
 291
 292
 293 }
 294
 295 }
 296 }
 297