src/smpi/colls/coll_tuned_topo.c

   1 /* Copyright (c) 2013-2014. 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 "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 }
  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     return ((pown(fanout,level) - 1)/(fanout - 1));
  56 }
  57
  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  */
  69
  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;
  83
  84     XBT_DEBUG("coll:tuned:topo_build_tree Building fo %d rt %d", fanout, root);
  85
  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     }
  94
  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);
 100
 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     }
 106
 107     tree->tree_root     = MPI_UNDEFINED;
 108     tree->tree_nextsize = MPI_UNDEFINED;
 109
 110     /*
 111      * Set root
 112      */
 113     tree->tree_root = root;
 114
 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     }
 126
 127     /* return if we have less than 2 processes */
 128     if( size < 2 ) {
 129         return tree;
 130     }
 131
 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     }
 142
 143     /* calculate my level */
 144     level = calculate_level( fanout, shiftedrank );
 145     delta = pown( fanout, level );
 146
 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     }
 157
 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;
 169
 170     return tree;
 171 }
 172
 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;
 194
 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);
 200
 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     }
 207
 208     tree->tree_root     = MPI_UNDEFINED;
 209     tree->tree_nextsize = MPI_UNDEFINED;
 210
 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[0]  = -1;
 220     tree->tree_next[1]  = -1;
 221     XBT_DEBUG(
 222                  "coll:tuned:topo_build_in_order_tree Building fo %d rt %d",
 223                  tree->tree_fanout, tree->tree_root);
 224
 225     /*
 226      * Build the tree
 227      */
 228     myrank = rank;
 229     parent = size - 1;
 230     delta = 0;
 231
 232     while ( 1 ) {
 233         /* Compute the size of the right subtree */
 234         rightsize = size >> 1;
 235
 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         }
 245
 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         */
 252
 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[0] = lchild + delta;
 257             if (rchild >= 0) tree->tree_next[1] = 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;
 273
 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     }
 288
 289     if (tree->tree_next[0] >= 0) { tree->tree_nextsize = 1; }
 290     if (tree->tree_next[1] >= 0) { tree->tree_nextsize += 1; }
 291
 292     return tree;
 293 }
 294
 295 int ompi_coll_tuned_topo_destroy_tree( ompi_coll_tree_t** tree )
 296 {
 297     ompi_coll_tree_t *ptr;
 298
 299     if ((!tree)||(!*tree)) {
 300         return MPI_SUCCESS;
 301     }
 302
 303     ptr = *tree;
 304
 305     free (ptr);
 306     *tree = NULL;   /* mark tree as gone */
 307
 308     return MPI_SUCCESS;
 309 }
 310
 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;
 330     int mask = 1;
 331     int index;
 332     int remote;
 333     ompi_coll_tree_t *bmtree;
 334     int i;
 335
 336     XBT_DEBUG("coll:tuned:topo:build_bmtree rt %d", root);
 337
 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);
 343
 344     index = rank -root;
 345
 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     }
 351
 352     bmtree->tree_bmtree   = 1;
 353
 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     }
 359
 360     if( index < 0 ) index += size;
 361
 362     while( mask <= index ) mask <<= 1;
 363
 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;
 383         mask <<= 1;
 384         childs++;
 385     }
 386     bmtree->tree_nextsize = childs;
 387     bmtree->tree_root     = root;
 388     return bmtree;
 389 }
 390
 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;
 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 = smpi_comm_size(comm);
 423     rank = smpi_comm_rank(comm);
 424
 425     vrank = (rank - root + size) % size;
 426
 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     }
 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(
 454                              "coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d",
 455                              MAXTREEFANOUT, childs);
 456                 return NULL;
 457             }
 458         }
 459         mask <<= 1;
 460     }
 461     bmtree->tree_nextsize = childs;
 462     bmtree->tree_root     = root;
 463
 464     return bmtree;
 465 }
 466
 467
 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;
 476     int mark,head,len;
 477     ompi_coll_tree_t *chain;
 478
 479     XBT_DEBUG("coll:tuned:topo:build_chain fo %d rt %d", fanout, root);
 480
 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);
 486
 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     }
 495
 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;
 508
 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     }
 519
 520     /*
 521      * Shift ranks
 522      */
 523     srank = rank - root;
 524     if (srank < 0) srank += size;
 525
 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;
 532
 533         if( (srank + 1) >= size) {
 534             chain->tree_next[0] = -1;
 535             chain->tree_nextsize = 0;
 536         } else {
 537             chain->tree_next[0] = (srank+1+root)%size;
 538             chain->tree_nextsize = 1;
 539         }
 540         return chain;
 541     }
 542
 543     /* Let's handle the case where there is just one node in the communicator */
 544     if( size == 1 ) {
 545         chain->tree_next[0] = -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     }
 560
 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;
 568             head = 1+column*maxchainlen;
 569             len = maxchainlen;
 570         } else {
 571             column = mark + (srank-1-mark*maxchainlen)/(maxchainlen-1);
 572             head = mark*maxchainlen+1+(column-mark)*(maxchainlen-1);
 573             len = maxchainlen-1;
 574         }
 575
 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[0] = -1;
 583             chain->tree_nextsize = 0;
 584         } else {
 585             if( (srank + 1) < size ) {
 586                 chain->tree_next[0] = srank+1;
 587                 chain->tree_nextsize = 1;
 588             } else {
 589                 chain->tree_next[0] = -1;
 590                 chain->tree_nextsize = 0;
 591             }
 592         }
 593     }
 594
 595     /*
 596      * Unshift values
 597      */
 598     if( rank == root ) {
 599         chain->tree_prev = -1;
 600         chain->tree_next[0] = (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[0] != -1 ) {
 612             chain->tree_next[0] = (chain->tree_next[0]+root)%size;
 613         }
 614     }
 615
 616     return chain;
 617 }
 618
 619 int ompi_coll_tuned_topo_dump_tree (ompi_coll_tree_t* tree, int rank)
 620 {
 621     int i;
 622
 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 }