src/smpi/colls/coll_tuned_topo.cpp

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