| // Copyright (C) 2005 Douglas Gregor. |
| |
| // Use, modification and distribution is subject to the Boost Software |
| // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Compute parents, children, levels, etc. to effect a parallel |
| // computation tree. |
| |
| #include <boost/mpi/detail/computation_tree.hpp> |
| |
| namespace boost { namespace mpi { namespace detail { |
| |
| int computation_tree::default_branching_factor = 3; |
| |
| computation_tree |
| ::computation_tree(int rank, int size, int root, int branching_factor) |
| : rank(rank), size(size), root(root), |
| branching_factor_(branching_factor > 1? branching_factor |
| /* default */: default_branching_factor), |
| level_(0) |
| { |
| // The position in the tree, once we've adjusted for non-zero |
| // roots. |
| int n = (rank + size - root) % size; |
| int sum = 0; |
| int term = 1; |
| |
| /* The level is the smallest value of k such that |
| |
| f^0 + f^1 + ... + f^k > n |
| |
| for branching factor f and index n in the tree. */ |
| while (sum <= n) { |
| ++level_; |
| term *= branching_factor_; |
| sum += term; |
| } |
| } |
| |
| int computation_tree::level_index(int n) const |
| { |
| int sum = 0; |
| int term = 1; |
| while (n--) { |
| sum += term; |
| term *= branching_factor_; |
| } |
| return sum; |
| } |
| |
| int computation_tree::parent() const |
| { |
| if (rank == root) return rank; |
| int n = rank + size - 1 - root; |
| return ((n % size / branching_factor_) + root) % size ; |
| } |
| |
| int computation_tree::child_begin() const |
| { |
| // Zero-based index of this node |
| int n = (rank + size - root) % size; |
| |
| // Compute the index of the child (in a zero-based tree) |
| int child_index = level_index(level_ + 1) |
| + branching_factor_ * (n - level_index(level_)); |
| |
| if (child_index >= size) return root; |
| else return (child_index + root) % size; |
| } |
| |
| } } } // end namespace boost::mpi::detail |