 Algorithmique Numérique Distribuée Public GIT Repository
1 /* Copyright (c) 2013-2019. The SimGrid Team.
2  * All rights reserved.                                                     */
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. */
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-2005 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  *
20  */
22 #include "coll_tuned_topo.hpp"
23 #include "colls_private.hpp"
24 /*
25  * Some static helpers.
26  */
27 static int pown( int fanout, int num )
28 {
29     int j, p = 1;
30     if( num < 0 ) return 0;
31     if (1==num) return fanout;
32     if (2==fanout) {
33         return p<<num;
34     }
35     else {
36         for( j = 0; j < num; j++ ) { p*= fanout; }
37     }
38     return p;
39 }
41 static int calculate_level( int fanout, int rank )
42 {
43     int level, num;
44     if( rank < 0 ) return -1;
45     for( level = 0, num = 0; num <= rank; level++ ) {
46         num += pown(fanout, level);
47     }
48     return level-1;
49 }
51 static int calculate_num_nodes_up_to_level( int fanout, int level )
52 {
53     /* just use geometric progression formula for sum:
54        a^0+a^1+...a^(n-1) = (a^n-1)/(a-1) */
55     if (fanout > 1)
56       return ((pown(fanout, level) - 1) / (fanout - 1));
57     else
58       return 0; // is this right ?
59 }
61 /*
62  * And now the building functions.
63  *
64  * An example for fanout = 2, comm_size = 7
65  *
66  *              0           <-- delta = 1 (fanout^0)
67  *            /   \
68  *           1     2        <-- delta = 2 (fanout^1)
69  *          / \   / \
70  *         3   5 4   6      <-- delta = 4 (fanout^2)
71  */
73 ompi_coll_tree_t*
74 ompi_coll_tuned_topo_build_tree( int fanout,
75                                  MPI_Comm comm,
76                                  int root )
77 {
78     int rank, size;
79     int schild, sparent;
80     int level; /* location of my rank in the tree structure of size */
81     int delta; /* number of nodes on my level */
82     int slimit; /* total number of nodes on levels above me */
83     int shiftedrank;
84     int i;
85     ompi_coll_tree_t* tree;
87     XBT_DEBUG("coll:tuned:topo_build_tree Building fo %d rt %d", fanout, root);
89     if (fanout<1) {
90         XBT_DEBUG("coll:tuned:topo_build_tree invalid fanout %d", fanout);
91         return NULL;
92     }
93     if (fanout>MAXTREEFANOUT) {
94         XBT_DEBUG("coll:tuned:topo_build_tree invalid fanout %d bigger than max %d", fanout, MAXTREEFANOUT);
95         return NULL;
96     }
98     /*
99      * Get size and rank of the process in this communicator
100      */
101     size = comm->size();
102     rank = comm->rank();
104     tree = new ompi_coll_tree_t;
105     if (not tree) {
106       XBT_DEBUG("coll:tuned:topo_build_tree PANIC::out of memory");
107       return NULL;
108     }
110     tree->tree_root     = MPI_UNDEFINED;
111     tree->tree_nextsize = MPI_UNDEFINED;
113     /*
114      * Set root
115      */
116     tree->tree_root = root;
118     /*
119      * Initialize tree
120      */
121     tree->tree_fanout   = fanout;
122     tree->tree_bmtree   = 0;
123     tree->tree_root     = root;
124     tree->tree_prev     = -1;
125     tree->tree_nextsize = 0;
126     for( i = 0; i < fanout; i++ ) {
127         tree->tree_next[i] = -1;
128     }
130     /* return if we have less than 2 processes */
131     if( size < 2 ) {
132         return tree;
133     }
135     /*
136      * Shift all ranks by root, so that the algorithm can be
137      * designed as if root would be always 0
138      * shiftedrank should be used in calculating distances
139      * and position in tree
140      */
141     shiftedrank = rank - root;
142     if( shiftedrank < 0 ) {
143         shiftedrank += size;
144     }
146     /* calculate my level */
147     level = calculate_level( fanout, shiftedrank );
148     delta = pown( fanout, level );
150     /* find my children */
151     for( i = 0; i < fanout; i++ ) {
152         schild = shiftedrank + delta * (i+1);
153         if( schild < size ) {
154             tree->tree_next[i] = (schild+root)%size;
155             tree->tree_nextsize = tree->tree_nextsize + 1;
156         } else {
157             break;
158         }
159     }
161     /* find my parent */
162     slimit = calculate_num_nodes_up_to_level( fanout, level );
163     sparent = shiftedrank;
164     if( sparent < fanout ) {
165         sparent = 0;
166     } else {
167         while( sparent >= slimit ) {
168             sparent -= delta/fanout;
169         }
170     }
171     tree->tree_prev = (sparent+root)%size;
173     return tree;
174 }
176 /*
177  * Constructs in-order binary tree which can be used for non-commutative reduce
178  * operations.
179  * Root of this tree is always rank (size-1) and fanout is 2.
180  * Here are some of the examples of this tree:
181  * size == 2     size == 3     size == 4                size == 9
182  *      1             2             3                        8
183  *     /             / \          /   \                    /   \
184  *    0             1  0         2     1                  7     3
185  *                                    /                 /  \   / \
186  *                                   0                 6    5 2   1
187  *                                                         /     /
188  *                                                        4     0
189  */
190 ompi_coll_tree_t*
191 ompi_coll_tuned_topo_build_in_order_bintree( MPI_Comm comm )
192 {
193     int rank, size;
194     int myrank, rightsize, delta;
195     int parent, lchild, rchild;
196     ompi_coll_tree_t* tree;
198     /*
199      * Get size and rank of the process in this communicator
200      */
201     size = comm->size();
202     rank = comm->rank();
204     tree = new ompi_coll_tree_t;
205     if (not tree) {
206       XBT_DEBUG("coll:tuned:topo_build_tree PANIC::out of memory");
207       return NULL;
208     }
210     tree->tree_root     = MPI_UNDEFINED;
211     tree->tree_nextsize = MPI_UNDEFINED;
213     /*
214      * Initialize tree
215      */
216     tree->tree_fanout   = 2;
217     tree->tree_bmtree   = 0;
218     tree->tree_root     = size - 1;
219     tree->tree_prev     = -1;
220     tree->tree_nextsize = 0;
221     tree->tree_next  = -1;
222     tree->tree_next  = -1;
223     XBT_DEBUG(
224                  "coll:tuned:topo_build_in_order_tree Building fo %d rt %d",
225                  tree->tree_fanout, tree->tree_root);
227     /*
228      * Build the tree
229      */
230     myrank = rank;
231     parent = size - 1;
232     delta = 0;
234     while ( 1 ) {
235         /* Compute the size of the right subtree */
236         rightsize = size >> 1;
238         /* Determine the left and right child of this parent  */
239         lchild = -1;
240         rchild = -1;
241         if (size - 1 > 0) {
242             lchild = parent - 1;
243             if (lchild > 0) {
244                 rchild = rightsize - 1;
245             }
246         }
248         /* The following cases are possible: myrank can be
249            - a parent,
250            - belong to the left subtree, or
251            - belong to the right subtee
252            Each of the cases need to be handled differently.
253         */
255         if (myrank == parent) {
256             /* I am the parent:
257                - compute real ranks of my children, and exit the loop. */
258             if (lchild >= 0) tree->tree_next = lchild + delta;
259             if (rchild >= 0) tree->tree_next = rchild + delta;
260             break;
261         }
262         if (myrank > rchild) {
263             /* I belong to the left subtree:
264                - If I am the left child, compute real rank of my parent
265                - Iterate down through tree:
266                compute new size, shift ranks down, and update delta.
267             */
268             if (myrank == lchild) {
269                 tree->tree_prev = parent + delta;
270             }
271             size = size - rightsize - 1;
272             delta = delta + rightsize;
273             myrank = myrank - rightsize;
274             parent = size - 1;
276         } else {
277             /* I belong to the right subtree:
278                - If I am the right child, compute real rank of my parent
279                - Iterate down through tree:
280                compute new size and parent,
281                but the delta and rank do not need to change.
282             */
283             if (myrank == rchild) {
284                 tree->tree_prev = parent + delta;
285             }
286             size = rightsize;
287             parent = rchild;
288         }
289     }
291     if (tree->tree_next >= 0) { tree->tree_nextsize = 1; }
292     if (tree->tree_next >= 0) { tree->tree_nextsize += 1; }
294     return tree;
295 }
297 int ompi_coll_tuned_topo_destroy_tree( ompi_coll_tree_t** tree )
298 {
299     ompi_coll_tree_t *ptr;
301     if ((tree == nullptr) || (*tree == nullptr)) {
302       return MPI_SUCCESS;
303     }
305     ptr = *tree;
307     delete ptr;
308     *tree = NULL;   /* mark tree as gone */
310     return MPI_SUCCESS;
311 }
313 /*
314  *
315  * Here are some of the examples of this tree:
316  * size == 2                   size = 4                 size = 8
317  *      0                           0                        0
318  *     /                            | \                    / | \
319  *    1                             2  1                  4  2  1
320  *                                     |                     |  |\
321  *                                     3                     6  5 3
322  *                                                                |
323  *                                                                7
324  */
325 ompi_coll_tree_t*
326 ompi_coll_tuned_topo_build_bmtree( MPI_Comm comm,
327                                    int root )
328 {
329     int childs = 0;
330     int rank;
331     int size;
333     int index;
334     int remote;
335     ompi_coll_tree_t *bmtree;
336     int i;
338     XBT_DEBUG("coll:tuned:topo:build_bmtree rt %d", root);
340     /*
341      * Get size and rank of the process in this communicator
342      */
343     size = comm->size();
344     rank = comm->rank();
346     index = rank -root;
348     bmtree = new ompi_coll_tree_t;
349     if (not bmtree) {
350       XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory");
351       return NULL;
352     }
354     bmtree->tree_bmtree   = 1;
356     bmtree->tree_root     = MPI_UNDEFINED;
357     bmtree->tree_nextsize = MPI_UNDEFINED;
358     for(i=0;i<MAXTREEFANOUT;i++) {
359         bmtree->tree_next[i] = -1;
360     }
362     if( index < 0 ) index += size;
366     /* Now I can compute my father rank */
367     if( root == rank ) {
368         bmtree->tree_prev = root;
369     } else {
370         remote = (index ^ (mask >> 1)) + root;
371         if( remote >= size ) remote -= size;
372         bmtree->tree_prev = remote;
373     }
374     /* And now let's fill my childs */
375     while( mask < size ) {
376         remote = (index ^ mask);
377         if( remote >= size ) break;
378         remote += root;
379         if( remote >= size ) remote -= size;
380         if (childs==MAXTREEFANOUT) {
381             XBT_DEBUG("coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d", MAXTREEFANOUT, childs);
382             return NULL;
383         }
384         bmtree->tree_next[childs] = remote;
386         childs++;
387     }
388     bmtree->tree_nextsize = childs;
389     bmtree->tree_root     = root;
390     return bmtree;
391 }
393 /*
394  * Constructs in-order binomial tree which can be used for gather/scatter
395  * operations.
396  *
397  * Here are some of the examples of this tree:
398  * size == 2                   size = 4                 size = 8
399  *      0                           0                        0
400  *     /                          / |                      / | \
401  *    1                          1  2                     1  2  4
402  *                                  |                        |  | \
403  *                                  3                        3  5  6
404  *                                                                 |
405  *                                                                 7
406  */
407 ompi_coll_tree_t* ompi_coll_tuned_topo_build_in_order_bmtree(MPI_Comm comm, int root)
408 {
409     int childs = 0;
410     int rank, vrank;
411     int size;
413     int remote;
414     ompi_coll_tree_t *bmtree;
415     int i;
417     XBT_DEBUG("coll:tuned:topo:build_in_order_bmtree rt %d", root);
419     /*
420      * Get size and rank of the process in this communicator
421      */
422     size = comm->size();
423     rank = comm->rank();
425     vrank = (rank - root + size) % size;
427     bmtree = new ompi_coll_tree_t;
428     if (not bmtree) {
429       XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory");
430       return NULL;
431     }
433     bmtree->tree_bmtree   = 1;
434     bmtree->tree_root     = MPI_UNDEFINED;
435     bmtree->tree_nextsize = MPI_UNDEFINED;
436     for(i=0;i<MAXTREEFANOUT;i++) {
437         bmtree->tree_next[i] = -1;
438     }
440     if (root == rank) {
441       bmtree->tree_prev = root;
442     }
444     while (mask < size) {
445       remote = vrank ^ mask;
446       if (remote < vrank) {
447         bmtree->tree_prev = (remote + root) % size;
448         break;
449       } else if (remote < size) {
450         bmtree->tree_next[childs] = (remote + root) % size;
451         childs++;
452         if (childs == MAXTREEFANOUT) {
453           XBT_DEBUG("coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d", MAXTREEFANOUT, childs);
454           return NULL;
455         }
456       }
458     }
459     bmtree->tree_nextsize = childs;
460     bmtree->tree_root     = root;
462     return bmtree;
463 }
466 ompi_coll_tree_t*
467 ompi_coll_tuned_topo_build_chain( int fanout,
468                                   MPI_Comm comm,
469                                   int root )
470 {
471     int rank, size;
472     int srank; /* shifted rank */
473     int i,maxchainlen;
475     ompi_coll_tree_t *chain;
477     XBT_DEBUG("coll:tuned:topo:build_chain fo %d rt %d", fanout, root);
479     /*
480      * Get size and rank of the process in this communicator
481      */
482     size = comm->size();
483     rank = comm->rank();
485     if( fanout < 1 ) {
486         XBT_DEBUG("coll:tuned:topo:build_chain WARNING invalid fanout of ZERO, forcing to 1 (pipeline)!");
487         fanout = 1;
488     }
489     if (fanout>MAXTREEFANOUT) {
490         XBT_DEBUG("coll:tuned:topo:build_chain WARNING invalid fanout %d bigger than max %d, forcing to max!", fanout, MAXTREEFANOUT);
491         fanout = MAXTREEFANOUT;
492     }
494     /*
495      * Allocate space for topology arrays if needed
496      */
497     chain = new ompi_coll_tree_t;
498     if (not chain) {
499       XBT_DEBUG("coll:tuned:topo:build_chain PANIC out of memory");
500       fflush(stdout);
501       return NULL;
502     }
503     chain->tree_root     = MPI_UNDEFINED;
504     chain->tree_nextsize = -1;
505     for(i=0;i<fanout;i++) chain->tree_next[i] = -1;
507     /*
508      * Set root & numchain
509      */
510     chain->tree_root = root;
511     if( (size - 1) < fanout ) {
512         chain->tree_nextsize = size-1;
513         fanout = size-1;
514     } else {
515         chain->tree_nextsize = fanout;
516     }
518     /*
519      * Shift ranks
520      */
521     srank = rank - root;
522     if (srank < 0) srank += size;
524     /*
525      * Special case - fanout == 1
526      */
527     if( fanout == 1 ) {
528         if( srank == 0 ) chain->tree_prev = -1;
529         else chain->tree_prev = (srank-1+root)%size;
531         if( (srank + 1) >= size) {
532             chain->tree_next = -1;
533             chain->tree_nextsize = 0;
534         } else {
535             chain->tree_next = (srank+1+root)%size;
536             chain->tree_nextsize = 1;
537         }
538         return chain;
539     }
541     /* Let's handle the case where there is just one node in the communicator */
542     if( size == 1 ) {
543         chain->tree_next = -1;
544         chain->tree_nextsize = 0;
545         chain->tree_prev = -1;
546         return chain;
547     }
548     /*
549      * Calculate maximum chain length
550      */
551     maxchainlen = (size-1) / fanout;
552     if( (size-1) % fanout != 0 ) {
553         maxchainlen++;
554         mark = (size-1)%fanout;
555     } else {
556         mark = fanout+1;
557     }
559     /*
560      * Find your own place in the list of shifted ranks
561      */
562     if( srank != 0 ) {
563         int column;
564         if( srank-1 < (mark * maxchainlen) ) {
565             column = (srank-1)/maxchainlen;
567             len = maxchainlen;
568         } else {
569             column = mark + (srank-1-mark*maxchainlen)/(maxchainlen-1);
571             len = maxchainlen-1;
572         }
574         if( srank == head ) {
575             chain->tree_prev = 0; /*root*/
576         } else {
577             chain->tree_prev = srank-1; /* rank -1 */
578         }
579         if( srank == (head + len - 1) ) {
580             chain->tree_next = -1;
581             chain->tree_nextsize = 0;
582         } else {
583             if( (srank + 1) < size ) {
584                 chain->tree_next = srank+1;
585                 chain->tree_nextsize = 1;
586             } else {
587                 chain->tree_next = -1;
588                 chain->tree_nextsize = 0;
589             }
590         }
591     }
593     /*
594      * Unshift values
595      */
596     if( rank == root ) {
597         chain->tree_prev = -1;
598         chain->tree_next = (root+1)%size;
599         for( i = 1; i < fanout; i++ ) {
600             chain->tree_next[i] = chain->tree_next[i-1] + maxchainlen;
601             if( i > mark ) {
602                 chain->tree_next[i]--;
603             }
604             chain->tree_next[i] %= size;
605         }
606         chain->tree_nextsize = fanout;
607     } else {
608         chain->tree_prev = (chain->tree_prev+root)%size;
609         if( chain->tree_next != -1 ) {
610             chain->tree_next = (chain->tree_next+root)%size;
611         }
612     }
614     return chain;
615 }
617 int ompi_coll_tuned_topo_dump_tree (ompi_coll_tree_t* tree, int rank)
618 {
619     int i;
621     XBT_DEBUG("coll:tuned:topo:topo_dump_tree %1d tree root %d"
622                  " fanout %d BM %1d nextsize %d prev %d",
623                  rank, tree->tree_root, tree->tree_bmtree, tree->tree_fanout,
624                  tree->tree_nextsize, tree->tree_prev);
625     if( tree->tree_nextsize ) {
626         for( i = 0; i < tree->tree_nextsize; i++ )
627             XBT_DEBUG("[%1d] %d", i, tree->tree_next[i]);
628     }
629     return (0);
630 }