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

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