src/smpi/smpi_coll.c

   1 /* smpi_coll.c -- various optimized routing for collectives                   */
   2
   3 /* Copyright (c) 2009, 2010. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include <stdio.h>
  10 #include <string.h>
  11 #include <assert.h>
  12
  13 #include "private.h"
  14
  15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(smpi_coll, smpi,
  16                                 "Logging specific to SMPI (coll)");
  17
  18 struct s_proc_tree {
  19   int PROCTREE_A;
  20   int numChildren;
  21   int *child;
  22   int parent;
  23   int me;
  24   int root;
  25   int isRoot;
  26 };
  27 typedef struct s_proc_tree *proc_tree_t;
  28
  29 /**
  30  * alloc and init
  31  **/
  32 static proc_tree_t alloc_tree(int arity)
  33 {
  34   proc_tree_t tree;
  35   int i;
  36
  37   tree = xbt_new(struct s_proc_tree, 1);
  38   tree->PROCTREE_A = arity;
  39   tree->isRoot = 0;
  40   tree->numChildren = 0;
  41   tree->child = xbt_new(int, arity);
  42   for (i = 0; i < arity; i++) {
  43     tree->child[i] = -1;
  44   }
  45   tree->root = -1;
  46   tree->parent = -1;
  47   return tree;
  48 }
  49
  50 /**
  51  * free
  52  **/
  53 static void free_tree(proc_tree_t tree)
  54 {
  55   xbt_free(tree->child);
  56   xbt_free(tree);
  57 }
  58
  59 /**
  60  * Build the tree depending on a process rank (index) and the group size (extent)
  61  * @param root the rank of the tree root
  62  * @param rank the rank of the calling process
  63  * @param size the total number of processes
  64  **/
  65 static void build_tree(int root, int rank, int size, proc_tree_t * tree)
  66 {
  67   int index = (rank - root + size) % size;
  68   int firstChildIdx = index * (*tree)->PROCTREE_A + 1;
  69   int i;
  70
  71   (*tree)->me = rank;
  72   (*tree)->root = root;
  73
  74   for (i = 0; i < (*tree)->PROCTREE_A && firstChildIdx + i < size; i++) {
  75     (*tree)->child[i] = (firstChildIdx + i + root) % size;
  76     (*tree)->numChildren++;
  77   }
  78   if (rank == root) {
  79     (*tree)->isRoot = 1;
  80   } else {
  81     (*tree)->isRoot = 0;
  82     (*tree)->parent = (((index - 1) / (*tree)->PROCTREE_A) + root) % size;
  83   }
  84 }
  85
  86 /**
  87  * bcast
  88  **/
  89 static void tree_bcast(void *buf, int count, MPI_Datatype datatype,
  90                        MPI_Comm comm, proc_tree_t tree)
  91 {
  92   int system_tag = 999;         // used negative int but smpi_create_request() declares this illegal (to be checked)
  93   int rank, i;
  94   MPI_Request *requests;
  95
  96   rank = smpi_comm_rank(comm);
  97   /* wait for data from my parent in the tree */
  98   if (!tree->isRoot) {
  99     XBT_DEBUG("<%d> tree_bcast(): i am not root: recv from %d, tag=%d)",
 100            rank, tree->parent, system_tag + rank);
 101     smpi_mpi_recv(buf, count, datatype, tree->parent, system_tag + rank,
 102                   comm, MPI_STATUS_IGNORE);
 103   }
 104   requests = xbt_new(MPI_Request, tree->numChildren);
 105   XBT_DEBUG("<%d> creates %d requests (1 per child)", rank,
 106          tree->numChildren);
 107   /* iniates sends to ranks lower in the tree */
 108   for (i = 0; i < tree->numChildren; i++) {
 109     if (tree->child[i] == -1) {
 110       requests[i] = MPI_REQUEST_NULL;
 111     } else {
 112       XBT_DEBUG("<%d> send to <%d>, tag=%d", rank, tree->child[i],
 113              system_tag + tree->child[i]);
 114       requests[i] =
 115           smpi_isend_init(buf, count, datatype, tree->child[i],
 116                           system_tag + tree->child[i], comm);
 117     }
 118   }
 119   smpi_mpi_startall(tree->numChildren, requests);
 120   smpi_mpi_waitall(tree->numChildren, requests, MPI_STATUS_IGNORE);
 121   for (i = 0; i < tree->numChildren; i++){
 122     xbt_free (requests[i]);
 123   }
 124   xbt_free(requests);
 125 }
 126
 127 /**
 128  * anti-bcast
 129  **/
 130 static void tree_antibcast(void *buf, int count, MPI_Datatype datatype,
 131                            MPI_Comm comm, proc_tree_t tree)
 132 {
 133   int system_tag = 999;         // used negative int but smpi_create_request() declares this illegal (to be checked)
 134   int rank, i;
 135   MPI_Request *requests;
 136
 137   rank = smpi_comm_rank(comm);
 138   // everyone sends to its parent, except root.
 139   if (!tree->isRoot) {
 140     XBT_DEBUG("<%d> tree_antibcast(): i am not root: send to %d, tag=%d)",
 141            rank, tree->parent, system_tag + rank);
 142     smpi_mpi_send(buf, count, datatype, tree->parent, system_tag + rank,
 143                   comm);
 144   }
 145   //every one receives as many messages as it has children
 146   requests = xbt_new(MPI_Request, tree->numChildren);
 147   XBT_DEBUG("<%d> creates %d requests (1 per child)", rank,
 148          tree->numChildren);
 149   for (i = 0; i < tree->numChildren; i++) {
 150     if (tree->child[i] == -1) {
 151       requests[i] = MPI_REQUEST_NULL;
 152     } else {
 153       XBT_DEBUG("<%d> recv from <%d>, tag=%d", rank, tree->child[i],
 154              system_tag + tree->child[i]);
 155       requests[i] =
 156           smpi_irecv_init(buf, count, datatype, tree->child[i],
 157                           system_tag + tree->child[i], comm);
 158     }
 159   }
 160   smpi_mpi_startall(tree->numChildren, requests);
 161   smpi_mpi_waitall(tree->numChildren, requests, MPI_STATUS_IGNORE);
 162   for (i = 0; i < tree->numChildren; i++){
 163     xbt_free (requests[i]);
 164   }
 165   xbt_free(requests);
 166 }
 167
 168 /**
 169  * bcast with a binary, ternary, or whatever tree ..
 170  **/
 171 void nary_tree_bcast(void *buf, int count, MPI_Datatype datatype, int root,
 172                      MPI_Comm comm, int arity)
 173 {
 174   proc_tree_t tree = alloc_tree(arity);
 175   int rank, size;
 176
 177   rank = smpi_comm_rank(comm);
 178   size = smpi_comm_size(comm);
 179   build_tree(root, rank, size, &tree);
 180   tree_bcast(buf, count, datatype, comm, tree);
 181   free_tree(tree);
 182 }
 183
 184 /**
 185  * barrier with a binary, ternary, or whatever tree ..
 186  **/
 187 void nary_tree_barrier(MPI_Comm comm, int arity)
 188 {
 189   proc_tree_t tree = alloc_tree(arity);
 190   int rank, size;
 191   char dummy = '$';
 192
 193   rank = smpi_comm_rank(comm);
 194   size = smpi_comm_size(comm);
 195   build_tree(0, rank, size, &tree);
 196   tree_antibcast(&dummy, 1, MPI_CHAR, comm, tree);
 197   tree_bcast(&dummy, 1, MPI_CHAR, comm, tree);
 198   free_tree(tree);
 199 }
 200
 201 /**
 202  * Alltoall Bruck
 203  *
 204  * Openmpi calls this routine when the message size sent to each rank < 2000 bytes and size < 12
 205  * FIXME: uh, check smpi_pmpi again, but this routine is called for > 12, not
 206  * less...
 207  **/
 208 int smpi_coll_tuned_alltoall_bruck(void *sendbuf, int sendcount,
 209                                    MPI_Datatype sendtype, void *recvbuf,
 210                                    int recvcount, MPI_Datatype recvtype,
 211                                    MPI_Comm comm)
 212 {
 213   int system_tag = 777;
 214   int i, rank, size, err, count;
 215   MPI_Aint lb;
 216   MPI_Aint sendext = 0;
 217   MPI_Aint recvext = 0;
 218   MPI_Request *requests;
 219
 220   // FIXME: check implementation
 221   rank = smpi_comm_rank(comm);
 222   size = smpi_comm_size(comm);
 223   XBT_DEBUG("<%d> algorithm alltoall_bruck() called.", rank);
 224   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 225   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 226   /* Local copy from self */
 227   err =
 228       smpi_datatype_copy((char *)sendbuf + rank * sendcount * sendext,
 229                          sendcount, sendtype,
 230                          (char *)recvbuf + rank * recvcount * recvext,
 231                          recvcount, recvtype);
 232   if (err == MPI_SUCCESS && size > 1) {
 233     /* Initiate all send/recv to/from others. */
 234     requests = xbt_new(MPI_Request, 2 * (size - 1));
 235     count = 0;
 236     /* Create all receives that will be posted first */
 237     for (i = 0; i < size; ++i) {
 238       if (i == rank) {
 239         XBT_DEBUG("<%d> skip request creation [src = %d, recvcount = %d]",
 240                rank, i, recvcount);
 241         continue;
 242       }
 243       requests[count] =
 244           smpi_irecv_init((char *)recvbuf + i * recvcount * recvext, recvcount,
 245                           recvtype, i, system_tag, comm);
 246       count++;
 247     }
 248     /* Now create all sends  */
 249     for (i = 0; i < size; ++i) {
 250       if (i == rank) {
 251         XBT_DEBUG("<%d> skip request creation [dst = %d, sendcount = %d]",
 252                rank, i, sendcount);
 253         continue;
 254       }
 255       requests[count] =
 256           smpi_isend_init((char *)sendbuf + i * sendcount * sendext, sendcount,
 257                           sendtype, i, system_tag, comm);
 258       count++;
 259     }
 260     /* Wait for them all. */
 261     smpi_mpi_startall(count, requests);
 262     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 263     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 264     xbt_free(requests);
 265   }
 266   return MPI_SUCCESS;
 267 }
 268
 269 /**
 270  * Alltoall basic_linear
 271  **/
 272 int smpi_coll_tuned_alltoall_basic_linear(void *sendbuf, int sendcount,
 273                                           MPI_Datatype sendtype,
 274                                           void *recvbuf, int recvcount,
 275                                           MPI_Datatype recvtype,
 276                                           MPI_Comm comm)
 277 {
 278   int system_tag = 888;
 279   int i, rank, size, err, count;
 280   MPI_Aint lb = 0, sendext = 0, recvext = 0;
 281   MPI_Request *requests;
 282
 283   /* Initialize. */
 284   rank = smpi_comm_rank(comm);
 285   size = smpi_comm_size(comm);
 286   XBT_DEBUG("<%d> algorithm alltoall_basic_linear() called.", rank);
 287   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 288   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 289   /* simple optimization */
 290   err = smpi_datatype_copy((char *)sendbuf + rank * sendcount * sendext,
 291                            sendcount, sendtype,
 292                            (char *)recvbuf + rank * recvcount * recvext,
 293                            recvcount, recvtype);
 294   if (err == MPI_SUCCESS && size > 1) {
 295     /* Initiate all send/recv to/from others. */
 296     requests = xbt_new(MPI_Request, 2 * (size - 1));
 297     /* Post all receives first -- a simple optimization */
 298     count = 0;
 299     for (i = (rank + 1) % size; i != rank; i = (i + 1) % size) {
 300       requests[count] =
 301           smpi_irecv_init((char *)recvbuf + i * recvcount * recvext, recvcount,
 302                           recvtype, i, system_tag, comm);
 303       count++;
 304     }
 305     /* Now post all sends in reverse order
 306      *   - We would like to minimize the search time through message queue
 307      *     when messages actually arrive in the order in which they were posted.
 308      * TODO: check the previous assertion
 309      */
 310     for (i = (rank + size - 1) % size; i != rank; i = (i + size - 1) % size) {
 311       requests[count] =
 312           smpi_isend_init((char *)sendbuf + i * sendcount * sendext, sendcount,
 313                           sendtype, i, system_tag, comm);
 314       count++;
 315     }
 316     /* Wait for them all. */
 317     smpi_mpi_startall(count, requests);
 318     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 319     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 320     xbt_free(requests);
 321   }
 322   return err;
 323 }
 324
 325 /**
 326  * Alltoall pairwise
 327  *
 328  * this algorithm performs size steps (1<=s<=size) and
 329  * at each step s, a process p sends iand receive to.from a unique distinct remote process
 330  * size=5 : s=1:  4->0->1, 0->1->2, 1->2->3, ...
 331  *          s=2:  3->0->2, 4->1->3, 0->2->4, 1->3->0 , 2->4->1
 332  *          ....
 333  * Openmpi calls this routine when the message size sent to each rank is greater than 3000 bytes
 334  **/
 335 int smpi_coll_tuned_alltoall_pairwise(void *sendbuf, int sendcount,
 336                                       MPI_Datatype sendtype, void *recvbuf,
 337                                       int recvcount, MPI_Datatype recvtype,
 338                                       MPI_Comm comm)
 339 {
 340   int system_tag = 999;
 341   int rank, size, step, sendto, recvfrom, sendsize, recvsize;
 342
 343   rank = smpi_comm_rank(comm);
 344   size = smpi_comm_size(comm);
 345   XBT_DEBUG("<%d> algorithm alltoall_pairwise() called.", rank);
 346   sendsize = smpi_datatype_size(sendtype);
 347   recvsize = smpi_datatype_size(recvtype);
 348   /* Perform pairwise exchange - starting from 1 so the local copy is last */
 349   for (step = 1; step < size + 1; step++) {
 350     /* who do we talk to in this step? */
 351     sendto = (rank + step) % size;
 352     recvfrom = (rank + size - step) % size;
 353     /* send and receive */
 354     smpi_mpi_sendrecv(&((char *) sendbuf)[sendto * sendsize * sendcount],
 355                       sendcount, sendtype, sendto, system_tag,
 356                       &((char *) recvbuf)[recvfrom * recvsize * recvcount],
 357                       recvcount, recvtype, recvfrom, system_tag, comm,
 358                       MPI_STATUS_IGNORE);
 359   }
 360   return MPI_SUCCESS;
 361 }
 362
 363 int smpi_coll_basic_alltoallv(void *sendbuf, int *sendcounts,
 364                               int *senddisps, MPI_Datatype sendtype,
 365                               void *recvbuf, int *recvcounts,
 366                               int *recvdisps, MPI_Datatype recvtype,
 367                               MPI_Comm comm)
 368 {
 369   int system_tag = 889;
 370   int i, rank, size, err, count;
 371   MPI_Aint lb = 0, sendext = 0, recvext = 0;
 372   MPI_Request *requests;
 373
 374   /* Initialize. */
 375   rank = smpi_comm_rank(comm);
 376   size = smpi_comm_size(comm);
 377   XBT_DEBUG("<%d> algorithm basic_alltoallv() called.", rank);
 378   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 379   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 380   /* Local copy from self */
 381   err =
 382       smpi_datatype_copy((char *)sendbuf + senddisps[rank] * sendext,
 383                          sendcounts[rank], sendtype,
 384                          (char *)recvbuf + recvdisps[rank] * recvext,
 385                          recvcounts[rank], recvtype);
 386   if (err == MPI_SUCCESS && size > 1) {
 387     /* Initiate all send/recv to/from others. */
 388     requests = xbt_new(MPI_Request, 2 * (size - 1));
 389     count = 0;
 390     /* Create all receives that will be posted first */
 391     for (i = 0; i < size; ++i) {
 392       if (i == rank || recvcounts[i] == 0) {
 393         XBT_DEBUG
 394             ("<%d> skip request creation [src = %d, recvcounts[src] = %d]",
 395              rank, i, recvcounts[i]);
 396         continue;
 397       }
 398       requests[count] =
 399           smpi_irecv_init((char *)recvbuf + recvdisps[i] * recvext,
 400                           recvcounts[i], recvtype, i, system_tag, comm);
 401       count++;
 402     }
 403     /* Now create all sends  */
 404     for (i = 0; i < size; ++i) {
 405       if (i == rank || sendcounts[i] == 0) {
 406         XBT_DEBUG
 407             ("<%d> skip request creation [dst = %d, sendcounts[dst] = %d]",
 408              rank, i, sendcounts[i]);
 409         continue;
 410       }
 411       requests[count] =
 412           smpi_isend_init((char *)sendbuf + senddisps[i] * sendext,
 413                           sendcounts[i], sendtype, i, system_tag, comm);
 414       count++;
 415     }
 416     /* Wait for them all. */
 417     smpi_mpi_startall(count, requests);
 418     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 419     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 420     xbt_free(requests);
 421   }
 422   return err;
 423 }