-/* Copyright (c) 2013-2017. 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
* 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<<num;
}
else {
- for( j = 0; j < num; j++ ) { p*= fanout; }
+ for (int j = 0; j < num; j++) {
+ p *= fanout;
+ }
}
return p;
}
{
/* just use geometric progression formula for sum:
a^0+a^1+...a^(n-1) = (a^n-1)/(a-1) */
- if(fanout > 1)
- return ((pown(fanout,level) - 1)/(fanout - 1));
- else
- return 0; // is this right ?
+ if (fanout > 1)
+ return ((pown(fanout, level) - 1) / (fanout - 1));
+ else
+ return 0; // is this right ?
}
/*
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 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;
}
/*
size = comm->size();
rank = comm->rank();
- tree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t));
+ tree = new ompi_coll_tree_t;
if (not tree) {
XBT_DEBUG("coll:tuned:topo_build_tree PANIC::out of memory");
- return NULL;
+ return nullptr;
}
- tree->tree_root = MPI_UNDEFINED;
- tree->tree_nextsize = MPI_UNDEFINED;
-
- /*
- * Set root
- */
- tree->tree_root = root;
-
/*
* Initialize tree
*/
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 */
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;
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;
/*
size = comm->size();
rank = comm->rank();
- tree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t));
+ tree = new ompi_coll_tree_t;
if (not tree) {
XBT_DEBUG("coll:tuned:topo_build_tree PANIC::out of memory");
- return NULL;
+ return nullptr;
}
- tree->tree_root = MPI_UNDEFINED;
- tree->tree_nextsize = MPI_UNDEFINED;
-
/*
* Initialize tree
*/
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; }
ptr = *tree;
- free (ptr);
- *tree = NULL; /* mark tree as gone */
+ delete ptr;
+ *tree = nullptr; /* mark tree as gone */
return MPI_SUCCESS;
}
ompi_coll_tuned_topo_build_bmtree( MPI_Comm comm,
int root )
{
- int childs = 0;
+ int children = 0;
int rank;
int size;
int mask = 1;
index = rank -root;
- bmtree = (ompi_coll_tree_t*)malloc(sizeof(ompi_coll_tree_t));
+ bmtree = new ompi_coll_tree_t;
if (not bmtree) {
XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory");
- return NULL;
+ return nullptr;
}
bmtree->tree_bmtree = 1;
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;
}
*/
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;
vrank = (rank - root + size) % size;
- bmtree = (ompi_coll_tree_t*)xbt_malloc(sizeof(ompi_coll_tree_t));
+ bmtree = new ompi_coll_tree_t;
if (not bmtree) {
XBT_DEBUG("coll:tuned:topo:build_bmtree PANIC out of memory");
- return NULL;
+ delete bmtree;
+ return nullptr;
}
bmtree->tree_bmtree = 1;
}
while (mask < size) {
- remote = vrank ^ mask;
+ int 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;
+ 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 = childs;
+ bmtree->tree_nextsize = children;
bmtree->tree_root = root;
return bmtree;
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);
/*
* Allocate space for topology arrays if needed
*/
- chain = (ompi_coll_tree_t*)malloc( sizeof(ompi_coll_tree_t) );
+ chain = new ompi_coll_tree_t;
if (not chain) {
XBT_DEBUG("coll:tuned:topo:build_chain PANIC out of memory");
fflush(stdout);
- return NULL;
+ return nullptr;
}
- chain->tree_root = MPI_UNDEFINED;
- chain->tree_nextsize = -1;
for(i=0;i<fanout;i++) chain->tree_next[i] = -1;
/*
*/
if( srank != 0 ) {
int column;
+ int head;
+ int len;
if( srank-1 < (mark * maxchainlen) ) {
column = (srank-1)/maxchainlen;
head = 1+column*maxchainlen;
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]--;
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);
}