root/ompi/patterns/net/netpatterns_multinomial_tree.c

DEFINITIONS

1. ompi_netpatterns_setup_multinomial_tree

   1 /*
   2  * Copyright (c) 2009-2012 Mellanox Technologies.  All rights reserved.
   3  * Copyright (c) 2009-2012 Oak Ridge National Laboratory.  All rights reserved.
   4  * Copyright (c) 2017      IBM Corporation. All rights reserved.
   5  * $COPYRIGHT$
   6  *
   7  * Additional copyrights may follow
   8  *
   9  * $HEADER$
  10  */
  11 
  12 #include "ompi_config.h"
  13 #ifdef HAVE_UNISTD_H
  14 #include <unistd.h>
  15 #endif
  16 #include <sys/types.h>
  17 #ifdef HAVE_SYS_MMAN_H
  18 #include <sys/mman.h>
  19 #endif
  20 #include <fcntl.h>
  21 #include <stdlib.h>
  22 
  23 #include "ompi/constants.h"
  24 #include "netpatterns.h"
  25 
  26 
  27 /* setup an multi-nomial tree - for each node in the tree
  28  *  this returns it's parent, and it's children */
  29 
  30 OMPI_DECLSPEC int ompi_netpatterns_setup_multinomial_tree(int tree_order, int num_nodes,
  31         netpatterns_tree_node_t *tree_nodes)
  32 {
  33     /* local variables */
  34     int i,result;
  35     int cnt, n_nodes_in_this_level,node_index;
  36     int n_cum_nodes,current_level,node,n_nodes_prev_level,rank,parent_rank;
  37     int n_nodes_in_last_level,n_full_stripes,n_in_partial_stipe,n_children;
  38     int n_lvls_in_tree;
  39 
  40     /* sanity check */
  41     if( 1 >= tree_order ) {
  42         goto Error;
  43     }
  44 
  45 
  46     /* figure out number of levels in the tree */
  47 
  48     n_lvls_in_tree=0;
  49     result=num_nodes;
  50     /* cnt - number of ranks in given level */
  51     cnt=1;
  52     /*  cummulative count of ranks */
  53     while( 0 < result ) {
  54         result-=cnt;
  55         cnt*=tree_order;
  56         n_lvls_in_tree++;
  57     };
  58 
  59     /* loop over tree levels */
  60     n_nodes_in_this_level=1;
  61     node_index=-1;
  62     n_cum_nodes=0;
  63     for( current_level = 0 ; current_level < n_lvls_in_tree ; current_level++) {
  64 
  65         /* loop over nodes in current level */
  66         for ( node=0 ; node < n_nodes_in_this_level ; node++ ) {
  67             /* get node index */
  68             node_index++;
  69 
  70             /* break if reach group size */
  71             if( node_index == num_nodes) {
  72                 break;
  73             }
  74 
  75             tree_nodes[node_index].my_rank=node_index;
  76             tree_nodes[node_index].children_ranks=NULL;
  77 
  78             /*
  79              *  Parents
  80              */
  81             if( 0 == current_level ) {
  82                 tree_nodes[node_index].n_parents=0;
  83                 /* get parent index */
  84                 tree_nodes[node_index].parent_rank=-1;
  85             } else {
  86                 tree_nodes[node_index].n_parents=1;
  87                 /* get parent index */
  88                 n_nodes_prev_level=n_nodes_in_this_level/tree_order;
  89                 if( current_level == n_lvls_in_tree -1 ) {
  90                     /* load balance the lowest level */
  91                     parent_rank=node-
  92                         (node/n_nodes_prev_level)*n_nodes_prev_level;
  93                     parent_rank=n_cum_nodes-n_nodes_prev_level+
  94                         parent_rank;
  95                     tree_nodes[node_index].parent_rank=parent_rank;
  96                 } else {
  97                     tree_nodes[node_index].parent_rank=
  98                         (n_cum_nodes-n_nodes_prev_level)+node/tree_order;
  99                 }
 100             }
 101 
 102             /*
 103              * Children
 104              */
 105 
 106             /* get number of children */
 107             if( (n_lvls_in_tree-1) == current_level ) {
 108                 /* leaves have no nodes */
 109                 tree_nodes[node_index].n_children=0;
 110                 tree_nodes[node_index].children_ranks=NULL;
 111             } else {
 112                 /* take into account last level being incomplete */
 113                 if( (n_lvls_in_tree-2) == current_level ) {
 114                     /* last level is load balanced */
 115                     n_nodes_in_last_level=num_nodes-
 116                         (n_cum_nodes+n_nodes_in_this_level);
 117                     n_full_stripes=n_nodes_in_last_level/n_nodes_in_this_level;
 118                     n_in_partial_stipe=n_nodes_in_last_level-
 119                         n_full_stripes*n_nodes_in_this_level;
 120                     n_children=n_full_stripes;
 121                     if( n_full_stripes < tree_order ) {
 122                         if( node <= n_in_partial_stipe-1 ) {
 123                             n_children++;
 124                         }
 125                     }
 126                     tree_nodes[node_index].n_children=n_children;
 127                     if( 0 < n_children ) {
 128                         tree_nodes[node_index].children_ranks=(int *)
 129                             malloc(sizeof(int)*n_children);
 130                         if( NULL == tree_nodes[node_index].children_ranks) {
 131                             goto Error;
 132                         }
 133                     } else {
 134                         tree_nodes[node_index].children_ranks=NULL;
 135                     }
 136                     /* fill in list */
 137                     for( rank=0 ; rank < n_children ; rank++ ) {
 138                         tree_nodes[node_index].children_ranks[rank]=
 139                             node+rank*n_nodes_in_this_level;
 140                         tree_nodes[node_index].children_ranks[rank]+=
 141                             (n_cum_nodes+n_nodes_in_this_level);
 142                     }
 143                 } else {
 144                     n_children=tree_order;
 145                     tree_nodes[node_index].n_children=tree_order;
 146                     tree_nodes[node_index].children_ranks=(int *)
 147                         malloc(sizeof(int)*n_children);
 148                     if( NULL == tree_nodes[node_index].children_ranks) {
 149                         goto Error;
 150                     }
 151                     for( rank=0 ; rank < n_children ; rank++ ) {
 152                         tree_nodes[node_index].children_ranks[rank]=
 153                             rank+tree_order*node;
 154                         tree_nodes[node_index].children_ranks[rank]+=
 155                             (n_cum_nodes+n_nodes_in_this_level);
 156                     }
 157                 }
 158             }
 159 
 160         } /* end node loop */
 161 
 162         /* update helper counters */
 163         n_cum_nodes+=n_nodes_in_this_level;
 164         n_nodes_in_this_level*=tree_order;
 165     }
 166 
 167     /* set node type */
 168     for(i=0 ; i < num_nodes ; i++ ) {
 169         if( 0 == tree_nodes[i].n_parents ) {
 170             tree_nodes[i].my_node_type=ROOT_NODE;
 171         } else if ( 0 == tree_nodes[i].n_children ) {
 172             tree_nodes[i].my_node_type=LEAF_NODE;
 173         } else {
 174             tree_nodes[i].my_node_type=INTERIOR_NODE;
 175         }
 176     }
 177 
 178     /* successful return */
 179     return OMPI_SUCCESS;
 180 
 181 Error:
 182     /* free allocated memory */
 183     for( i=0 ; i < num_nodes ; i++ ) {
 184         if( NULL != tree_nodes[i].children_ranks ) {
 185             free(tree_nodes[i].children_ranks);
 186         }
 187     }
 188 
 189     /* error return */
 190     return OMPI_ERROR;
 191 }