src/smpi/colls/coll_tuned_topo.cpp

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