src/smpi/colls/coll_tuned_topo.cpp

   1 /* Copyright (c) 2013-2017. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   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. */
   6
   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  *
  19  * Additional copyrights may follow
  20  */
  21
  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 }
  40
  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 }
  50
  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 }
  60
  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  */
  72
  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;
  86
  87     XBT_DEBUG("coll:tuned:topo_build_tree Building fo %d rt %d", fanout, root);
  88
  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     }
  97
  98     /*
  99      * Get size and rank of the process in this communicator
 100      */
 101     size = comm->size();
 102     rank = comm->rank();
 103
 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     }
 109
 110     tree->tree_root     = MPI_UNDEFINED;
 111     tree->tree_nextsize = MPI_UNDEFINED;
 112
 113     /*
 114      * Set root
 115      */
 116     tree->tree_root = root;
 117
 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     }
 129
 130     /* return if we have less than 2 processes */
 131     if( size < 2 ) {
 132         return tree;
 133     }
 134
 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     }
 145
 146     /* calculate my level */
 147     level = calculate_level( fanout, shiftedrank );
 148     delta = pown( fanout, level );
 149
 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     }
 160
 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;
 172
 173     return tree;
 174 }
 175
 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;
 197
 198     /*
 199      * Get size and rank of the process in this communicator
 200      */
 201     size = comm->size();
 202     rank = comm->rank();
 203
 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     }
 209
 210     tree->tree_root     = MPI_UNDEFINED;
 211     tree->tree_nextsize = MPI_UNDEFINED;
 212
 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[0]  = -1;
 222     tree->tree_next[1]  = -1;
 223     XBT_DEBUG(
 224                  "coll:tuned:topo_build_in_order_tree Building fo %d rt %d",
 225                  tree->tree_fanout, tree->tree_root);
 226
 227     /*
 228      * Build the tree
 229      */
 230     myrank = rank;
 231     parent = size - 1;
 232     delta = 0;
 233
 234     while ( 1 ) {
 235         /* Compute the size of the right subtree */
 236         rightsize = size >> 1;
 237
 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         }
 247
 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         */
 254
 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[0] = lchild + delta;
 259             if (rchild >= 0) tree->tree_next[1] = 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;
 275
 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     }
 290
 291     if (tree->tree_next[0] >= 0) { tree->tree_nextsize = 1; }
 292     if (tree->tree_next[1] >= 0) { tree->tree_nextsize += 1; }
 293
 294     return tree;
 295 }
 296
 297 int ompi_coll_tuned_topo_destroy_tree( ompi_coll_tree_t** tree )
 298 {
 299     ompi_coll_tree_t *ptr;
 300
 301     if ((tree == nullptr) || (*tree == nullptr)) {
 302       return MPI_SUCCESS;
 303     }
 304
 305     ptr = *tree;
 306
 307     delete ptr;
 308     *tree = NULL;   /* mark tree as gone */
 309
 310     return MPI_SUCCESS;
 311 }
 312
 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;
 332     int mask = 1;
 333     int index;
 334     int remote;
 335     ompi_coll_tree_t *bmtree;
 336     int i;
 337
 338     XBT_DEBUG("coll:tuned:topo:build_bmtree rt %d", root);
 339
 340     /*
 341      * Get size and rank of the process in this communicator
 342      */
 343     size = comm->size();
 344     rank = comm->rank();
 345
 346     index = rank -root;
 347
 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     }
 353
 354     bmtree->tree_bmtree   = 1;
 355
 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     }
 361
 362     if( index < 0 ) index += size;
 363
 364     while( mask <= index ) mask <<= 1;
 365
 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;
 385         mask <<= 1;
 386         childs++;
 387     }
 388     bmtree->tree_nextsize = childs;
 389     bmtree->tree_root     = root;
 390     return bmtree;
 391 }
 392
 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;
 412     int mask = 1;
 413     int remote;
 414     ompi_coll_tree_t *bmtree;
 415     int i;
 416
 417     XBT_DEBUG("coll:tuned:topo:build_in_order_bmtree rt %d", root);
 418
 419     /*
 420      * Get size and rank of the process in this communicator
 421      */
 422     size = comm->size();
 423     rank = comm->rank();
 424
 425     vrank = (rank - root + size) % size;
 426
 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     }
 432
 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     }
 439
 440     if (root == rank) {
 441       bmtree->tree_prev = root;
 442     }
 443
 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       }
 457       mask <<= 1;
 458     }
 459     bmtree->tree_nextsize = childs;
 460     bmtree->tree_root     = root;
 461
 462     return bmtree;
 463 }
 464
 465
 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;
 474     int mark,head,len;
 475     ompi_coll_tree_t *chain;
 476
 477     XBT_DEBUG("coll:tuned:topo:build_chain fo %d rt %d", fanout, root);
 478
 479     /*
 480      * Get size and rank of the process in this communicator
 481      */
 482     size = comm->size();
 483     rank = comm->rank();
 484
 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     }
 493
 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;
 506
 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     }
 517
 518     /*
 519      * Shift ranks
 520      */
 521     srank = rank - root;
 522     if (srank < 0) srank += size;
 523
 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;
 530
 531         if( (srank + 1) >= size) {
 532             chain->tree_next[0] = -1;
 533             chain->tree_nextsize = 0;
 534         } else {
 535             chain->tree_next[0] = (srank+1+root)%size;
 536             chain->tree_nextsize = 1;
 537         }
 538         return chain;
 539     }
 540
 541     /* Let's handle the case where there is just one node in the communicator */
 542     if( size == 1 ) {
 543         chain->tree_next[0] = -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     }
 558
 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;
 566             head = 1+column*maxchainlen;
 567             len = maxchainlen;
 568         } else {
 569             column = mark + (srank-1-mark*maxchainlen)/(maxchainlen-1);
 570             head = mark*maxchainlen+1+(column-mark)*(maxchainlen-1);
 571             len = maxchainlen-1;
 572         }
 573
 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[0] = -1;
 581             chain->tree_nextsize = 0;
 582         } else {
 583             if( (srank + 1) < size ) {
 584                 chain->tree_next[0] = srank+1;
 585                 chain->tree_nextsize = 1;
 586             } else {
 587                 chain->tree_next[0] = -1;
 588                 chain->tree_nextsize = 0;
 589             }
 590         }
 591     }
 592
 593     /*
 594      * Unshift values
 595      */
 596     if( rank == root ) {
 597         chain->tree_prev = -1;
 598         chain->tree_next[0] = (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[0] != -1 ) {
 610             chain->tree_next[0] = (chain->tree_next[0]+root)%size;
 611         }
 612     }
 613
 614     return chain;
 615 }
 616
 617 int ompi_coll_tuned_topo_dump_tree (ompi_coll_tree_t* tree, int rank)
 618 {
 619     int i;
 620
 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 }