X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/ca2e418072d73461d9c4f1e39e77c9f7380eb3fd..ea74f5d95928a521a588737e81f1de94eef25d19:/src/smpi/colls/coll_tuned_topo.cpp diff --git a/src/smpi/colls/coll_tuned_topo.cpp b/src/smpi/colls/coll_tuned_topo.cpp index b04da38baf..087f488be7 100644 --- a/src/smpi/colls/coll_tuned_topo.cpp +++ b/src/smpi/colls/coll_tuned_topo.cpp @@ -1,4 +1,4 @@ -/* Copyright (c) 2013-2014. The SimGrid Team. +/* Copyright (c) 2013-2022. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it @@ -11,29 +11,31 @@ * Copyright (c) 2004-2005 The University of Tennessee and The University * of Tennessee Research Foundation. All rights * reserved. - * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart, + * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart, * University of Stuttgart. All rights reserved. * Copyright (c) 2004-2005 The Regents of the University of California. * All rights reserved. - * + * * Additional copyrights may follow */ -#include "colls_private.h" -#include "coll_tuned_topo.h" +#include "coll_tuned_topo.hpp" +#include "colls_private.hpp" /* * Some static helpers. */ static int pown( int fanout, int num ) { - int j, p = 1; + int p = 1; if( num < 0 ) return 0; if (1==num) return fanout; if (2==fanout) { return p< 1) + return ((pown(fanout, level) - 1) / (fanout - 1)); + else + return 0; // is this right ? } /* @@ -73,46 +78,37 @@ ompi_coll_tuned_topo_build_tree( int fanout, int root ) { int rank, size; - int schild, sparent; + int sparent; int level; /* location of my rank in the tree structure of size */ int delta; /* number of nodes on my level */ - int slimit; /* total number of nodes on levels above me */ + int slimit; /* total number of nodes on levels above me */ int shiftedrank; - int i; ompi_coll_tree_t* tree; XBT_DEBUG("coll:tuned:topo_build_tree Building fo %d rt %d", fanout, root); if (fanout<1) { XBT_DEBUG("coll:tuned:topo_build_tree invalid fanout %d", fanout); - return NULL; + return nullptr; } if (fanout>MAXTREEFANOUT) { XBT_DEBUG("coll:tuned:topo_build_tree invalid fanout %d bigger than max %d", fanout, MAXTREEFANOUT); - return NULL; + return nullptr; } - /* - * Get size and rank of the process in this communicator + /* + * Get size and rank of the process in this communicator */ size = comm->size(); rank = comm->rank(); - tree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t)); - if (!tree) { - XBT_DEBUG("coll:tuned:topo_build_tree PANIC::out of memory"); - return NULL; + tree = new ompi_coll_tree_t; + if (not tree) { + XBT_DEBUG("coll:tuned:topo_build_tree PANIC::out of memory"); + return nullptr; } - tree->tree_root = MPI_UNDEFINED; - tree->tree_nextsize = MPI_UNDEFINED; - /* - * Set root - */ - tree->tree_root = root; - - /* * Initialize tree */ tree->tree_fanout = fanout; @@ -120,19 +116,19 @@ ompi_coll_tuned_topo_build_tree( int fanout, tree->tree_root = root; tree->tree_prev = -1; tree->tree_nextsize = 0; - for( i = 0; i < fanout; i++ ) { - tree->tree_next[i] = -1; + for (int i = 0; i < fanout; i++) { + tree->tree_next[i] = -1; } /* return if we have less than 2 processes */ if( size < 2 ) { return tree; } - + /* - * Shift all ranks by root, so that the algorithm can be + * Shift all ranks by root, so that the algorithm can be * designed as if root would be always 0 - * shiftedrank should be used in calculating distances + * shiftedrank should be used in calculating distances * and position in tree */ shiftedrank = rank - root; @@ -145,8 +141,8 @@ ompi_coll_tuned_topo_build_tree( int fanout, delta = pown( fanout, level ); /* find my children */ - for( i = 0; i < fanout; i++ ) { - schild = shiftedrank + delta * (i+1); + for (int i = 0; i < fanout; i++) { + int schild = shiftedrank + delta * (i+1); if( schild < size ) { tree->tree_next[i] = (schild+root)%size; tree->tree_nextsize = tree->tree_nextsize + 1; @@ -154,7 +150,7 @@ ompi_coll_tuned_topo_build_tree( int fanout, break; } } - + /* find my parent */ slimit = calculate_num_nodes_up_to_level( fanout, level ); sparent = shiftedrank; @@ -166,12 +162,12 @@ ompi_coll_tuned_topo_build_tree( int fanout, } } tree->tree_prev = (sparent+root)%size; - + return tree; } /* - * Constructs in-order binary tree which can be used for non-commutative reduce + * Constructs in-order binary tree which can be used for non-commutative reduce * operations. * Root of this tree is always rank (size-1) and fanout is 2. * Here are some of the examples of this tree: @@ -188,27 +184,23 @@ ompi_coll_tree_t* ompi_coll_tuned_topo_build_in_order_bintree( MPI_Comm comm ) { int rank, size; - int myrank, rightsize, delta; - int parent, lchild, rchild; + int myrank, delta; + int parent; ompi_coll_tree_t* tree; - /* - * Get size and rank of the process in this communicator + /* + * Get size and rank of the process in this communicator */ size = comm->size(); rank = comm->rank(); - tree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t)); - if (!tree) { - XBT_DEBUG( - "coll:tuned:topo_build_tree PANIC::out of memory"); - return NULL; + tree = new ompi_coll_tree_t; + if (not tree) { + XBT_DEBUG("coll:tuned:topo_build_tree PANIC::out of memory"); + return nullptr; } - tree->tree_root = MPI_UNDEFINED; - tree->tree_nextsize = MPI_UNDEFINED; - - /* + /* * Initialize tree */ tree->tree_fanout = 2; @@ -219,73 +211,75 @@ ompi_coll_tuned_topo_build_in_order_bintree( MPI_Comm comm ) tree->tree_next[0] = -1; tree->tree_next[1] = -1; XBT_DEBUG( - "coll:tuned:topo_build_in_order_tree Building fo %d rt %d", + "coll:tuned:topo_build_in_order_tree Building fo %d rt %d", tree->tree_fanout, tree->tree_root); - /* + /* * Build the tree */ myrank = rank; parent = size - 1; delta = 0; - while ( 1 ) { - /* Compute the size of the right subtree */ - rightsize = size >> 1; - - /* Determine the left and right child of this parent */ - lchild = -1; - rchild = -1; - if (size - 1 > 0) { - lchild = parent - 1; - if (lchild > 0) { - rchild = rightsize - 1; - } + while (true) { + /* Compute the size of the right subtree */ + int rightsize = size >> 1; + + /* Determine the left and right child of this parent */ + int lchild = -1; + int rchild = -1; + if (size - 1 > 0) { + lchild = parent - 1; + if (lchild > 0) { + rchild = rightsize - 1; } - - /* The following cases are possible: myrank can be - - a parent, - - belong to the left subtree, or - - belong to the right subtee - Each of the cases need to be handled differently. + } + + /* The following cases are possible: myrank can be + - a parent, + - belong to the left subtree, or + - belong to the right subtee + Each of the cases need to be handled differently. + */ + + if (myrank == parent) { + /* I am the parent: + - compute real ranks of my children, and exit the loop. */ + if (lchild >= 0) + tree->tree_next[0] = lchild + delta; + if (rchild >= 0) + tree->tree_next[1] = rchild + delta; + break; + } + if (myrank > rchild) { + /* I belong to the left subtree: + - If I am the left child, compute real rank of my parent + - Iterate down through tree: + compute new size, shift ranks down, and update delta. */ - - if (myrank == parent) { - /* I am the parent: - - compute real ranks of my children, and exit the loop. */ - if (lchild >= 0) tree->tree_next[0] = lchild + delta; - if (rchild >= 0) tree->tree_next[1] = rchild + delta; - break; + if (myrank == lchild) { + tree->tree_prev = parent + delta; } - if (myrank > rchild) { - /* I belong to the left subtree: - - If I am the left child, compute real rank of my parent - - Iterate down through tree: - compute new size, shift ranks down, and update delta. - */ - if (myrank == lchild) { - tree->tree_prev = parent + delta; - } - size = size - rightsize - 1; - delta = delta + rightsize; - myrank = myrank - rightsize; - parent = size - 1; - - } else { - /* I belong to the right subtree: - - If I am the right child, compute real rank of my parent - - Iterate down through tree: - compute new size and parent, - but the delta and rank do not need to change. - */ - if (myrank == rchild) { - tree->tree_prev = parent + delta; - } - size = rightsize; - parent = rchild; + size = size - rightsize - 1; + delta = delta + rightsize; + myrank = myrank - rightsize; + parent = size - 1; + + } else { + /* I belong to the right subtree: + - If I am the right child, compute real rank of my parent + - Iterate down through tree: + compute new size and parent, + but the delta and rank do not need to change. + */ + if (myrank == rchild) { + tree->tree_prev = parent + delta; } + size = rightsize; + parent = rchild; + } } - + if (tree->tree_next[0] >= 0) { tree->tree_nextsize = 1; } if (tree->tree_next[1] >= 0) { tree->tree_nextsize += 1; } @@ -296,20 +290,20 @@ int ompi_coll_tuned_topo_destroy_tree( ompi_coll_tree_t** tree ) { ompi_coll_tree_t *ptr; - if ((!tree)||(!*tree)) { - return MPI_SUCCESS; + if ((tree == nullptr) || (*tree == nullptr)) { + return MPI_SUCCESS; } ptr = *tree; - free (ptr); - *tree = NULL; /* mark tree as gone */ + delete ptr; + *tree = nullptr; /* mark tree as gone */ return MPI_SUCCESS; } /* - * + * * Here are some of the examples of this tree: * size == 2 size = 4 size = 8 * 0 0 0 @@ -324,7 +318,7 @@ ompi_coll_tree_t* ompi_coll_tuned_topo_build_bmtree( MPI_Comm comm, int root ) { - int childs = 0; + int children = 0; int rank; int size; int mask = 1; @@ -335,18 +329,18 @@ ompi_coll_tuned_topo_build_bmtree( MPI_Comm comm, XBT_DEBUG("coll:tuned:topo:build_bmtree rt %d", root); - /* - * Get size and rank of the process in this communicator + /* + * Get size and rank of the process in this communicator */ size = comm->size(); rank = comm->rank(); index = rank -root; - bmtree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t)); - if (!bmtree) { - XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory"); - return NULL; + bmtree = new ompi_coll_tree_t; + if (not bmtree) { + XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory"); + return nullptr; } bmtree->tree_bmtree = 1; @@ -369,21 +363,22 @@ ompi_coll_tuned_topo_build_bmtree( MPI_Comm comm, if( remote >= size ) remote -= size; bmtree->tree_prev = remote; } - /* And now let's fill my childs */ + /* And now let's fill my children */ while( mask < size ) { remote = (index ^ mask); if( remote >= size ) break; remote += root; if( remote >= size ) remote -= size; - if (childs==MAXTREEFANOUT) { - XBT_DEBUG("coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d", MAXTREEFANOUT, childs); - return NULL; + if (children==MAXTREEFANOUT) { + XBT_DEBUG("coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d", MAXTREEFANOUT, children); + delete bmtree; + return nullptr; } - bmtree->tree_next[childs] = remote; + bmtree->tree_next[children] = remote; mask <<= 1; - childs++; + children++; } - bmtree->tree_nextsize = childs; + bmtree->tree_nextsize = children; bmtree->tree_root = root; return bmtree; } @@ -391,7 +386,7 @@ ompi_coll_tuned_topo_build_bmtree( MPI_Comm comm, /* * Constructs in-order binomial tree which can be used for gather/scatter * operations. - * + * * Here are some of the examples of this tree: * size == 2 size = 4 size = 8 * 0 0 0 @@ -402,32 +397,30 @@ ompi_coll_tuned_topo_build_bmtree( MPI_Comm comm, * | * 7 */ -ompi_coll_tree_t* -ompi_coll_tuned_topo_build_in_order_bmtree( MPI_Comm comm, - int root ) +ompi_coll_tree_t* ompi_coll_tuned_topo_build_in_order_bmtree(MPI_Comm comm, int root) { - int childs = 0; + int children = 0; int rank, vrank; int size; int mask = 1; - int remote; ompi_coll_tree_t *bmtree; int i; XBT_DEBUG("coll:tuned:topo:build_in_order_bmtree rt %d", root); - /* - * Get size and rank of the process in this communicator + /* + * Get size and rank of the process in this communicator */ size = comm->size(); rank = comm->rank(); vrank = (rank - root + size) % size; - bmtree = (ompi_coll_tree_t*)xbt_malloc(sizeof(ompi_coll_tree_t)); - if (!bmtree) { - XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory"); - return NULL; + bmtree = new ompi_coll_tree_t; + if (not bmtree) { + XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory"); + delete bmtree; + return nullptr; } bmtree->tree_bmtree = 1; @@ -438,27 +431,26 @@ ompi_coll_tuned_topo_build_in_order_bmtree( MPI_Comm comm, } if (root == rank) { - bmtree->tree_prev = root; + bmtree->tree_prev = root; } while (mask < size) { - remote = vrank ^ mask; - if (remote < vrank) { - bmtree->tree_prev = (remote + root) % size; - break; - } else if (remote < size) { - bmtree->tree_next[childs] = (remote + root) % size; - childs++; - if (childs==MAXTREEFANOUT) { - XBT_DEBUG( - "coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d", - MAXTREEFANOUT, childs); - return NULL; - } - } - mask <<= 1; - } - bmtree->tree_nextsize = childs; + int remote = vrank ^ mask; + if (remote < vrank) { + bmtree->tree_prev = (remote + root) % size; + break; + } else if (remote < size) { + bmtree->tree_next[children] = (remote + root) % size; + children++; + if (children == MAXTREEFANOUT) { + XBT_DEBUG("coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d", MAXTREEFANOUT, children); + delete bmtree; + return nullptr; + } + } + mask <<= 1; + } + bmtree->tree_nextsize = children; bmtree->tree_root = root; return bmtree; @@ -473,13 +465,13 @@ ompi_coll_tuned_topo_build_chain( int fanout, int rank, size; int srank; /* shifted rank */ int i,maxchainlen; - int mark,head,len; + int mark; ompi_coll_tree_t *chain; XBT_DEBUG("coll:tuned:topo:build_chain fo %d rt %d", fanout, root); - /* - * Get size and rank of the process in this communicator + /* + * Get size and rank of the process in this communicator */ size = comm->size(); rank = comm->rank(); @@ -494,29 +486,27 @@ ompi_coll_tuned_topo_build_chain( int fanout, } /* - * Allocate space for topology arrays if needed + * Allocate space for topology arrays if needed */ - chain = (ompi_coll_tree_t*)malloc( sizeof(ompi_coll_tree_t) ); - if (!chain) { - XBT_DEBUG("coll:tuned:topo:build_chain PANIC out of memory"); - fflush(stdout); - return NULL; - } - chain->tree_root = MPI_UNDEFINED; - chain->tree_nextsize = -1; + chain = new ompi_coll_tree_t; + if (not chain) { + XBT_DEBUG("coll:tuned:topo:build_chain PANIC out of memory"); + fflush(stdout); + return nullptr; + } for(i=0;itree_next[i] = -1; - /* + /* * Set root & numchain */ chain->tree_root = root; - if( (size - 1) < fanout ) { + if( (size - 1) < fanout ) { chain->tree_nextsize = size-1; fanout = size-1; } else { chain->tree_nextsize = fanout; } - + /* * Shift ranks */ @@ -563,6 +553,8 @@ ompi_coll_tuned_topo_build_chain( int fanout, */ if( srank != 0 ) { int column; + int head; + int len; if( srank-1 < (mark * maxchainlen) ) { column = (srank-1)/maxchainlen; head = 1+column*maxchainlen; @@ -587,18 +579,18 @@ ompi_coll_tuned_topo_build_chain( int fanout, chain->tree_nextsize = 1; } else { chain->tree_next[0] = -1; - chain->tree_nextsize = 0; + chain->tree_nextsize = 0; } } } - + /* - * Unshift values + * Unshift values */ if( rank == root ) { chain->tree_prev = -1; chain->tree_next[0] = (root+1)%size; - for( i = 1; i < fanout; i++ ) { + for (int i = 1; i < fanout; i++) { chain->tree_next[i] = chain->tree_next[i-1] + maxchainlen; if( i > mark ) { chain->tree_next[i]--; @@ -618,15 +610,13 @@ ompi_coll_tuned_topo_build_chain( int fanout, int ompi_coll_tuned_topo_dump_tree (ompi_coll_tree_t* tree, int rank) { - int i; - XBT_DEBUG("coll:tuned:topo:topo_dump_tree %1d tree root %d" " fanout %d BM %1d nextsize %d prev %d", rank, tree->tree_root, tree->tree_bmtree, tree->tree_fanout, tree->tree_nextsize, tree->tree_prev); if( tree->tree_nextsize ) { - for( i = 0; i < tree->tree_nextsize; i++ ) - XBT_DEBUG("[%1d] %d", i, tree->tree_next[i]); + for (int i = 0; i < tree->tree_nextsize; i++) + XBT_DEBUG("[%1d] %d", i, tree->tree_next[i]); } return (0); }