-/* Copyright (c) 2013-2014. The SimGrid Team.
+/* Copyright (c) 2013-2019. The SimGrid Team.
* All rights reserved. */
/* This program is free software; you can redistribute it and/or modify it
* 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<<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) */
- return ((pown(fanout,level) - 1)/(fanout - 1));
+ 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 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);
return NULL;
}
- /*
- * 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 NULL;
}
tree->tree_root = MPI_UNDEFINED;
* Set root
*/
tree->tree_root = root;
-
- /*
+
+ /*
* Initialize tree
*/
tree->tree_fanout = 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;
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;
break;
}
}
-
+
/* find my parent */
slimit = calculate_num_nodes_up_to_level( fanout, level );
sparent = shiftedrank;
}
}
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:
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 NULL;
}
tree->tree_root = MPI_UNDEFINED;
tree->tree_nextsize = MPI_UNDEFINED;
- /*
+ /*
* Initialize tree
*/
tree->tree_fanout = 2;
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;
while ( 1 ) {
/* Compute the size of the right subtree */
- rightsize = size >> 1;
+ int rightsize = size >> 1;
/* Determine the left and right child of this parent */
- lchild = -1;
- rchild = -1;
+ int lchild = -1;
+ int rchild = -1;
if (size - 1 > 0) {
lchild = parent - 1;
- if (lchild > 0) {
+ if (lchild > 0) {
rchild = rightsize - 1;
}
}
-
- /* The following cases are possible: myrank can be
+
+ /* 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 (myrank > rchild) {
/* I belong to the left subtree:
- If I am the left child, compute real rank of my parent
- - Iterate down through tree:
+ - Iterate down through tree:
compute new size, shift ranks down, and update delta.
*/
if (myrank == lchild) {
} 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,
+ - Iterate down through tree:
+ compute new size and parent,
but the delta and rank do not need to change.
*/
if (myrank == rchild) {
parent = rchild;
}
}
-
+
if (tree->tree_next[0] >= 0) { tree->tree_nextsize = 1; }
if (tree->tree_next[1] >= 0) { tree->tree_nextsize += 1; }
{
ompi_coll_tree_t *ptr;
- if ((!tree)||(!*tree)) {
- return MPI_SUCCESS;
+ if ((tree == nullptr) || (*tree == nullptr)) {
+ return MPI_SUCCESS;
}
ptr = *tree;
- free (ptr);
+ delete ptr;
*tree = NULL; /* 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
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 NULL;
}
bmtree->tree_bmtree = 1;
if( remote >= size ) remote -= size;
if (childs==MAXTREEFANOUT) {
XBT_DEBUG("coll:tuned:topo:build_bmtree max fanout incorrect %d needed %d", MAXTREEFANOUT, childs);
+ delete bmtree;
return NULL;
}
bmtree->tree_next[childs] = remote;
/*
* 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
* |
* 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 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 NULL;
}
bmtree->tree_bmtree = 1;
}
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;
+ 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);
+ delete bmtree;
+ return NULL;
+ }
+ }
+ mask <<= 1;
}
bmtree->tree_nextsize = childs;
bmtree->tree_root = root;
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();
}
/*
- * 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 = new ompi_coll_tree_t;
+ if (not 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;
for(i=0;i<fanout;i++) chain->tree_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
*/
*/
if( srank != 0 ) {
int column;
+ int head;
+ int len;
if( srank-1 < (mark * maxchainlen) ) {
column = (srank-1)/maxchainlen;
head = 1+column*maxchainlen;
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]--;
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);
}
