1 /*
2 * Copyright (c) 2009-2012 Mellanox Technologies. All rights reserved.
3 * Copyright (c) 2009-2012 Oak Ridge National Laboratory. All rights reserved.
4 * Copyright (c) 2012 Los Alamos National Security, LLC.
5 * All rights reserved.
6 * Copyright (c) 2014 Research Organization for Information Science
7 * and Technology (RIST). All rights reserved.
8 * Copyright (c) 2017 IBM Corporation. All rights reserved.
9 * $COPYRIGHT$
10 *
11 * Additional copyrights may follow
12 *
13 * $HEADER$
14 */
15
16 #ifndef COMM_PATTERNS_KNOMIAL_TREE_H
17 #define COMM_PATTERNS_KNOMIAL_TREE_H
18
19 #include "ompi_config.h"
20
21 BEGIN_C_DECLS
22
23
24 /*
25 * Pair-wise data exchange
26 */
27
28 /* enum for node type */
29 enum {
30 EXCHANGE_NODE,
31 EXTRA_NODE
32 };
33
34 struct netpatterns_pair_exchange_node_t {
35
36 /* Order of a node in the tree - usually 2 */
37 int tree_order;
38
39 /* number of nodes this node will exchange data with */
40 int n_exchanges;
41
42 /* ranks of nodes involved in data exchnge */
43 int *rank_exchanges;
44
45 /* number of extra sources of data - outside largest power of 2 in
46 * this group */
47 int n_extra_sources;
48
49 /* rank of the extra source */
50 /* deprecated */ int rank_extra_source;
51 int *rank_extra_sources_array;
52
53 /* number of tags needed per stripe */
54 int n_tags;
55
56 /* log 2 of largest full power of 2 for this node set */
57 /* deprecated */ int log_2;
58 int log_tree_order;
59
60 /* largest power of 2 that fits in this group */
61 /* deprecated */ int n_largest_pow_2;
62 int n_largest_pow_tree_order;
63
64 /* node type */
65 int node_type;
66
67 };
68 typedef struct netpatterns_pair_exchange_node_t netpatterns_pair_exchange_node_t;
69
70 struct netpatterns_payload_t {
71 int s_len;
72 int r_len;
73 int s_offset;
74 int r_offset;
75 };
76 typedef struct netpatterns_payload_t netpatterns_payload_t;
77
78 struct netpatterns_k_exchange_node_t {
79 /* Order of a node in the tree - usually 2 */
80 int tree_order;
81 /* number of nodes this node will exchange data with */
82 int n_exchanges;
83 /* total number of exchanges that I actually participate in */
84 int n_actual_exchanges;
85 /* ranks of nodes involved in data exchnge */
86 int **rank_exchanges;
87 /* number of extra sources of data - outside largest power of 2 in
88 * this group */
89 int n_extra_sources;
90 /* rank/s of the extra source */
91 int *rank_extra_sources_array;
92 /* number of tags needed per stripe */
93 int n_tags;
94 /* log k of largest full power of k for this node set */
95 int log_tree_order;
96 /* largest power of k that fits in this group */
97 int n_largest_pow_tree_order;
98 /* node type */
99 int node_type;
100 /* start of extra ranks k_nomial */
101 int k_nomial_stray;
102 /* reindex map */
103 int *reindex_map;
104 /* inverse of reindex map, i.e. given a reindexed id find out its actual rank */
105 int *inv_reindex_map;
106 /* reindexed node_rank */
107 int reindex_myid;
108 /* 2-d array that hold payload info for each level of recursive k-ing */
109 netpatterns_payload_t **payload_info;
110 };
111 typedef struct netpatterns_k_exchange_node_t
112 netpatterns_k_exchange_node_t;
113
114 OMPI_DECLSPEC int ompi_netpatterns_setup_recursive_doubling_n_tree_node(int num_nodes, int node_rank, int tree_order,
115 netpatterns_pair_exchange_node_t *exchange_node);
116
117 OMPI_DECLSPEC void ompi_netpatterns_cleanup_recursive_doubling_tree_node(
118 netpatterns_pair_exchange_node_t *exchange_node);
119
120 OMPI_DECLSPEC int ompi_netpatterns_setup_recursive_doubling_tree_node(int num_nodes, int node_rank,
121 netpatterns_pair_exchange_node_t *exchange_node);
122
123 OMPI_DECLSPEC int ompi_netpatterns_setup_recursive_knomial_tree_node(
124 int num_nodes, int node_rank, int tree_order,
125 netpatterns_k_exchange_node_t *exchange_node);
126
127 OMPI_DECLSPEC void ompi_netpatterns_cleanup_recursive_knomial_tree_node(
128 netpatterns_k_exchange_node_t *exchange_node);
129
130 OMPI_DECLSPEC int ompi_netpatterns_setup_recursive_knomial_allgather_tree_node(
131 int num_nodes, int node_rank, int tree_order, int *hier_ranks,
132 netpatterns_k_exchange_node_t *exchange_node);
133
134 OMPI_DECLSPEC void ompi_netpatterns_cleanup_recursive_knomial_allgather_tree_node(
135 netpatterns_k_exchange_node_t *exchange_node);
136
137 /* Input: k_exchange_node structure
138 Output: index in rank_exchanges array that points
139 to the "start_point" for outgoing send.
140
141 Please see below example of usage:
142 for (i = start_point ; i > 0; i--)
143 for (k = 0; k < tree_radix; k++)
144 send messages to exchange_node->rank_exchanges[i][k];
145 */
146
147 static inline __opal_attribute_always_inline__
148 int netpatterns_get_knomial_level(
149 int my_rank, int src_rank,
150 int radix, int size,
151 int *k_level)
152 {
153 int distance,
154 pow_k;
155 int logk_level = 0;
156
157 /* Calculate disctance from source of data */
158 distance = src_rank - my_rank;
159
160 /* Wrap around */
161 if (0 > distance) {
162 distance += size;
163 }
164
165 pow_k = 1;
166 while(distance / (pow_k * radix)) {
167 pow_k *= radix;
168 ++logk_level;
169 }
170 --logk_level;
171
172 *k_level = pow_k;
173 return logk_level;
174 }
175
176 /* Input: my_rank, root, radix, size
177 * Output: source of the data, offset in power of K
178 */
179 static inline __opal_attribute_always_inline__
180 int netpatterns_get_knomial_data_source(
181 int my_rank, int root, int radix, int size,
182 int *k_level, int *logk_level)
183 {
184 int level = radix;
185 int step = 0;
186
187 /* Calculate source of the data */
188 while((0 == (root - my_rank) % level)
189 && (level <= size)) {
190 level *= radix;
191 ++step;
192 }
193
194 *k_level = level/radix;
195 *logk_level = step;
196 return my_rank - (my_rank % level - root % level);
197 }
198
199 /* Input: my_rank, radix,
200 * k_level - that you get from netpatterns_get_knomial_data_source
201 * k_step - some integer
202 * Output: peer - next children in the tree
203 * Usage:
204 * src = netpatterns_get_knomial_data_source(
205 * my_rank, root, radix, size,
206 * &k_level, &logk_level)
207 * recv_from(src......);
208 *
209 * MCA_COMMON_NETPATTERNS_GET_NEXT_KNOMIAL_INIT(step_info, k_level, my_rank);
210 * while(MCA_COMMON_NETPATTERNS_GET_NEXT_KNOMIAL_PEER_CHECK_LEVEL(step_info)) {
211 * MCA_COMMON_NETPATTERNS_GET_NEXT_KNOMIAL_PEER(my_rank, radix, step_info, peer);
212 * send_to(peer....);
213 * }
214 * for more example please grep in ptpcoll bcol bcast files
215 */
216
217 typedef struct netpatterns_knomial_step_info_t {
218 int k_step;
219 int k_level;
220 int k_tmp_peer;
221 } netpatterns_knomial_step_info_t;
222
223 #define MCA_COMMON_NETPATTERNS_GET_NEXT_KNOMIAL_UPDATE_LEVEL_FOR_BCAST(step_info, radix)\
224 do { \
225 if (1 != step_info.k_step) { \
226 step_info.k_level /= radix; \
227 } \
228 } while (0) \
229
230 #define MCA_COMMON_NETPATTERNS_GET_NEXT_KNOMIAL_INIT(step_info, in_k_level, in_peer)\
231 do { \
232 step_info.k_step = 1; \
233 step_info.k_level = in_k_level; \
234 step_info.k_tmp_peer = in_peer; \
235 } while (0)
236
237 #define MCA_COMMON_NETPATTERNS_GET_NEXT_KNOMIAL_PEER_CHECK_LEVEL(step_info) \
238 (step_info.k_level > 1)
239
240 #define MCA_COMMON_NETPATTERNS_GET_NEXT_KNOMIAL_PEER(my_rank, radix, step_info, peer) \
241 do { \
242 int rank_radix_base = my_rank/step_info.k_level; \
243 \
244 peer = step_info.k_tmp_peer + step_info.k_level/radix; \
245 if (rank_radix_base != peer/step_info.k_level) { \
246 /* Wraparound the number */ \
247 peer -= step_info.k_level; \
248 assert(peer >=0); \
249 } \
250 ++step_info.k_step; \
251 if (radix == step_info.k_step) { \
252 step_info.k_level /= radix; \
253 step_info.k_step = 1; \
254 step_info.k_tmp_peer = my_rank; \
255 } else { \
256 step_info.k_tmp_peer = peer; \
257 } \
258 \
259 } while (0)
260
261 END_C_DECLS
262 #endif