 Algorithmique Numérique Distribuée Public GIT Repository
a5c53b10f289fceaa888320f37bdcfe74624f12d
1 /* Copyright (c) 2013-2014. 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 "colls_private.h"
23 #include "coll_tuned_topo.h"
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     return ((pown(fanout,level) - 1)/(fanout - 1));
56 }
58 /*
59  * And now the building functions.
60  *
61  * An example for fanout = 2, comm_size = 7
62  *
63  *              0           <-- delta = 1 (fanout^0)
64  *            /   \
65  *           1     2        <-- delta = 2 (fanout^1)
66  *          / \   / \
67  *         3   5 4   6      <-- delta = 4 (fanout^2)
68  */
70 ompi_coll_tree_t*
71 ompi_coll_tuned_topo_build_tree( int fanout,
72                                  MPI_Comm comm,
73                                  int root )
74 {
75     int rank, size;
76     int schild, sparent;
77     int level; /* location of my rank in the tree structure of size */
78     int delta; /* number of nodes on my level */
79     int slimit; /* total number of nodes on levels above me */
80     int shiftedrank;
81     int i;
82     ompi_coll_tree_t* tree;
84     XBT_DEBUG("coll:tuned:topo_build_tree Building fo %d rt %d", fanout, root);
86     if (fanout<1) {
87         XBT_DEBUG("coll:tuned:topo_build_tree invalid fanout %d", fanout);
88         return NULL;
89     }
90     if (fanout>MAXTREEFANOUT) {
91         XBT_DEBUG("coll:tuned:topo_build_tree invalid fanout %d bigger than max %d", fanout, MAXTREEFANOUT);
92         return NULL;
93     }
95     /*
96      * Get size and rank of the process in this communicator
97      */
98     size = smpi_comm_size(comm);
99     rank = smpi_comm_rank(comm);
101     tree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t));
102     if (!tree) {
103         XBT_DEBUG("coll:tuned:topo_build_tree PANIC::out of memory");
104         return NULL;
105     }
107     tree->tree_root     = MPI_UNDEFINED;
108     tree->tree_nextsize = MPI_UNDEFINED;
110     /*
111      * Set root
112      */
113     tree->tree_root = root;
115     /*
116      * Initialize tree
117      */
118     tree->tree_fanout   = fanout;
119     tree->tree_bmtree   = 0;
120     tree->tree_root     = root;
121     tree->tree_prev     = -1;
122     tree->tree_nextsize = 0;
123     for( i = 0; i < fanout; i++ ) {
124         tree->tree_next[i] = -1;
125     }
127     /* return if we have less than 2 processes */
128     if( size < 2 ) {
129         return tree;
130     }
132     /*
133      * Shift all ranks by root, so that the algorithm can be
134      * designed as if root would be always 0
135      * shiftedrank should be used in calculating distances
136      * and position in tree
137      */
138     shiftedrank = rank - root;
139     if( shiftedrank < 0 ) {
140         shiftedrank += size;
141     }
143     /* calculate my level */
144     level = calculate_level( fanout, shiftedrank );
145     delta = pown( fanout, level );
147     /* find my children */
148     for( i = 0; i < fanout; i++ ) {
149         schild = shiftedrank + delta * (i+1);
150         if( schild < size ) {
151             tree->tree_next[i] = (schild+root)%size;
152             tree->tree_nextsize = tree->tree_nextsize + 1;
153         } else {
154             break;
155         }
156     }
158     /* find my parent */
159     slimit = calculate_num_nodes_up_to_level( fanout, level );
160     sparent = shiftedrank;
161     if( sparent < fanout ) {
162         sparent = 0;
163     } else {
164         while( sparent >= slimit ) {
165             sparent -= delta/fanout;
166         }
167     }
168     tree->tree_prev = (sparent+root)%size;
170     return tree;
171 }
173 /*
174  * Constructs in-order binary tree which can be used for non-commutative reduce
175  * operations.
176  * Root of this tree is always rank (size-1) and fanout is 2.
177  * Here are some of the examples of this tree:
178  * size == 2     size == 3     size == 4                size == 9
179  *      1             2             3                        8
180  *     /             / \          /   \                    /   \
181  *    0             1  0         2     1                  7     3
182  *                                    /                 /  \   / \
183  *                                   0                 6    5 2   1
184  *                                                         /     /
185  *                                                        4     0
186  */
187 ompi_coll_tree_t*
188 ompi_coll_tuned_topo_build_in_order_bintree( MPI_Comm comm )
189 {
190     int rank, size;
191     int myrank, rightsize, delta;
192     int parent, lchild, rchild;
193     ompi_coll_tree_t* tree;
195     /*
196      * Get size and rank of the process in this communicator
197      */
198     size = smpi_comm_size(comm);
199     rank = smpi_comm_rank(comm);
201     tree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t));
202     if (!tree) {
203         XBT_DEBUG(
204                      "coll:tuned:topo_build_tree PANIC::out of memory");
205         return NULL;
206     }
208     tree->tree_root     = MPI_UNDEFINED;
209     tree->tree_nextsize = MPI_UNDEFINED;
211     /*
212      * Initialize tree
213      */
214     tree->tree_fanout   = 2;
215     tree->tree_bmtree   = 0;
216     tree->tree_root     = size - 1;
217     tree->tree_prev     = -1;
218     tree->tree_nextsize = 0;
219     tree->tree_next  = -1;
220     tree->tree_next  = -1;
221     XBT_DEBUG(
222                  "coll:tuned:topo_build_in_order_tree Building fo %d rt %d",
223                  tree->tree_fanout, tree->tree_root);
225     /*
226      * Build the tree
227      */
228     myrank = rank;
229     parent = size - 1;
230     delta = 0;
232     while ( 1 ) {
233         /* Compute the size of the right subtree */
234         rightsize = size >> 1;
236         /* Determine the left and right child of this parent  */
237         lchild = -1;
238         rchild = -1;
239         if (size - 1 > 0) {
240             lchild = parent - 1;
241             if (lchild > 0) {
242                 rchild = rightsize - 1;
243             }
244         }
246         /* The following cases are possible: myrank can be
247            - a parent,
248            - belong to the left subtree, or
249            - belong to the right subtee
250            Each of the cases need to be handled differently.
251         */
253         if (myrank == parent) {
254             /* I am the parent:
255                - compute real ranks of my children, and exit the loop. */
256             if (lchild >= 0) tree->tree_next = lchild + delta;
257             if (rchild >= 0) tree->tree_next = rchild + delta;
258             break;
259         }
260         if (myrank > rchild) {
261             /* I belong to the left subtree:
262                - If I am the left child, compute real rank of my parent
263                - Iterate down through tree:
264                compute new size, shift ranks down, and update delta.
265             */
266             if (myrank == lchild) {
267                 tree->tree_prev = parent + delta;
268             }
269             size = size - rightsize - 1;
270             delta = delta + rightsize;
271             myrank = myrank - rightsize;
272             parent = size - 1;
274         } else {
275             /* I belong to the right subtree:
276                - If I am the right child, compute real rank of my parent
277                - Iterate down through tree:
278                compute new size and parent,
279                but the delta and rank do not need to change.
280             */
281             if (myrank == rchild) {
282                 tree->tree_prev = parent + delta;
283             }
284             size = rightsize;
285             parent = rchild;
286         }
287     }
289     if (tree->tree_next >= 0) { tree->tree_nextsize = 1; }
290     if (tree->tree_next >= 0) { tree->tree_nextsize += 1; }
292     return tree;
293 }
295 int ompi_coll_tuned_topo_destroy_tree( ompi_coll_tree_t** tree )
296 {
297     ompi_coll_tree_t *ptr;
299     if ((!tree)||(!*tree)) {
300         return MPI_SUCCESS;
301     }
303     ptr = *tree;
305     free (ptr);
306     *tree = NULL;   /* mark tree as gone */
308     return MPI_SUCCESS;
309 }
311 /*
312  *
313  * Here are some of the examples of this tree:
314  * size == 2                   size = 4                 size = 8
315  *      0                           0                        0
316  *     /                            | \                    / | \
317  *    1                             2  1                  4  2  1
318  *                                     |                     |  |\
319  *                                     3                     6  5 3
320  *                                                                |
321  *                                                                7
322  */
323 ompi_coll_tree_t*
324 ompi_coll_tuned_topo_build_bmtree( MPI_Comm comm,
325                                    int root )
326 {
327     int childs = 0;
328     int rank;
329     int size;
331     int index;
332     int remote;
333     ompi_coll_tree_t *bmtree;
334     int i;
336     XBT_DEBUG("coll:tuned:topo:build_bmtree rt %d", root);
338     /*
339      * Get size and rank of the process in this communicator
340      */
341     size = smpi_comm_size(comm);
342     rank = smpi_comm_rank(comm);
344     index = rank -root;
346     bmtree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t));
347     if (!bmtree) {
348         XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory");
349         return NULL;
350     }
352     bmtree->tree_bmtree   = 1;
354     bmtree->tree_root     = MPI_UNDEFINED;
355     bmtree->tree_nextsize = MPI_UNDEFINED;
356     for(i=0;i<MAXTREEFANOUT;i++) {
357         bmtree->tree_next[i] = -1;
358     }
360     if( index < 0 ) index += size;
364     /* Now I can compute my father rank */
365     if( root == rank ) {
366         bmtree->tree_prev = root;
367     } else {
368         remote = (index ^ (mask >> 1)) + root;
369         if( remote >= size ) remote -= size;
370         bmtree->tree_prev = remote;
371     }
372     /* And now let's fill my childs */
373     while( mask < size ) {
374         remote = (index ^ mask);
375         if( remote >= size ) break;
376         remote += root;
377         if( remote >= size ) remote -= size;
378         if (childs==MAXTREEFANOUT) {
379             XBT_DEBUG("coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d", MAXTREEFANOUT, childs);
380             return NULL;
381         }
382         bmtree->tree_next[childs] = remote;
384         childs++;
385     }
386     bmtree->tree_nextsize = childs;
387     bmtree->tree_root     = root;
388     return bmtree;
389 }
391 /*
392  * Constructs in-order binomial tree which can be used for gather/scatter
393  * operations.
394  *
395  * Here are some of the examples of this tree:
396  * size == 2                   size = 4                 size = 8
397  *      0                           0                        0
398  *     /                          / |                      / | \
399  *    1                          1  2                     1  2  4
400  *                                  |                        |  | \
401  *                                  3                        3  5  6
402  *                                                                 |
403  *                                                                 7
404  */
405 ompi_coll_tree_t*
406 ompi_coll_tuned_topo_build_in_order_bmtree( MPI_Comm comm,
407                                             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 = smpi_comm_size(comm);
423     rank = smpi_comm_rank(comm);
425     vrank = (rank - root + size) % size;
427     bmtree = (ompi_coll_tree_t*)xbt_malloc(sizeof(ompi_coll_tree_t));
428     if (!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(
454                              "coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d",
455                              MAXTREEFANOUT, childs);
456                 return NULL;
457             }
458         }
460     }
461     bmtree->tree_nextsize = childs;
462     bmtree->tree_root     = root;
464     return bmtree;
465 }
468 ompi_coll_tree_t*
469 ompi_coll_tuned_topo_build_chain( int fanout,
470                                   MPI_Comm comm,
471                                   int root )
472 {
473     int rank, size;
474     int srank; /* shifted rank */
475     int i,maxchainlen;
477     ompi_coll_tree_t *chain;
479     XBT_DEBUG("coll:tuned:topo:build_chain fo %d rt %d", fanout, root);
481     /*
482      * Get size and rank of the process in this communicator
483      */
484     size = smpi_comm_size(comm);
485     rank = smpi_comm_rank(comm);
487     if( fanout < 1 ) {
488         XBT_DEBUG("coll:tuned:topo:build_chain WARNING invalid fanout of ZERO, forcing to 1 (pipeline)!");
489         fanout = 1;
490     }
491     if (fanout>MAXTREEFANOUT) {
492         XBT_DEBUG("coll:tuned:topo:build_chain WARNING invalid fanout %d bigger than max %d, forcing to max!", fanout, MAXTREEFANOUT);
493         fanout = MAXTREEFANOUT;
494     }
496     /*
497      * Allocate space for topology arrays if needed
498      */
499     chain = (ompi_coll_tree_t*)malloc( sizeof(ompi_coll_tree_t) );
500     if (!chain) {
501         XBT_DEBUG("coll:tuned:topo:build_chain PANIC out of memory");
502         fflush(stdout);
503         return NULL;
504     }
505     chain->tree_root     = MPI_UNDEFINED;
506     chain->tree_nextsize = -1;
507     for(i=0;i<fanout;i++) chain->tree_next[i] = -1;
509     /*
510      * Set root & numchain
511      */
512     chain->tree_root = root;
513     if( (size - 1) < fanout ) {
514         chain->tree_nextsize = size-1;
515         fanout = size-1;
516     } else {
517         chain->tree_nextsize = fanout;
518     }
520     /*
521      * Shift ranks
522      */
523     srank = rank - root;
524     if (srank < 0) srank += size;
526     /*
527      * Special case - fanout == 1
528      */
529     if( fanout == 1 ) {
530         if( srank == 0 ) chain->tree_prev = -1;
531         else chain->tree_prev = (srank-1+root)%size;
533         if( (srank + 1) >= size) {
534             chain->tree_next = -1;
535             chain->tree_nextsize = 0;
536         } else {
537             chain->tree_next = (srank+1+root)%size;
538             chain->tree_nextsize = 1;
539         }
540         return chain;
541     }
543     /* Let's handle the case where there is just one node in the communicator */
544     if( size == 1 ) {
545         chain->tree_next = -1;
546         chain->tree_nextsize = 0;
547         chain->tree_prev = -1;
548         return chain;
549     }
550     /*
551      * Calculate maximum chain length
552      */
553     maxchainlen = (size-1) / fanout;
554     if( (size-1) % fanout != 0 ) {
555         maxchainlen++;
556         mark = (size-1)%fanout;
557     } else {
558         mark = fanout+1;
559     }
561     /*
562      * Find your own place in the list of shifted ranks
563      */
564     if( srank != 0 ) {
565         int column;
566         if( srank-1 < (mark * maxchainlen) ) {
567             column = (srank-1)/maxchainlen;
569             len = maxchainlen;
570         } else {
571             column = mark + (srank-1-mark*maxchainlen)/(maxchainlen-1);
573             len = maxchainlen-1;
574         }
576         if( srank == head ) {
577             chain->tree_prev = 0; /*root*/
578         } else {
579             chain->tree_prev = srank-1; /* rank -1 */
580         }
581         if( srank == (head + len - 1) ) {
582             chain->tree_next = -1;
583             chain->tree_nextsize = 0;
584         } else {
585             if( (srank + 1) < size ) {
586                 chain->tree_next = srank+1;
587                 chain->tree_nextsize = 1;
588             } else {
589                 chain->tree_next = -1;
590                 chain->tree_nextsize = 0;
591             }
592         }
593     }
595     /*
596      * Unshift values
597      */
598     if( rank == root ) {
599         chain->tree_prev = -1;
600         chain->tree_next = (root+1)%size;
601         for( i = 1; i < fanout; i++ ) {
602             chain->tree_next[i] = chain->tree_next[i-1] + maxchainlen;
603             if( i > mark ) {
604                 chain->tree_next[i]--;
605             }
606             chain->tree_next[i] %= size;
607         }
608         chain->tree_nextsize = fanout;
609     } else {
610         chain->tree_prev = (chain->tree_prev+root)%size;
611         if( chain->tree_next != -1 ) {
612             chain->tree_next = (chain->tree_next+root)%size;
613         }
614     }
616     return chain;
617 }
619 int ompi_coll_tuned_topo_dump_tree (ompi_coll_tree_t* tree, int rank)
620 {
621     int i;
623     XBT_DEBUG("coll:tuned:topo:topo_dump_tree %1d tree root %d"
624                  " fanout %d BM %1d nextsize %d prev %d",
625                  rank, tree->tree_root, tree->tree_bmtree, tree->tree_fanout,
626                  tree->tree_nextsize, tree->tree_prev);
627     if( tree->tree_nextsize ) {
628         for( i = 0; i < tree->tree_nextsize; i++ )
629             XBT_DEBUG("[%1d] %d", i, tree->tree_next[i]);
630     }
631     return (0);
632 }