Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'dvfs'
[simgrid.git] / 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 #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 = 999;         // used negative int but smpi_create_request() declares this illegal (to be checked)
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 = 999;         // used negative int but smpi_create_request() declares this illegal (to be checked)
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 }