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

   1 /* Copyright (c) 2013-2020. 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 segmenets */
  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     if ( segsize > 0 ) {
 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) num_segments[0]++;
 125         num_segments[1] = counts[1]/segcount[1];
 126         if ((counts[1] % segcount[1]) != 0) num_segments[1]++;
 127     } else {
 128         segcount[0]     = counts[0];
 129         segcount[1]     = counts[1];
 130         num_segments[0] = num_segments[1] = 1;
 131     }
 132
 133     /* if the message is too small to be split into segments */
 134     if( (counts[0] == 0 || counts[1] == 0) ||
 135         (segsize > counts[0] * type_size) ||
 136         (segsize > counts[1] * type_size) ) {
 137         /* call linear version here ! */
 138         return bcast__SMP_linear( buffer, count, datatype, root, comm);
 139     }
 140     type_extent = datatype->get_extent();
 141
 142
 143     /* Determine real segment size */
 144     realsegsize[0] = segcount[0] * type_extent;
 145     realsegsize[1] = segcount[1] * type_extent;
 146
 147     /* set the buffer pointers */
 148     tmpbuf[0] = (char *) buffer;
 149     tmpbuf[1] = (char *) buffer+counts[0] * type_extent;
 150
 151     /* Step 1:
 152        Root splits the buffer in 2 and sends segmented message down the branches.
 153        Left subtree of the tree receives first half of the buffer, while right
 154        subtree receives the remaining message.
 155     */
 156
 157     /* determine if I am left (0) or right (1), (root is right) */
 158     lr = ((rank + size - root)%size + 1)%2;
 159
 160     /* root code */
 161     if( rank == root ) {
 162         /* determine segment count */
 163         sendcount[0] = segcount[0];
 164         sendcount[1] = segcount[1];
 165         /* for each segment */
 166         for (segindex = 0; segindex < num_segments[0]; segindex++) {
 167             /* for each child */
 168             for( i = 0; i < tree->tree_nextsize && i < 2; i++ ) {
 169                 if (segindex >= num_segments[i]) { /* no more segments */
 170                     continue;
 171                 }
 172                 /* determine how many elements are being sent in this round */
 173                 if(segindex == (num_segments[i] - 1))
 174                     sendcount[i] = counts[i] - segindex*segcount[i];
 175                 /* send data */
 176                 Request::send(tmpbuf[i], sendcount[i], datatype,
 177                                   tree->tree_next[i], COLL_TAG_BCAST, comm);
 178                 /* update tmp buffer */
 179                 tmpbuf[i] += realsegsize[i];
 180             }
 181         }
 182     }
 183
 184     /* intermediate nodes code */
 185     else if( tree->tree_nextsize > 0 ) {
 186       /* Intermediate nodes:
 187        * It will receive segments only from one half of the data.
 188        * Which one is determined by whether the node belongs to the "left" or "right"
 189        * subtree. Topology building function builds binary tree such that
 190        * odd "shifted ranks" ((rank + size - root)%size) are on the left subtree,
 191        * and even on the right subtree.
 192        *
 193        * Create the pipeline. We first post the first receive, then in the loop we
 194        * post the next receive and after that wait for the previous receive to complete
 195        * and we disseminating the data to all children.
 196        */
 197       sendcount[lr] = segcount[lr];
 198       base_req      = Request::irecv(tmpbuf[lr], sendcount[lr], datatype, tree->tree_prev, COLL_TAG_BCAST, comm);
 199
 200       for (segindex = 1; segindex < num_segments[lr]; segindex++) {
 201         /* determine how many elements to expect in this round */
 202         if (segindex == (num_segments[lr] - 1))
 203           sendcount[lr] = counts[lr] - segindex * segcount[lr];
 204         /* post new irecv */
 205         new_req = Request::irecv(tmpbuf[lr] + realsegsize[lr], sendcount[lr], datatype, tree->tree_prev, COLL_TAG_BCAST,
 206                                  comm);
 207
 208         /* wait for and forward current segment */
 209         Request::waitall(1, &base_req, MPI_STATUSES_IGNORE);
 210         for (i = 0; i < tree->tree_nextsize; i++) { /* send data to children (segcount[lr]) */
 211           Request::send(tmpbuf[lr], segcount[lr], datatype, tree->tree_next[i], COLL_TAG_BCAST, comm);
 212         } /* end of for each child */
 213
 214         /* upate the base request */
 215         base_req = new_req;
 216         /* go to the next buffer (ie. the one corresponding to the next recv) */
 217         tmpbuf[lr] += realsegsize[lr];
 218         } /* end of for segindex */
 219
 220         /* wait for the last segment and forward current segment */
 221         Request::waitall( 1, &base_req, MPI_STATUSES_IGNORE );
 222         for( i = 0; i < tree->tree_nextsize; i++ ) {  /* send data to children */
 223             Request::send(tmpbuf[lr], sendcount[lr], datatype,
 224                               tree->tree_next[i], COLL_TAG_BCAST, comm);
 225         } /* end of for each child */
 226     }
 227
 228     /* leaf nodes */
 229     else {
 230         /* Just consume segments as fast as possible */
 231         sendcount[lr] = segcount[lr];
 232         for (segindex = 0; segindex < num_segments[lr]; segindex++) {
 233             /* determine how many elements to expect in this round */
 234             if (segindex == (num_segments[lr] - 1)) sendcount[lr] = counts[lr] - segindex*segcount[lr];
 235             /* receive segments */
 236             Request::recv(tmpbuf[lr], sendcount[lr], datatype,
 237                               tree->tree_prev, COLL_TAG_BCAST,
 238                               comm, MPI_STATUS_IGNORE);
 239             /* update the initial pointer to the buffer */
 240             tmpbuf[lr] += realsegsize[lr];
 241         }
 242     }
 243
 244     /* reset the buffer pointers */
 245     tmpbuf[0] = (char *) buffer;
 246     tmpbuf[1] = (char *) buffer+counts[0] * type_extent;
 247
 248     /* Step 2:
 249        Find your immediate pair (identical node in opposite subtree) and SendRecv
 250        data buffer with them.
 251        The tree building function ensures that
 252        if (we are not root)
 253        if we are in the left subtree (lr == 0) our pair is (rank+1)%size.
 254        if we are in the right subtree (lr == 1) our pair is (rank-1)%size
 255        If we have even number of nodes the rank (size-1) will pair up with root.
 256     */
 257     if (lr == 0) {
 258         pair = (rank+1)%size;
 259     } else {
 260         pair = (rank+size-1)%size;
 261     }
 262
 263     if ( (size%2) != 0 && rank != root) {
 264
 265         Request::sendrecv( tmpbuf[lr], counts[lr], datatype,
 266                                         pair, COLL_TAG_BCAST,
 267                                         tmpbuf[(lr+1)%2], counts[(lr+1)%2], datatype,
 268                                         pair, COLL_TAG_BCAST,
 269                                         comm, MPI_STATUS_IGNORE);
 270     } else if ( (size%2) == 0 ) {
 271         /* root sends right buffer to the last node */
 272         if( rank == root ) {
 273             Request::send(tmpbuf[1], counts[1], datatype,
 274                               (root+size-1)%size, COLL_TAG_BCAST, comm);
 275
 276         }
 277         /* last node receives right buffer from the root */
 278         else if (rank == (root+size-1)%size) {
 279             Request::recv(tmpbuf[1], counts[1], datatype,
 280                               root, COLL_TAG_BCAST,
 281                               comm, MPI_STATUS_IGNORE);
 282         }
 283         /* everyone else exchanges buffers */
 284         else {
 285             Request::sendrecv( tmpbuf[lr], counts[lr], datatype,
 286                                             pair, COLL_TAG_BCAST,
 287                                             tmpbuf[(lr+1)%2], counts[(lr+1)%2], datatype,
 288                                             pair, COLL_TAG_BCAST,
 289                                             comm, MPI_STATUS_IGNORE);
 290         }
 291     }
 292     ompi_coll_tuned_topo_destroy_tree(&tree);
 293     return (MPI_SUCCESS);
 294
 295
 296 }
 297
 298 }
 299 }
 300