1 /*
2 * Copyright (C) by Argonne National Laboratory
3 * See COPYRIGHT in top-level directory
4 */
5
6 #include "mpiimpl.h"
7 #include "utarray.h"
8 #include "treealgo_types.h"
9 #include "treeutil.h"
10 #include "mpiimpl.h"
11
tree_add_child(MPIR_Treealgo_tree_t * t,int rank)12 static int tree_add_child(MPIR_Treealgo_tree_t * t, int rank)
13 {
14 int mpi_errno = MPI_SUCCESS;
15
16 utarray_push_back(t->children, &rank, MPL_MEM_COLL);
17 t->num_children++;
18
19 return mpi_errno;
20 }
21
22
MPII_Treeutil_tree_kary_init(int rank,int nranks,int k,int root,MPIR_Treealgo_tree_t * ct)23 int MPII_Treeutil_tree_kary_init(int rank, int nranks, int k, int root, MPIR_Treealgo_tree_t * ct)
24 {
25 int lrank, child;
26 int mpi_errno = MPI_SUCCESS;
27
28 ct->rank = rank;
29 ct->nranks = nranks;
30 ct->parent = -1;
31 utarray_new(ct->children, &ut_int_icd, MPL_MEM_COLL);
32 ct->num_children = 0;
33
34 MPIR_Assert(nranks >= 0);
35
36 if (nranks == 0)
37 goto fn_exit;
38
39 lrank = (rank + (nranks - root)) % nranks;
40
41 ct->parent = (lrank == 0) ? -1 : (((lrank - 1) / k) + root) % nranks;
42
43 for (child = 1; child <= k; child++) {
44 int val = lrank * k + child;
45
46 if (val >= nranks)
47 break;
48
49 val = (val + root) % nranks;
50 mpi_errno = tree_add_child(ct, val);
51 MPIR_ERR_CHECK(mpi_errno);
52 }
53
54 fn_exit:
55 return mpi_errno;
56
57 fn_fail:
58 goto fn_exit;
59 }
60
61 /* Some examples of knomial_1 tree */
62 /* 4 ranks 8 ranks
63 * 0 0
64 * / \ / | \
65 * 1 3 1 5 7
66 * | / \ |
67 * 2 2 4 6
68 * |
69 * 3
70 */
MPII_Treeutil_tree_knomial_1_init(int rank,int nranks,int k,int root,MPIR_Treealgo_tree_t * ct)71 int MPII_Treeutil_tree_knomial_1_init(int rank, int nranks, int k, int root,
72 MPIR_Treealgo_tree_t * ct)
73 {
74 int lrank, i, j, maxstep, tmp, step, parent, current_rank, running_rank, crank;
75 int mpi_errno = MPI_SUCCESS;
76
77 ct->rank = rank;
78 ct->nranks = nranks;
79 ct->parent = -1;
80
81 MPIR_Assert(nranks >= 0);
82
83 if (nranks == 0)
84 goto fn_exit;
85
86 lrank = (rank + (nranks - root)) % nranks;
87 MPIR_Assert(k >= 2);
88
89 /* maximum number of steps while generating the knomial tree */
90 maxstep = 0;
91 for (tmp = nranks - 1; tmp; tmp /= k)
92 maxstep++;
93
94 utarray_new(ct->children, &ut_int_icd, MPL_MEM_COLL);
95 ct->num_children = 0;
96 step = 0;
97 parent = -1; /* root has no parent */
98 current_rank = 0; /* start at root of the tree */
99 running_rank = current_rank + 1; /* used for calculation below
100 * start with first child of the current_rank */
101
102 for (step = 0;; step++) {
103 MPIR_Assert(step <= nranks); /* actually, should not need more steps than log_k(nranks) */
104
105 /* desired rank found */
106 if (lrank == current_rank)
107 break;
108
109 /* check if rank lies in this range */
110 for (j = 1; j < k; j++) {
111 if (lrank >= running_rank && lrank < running_rank + MPL_ipow(k, maxstep - step - 1)) {
112 /* move to the corresponding subtree */
113 parent = current_rank;
114 current_rank = running_rank;
115 running_rank = current_rank + 1;
116 break;
117 }
118
119 running_rank += MPL_ipow(k, maxstep - step - 1);
120 }
121 }
122
123 /* set the parent */
124 if (parent == -1)
125 ct->parent = -1;
126 else
127 ct->parent = (parent + root) % nranks;
128
129 /* set the children */
130 crank = lrank + 1; /* crank stands for child rank */
131 MPL_DBG_MSG_FMT(MPIR_DBG_COLL, VERBOSE,
132 (MPL_DBG_FDEST, "parent of rank %d is %d, total ranks = %d (root=%d)", rank,
133 ct->parent, nranks, root));
134 for (i = step; i < maxstep; i++) {
135 for (j = 1; j < k; j++) {
136 if (crank < nranks) {
137 MPL_DBG_MSG_FMT(MPIR_DBG_COLL, VERBOSE,
138 (MPL_DBG_FDEST, "adding child %d to rank %d",
139 (crank + root) % nranks, rank));
140 mpi_errno = tree_add_child(ct, (crank + root) % nranks);
141 MPIR_ERR_CHECK(mpi_errno);
142 }
143 crank += MPL_ipow(k, maxstep - i - 1);
144 }
145 }
146
147 fn_exit:
148 return mpi_errno;
149
150 fn_fail:
151 goto fn_exit;
152 }
153
154
155 /* Some examples of knomial_2 tree */
156 /* 4 ranks 8 ranks
157 * 0 0
158 * / \ / | \
159 * 2 1 4 2 1
160 * | / \ |
161 * 3 6 5 3
162 * |
163 * 7
164 */
MPII_Treeutil_tree_knomial_2_init(int rank,int nranks,int k,int root,MPIR_Treealgo_tree_t * ct)165 int MPII_Treeutil_tree_knomial_2_init(int rank, int nranks, int k, int root,
166 MPIR_Treealgo_tree_t * ct)
167 {
168 int mpi_errno = MPI_SUCCESS;
169 int lrank, i, j, depth;
170 int *flip_bit, child;
171
172 ct->rank = rank;
173 ct->nranks = nranks;
174 ct->num_children = 0;
175 ct->parent = -1;
176
177 MPIR_Assert(nranks >= 0);
178 if (nranks <= 0)
179 return mpi_errno;
180
181 lrank = (rank + (nranks - root)) % nranks;
182 MPIR_Assert(k >= 2);
183
184 utarray_new(ct->children, &ut_int_icd, MPL_MEM_COLL);
185 ct->num_children = 0;
186
187 /* Parent calculation */
188 if (lrank <= 0)
189 ct->parent = -1;
190 else {
191 depth = MPL_ilog(k, nranks - 1);
192
193 for (i = 0; i < depth; i++) {
194 if (MPL_getdigit(k, lrank, i)) {
195 ct->parent = (MPL_setdigit(k, lrank, i, 0) + root) % nranks;
196 break;
197 }
198 }
199 }
200
201 /* Children calculation */
202 depth = MPL_ilog(k, nranks - 1);
203 flip_bit = (int *) MPL_calloc(depth, sizeof(int), MPL_MEM_COLL);
204
205 for (j = 0; j < depth; j++) {
206 if (MPL_getdigit(k, lrank, j)) {
207 break;
208 }
209 flip_bit[j] = 1;
210 }
211
212 for (j = depth - 1; j >= 0; j--) {
213 if (flip_bit[j] == 1) {
214 for (i = k - 1; i >= 1; i--) {
215 child = MPL_setdigit(k, lrank, j, i);
216 if (child < nranks)
217 tree_add_child(ct, (child + root) % nranks);
218 }
219 }
220 }
221
222 MPL_DBG_MSG_FMT(MPIR_DBG_COLL, VERBOSE,
223 (MPL_DBG_FDEST, "parent of rank %d is %d, total ranks = %d (root=%d)", rank,
224 ct->parent, nranks, root));
225 MPL_free(flip_bit);
226
227 return mpi_errno;
228 }
229