1 /*
2 * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana
3 * University Research and Technology
4 * Corporation. All rights reserved.
5 * Copyright (c) 2004-2005 The University of Tennessee and The University
6 * of Tennessee Research Foundation. All rights
7 * reserved.
8 * Copyright (c) 2004-2014 High Performance Computing Center Stuttgart,
9 * University of Stuttgart. All rights reserved.
10 * Copyright (c) 2004-2005 The Regents of the University of California.
11 * All rights reserved.
12 * Copyright (c) 2012 Los Alamos National Security, LLC. All rights
13 * reserved.
14 * Copyright (c) 2014 Intel, Inc. All rights reserved
15 * Copyright (c) 2015 Cisco Systems, Inc. All rights reserved.
16 * Copyright (c) 2015-2016 Research Organization for Information Science
17 * and Technology (RIST). All rights reserved.
18 * $COPYRIGHT$
19 *
20 * Additional copyrights may follow
21 *
22 * $HEADER$
23 */
24
25 #include "ompi_config.h"
26
27 #include <math.h>
28
29 #include "ompi/mpi/c/bindings.h"
30 #include "ompi/runtime/params.h"
31 #include "ompi/communicator/communicator.h"
32 #include "ompi/errhandler/errhandler.h"
33
34 #if OMPI_BUILD_MPI_PROFILING
35 #if OPAL_HAVE_WEAK_SYMBOLS
36 #pragma weak MPI_Dims_create = PMPI_Dims_create
37 #endif
38 #define MPI_Dims_create PMPI_Dims_create
39 #endif
40
41 static const char FUNC_NAME[] = "MPI_Dims_create";
42
43 /* static functions */
44 static int assignnodes(int ndim, int nfactor, int *pfacts,int **pdims);
45 static int getfactors(int num, int *nfators, int **factors);
46
47
48 /*
49 * This is a utility function, no need to have anything in the lower
50 * layer for this at all
51 */
MPI_Dims_create(int nnodes,int ndims,int dims[])52 int MPI_Dims_create(int nnodes, int ndims, int dims[])
53 {
54 int i;
55 int freeprocs;
56 int freedims;
57 int nfactors;
58 int *factors;
59 int *procs;
60 int *p;
61 int err;
62
63 OPAL_CR_NOOP_PROGRESS();
64
65 if (MPI_PARAM_CHECK) {
66 OMPI_ERR_INIT_FINALIZE(FUNC_NAME);
67
68 if (0 > ndims) {
69 return OMPI_ERRHANDLER_INVOKE (MPI_COMM_WORLD,
70 MPI_ERR_DIMS, FUNC_NAME);
71 }
72
73 if ((0 != ndims) && (NULL == dims)) {
74 return OMPI_ERRHANDLER_INVOKE (MPI_COMM_WORLD,
75 MPI_ERR_ARG, FUNC_NAME);
76 }
77
78 if (1 > nnodes) {
79 return OMPI_ERRHANDLER_INVOKE (MPI_COMM_WORLD,
80 MPI_ERR_DIMS, FUNC_NAME);
81 }
82 }
83
84 /* Get # of free-to-be-assigned processes and # of free dimensions */
85 freeprocs = nnodes;
86 freedims = 0;
87 for (i = 0, p = dims; i < ndims; ++i,++p) {
88 if (*p == 0) {
89 ++freedims;
90 } else if ((*p < 0) || ((nnodes % *p) != 0)) {
91 return OMPI_ERRHANDLER_INVOKE (MPI_COMM_WORLD, MPI_ERR_DIMS,
92 FUNC_NAME);
93 } else {
94 freeprocs /= *p;
95 }
96 }
97
98 if (freedims == 0) {
99 if (freeprocs == 1) {
100 return MPI_SUCCESS;
101 }
102 return OMPI_ERRHANDLER_INVOKE(MPI_COMM_WORLD, MPI_ERR_DIMS,
103 FUNC_NAME);
104 }
105
106 if (freeprocs == 1) {
107 for (i = 0; i < ndims; ++i, ++dims) {
108 if (*dims == 0) {
109 *dims = 1;
110 }
111 }
112 return MPI_SUCCESS;
113 }
114
115 /* Factor the number of free processes */
116 if (MPI_SUCCESS != (err = getfactors(freeprocs, &nfactors, &factors))) {
117 return OMPI_ERRHANDLER_INVOKE(MPI_COMM_WORLD, err,
118 FUNC_NAME);
119 }
120
121 /* Assign free processes to free dimensions */
122 if (MPI_SUCCESS != (err = assignnodes(freedims, nfactors, factors, &procs))) {
123 free(factors);
124 return OMPI_ERRHANDLER_INVOKE(MPI_COMM_WORLD, err,
125 FUNC_NAME);
126 }
127
128 /* Return assignment results */
129 p = procs;
130 for (i = 0; i < ndims; ++i, ++dims) {
131 if (*dims == 0) {
132 *dims = *p++;
133 }
134 }
135
136 free((char *) factors);
137 free((char *) procs);
138
139 /* all done */
140 return MPI_SUCCESS;
141 }
142
143 /*
144 * assignnodes
145 *
146 * Function: - assign processes to dimensions
147 * - get "best-balanced" grid
148 * - greedy bin-packing algorithm used
149 * - sort dimensions in decreasing order
150 * - dimensions array dynamically allocated
151 * Accepts: - # of dimensions
152 * - # of prime factors
153 * - array of prime factors
154 * - ptr to array of dimensions (returned value)
155 * Returns: - 0 or ERROR
156 */
157 static int
assignnodes(int ndim,int nfactor,int * pfacts,int ** pdims)158 assignnodes(int ndim, int nfactor, int *pfacts, int **pdims)
159 {
160 int *bins;
161 int i, j;
162 int n;
163 int f;
164 int *p;
165 int *pmin;
166
167 if (0 >= ndim) {
168 return MPI_ERR_DIMS;
169 }
170
171 /* Allocate and initialize the bins */
172 bins = (int *) malloc((unsigned) ndim * sizeof(int));
173 if (NULL == bins) {
174 return MPI_ERR_NO_MEM;
175 }
176 *pdims = bins;
177
178 for (i = 0, p = bins; i < ndim; ++i, ++p) {
179 *p = 1;
180 }
181
182 /* Loop assigning factors from the highest to the lowest */
183 for (j = nfactor - 1; j >= 0; --j) {
184 f = pfacts[j];
185 /* Assign a factor to the smallest bin */
186 pmin = bins;
187 for (i = 1, p = pmin + 1; i < ndim; ++i, ++p) {
188 if (*p < *pmin) {
189 pmin = p;
190 }
191 }
192 *pmin *= f;
193 }
194
195 /* Sort dimensions in decreasing order (O(n^2) for now) */
196 for (i = 0, pmin = bins; i < ndim - 1; ++i, ++pmin) {
197 for (j = i + 1, p = pmin + 1; j < ndim; ++j, ++p) {
198 if (*p > *pmin) {
199 n = *p;
200 *p = *pmin;
201 *pmin = n;
202 }
203 }
204 }
205
206 return MPI_SUCCESS;
207 }
208
209 /*
210 * getfactors
211 *
212 * Function: - factorize a number
213 * Accepts: - number
214 * - # prime factors
215 * - array of prime factors
216 * Returns: - MPI_SUCCESS or ERROR
217 */
218 static int
getfactors(int num,int * nfactors,int ** factors)219 getfactors(int num, int *nfactors, int **factors) {
220 int size;
221 int d;
222 int i;
223 int sqrtnum;
224
225 if(num < 2) {
226 (*nfactors) = 0;
227 (*factors) = NULL;
228 return MPI_SUCCESS;
229 }
230 /* Allocate the array of prime factors which cannot exceed log_2(num) entries */
231 sqrtnum = ceil(sqrt(num));
232 size = ceil(log(num) / log(2));
233 *factors = (int *) malloc((unsigned) size * sizeof(int));
234
235 i = 0;
236 /* determine all occurences of factor 2 */
237 while((num % 2) == 0) {
238 num /= 2;
239 (*factors)[i++] = 2;
240 }
241 /* determine all occurences of uneven prime numbers up to sqrt(num) */
242 d = 3;
243 for(d = 3; (num > 1) && (d <= sqrtnum); d += 2) {
244 while((num % d) == 0) {
245 num /= d;
246 (*factors)[i++] = d;
247 }
248 }
249 /* as we looped only up to sqrt(num) one factor > sqrt(num) may be left over */
250 if(num != 1) {
251 (*factors)[i++] = num;
252 }
253 (*nfactors) = i;
254 return MPI_SUCCESS;
255 }
256