src/smpi/colls/coll_tuned_topo.c

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