ompi/patterns/net/netpatterns_nary

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
ompi_netpatterns_setup_narray_tree
ompi_netpatterns_cleanup_narray_knomial_tree
ompi_netpatterns_setup_narray_knomial_tree
ompi_roundup_to_power_radix
fill_in_node_data
ompi_netpatterns_setup_narray_tree_contigous_ranks
   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
   2 /*
   3  * Copyright (c) 2009-2012 Mellanox Technologies.  All rights reserved.
   4  * Copyright (c) 2009-2012 Oak Ridge National Laboratory.  All rights reserved.
   5  * Copyright (c) 2014      Los Alamos National Security, LLC. All rights
   6  *                         reserved.
   7  * Copyright (c) 2017      IBM Corporation. All rights reserved.
   8  * $COPYRIGHT$
   9  *
  10  * Additional copyrights may follow
  11  *
  12  * $HEADER$
  13  */
  14 
  15 #include "ompi_config.h"
  16 #ifdef HAVE_UNISTD_H
  17 #include <unistd.h>
  18 #endif
  19 #include <sys/types.h>
  20 #ifdef HAVE_SYS_MMAN_H
  21 #include <sys/mman.h>
  22 #endif
  23 #include <fcntl.h>
  24 #include <errno.h>
  25 #include <stdlib.h>
  26 
  27 #include "ompi/constants.h"
  28 #include "netpatterns.h"
  29 
  30 /*
  31  * Create mmaped shared file
  32  */
  33 
  34 /* setup an n-array tree */
  35 
  36 int ompi_netpatterns_setup_narray_tree(int tree_order, int my_rank, int num_nodes,
  37         netpatterns_tree_node_t *my_node)
  38 {
  39     /* local variables */
  40     int n_levels, result;
  41     int my_level_in_tree, cnt;
  42     int lvl,cum_cnt, my_rank_in_my_level,n_lvls_in_tree;
  43     int start_index,end_index;
  44 
  45     /* sanity check */
  46     if( 1 >= tree_order ) {
  47         goto Error;
  48     }
  49 
  50     my_node->my_rank=my_rank;
  51     my_node->tree_size=num_nodes;
  52 
  53     /* figure out number of levels in tree */
  54     n_levels=0;
  55     result=num_nodes-1;
  56     while (0 < result ) {
  57         result/=tree_order;
  58         n_levels++;
  59     };
  60 
  61     /* figure out who my children and parents are */
  62     my_level_in_tree=-1;
  63     result=my_rank;
  64     /* cnt - number of ranks in given level */
  65     cnt=1;
  66     /*  cummulative count of ranks */
  67     while( 0 <= result ) {
  68         result-=cnt;
  69         cnt*=tree_order;
  70         my_level_in_tree++;
  71     };
  72     /* int my_level_in_tree, n_children, n_parents; */
  73 
  74     if( 0 == my_rank ) {
  75         my_node->n_parents=0;
  76         my_node->parent_rank=-1;
  77         my_rank_in_my_level=0;
  78     } else {
  79         my_node->n_parents=1;
  80         cnt=1;
  81         cum_cnt=0;
  82         for (lvl = 0 ; lvl < my_level_in_tree ; lvl ++ ) {
  83             /* cummulative count up to this level */
  84             cum_cnt+=cnt;
  85             /* number of ranks in this level */
  86             cnt*=tree_order;
  87         }
  88         my_rank_in_my_level=my_rank-cum_cnt;
  89         /* tree_order consecutive ranks have the same parent */
  90         my_node->parent_rank=cum_cnt-cnt/tree_order+my_rank_in_my_level/tree_order;
  91     }
  92 
  93     /* figure out number of levels in the tree */
  94     n_lvls_in_tree=0;
  95     result=num_nodes;
  96     /* cnt - number of ranks in given level */
  97     cnt=1;
  98     /*  cummulative count of ranks */
  99     while( 0 < result ) {
 100         result-=cnt;
 101         cnt*=tree_order;
 102         n_lvls_in_tree++;
 103     };
 104 
 105     my_node->children_ranks=(int *)NULL;
 106 
 107     /* get list of children */
 108     if( my_level_in_tree == (n_lvls_in_tree -1 ) ) {
 109         /* last level has no children */
 110         my_node->n_children=0;
 111     } else {
 112         cum_cnt=0;
 113         cnt=1;
 114         for( lvl=0 ; lvl <= my_level_in_tree ; lvl++ ) {
 115             cum_cnt+=cnt;
 116             cnt*=tree_order;
 117         }
 118         start_index=cum_cnt+my_rank_in_my_level*tree_order;
 119         end_index=start_index+tree_order-1;
 120 
 121         /* don't go out of bounds at the end of the list */
 122         if( end_index >= num_nodes ) {
 123             end_index = num_nodes-1;
 124         }
 125 
 126         if( start_index <= (num_nodes-1) ) {
 127             my_node->n_children=end_index-start_index+1;
 128         } else {
 129             my_node->n_children=0;
 130         }
 131 
 132         my_node->children_ranks=NULL;
 133         if( 0 < my_node->n_children ) {
 134             my_node->children_ranks=
 135                 (int *)malloc( sizeof(int)*my_node->n_children);
 136             if( NULL == my_node->children_ranks) {
 137                 goto Error;
 138             }
 139             for (lvl= start_index ; lvl <= end_index ; lvl++ ) {
 140                 my_node->children_ranks[lvl-start_index]=lvl;
 141             }
 142         }
 143     }
 144     /* set node type */
 145     if( 0 == my_node->n_parents ) {
 146         my_node->my_node_type=ROOT_NODE;
 147     } else if ( 0 == my_node->n_children ) {
 148         my_node->my_node_type=LEAF_NODE;
 149     } else {
 150         my_node->my_node_type=INTERIOR_NODE;
 151     }
 152 
 153 
 154     /* successful return */
 155     return OMPI_SUCCESS;
 156 
 157 Error:
 158 
 159     /* error return */
 160     return OMPI_ERROR;
 161 }
 162 
 163 void ompi_netpatterns_cleanup_narray_knomial_tree (netpatterns_narray_knomial_tree_node_t *my_node)
 164 {
 165     if (my_node->children_ranks) {
 166         free (my_node->children_ranks);
 167         my_node->children_ranks = NULL;
 168     }
 169 
 170     if (0 != my_node->my_rank) {
 171         ompi_netpatterns_cleanup_recursive_knomial_tree_node (&my_node->k_node);
 172     }
 173 }
 174 
 175 int ompi_netpatterns_setup_narray_knomial_tree(
 176         int tree_order, int my_rank, int num_nodes,
 177         netpatterns_narray_knomial_tree_node_t *my_node)
 178 {
 179     /* local variables */
 180     int n_levels, result;
 181     int my_level_in_tree, cnt ;
 182     int lvl,cum_cnt, my_rank_in_my_level,n_lvls_in_tree;
 183     int start_index,end_index;
 184     int rc;
 185 
 186     /* sanity check */
 187     if( 1 >= tree_order ) {
 188         goto Error;
 189     }
 190 
 191     my_node->my_rank=my_rank;
 192     my_node->tree_size=num_nodes;
 193 
 194     /* figure out number of levels in tree */
 195     n_levels=0;
 196     result=num_nodes-1;
 197     while (0 < result ) {
 198         result/=tree_order;
 199         n_levels++;
 200     };
 201 
 202     /* figure out who my children and parents are */
 203     my_level_in_tree=-1;
 204     result=my_rank;
 205     /* cnt - number of ranks in given level */
 206     cnt=1;
 207     /*  cummulative count of ranks */
 208     while( 0 <= result ) {
 209         result-=cnt;
 210         cnt*=tree_order;
 211         my_level_in_tree++;
 212     };
 213     /* int my_level_in_tree, n_children, n_parents; */
 214 
 215     if( 0 == my_rank ) {
 216         my_node->n_parents=0;
 217         my_node->parent_rank=-1;
 218         my_rank_in_my_level=0;
 219     } else {
 220         my_node->n_parents=1;
 221         cnt=1;
 222         cum_cnt=0;
 223         for (lvl = 0 ; lvl < my_level_in_tree ; lvl ++ ) {
 224             /* cummulative count up to this level */
 225             cum_cnt+=cnt;
 226             /* number of ranks in this level */
 227             cnt*=tree_order;
 228         }
 229 
 230         my_node->rank_on_level =
 231             my_rank_in_my_level =
 232             my_rank-cum_cnt;
 233         my_node->level_size = cnt;
 234 
 235         rc = ompi_netpatterns_setup_recursive_knomial_tree_node(
 236                 my_node->level_size, my_node->rank_on_level,
 237                 tree_order, &my_node->k_node);
 238         if (OMPI_SUCCESS != rc) {
 239             goto Error;
 240         }
 241 
 242         /* tree_order consecutive ranks have the same parent */
 243         my_node->parent_rank=cum_cnt-cnt/tree_order+my_rank_in_my_level/tree_order;
 244     }
 245 
 246     /* figure out number of levels in the tree */
 247     n_lvls_in_tree=0;
 248     result=num_nodes;
 249     /* cnt - number of ranks in given level */
 250     cnt=1;
 251     /*  cummulative count of ranks */
 252     while( 0 < result ) {
 253         result-=cnt;
 254         cnt*=tree_order;
 255         n_lvls_in_tree++;
 256     };
 257 
 258     if(result < 0) {
 259         /* reset the size on group */
 260         num_nodes = cnt / tree_order;
 261     }
 262 
 263     my_node->children_ranks=(int *)NULL;
 264 
 265     /* get list of children */
 266     if( my_level_in_tree == (n_lvls_in_tree -1 ) ) {
 267         /* last level has no children */
 268         my_node->n_children=0;
 269     } else {
 270         cum_cnt=0;
 271         cnt=1;
 272         for( lvl=0 ; lvl <= my_level_in_tree ; lvl++ ) {
 273             cum_cnt+=cnt;
 274             cnt*=tree_order;
 275         }
 276         start_index=cum_cnt+my_rank_in_my_level*tree_order;
 277         end_index=start_index+tree_order-1;
 278 
 279         /* don't go out of bounds at the end of the list */
 280         if( end_index >= num_nodes ) {
 281             end_index = num_nodes-1;
 282         }
 283 
 284         if( start_index <= (num_nodes-1) ) {
 285             my_node->n_children=end_index-start_index+1;
 286         } else {
 287             my_node->n_children=0;
 288         }
 289 
 290         my_node->children_ranks=NULL;
 291         if( 0 < my_node->n_children ) {
 292             my_node->children_ranks=
 293                 (int *)malloc( sizeof(int)*my_node->n_children);
 294             if( NULL == my_node->children_ranks) {
 295                 goto Error;
 296             }
 297             for (lvl= start_index ; lvl <= end_index ; lvl++ ) {
 298                 my_node->children_ranks[lvl-start_index]=lvl;
 299             }
 300         }
 301     }
 302     /* set node type */
 303     if( 0 == my_node->n_parents ) {
 304         my_node->my_node_type=ROOT_NODE;
 305     } else if ( 0 == my_node->n_children ) {
 306         my_node->my_node_type=LEAF_NODE;
 307     } else {
 308         my_node->my_node_type=INTERIOR_NODE;
 309     }
 310 
 311 
 312     /* successful return */
 313     return OMPI_SUCCESS;
 314 
 315 Error:
 316 
 317     /* error return */
 318     return OMPI_ERROR;
 319 }
 320 
 321 /* calculate the nearest power of radix that is equal to or greater
 322  * than size, with the specified radix.  The resulting tree is of
 323  * depth n_lvls.
 324  */
 325 int ompi_roundup_to_power_radix ( int radix, int size, int *n_lvls )
 326 {
 327     int n_levels=0, return_value=1;
 328     int result;
 329     if( 1 > size ) {
 330         return 0;
 331     }
 332 
 333     result=size-1;
 334     while (0 < result ) {
 335         result/=radix;
 336         n_levels++;
 337         return_value*=radix;
 338     };
 339     *n_lvls=n_levels;
 340     return return_value;
 341 }
 342 
 343 static int fill_in_node_data(int tree_order, int num_nodes, int my_node,
 344         netpatterns_tree_node_t *nodes_data)
 345 {
 346     /* local variables */
 347     int rc, num_ranks_per_child, num_children, n_extra;
 348     int child, rank, n_to_offset, n_ranks_to_child;
 349 
 350     /* figure out who are my children */
 351     num_ranks_per_child=num_nodes/tree_order;
 352     if( num_ranks_per_child ) {
 353         num_children=tree_order;
 354         n_extra=num_nodes-num_ranks_per_child*tree_order;
 355     } else {
 356         num_children=num_nodes;
 357         /* each child has the same number of descendents - 1 */
 358         n_extra=0;
 359         /* when there is a child, there is at least one
 360          * descendent */
 361         num_ranks_per_child=1;
 362     }
 363 
 364     nodes_data[my_node].n_children=num_children;
 365     if( num_children ) {
 366         nodes_data[my_node].children_ranks=(int *)
 367             malloc(sizeof(int)*num_children);
 368         if(!nodes_data[my_node].children_ranks) {
 369 
 370             if ( NULL == nodes_data[my_node].children_ranks )
 371             {
 372                 fprintf(stderr, "Cannot allocate memory for children_ranks.\n");
 373                 rc = OMPI_ERR_OUT_OF_RESOURCE;
 374                 goto error;
 375             }
 376         }
 377     }
 378 
 379     rank = my_node;
 380     for( child=0 ; child < num_children ; child ++ ) {
 381 
 382     /* set parent information */
 383         nodes_data[rank].n_parents=1;
 384         nodes_data[rank].parent_rank=my_node;
 385         if( n_extra ) {
 386             n_to_offset=child;
 387             if( n_to_offset > n_extra){
 388                 n_to_offset=n_extra;
 389             }
 390         } else {
 391             n_to_offset=0;
 392         }
 393 
 394         rank=my_node+1+child*num_ranks_per_child;
 395         rank+=n_to_offset;
 396 
 397         /* set parent information */
 398         nodes_data[rank].n_parents=1;
 399         nodes_data[rank].parent_rank=my_node;
 400 
 401         n_ranks_to_child=num_ranks_per_child;
 402         if(n_extra && (child < n_extra) ) {
 403             n_ranks_to_child++;
 404         }
 405 
 406         /* set child information */
 407         nodes_data[my_node].children_ranks[child]=rank;
 408 
 409         /* remove the child from the list of ranks */
 410         n_ranks_to_child--;
 411         rc=fill_in_node_data(tree_order, n_ranks_to_child, rank, nodes_data);
 412         if( OMPI_SUCCESS != rc ) {
 413             goto error;
 414         }
 415 
 416     }
 417 
 418     /* return */
 419     return OMPI_SUCCESS;
 420 
 421     /* Error */
 422 error:
 423     return rc;
 424 
 425 }
 426 
 427 /*
 428  * This routine sets up the array describing the communication tree for
 429  * a k-ary tree where the children form a contiguous range of ranks at
 430  * each level.  The assumption here is that rank 0 is always the root -
 431  * ranks may be rotated based on who the actual root is, to obtain the
 432  * appropriate communication pattern for such roots.
 433  */
 434 OMPI_DECLSPEC int ompi_netpatterns_setup_narray_tree_contigous_ranks(
 435         int tree_order, int num_nodes,
 436         netpatterns_tree_node_t **tree_nodes)
 437 {
 438     /* local variables */
 439     int num_descendent_ranks=num_nodes-1;
 440     int rc=OMPI_SUCCESS;
 441 
 442     *tree_nodes=(netpatterns_tree_node_t *)malloc(
 443             sizeof(netpatterns_tree_node_t)*
 444             num_nodes);
 445     if(!(*tree_nodes) ) {
 446         fprintf(stderr, "Cannot allocate memory for tree_nodes.\n");
 447         rc = OMPI_ERR_OUT_OF_RESOURCE;
 448         return rc;
 449     }
 450 
 451     (*tree_nodes)[0].n_parents=0;
 452     rc=fill_in_node_data(tree_order,
 453             num_descendent_ranks, 0, *tree_nodes);
 454 
 455     /* successful return */
 456     return rc;
 457 
 458 }
/* [<][>][^][v][top][bottom][index][help] */
root/ompi/patterns/net/netpatterns_nary_tree.c

DEFINITIONS
