src/smpi/smpi_coll.c

   1 /* smpi_coll.c -- various optimized routing for collectives                   */
   2
   3 /* Copyright (c) 2009-2013. 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 #include "colls/colls.h"
  15 #include "simgrid/sg_config.h"
  16
  17 s_mpi_coll_description_t mpi_coll_gather_description[] = {
  18   {"default",
  19    "gather default collective",
  20    smpi_mpi_gather},
  21 COLL_GATHERS(COLL_DESCRIPTION, COLL_COMMA),
  22   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  23 };
  24
  25
  26 s_mpi_coll_description_t mpi_coll_allgather_description[] = {
  27   {"default",
  28    "allgather default collective",
  29    smpi_mpi_allgather},
  30 COLL_ALLGATHERS(COLL_DESCRIPTION, COLL_COMMA),
  31   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  32 };
  33
  34 s_mpi_coll_description_t mpi_coll_allgatherv_description[] = {
  35   {"default",
  36    "allgatherv default collective",
  37    smpi_mpi_allgatherv},
  38 COLL_ALLGATHERVS(COLL_DESCRIPTION, COLL_COMMA),
  39   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  40 };
  41
  42 s_mpi_coll_description_t mpi_coll_allreduce_description[] = {
  43   {"default",
  44    "allreduce default collective",
  45    smpi_mpi_allreduce},
  46 COLL_ALLREDUCES(COLL_DESCRIPTION, COLL_COMMA),
  47   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  48 };
  49
  50 s_mpi_coll_description_t mpi_coll_reduce_scatter_description[] = {
  51   {"default",
  52    "reduce_scatter default collective",
  53    smpi_mpi_reduce_scatter},
  54 COLL_REDUCE_SCATTERS(COLL_DESCRIPTION, COLL_COMMA),
  55   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  56 };
  57
  58 s_mpi_coll_description_t mpi_coll_scatter_description[] = {
  59   {"default",
  60    "scatter default collective",
  61    smpi_mpi_scatter},
  62 COLL_SCATTERS(COLL_DESCRIPTION, COLL_COMMA),
  63   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  64 };
  65
  66 s_mpi_coll_description_t mpi_coll_barrier_description[] = {
  67   {"default",
  68    "barrier default collective",
  69    smpi_mpi_barrier},
  70 COLL_BARRIERS(COLL_DESCRIPTION, COLL_COMMA),
  71   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  72 };
  73 s_mpi_coll_description_t mpi_coll_alltoall_description[] = {
  74   {"default",
  75    "Ompi alltoall default collective",
  76    smpi_coll_tuned_alltoall_ompi2},
  77 COLL_ALLTOALLS(COLL_DESCRIPTION, COLL_COMMA),
  78   {"bruck",
  79    "Alltoall Bruck (SG) collective",
  80    smpi_coll_tuned_alltoall_bruck},
  81   {"basic_linear",
  82    "Alltoall basic linear (SG) collective",
  83    smpi_coll_tuned_alltoall_basic_linear},
  84   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  85 };
  86
  87 s_mpi_coll_description_t mpi_coll_alltoallv_description[] = {
  88   {"default",
  89    "Ompi alltoallv default collective",
  90    smpi_coll_basic_alltoallv},
  91 COLL_ALLTOALLVS(COLL_DESCRIPTION, COLL_COMMA),
  92   {NULL, NULL, NULL}      /* this array must be NULL terminated */
  93 };
  94
  95 s_mpi_coll_description_t mpi_coll_bcast_description[] = {
  96   {"default",
  97    "bcast default collective",
  98    smpi_mpi_bcast},
  99 COLL_BCASTS(COLL_DESCRIPTION, COLL_COMMA),
 100   {NULL, NULL, NULL}      /* this array must be NULL terminated */
 101 };
 102
 103 s_mpi_coll_description_t mpi_coll_reduce_description[] = {
 104   {"default",
 105    "reduce default collective",
 106    smpi_mpi_reduce},
 107 COLL_REDUCES(COLL_DESCRIPTION, COLL_COMMA),
 108   {NULL, NULL, NULL}      /* this array must be NULL terminated */
 109 };
 110
 111
 112
 113 /** Displays the long description of all registered models, and quit */
 114 void coll_help(const char *category, s_mpi_coll_description_t * table)
 115 {
 116   int i;
 117   printf("Long description of the %s models accepted by this simulator:\n",
 118          category);
 119   for (i = 0; table[i].name; i++)
 120     printf("  %s: %s\n", table[i].name, table[i].description);
 121 }
 122
 123 int find_coll_description(s_mpi_coll_description_t * table,
 124                            char *name)
 125 {
 126   int i;
 127   char *name_list = NULL;
 128   int selector_on=0;
 129   if(name==NULL){//no argument provided, use active selector's algorithm
 130     name=(char*)sg_cfg_get_string("smpi/coll_selector");
 131     selector_on=1;
 132   }
 133   for (i = 0; table[i].name; i++)
 134     if (!strcmp(name, table[i].name)) {
 135       return i;
 136     }
 137
 138   if(selector_on){
 139     // collective seems not handled by the active selector, try with default one
 140     name=(char*)"default";
 141     for (i = 0; table[i].name; i++)
 142       if (!strcmp(name, table[i].name)) {
 143         return i;
 144     }
 145   }
 146   name_list = strdup(table[0].name);
 147   for (i = 1; table[i].name; i++) {
 148     name_list =
 149         xbt_realloc(name_list,
 150                     strlen(name_list) + strlen(table[i].name) + 3);
 151     strcat(name_list, ", ");
 152     strcat(name_list, table[i].name);
 153   }
 154   xbt_die("Model '%s' is invalid! Valid models are: %s.", name, name_list);
 155   return -1;
 156 }
 157
 158 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(smpi_coll, smpi,
 159                                 "Logging specific to SMPI (coll)");
 160
 161 int (*mpi_coll_gather_fun)(void *, int, MPI_Datatype, void*, int, MPI_Datatype, int root, MPI_Comm);
 162 int (*mpi_coll_allgather_fun)(void *, int, MPI_Datatype, void*, int, MPI_Datatype, MPI_Comm);
 163 int (*mpi_coll_allgatherv_fun)(void *, int, MPI_Datatype, void*, int*, int*, MPI_Datatype, MPI_Comm);
 164 int (*mpi_coll_allreduce_fun)(void *sbuf, void *rbuf, int rcount, MPI_Datatype dtype, MPI_Op op, MPI_Comm comm);
 165 int (*mpi_coll_alltoall_fun)(void *, int, MPI_Datatype, void*, int, MPI_Datatype, MPI_Comm);
 166 int (*mpi_coll_alltoallv_fun)(void *, int*, int*, MPI_Datatype, void*, int*, int*, MPI_Datatype, MPI_Comm);
 167 int (*mpi_coll_bcast_fun)(void *buf, int count, MPI_Datatype datatype, int root, MPI_Comm com);
 168 int (*mpi_coll_reduce_fun)(void *buf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm);
 169 int (*mpi_coll_reduce_scatter_fun)(void *sbuf, void *rbuf, int *rcounts,MPI_Datatype dtype,MPI_Op  op,MPI_Comm  comm);
 170 int (*mpi_coll_scatter_fun)(void *sendbuf, int sendcount, MPI_Datatype sendtype,void *recvbuf, int recvcount, MPI_Datatype recvtype,int root, MPI_Comm comm);
 171 int (*mpi_coll_barrier_fun)(MPI_Comm comm);
 172 struct s_proc_tree {
 173   int PROCTREE_A;
 174   int numChildren;
 175   int *child;
 176   int parent;
 177   int me;
 178   int root;
 179   int isRoot;
 180 };
 181 typedef struct s_proc_tree *proc_tree_t;
 182
 183 /**
 184  * alloc and init
 185  **/
 186 static proc_tree_t alloc_tree(int arity)
 187 {
 188   proc_tree_t tree;
 189   int i;
 190
 191   tree = xbt_new(struct s_proc_tree, 1);
 192   tree->PROCTREE_A = arity;
 193   tree->isRoot = 0;
 194   tree->numChildren = 0;
 195   tree->child = xbt_new(int, arity);
 196   for (i = 0; i < arity; i++) {
 197     tree->child[i] = -1;
 198   }
 199   tree->root = -1;
 200   tree->parent = -1;
 201   return tree;
 202 }
 203
 204 /**
 205  * free
 206  **/
 207 static void free_tree(proc_tree_t tree)
 208 {
 209   xbt_free(tree->child);
 210   xbt_free(tree);
 211 }
 212
 213 /**
 214  * Build the tree depending on a process rank (index) and the group size (extent)
 215  * @param root the rank of the tree root
 216  * @param rank the rank of the calling process
 217  * @param size the total number of processes
 218  **/
 219 static void build_tree(int root, int rank, int size, proc_tree_t * tree)
 220 {
 221   int index = (rank - root + size) % size;
 222   int firstChildIdx = index * (*tree)->PROCTREE_A + 1;
 223   int i;
 224
 225   (*tree)->me = rank;
 226   (*tree)->root = root;
 227
 228   for (i = 0; i < (*tree)->PROCTREE_A && firstChildIdx + i < size; i++) {
 229     (*tree)->child[i] = (firstChildIdx + i + root) % size;
 230     (*tree)->numChildren++;
 231   }
 232   if (rank == root) {
 233     (*tree)->isRoot = 1;
 234   } else {
 235     (*tree)->isRoot = 0;
 236     (*tree)->parent = (((index - 1) / (*tree)->PROCTREE_A) + root) % size;
 237   }
 238 }
 239
 240 /**
 241  * bcast
 242  **/
 243 static void tree_bcast(void *buf, int count, MPI_Datatype datatype,
 244                        MPI_Comm comm, proc_tree_t tree)
 245 {
 246   int system_tag = COLL_TAG_BCAST;
 247   int rank, i;
 248   MPI_Request *requests;
 249
 250   rank = smpi_comm_rank(comm);
 251   /* wait for data from my parent in the tree */
 252   if (!tree->isRoot) {
 253     XBT_DEBUG("<%d> tree_bcast(): i am not root: recv from %d, tag=%d)",
 254            rank, tree->parent, system_tag + rank);
 255     smpi_mpi_recv(buf, count, datatype, tree->parent, system_tag + rank,
 256                   comm, MPI_STATUS_IGNORE);
 257   }
 258   requests = xbt_new(MPI_Request, tree->numChildren);
 259   XBT_DEBUG("<%d> creates %d requests (1 per child)", rank,
 260          tree->numChildren);
 261   /* iniates sends to ranks lower in the tree */
 262   for (i = 0; i < tree->numChildren; i++) {
 263     if (tree->child[i] == -1) {
 264       requests[i] = MPI_REQUEST_NULL;
 265     } else {
 266       XBT_DEBUG("<%d> send to <%d>, tag=%d", rank, tree->child[i],
 267              system_tag + tree->child[i]);
 268       requests[i] =
 269           smpi_isend_init(buf, count, datatype, tree->child[i],
 270                           system_tag + tree->child[i], comm);
 271     }
 272   }
 273   smpi_mpi_startall(tree->numChildren, requests);
 274   smpi_mpi_waitall(tree->numChildren, requests, MPI_STATUS_IGNORE);
 275   xbt_free(requests);
 276 }
 277
 278 /**
 279  * anti-bcast
 280  **/
 281 static void tree_antibcast(void *buf, int count, MPI_Datatype datatype,
 282                            MPI_Comm comm, proc_tree_t tree)
 283 {
 284   int system_tag = COLL_TAG_BCAST;
 285   int rank, i;
 286   MPI_Request *requests;
 287
 288   rank = smpi_comm_rank(comm);
 289   // everyone sends to its parent, except root.
 290   if (!tree->isRoot) {
 291     XBT_DEBUG("<%d> tree_antibcast(): i am not root: send to %d, tag=%d)",
 292            rank, tree->parent, system_tag + rank);
 293     smpi_mpi_send(buf, count, datatype, tree->parent, system_tag + rank,
 294                   comm);
 295   }
 296   //every one receives as many messages as it has children
 297   requests = xbt_new(MPI_Request, tree->numChildren);
 298   XBT_DEBUG("<%d> creates %d requests (1 per child)", rank,
 299          tree->numChildren);
 300   for (i = 0; i < tree->numChildren; i++) {
 301     if (tree->child[i] == -1) {
 302       requests[i] = MPI_REQUEST_NULL;
 303     } else {
 304       XBT_DEBUG("<%d> recv from <%d>, tag=%d", rank, tree->child[i],
 305              system_tag + tree->child[i]);
 306       requests[i] =
 307           smpi_irecv_init(buf, count, datatype, tree->child[i],
 308                           system_tag + tree->child[i], comm);
 309     }
 310   }
 311   smpi_mpi_startall(tree->numChildren, requests);
 312   smpi_mpi_waitall(tree->numChildren, requests, MPI_STATUS_IGNORE);
 313   xbt_free(requests);
 314 }
 315
 316 /**
 317  * bcast with a binary, ternary, or whatever tree ..
 318  **/
 319 void nary_tree_bcast(void *buf, int count, MPI_Datatype datatype, int root,
 320                      MPI_Comm comm, int arity)
 321 {
 322   proc_tree_t tree = alloc_tree(arity);
 323   int rank, size;
 324
 325   rank = smpi_comm_rank(comm);
 326   size = smpi_comm_size(comm);
 327   build_tree(root, rank, size, &tree);
 328   tree_bcast(buf, count, datatype, comm, tree);
 329   free_tree(tree);
 330 }
 331
 332 /**
 333  * barrier with a binary, ternary, or whatever tree ..
 334  **/
 335 void nary_tree_barrier(MPI_Comm comm, int arity)
 336 {
 337   proc_tree_t tree = alloc_tree(arity);
 338   int rank, size;
 339   char dummy = '$';
 340
 341   rank = smpi_comm_rank(comm);
 342   size = smpi_comm_size(comm);
 343   build_tree(0, rank, size, &tree);
 344   tree_antibcast(&dummy, 1, MPI_CHAR, comm, tree);
 345   tree_bcast(&dummy, 1, MPI_CHAR, comm, tree);
 346   free_tree(tree);
 347 }
 348
 349 int smpi_coll_tuned_alltoall_ompi2(void *sendbuf, int sendcount,
 350                                    MPI_Datatype sendtype, void *recvbuf,
 351                                    int recvcount, MPI_Datatype recvtype,
 352                                    MPI_Comm comm)
 353 {
 354   int size, sendsize;
 355   size = smpi_comm_size(comm);
 356   sendsize = smpi_datatype_size(sendtype) * sendcount;
 357   if (sendsize < 200 && size > 12) {
 358     return
 359         smpi_coll_tuned_alltoall_bruck(sendbuf, sendcount, sendtype,
 360                                        recvbuf, recvcount, recvtype,
 361                                        comm);
 362   } else if (sendsize < 3000) {
 363     return
 364         smpi_coll_tuned_alltoall_basic_linear(sendbuf, sendcount,
 365                                               sendtype, recvbuf,
 366                                               recvcount, recvtype, comm);
 367   } else {
 368     return
 369         smpi_coll_tuned_alltoall_ring(sendbuf, sendcount, sendtype,
 370                                       recvbuf, recvcount, recvtype,
 371                                       comm);
 372   }
 373 }
 374
 375 /**
 376  * Alltoall Bruck
 377  *
 378  * Openmpi calls this routine when the message size sent to each rank < 2000 bytes and size < 12
 379  * FIXME: uh, check smpi_pmpi again, but this routine is called for > 12, not
 380  * less...
 381  **/
 382 int smpi_coll_tuned_alltoall_bruck(void *sendbuf, int sendcount,
 383                                    MPI_Datatype sendtype, void *recvbuf,
 384                                    int recvcount, MPI_Datatype recvtype,
 385                                    MPI_Comm comm)
 386 {
 387   int system_tag = 777;
 388   int i, rank, size, err, count;
 389   MPI_Aint lb;
 390   MPI_Aint sendext = 0;
 391   MPI_Aint recvext = 0;
 392   MPI_Request *requests;
 393
 394   // FIXME: check implementation
 395   rank = smpi_comm_rank(comm);
 396   size = smpi_comm_size(comm);
 397   XBT_DEBUG("<%d> algorithm alltoall_bruck() called.", rank);
 398   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 399   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 400   /* Local copy from self */
 401   err =
 402       smpi_datatype_copy((char *)sendbuf + rank * sendcount * sendext,
 403                          sendcount, sendtype,
 404                          (char *)recvbuf + rank * recvcount * recvext,
 405                          recvcount, recvtype);
 406   if (err == MPI_SUCCESS && size > 1) {
 407     /* Initiate all send/recv to/from others. */
 408     requests = xbt_new(MPI_Request, 2 * (size - 1));
 409     count = 0;
 410     /* Create all receives that will be posted first */
 411     for (i = 0; i < size; ++i) {
 412       if (i == rank) {
 413         XBT_DEBUG("<%d> skip request creation [src = %d, recvcount = %d]",
 414                rank, i, recvcount);
 415         continue;
 416       }
 417       requests[count] =
 418           smpi_irecv_init((char *)recvbuf + i * recvcount * recvext, recvcount,
 419                           recvtype, i, system_tag, comm);
 420       count++;
 421     }
 422     /* Now create all sends  */
 423     for (i = 0; i < size; ++i) {
 424       if (i == rank) {
 425         XBT_DEBUG("<%d> skip request creation [dst = %d, sendcount = %d]",
 426                rank, i, sendcount);
 427         continue;
 428       }
 429       requests[count] =
 430           smpi_isend_init((char *)sendbuf + i * sendcount * sendext, sendcount,
 431                           sendtype, i, system_tag, comm);
 432       count++;
 433     }
 434     /* Wait for them all. */
 435     smpi_mpi_startall(count, requests);
 436     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 437     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 438     xbt_free(requests);
 439   }
 440   return MPI_SUCCESS;
 441 }
 442
 443 /**
 444  * Alltoall basic_linear (STARMPI:alltoall-simple)
 445  **/
 446 int smpi_coll_tuned_alltoall_basic_linear(void *sendbuf, int sendcount,
 447                                           MPI_Datatype sendtype,
 448                                           void *recvbuf, int recvcount,
 449                                           MPI_Datatype recvtype,
 450                                           MPI_Comm comm)
 451 {
 452   int system_tag = 888;
 453   int i, rank, size, err, count;
 454   MPI_Aint lb = 0, sendext = 0, recvext = 0;
 455   MPI_Request *requests;
 456
 457   /* Initialize. */
 458   rank = smpi_comm_rank(comm);
 459   size = smpi_comm_size(comm);
 460   XBT_DEBUG("<%d> algorithm alltoall_basic_linear() called.", rank);
 461   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 462   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 463   /* simple optimization */
 464   err = smpi_datatype_copy((char *)sendbuf + rank * sendcount * sendext,
 465                            sendcount, sendtype,
 466                            (char *)recvbuf + rank * recvcount * recvext,
 467                            recvcount, recvtype);
 468   if (err == MPI_SUCCESS && size > 1) {
 469     /* Initiate all send/recv to/from others. */
 470     requests = xbt_new(MPI_Request, 2 * (size - 1));
 471     /* Post all receives first -- a simple optimization */
 472     count = 0;
 473     for (i = (rank + 1) % size; i != rank; i = (i + 1) % size) {
 474       requests[count] =
 475           smpi_irecv_init((char *)recvbuf + i * recvcount * recvext, recvcount,
 476                           recvtype, i, system_tag, comm);
 477       count++;
 478     }
 479     /* Now post all sends in reverse order
 480      *   - We would like to minimize the search time through message queue
 481      *     when messages actually arrive in the order in which they were posted.
 482      * TODO: check the previous assertion
 483      */
 484     for (i = (rank + size - 1) % size; i != rank; i = (i + size - 1) % size) {
 485       requests[count] =
 486           smpi_isend_init((char *)sendbuf + i * sendcount * sendext, sendcount,
 487                           sendtype, i, system_tag, comm);
 488       count++;
 489     }
 490     /* Wait for them all. */
 491     smpi_mpi_startall(count, requests);
 492     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 493     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 494     xbt_free(requests);
 495   }
 496   return err;
 497 }
 498
 499 int smpi_coll_basic_alltoallv(void *sendbuf, int *sendcounts,
 500                               int *senddisps, MPI_Datatype sendtype,
 501                               void *recvbuf, int *recvcounts,
 502                               int *recvdisps, MPI_Datatype recvtype,
 503                               MPI_Comm comm)
 504 {
 505   int system_tag = 889;
 506   int i, rank, size, err, count;
 507   MPI_Aint lb = 0, sendext = 0, recvext = 0;
 508   MPI_Request *requests;
 509
 510   /* Initialize. */
 511   rank = smpi_comm_rank(comm);
 512   size = smpi_comm_size(comm);
 513   XBT_DEBUG("<%d> algorithm basic_alltoallv() called.", rank);
 514   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 515   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 516   /* Local copy from self */
 517   err =
 518       smpi_datatype_copy((char *)sendbuf + senddisps[rank] * sendext,
 519                          sendcounts[rank], sendtype,
 520                          (char *)recvbuf + recvdisps[rank] * recvext,
 521                          recvcounts[rank], recvtype);
 522   if (err == MPI_SUCCESS && size > 1) {
 523     /* Initiate all send/recv to/from others. */
 524     requests = xbt_new(MPI_Request, 2 * (size - 1));
 525     count = 0;
 526     /* Create all receives that will be posted first */
 527     for (i = 0; i < size; ++i) {
 528       if (i == rank || recvcounts[i] == 0) {
 529         XBT_DEBUG
 530             ("<%d> skip request creation [src = %d, recvcounts[src] = %d]",
 531              rank, i, recvcounts[i]);
 532         continue;
 533       }
 534       requests[count] =
 535           smpi_irecv_init((char *)recvbuf + recvdisps[i] * recvext,
 536                           recvcounts[i], recvtype, i, system_tag, comm);
 537       count++;
 538     }
 539     /* Now create all sends  */
 540     for (i = 0; i < size; ++i) {
 541       if (i == rank || sendcounts[i] == 0) {
 542         XBT_DEBUG
 543             ("<%d> skip request creation [dst = %d, sendcounts[dst] = %d]",
 544              rank, i, sendcounts[i]);
 545         continue;
 546       }
 547       requests[count] =
 548           smpi_isend_init((char *)sendbuf + senddisps[i] * sendext,
 549                           sendcounts[i], sendtype, i, system_tag, comm);
 550       count++;
 551     }
 552     /* Wait for them all. */
 553     smpi_mpi_startall(count, requests);
 554     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 555     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 556     xbt_free(requests);
 557   }
 558   return err;
 559 }