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