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   if (!table[0].name)
 147     xbt_die("No collective is valid! This is a bug.");
 148   name_list = xbt_strdup(table[0].name);
 149   for (i = 1; table[i].name; i++) {
 150     name_list =
 151         xbt_realloc(name_list,
 152                     strlen(name_list) + strlen(table[i].name) + 3);
 153     strcat(name_list, ", ");
 154     strcat(name_list, table[i].name);
 155   }
 156   xbt_die("Collective '%s' is invalid! Valid collectives are: %s.", name, name_list);
 157   return -1;
 158 }
 159
 160 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(smpi_coll, smpi,
 161                                 "Logging specific to SMPI (coll)");
 162
 163 int (*mpi_coll_gather_fun)(void *, int, MPI_Datatype, void*, int, MPI_Datatype, int root, MPI_Comm);
 164 int (*mpi_coll_allgather_fun)(void *, int, MPI_Datatype, void*, int, MPI_Datatype, MPI_Comm);
 165 int (*mpi_coll_allgatherv_fun)(void *, int, MPI_Datatype, void*, int*, int*, MPI_Datatype, MPI_Comm);
 166 int (*mpi_coll_allreduce_fun)(void *sbuf, void *rbuf, int rcount, MPI_Datatype dtype, MPI_Op op, MPI_Comm comm);
 167 int (*mpi_coll_alltoall_fun)(void *, int, MPI_Datatype, void*, int, MPI_Datatype, MPI_Comm);
 168 int (*mpi_coll_alltoallv_fun)(void *, int*, int*, MPI_Datatype, void*, int*, int*, MPI_Datatype, MPI_Comm);
 169 int (*mpi_coll_bcast_fun)(void *buf, int count, MPI_Datatype datatype, int root, MPI_Comm com);
 170 int (*mpi_coll_reduce_fun)(void *buf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm);
 171 int (*mpi_coll_reduce_scatter_fun)(void *sbuf, void *rbuf, int *rcounts,MPI_Datatype dtype,MPI_Op  op,MPI_Comm  comm);
 172 int (*mpi_coll_scatter_fun)(void *sendbuf, int sendcount, MPI_Datatype sendtype,void *recvbuf, int recvcount, MPI_Datatype recvtype,int root, MPI_Comm comm);
 173 int (*mpi_coll_barrier_fun)(MPI_Comm comm);
 174 struct s_proc_tree {
 175   int PROCTREE_A;
 176   int numChildren;
 177   int *child;
 178   int parent;
 179   int me;
 180   int root;
 181   int isRoot;
 182 };
 183 typedef struct s_proc_tree *proc_tree_t;
 184
 185 /**
 186  * alloc and init
 187  **/
 188 static proc_tree_t alloc_tree(int arity)
 189 {
 190   proc_tree_t tree;
 191   int i;
 192
 193   tree = xbt_new(struct s_proc_tree, 1);
 194   tree->PROCTREE_A = arity;
 195   tree->isRoot = 0;
 196   tree->numChildren = 0;
 197   tree->child = xbt_new(int, arity);
 198   for (i = 0; i < arity; i++) {
 199     tree->child[i] = -1;
 200   }
 201   tree->root = -1;
 202   tree->parent = -1;
 203   return tree;
 204 }
 205
 206 /**
 207  * free
 208  **/
 209 static void free_tree(proc_tree_t tree)
 210 {
 211   xbt_free(tree->child);
 212   xbt_free(tree);
 213 }
 214
 215 /**
 216  * Build the tree depending on a process rank (index) and the group size (extent)
 217  * @param root the rank of the tree root
 218  * @param rank the rank of the calling process
 219  * @param size the total number of processes
 220  **/
 221 static void build_tree(int root, int rank, int size, proc_tree_t * tree)
 222 {
 223   int index = (rank - root + size) % size;
 224   int firstChildIdx = index * (*tree)->PROCTREE_A + 1;
 225   int i;
 226
 227   (*tree)->me = rank;
 228   (*tree)->root = root;
 229
 230   for (i = 0; i < (*tree)->PROCTREE_A && firstChildIdx + i < size; i++) {
 231     (*tree)->child[i] = (firstChildIdx + i + root) % size;
 232     (*tree)->numChildren++;
 233   }
 234   if (rank == root) {
 235     (*tree)->isRoot = 1;
 236   } else {
 237     (*tree)->isRoot = 0;
 238     (*tree)->parent = (((index - 1) / (*tree)->PROCTREE_A) + root) % size;
 239   }
 240 }
 241
 242 /**
 243  * bcast
 244  **/
 245 static void tree_bcast(void *buf, int count, MPI_Datatype datatype,
 246                        MPI_Comm comm, proc_tree_t tree)
 247 {
 248   int system_tag = COLL_TAG_BCAST;
 249   int rank, i;
 250   MPI_Request *requests;
 251
 252   rank = smpi_comm_rank(comm);
 253   /* wait for data from my parent in the tree */
 254   if (!tree->isRoot) {
 255     XBT_DEBUG("<%d> tree_bcast(): i am not root: recv from %d, tag=%d)",
 256            rank, tree->parent, system_tag + rank);
 257     smpi_mpi_recv(buf, count, datatype, tree->parent, system_tag + rank,
 258                   comm, MPI_STATUS_IGNORE);
 259   }
 260   requests = xbt_new(MPI_Request, tree->numChildren);
 261   XBT_DEBUG("<%d> creates %d requests (1 per child)", rank,
 262          tree->numChildren);
 263   /* iniates sends to ranks lower in the tree */
 264   for (i = 0; i < tree->numChildren; i++) {
 265     if (tree->child[i] == -1) {
 266       requests[i] = MPI_REQUEST_NULL;
 267     } else {
 268       XBT_DEBUG("<%d> send to <%d>, tag=%d", rank, tree->child[i],
 269              system_tag + tree->child[i]);
 270       requests[i] =
 271           smpi_isend_init(buf, count, datatype, tree->child[i],
 272                           system_tag + tree->child[i], comm);
 273     }
 274   }
 275   smpi_mpi_startall(tree->numChildren, requests);
 276   smpi_mpi_waitall(tree->numChildren, requests, MPI_STATUS_IGNORE);
 277   xbt_free(requests);
 278 }
 279
 280 /**
 281  * anti-bcast
 282  **/
 283 static void tree_antibcast(void *buf, int count, MPI_Datatype datatype,
 284                            MPI_Comm comm, proc_tree_t tree)
 285 {
 286   int system_tag = COLL_TAG_BCAST;
 287   int rank, i;
 288   MPI_Request *requests;
 289
 290   rank = smpi_comm_rank(comm);
 291   // everyone sends to its parent, except root.
 292   if (!tree->isRoot) {
 293     XBT_DEBUG("<%d> tree_antibcast(): i am not root: send to %d, tag=%d)",
 294            rank, tree->parent, system_tag + rank);
 295     smpi_mpi_send(buf, count, datatype, tree->parent, system_tag + rank,
 296                   comm);
 297   }
 298   //every one receives as many messages as it has children
 299   requests = xbt_new(MPI_Request, tree->numChildren);
 300   XBT_DEBUG("<%d> creates %d requests (1 per child)", rank,
 301          tree->numChildren);
 302   for (i = 0; i < tree->numChildren; i++) {
 303     if (tree->child[i] == -1) {
 304       requests[i] = MPI_REQUEST_NULL;
 305     } else {
 306       XBT_DEBUG("<%d> recv from <%d>, tag=%d", rank, tree->child[i],
 307              system_tag + tree->child[i]);
 308       requests[i] =
 309           smpi_irecv_init(buf, count, datatype, tree->child[i],
 310                           system_tag + tree->child[i], comm);
 311     }
 312   }
 313   smpi_mpi_startall(tree->numChildren, requests);
 314   smpi_mpi_waitall(tree->numChildren, requests, MPI_STATUS_IGNORE);
 315   xbt_free(requests);
 316 }
 317
 318 /**
 319  * bcast with a binary, ternary, or whatever tree ..
 320  **/
 321 void nary_tree_bcast(void *buf, int count, MPI_Datatype datatype, int root,
 322                      MPI_Comm comm, int arity)
 323 {
 324   proc_tree_t tree = alloc_tree(arity);
 325   int rank, size;
 326
 327   rank = smpi_comm_rank(comm);
 328   size = smpi_comm_size(comm);
 329   build_tree(root, rank, size, &tree);
 330   tree_bcast(buf, count, datatype, comm, tree);
 331   free_tree(tree);
 332 }
 333
 334 /**
 335  * barrier with a binary, ternary, or whatever tree ..
 336  **/
 337 void nary_tree_barrier(MPI_Comm comm, int arity)
 338 {
 339   proc_tree_t tree = alloc_tree(arity);
 340   int rank, size;
 341   char dummy = '$';
 342
 343   rank = smpi_comm_rank(comm);
 344   size = smpi_comm_size(comm);
 345   build_tree(0, rank, size, &tree);
 346   tree_antibcast(&dummy, 1, MPI_CHAR, comm, tree);
 347   tree_bcast(&dummy, 1, MPI_CHAR, comm, tree);
 348   free_tree(tree);
 349 }
 350
 351 int smpi_coll_tuned_alltoall_ompi2(void *sendbuf, int sendcount,
 352                                    MPI_Datatype sendtype, void *recvbuf,
 353                                    int recvcount, MPI_Datatype recvtype,
 354                                    MPI_Comm comm)
 355 {
 356   int size, sendsize;
 357   size = smpi_comm_size(comm);
 358   sendsize = smpi_datatype_size(sendtype) * sendcount;
 359   if (sendsize < 200 && size > 12) {
 360     return
 361         smpi_coll_tuned_alltoall_bruck(sendbuf, sendcount, sendtype,
 362                                        recvbuf, recvcount, recvtype,
 363                                        comm);
 364   } else if (sendsize < 3000) {
 365     return
 366         smpi_coll_tuned_alltoall_basic_linear(sendbuf, sendcount,
 367                                               sendtype, recvbuf,
 368                                               recvcount, recvtype, comm);
 369   } else {
 370     return
 371         smpi_coll_tuned_alltoall_ring(sendbuf, sendcount, sendtype,
 372                                       recvbuf, recvcount, recvtype,
 373                                       comm);
 374   }
 375 }
 376
 377 /**
 378  * Alltoall Bruck
 379  *
 380  * Openmpi calls this routine when the message size sent to each rank < 2000 bytes and size < 12
 381  * FIXME: uh, check smpi_pmpi again, but this routine is called for > 12, not
 382  * less...
 383  **/
 384 int smpi_coll_tuned_alltoall_bruck(void *sendbuf, int sendcount,
 385                                    MPI_Datatype sendtype, void *recvbuf,
 386                                    int recvcount, MPI_Datatype recvtype,
 387                                    MPI_Comm comm)
 388 {
 389   int system_tag = 777;
 390   int i, rank, size, err, count;
 391   MPI_Aint lb;
 392   MPI_Aint sendext = 0;
 393   MPI_Aint recvext = 0;
 394   MPI_Request *requests;
 395
 396   // FIXME: check implementation
 397   rank = smpi_comm_rank(comm);
 398   size = smpi_comm_size(comm);
 399   XBT_DEBUG("<%d> algorithm alltoall_bruck() called.", rank);
 400   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 401   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 402   /* Local copy from self */
 403   err =
 404       smpi_datatype_copy((char *)sendbuf + rank * sendcount * sendext,
 405                          sendcount, sendtype,
 406                          (char *)recvbuf + rank * recvcount * recvext,
 407                          recvcount, recvtype);
 408   if (err == MPI_SUCCESS && size > 1) {
 409     /* Initiate all send/recv to/from others. */
 410     requests = xbt_new(MPI_Request, 2 * (size - 1));
 411     count = 0;
 412     /* Create all receives that will be posted first */
 413     for (i = 0; i < size; ++i) {
 414       if (i == rank) {
 415         XBT_DEBUG("<%d> skip request creation [src = %d, recvcount = %d]",
 416                rank, i, recvcount);
 417         continue;
 418       }
 419       requests[count] =
 420           smpi_irecv_init((char *)recvbuf + i * recvcount * recvext, recvcount,
 421                           recvtype, i, system_tag, comm);
 422       count++;
 423     }
 424     /* Now create all sends  */
 425     for (i = 0; i < size; ++i) {
 426       if (i == rank) {
 427         XBT_DEBUG("<%d> skip request creation [dst = %d, sendcount = %d]",
 428                rank, i, sendcount);
 429         continue;
 430       }
 431       requests[count] =
 432           smpi_isend_init((char *)sendbuf + i * sendcount * sendext, sendcount,
 433                           sendtype, i, system_tag, comm);
 434       count++;
 435     }
 436     /* Wait for them all. */
 437     smpi_mpi_startall(count, requests);
 438     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 439     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 440     xbt_free(requests);
 441   }
 442   return MPI_SUCCESS;
 443 }
 444
 445 /**
 446  * Alltoall basic_linear (STARMPI:alltoall-simple)
 447  **/
 448 int smpi_coll_tuned_alltoall_basic_linear(void *sendbuf, int sendcount,
 449                                           MPI_Datatype sendtype,
 450                                           void *recvbuf, int recvcount,
 451                                           MPI_Datatype recvtype,
 452                                           MPI_Comm comm)
 453 {
 454   int system_tag = 888;
 455   int i, rank, size, err, count;
 456   MPI_Aint lb = 0, sendext = 0, recvext = 0;
 457   MPI_Request *requests;
 458
 459   /* Initialize. */
 460   rank = smpi_comm_rank(comm);
 461   size = smpi_comm_size(comm);
 462   XBT_DEBUG("<%d> algorithm alltoall_basic_linear() called.", rank);
 463   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 464   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 465   /* simple optimization */
 466   err = smpi_datatype_copy((char *)sendbuf + rank * sendcount * sendext,
 467                            sendcount, sendtype,
 468                            (char *)recvbuf + rank * recvcount * recvext,
 469                            recvcount, recvtype);
 470   if (err == MPI_SUCCESS && size > 1) {
 471     /* Initiate all send/recv to/from others. */
 472     requests = xbt_new(MPI_Request, 2 * (size - 1));
 473     /* Post all receives first -- a simple optimization */
 474     count = 0;
 475     for (i = (rank + 1) % size; i != rank; i = (i + 1) % size) {
 476       requests[count] =
 477           smpi_irecv_init((char *)recvbuf + i * recvcount * recvext, recvcount,
 478                           recvtype, i, system_tag, comm);
 479       count++;
 480     }
 481     /* Now post all sends in reverse order
 482      *   - We would like to minimize the search time through message queue
 483      *     when messages actually arrive in the order in which they were posted.
 484      * TODO: check the previous assertion
 485      */
 486     for (i = (rank + size - 1) % size; i != rank; i = (i + size - 1) % size) {
 487       requests[count] =
 488           smpi_isend_init((char *)sendbuf + i * sendcount * sendext, sendcount,
 489                           sendtype, i, system_tag, comm);
 490       count++;
 491     }
 492     /* Wait for them all. */
 493     smpi_mpi_startall(count, requests);
 494     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 495     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 496     xbt_free(requests);
 497   }
 498   return err;
 499 }
 500
 501 int smpi_coll_basic_alltoallv(void *sendbuf, int *sendcounts,
 502                               int *senddisps, MPI_Datatype sendtype,
 503                               void *recvbuf, int *recvcounts,
 504                               int *recvdisps, MPI_Datatype recvtype,
 505                               MPI_Comm comm)
 506 {
 507   int system_tag = 889;
 508   int i, rank, size, err, count;
 509   MPI_Aint lb = 0, sendext = 0, recvext = 0;
 510   MPI_Request *requests;
 511
 512   /* Initialize. */
 513   rank = smpi_comm_rank(comm);
 514   size = smpi_comm_size(comm);
 515   XBT_DEBUG("<%d> algorithm basic_alltoallv() called.", rank);
 516   err = smpi_datatype_extent(sendtype, &lb, &sendext);
 517   err = smpi_datatype_extent(recvtype, &lb, &recvext);
 518   /* Local copy from self */
 519   err =
 520       smpi_datatype_copy((char *)sendbuf + senddisps[rank] * sendext,
 521                          sendcounts[rank], sendtype,
 522                          (char *)recvbuf + recvdisps[rank] * recvext,
 523                          recvcounts[rank], recvtype);
 524   if (err == MPI_SUCCESS && size > 1) {
 525     /* Initiate all send/recv to/from others. */
 526     requests = xbt_new(MPI_Request, 2 * (size - 1));
 527     count = 0;
 528     /* Create all receives that will be posted first */
 529     for (i = 0; i < size; ++i) {
 530       if (i == rank || recvcounts[i] == 0) {
 531         XBT_DEBUG
 532             ("<%d> skip request creation [src = %d, recvcounts[src] = %d]",
 533              rank, i, recvcounts[i]);
 534         continue;
 535       }
 536       requests[count] =
 537           smpi_irecv_init((char *)recvbuf + recvdisps[i] * recvext,
 538                           recvcounts[i], recvtype, i, system_tag, comm);
 539       count++;
 540     }
 541     /* Now create all sends  */
 542     for (i = 0; i < size; ++i) {
 543       if (i == rank || sendcounts[i] == 0) {
 544         XBT_DEBUG
 545             ("<%d> skip request creation [dst = %d, sendcounts[dst] = %d]",
 546              rank, i, sendcounts[i]);
 547         continue;
 548       }
 549       requests[count] =
 550           smpi_isend_init((char *)sendbuf + senddisps[i] * sendext,
 551                           sendcounts[i], sendtype, i, system_tag, comm);
 552       count++;
 553     }
 554     /* Wait for them all. */
 555     smpi_mpi_startall(count, requests);
 556     XBT_DEBUG("<%d> wait for %d requests", rank, count);
 557     smpi_mpi_waitall(count, requests, MPI_STATUS_IGNORE);
 558     xbt_free(requests);
 559   }
 560   return err;
 561 }