1 // Copyright (C) 2005 Douglas Gregor.
2
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 // Compute parents, children, levels, etc. to effect a parallel
8 // computation tree.
9
10 #include <boost/mpi/detail/computation_tree.hpp>
11
12 namespace boost { namespace mpi { namespace detail {
13
14 int computation_tree::default_branching_factor = 3;
15
16 computation_tree
computation_tree(int rank,int size,int root,int branching_factor)17 ::computation_tree(int rank, int size, int root, int branching_factor)
18 : rank(rank), size(size), root(root),
19 branching_factor_(branching_factor > 1? branching_factor
20 /* default */: default_branching_factor),
21 level_(0)
22 {
23 // The position in the tree, once we've adjusted for non-zero
24 // roots.
25 int n = (rank + size - root) % size;
26 int sum = 0;
27 int term = 1;
28
29 /* The level is the smallest value of k such that
30
31 f^0 + f^1 + ... + f^k > n
32
33 for branching factor f and index n in the tree. */
34 while (sum <= n) {
35 ++level_;
36 term *= branching_factor_;
37 sum += term;
38 }
39 }
40
level_index(int n) const41 int computation_tree::level_index(int n) const
42 {
43 int sum = 0;
44 int term = 1;
45 while (n--) {
46 sum += term;
47 term *= branching_factor_;
48 }
49 return sum;
50 }
51
parent() const52 int computation_tree::parent() const
53 {
54 if (rank == root) return rank;
55 int n = rank + size - 1 - root;
56 return ((n % size / branching_factor_) + root) % size ;
57 }
58
child_begin() const59 int computation_tree::child_begin() const
60 {
61 // Zero-based index of this node
62 int n = (rank + size - root) % size;
63
64 // Compute the index of the child (in a zero-based tree)
65 int child_index = level_index(level_ + 1)
66 + branching_factor_ * (n - level_index(level_));
67
68 if (child_index >= size) return root;
69 else return (child_index + root) % size;
70 }
71
72 } } } // end namespace boost::mpi::detail
73