Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Memory leak--
[simgrid.git] / src / smpi / mpi / smpi_topo.cpp
1 /* Copyright (c) 2014-2019. The SimGrid Team. All rights reserved.          */
2
3 /* This program is free software; you can redistribute it and/or modify it
4  * under the terms of the license (GNU LGPL) which comes with this package. */
5
6 #include "smpi/smpi.h"
7 #include "private.hpp"
8 #include "smpi_comm.hpp"
9 #include "smpi_topo.hpp"
10 #include "xbt/sysdep.h"
11 #include <cmath>
12 #include <vector>
13
14 /* static functions */
15 static int assignnodes(int ndim, int nfactor, int *pfacts,int **pdims);
16 static int getfactors(int num, int *nfators, int **factors);
17
18
19 namespace simgrid{
20 namespace smpi{
21
22 /*******************************************************************************
23  * Cartesian topologies
24  ******************************************************************************/
25
26 Topo_Cart::Topo_Cart(int ndims) : ndims_(ndims), dims_(ndims), periodic_(ndims), position_(ndims)
27 {
28 }
29
30 /* reorder is ignored, don't know what would be the consequences of a dumb reordering but neither do I see the point of
31  * reordering*/
32 Topo_Cart::Topo_Cart(MPI_Comm comm_old, int ndims, const int dims[], const int periods[], int /*reorder*/, MPI_Comm* comm_cart)
33     : Topo_Cart(ndims)
34 {
35   MPI_Group newGroup;
36   MPI_Group oldGroup;
37
38   int rank = comm_old->rank();
39
40   if(ndims != 0) {
41     int newSize = 1;
42     for (int i = 0 ; i < ndims ; i++) {
43       newSize *= dims[i];
44     }
45     if(rank >= newSize) {
46       *comm_cart = MPI_COMM_NULL;
47       return;
48     }
49     oldGroup = comm_old->group();
50     newGroup = new  Group(newSize);
51     for (int i = 0 ; i < newSize ; i++) {
52       newGroup->set_mapping(oldGroup->actor(i), i);
53     }
54
55     nnodes_ = newSize;
56
57     //  FIXME : code duplication... See coords
58     int nranks = newSize;
59     for (int i=0; i<ndims; i++) {
60       dims_[i] = dims[i];
61      periodic_[i] = periods[i];
62       nranks = nranks / dims[i];
63       /* FIXME: nranks could be zero (?) */
64       position_[i] = rank / nranks;
65       rank = rank % nranks;
66     }
67
68     *comm_cart = new  Comm(newGroup, this);
69   } else {
70     if (rank == 0) {
71       *comm_cart = new  Comm(new  Group(MPI_COMM_SELF->group()), this);
72     } else {
73       *comm_cart = MPI_COMM_NULL;
74     }
75   }
76   setComm(*comm_cart);
77 }
78
79 Topo_Cart* Topo_Cart::sub(const int remain_dims[], MPI_Comm *newcomm) {
80   int oldNDims = ndims_;
81   int *newDims = nullptr;
82   int *newPeriodic = nullptr;
83
84   if (remain_dims == nullptr && oldNDims != 0) {
85     return nullptr;
86   }
87   int newNDims = 0;
88   for (int i = 0 ; i < oldNDims ; i++) {
89     if (remain_dims[i])
90       newNDims++;
91   }
92
93   if (newNDims > 0) {
94     newDims     = new int[newNDims];
95     newPeriodic = new int[newNDims];
96
97     // that should not segfault
98     int j = 0;
99     for (int i = 0 ; j < newNDims ; i++) {
100       if(remain_dims[i]) {
101         newDims[j] =dims_[i];
102         newPeriodic[j] =periodic_[i];
103         j++;
104       }
105     }
106   }
107   Topo_Cart* res = new Topo_Cart(getComm(), newNDims, newDims, newPeriodic, 0, newcomm);
108   delete[] newDims;
109   delete[] newPeriodic;
110   return res;
111 }
112
113 int Topo_Cart::coords(int rank, int /*maxdims*/, int coords[])
114 {
115   int nnodes = nnodes_;
116   for (int i = 0; i< ndims_; i++ ) {
117     nnodes    = nnodes /dims_[i];
118     coords[i] = rank / nnodes;
119     rank      = rank % nnodes;
120   }
121   return MPI_SUCCESS;
122 }
123
124 int Topo_Cart::get(int maxdims, int* dims, int* periods, int* coords) {
125   int ndims=ndims_ < maxdims ?ndims_ : maxdims;
126   for(int i = 0 ; i < ndims ; i++) {
127     dims[i] =dims_[i];
128     periods[i] =periodic_[i];
129     coords[i] =position_[i];
130   }
131   return MPI_SUCCESS;
132 }
133
134 int Topo_Cart::rank(const int* coords, int* rank) {
135   int ndims =ndims_;
136   *rank = 0;
137   int multiplier = 1;
138
139   for (int i=ndims-1; i >=0; i-- ) {
140     int coord = coords[i];
141
142     /* The user can give us whatever coordinates he wants. If one of them is out of range, either this dimension is
143      * periodic, and we consider the equivalent coordinate inside the bounds, or it's not and then it's an error
144      */
145     if (coord >=dims_[i]) {
146       if (periodic_[i] ) {
147         coord = coord %dims_[i];
148       } else {
149         // Should I do that ?
150         *rank = -1;
151         return MPI_ERR_ARG;
152       }
153     } else if (coord <  0) {
154       if(periodic_[i]) {
155         coord = coord %dims_[i];
156         if (coord)
157           coord =dims_[i] + coord;
158       } else {
159         *rank = -1;
160         return MPI_ERR_ARG;
161       }
162     }
163
164     *rank += multiplier * coord;
165     multiplier *=dims_[i];
166   }
167   return MPI_SUCCESS;
168 }
169
170 int Topo_Cart::shift(int direction, int disp, int* rank_source, int* rank_dest)
171 {
172   if(ndims_ == 0) {
173     return MPI_ERR_ARG;
174   }
175   if (ndims_ < direction) {
176     return MPI_ERR_DIMS;
177   }
178
179   int* position = new int[ndims_];
180   this->coords(getComm()->rank(), ndims_, position);
181   position[direction] += disp;
182
183   if(position[direction] < 0 ||
184       position[direction] >=dims_[direction]) {
185     if(periodic_[direction]) {
186       position[direction] %=dims_[direction];
187       this->rank(position, rank_dest);
188     } else {
189       *rank_dest = MPI_PROC_NULL;
190     }
191   } else {
192     this->rank(position, rank_dest);
193   }
194
195   position[direction] = position_[direction] - disp;
196   if(position[direction] < 0 || position[direction] >=dims_[direction]) {
197     if(periodic_[direction]) {
198       position[direction] %=dims_[direction];
199       this->rank(position, rank_source);
200     } else {
201       *rank_source = MPI_PROC_NULL;
202     }
203   } else {
204     this->rank(position, rank_source);
205   }
206   delete[] position;
207   return MPI_SUCCESS;
208 }
209
210 int Topo_Cart::dim_get(int *ndims) {
211   *ndims =ndims_;
212   return MPI_SUCCESS;
213 }
214
215 // Everything below has been taken from ompi, but could be easily rewritten (and partially was to follow sonar rules).
216
217 /*
218  * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana
219  *                         University Research and Technology
220  *                         Corporation.  All rights reserved.
221  * Copyright (c) 2004-2005 The University of Tennessee and The University
222  *                         of Tennessee Research Foundation.  All rights
223  *                         reserved.
224  * Copyright (c) 2004-2014 High Performance Computing Center Stuttgart,
225  *                         University of Stuttgart.  All rights reserved.
226  * Copyright (c) 2004-2005 The Regents of the University of California.
227  *                         All rights reserved.
228  * Copyright (c) 2012      Los Alamos National Security, LLC.  All rights
229  *                         reserved.
230  * Copyright (c) 2014      Intel, Inc. All rights reserved
231  * $COPYRIGHT$
232  *
233  * Additional copyrights may follow
234  *
235  * $HEADER$
236  */
237
238 /*
239  * This is a utility function, no need to have anything in the lower layer for this at all
240  */
241 int Topo_Cart::Dims_create(int nnodes, int ndims, int dims[])
242 {
243   /* Get # of free-to-be-assigned processes and # of free dimensions */
244   int freeprocs = nnodes;
245   int freedims = 0;
246   int *p = dims;
247   for (int i = 0; i < ndims; ++i) {
248     if (*p == 0) {
249       ++freedims;
250     } else if ((*p < 0) || ((nnodes % *p) != 0)) {
251       return  MPI_ERR_DIMS;
252
253     } else {
254       freeprocs /= *p;
255     }
256     p++;
257   }
258
259   if (freedims == 0) {
260     if (freeprocs == 1) {
261       return MPI_SUCCESS;
262     }
263     return MPI_ERR_DIMS;
264   }
265
266   if (freeprocs == 1) {
267     for (int i = 0; i < ndims; ++i) {
268       if (*dims == 0) {
269         *dims = 1;
270       }
271       dims++;
272     }
273     return MPI_SUCCESS;
274   }
275
276   /* Factor the number of free processes */
277   int nfactors;
278   int *factors;
279   int err = getfactors(freeprocs, &nfactors, &factors);
280   if (MPI_SUCCESS != err)
281     return  err;
282
283   /* Assign free processes to free dimensions */
284   int *procs;
285   err = assignnodes(freedims, nfactors, factors, &procs);
286   if (MPI_SUCCESS != err)
287     return err;
288
289   /* Return assignment results */
290   p = procs;
291   for (int i = 0; i < ndims; ++i) {
292     if (*dims == 0) {
293       *dims = *p++;
294     }
295     dims++;
296   }
297
298   delete[] factors;
299   delete[] procs;
300
301   /* all done */
302   return MPI_SUCCESS;
303 }
304
305 }
306 }
307
308 /*
309  *  assignnodes
310  *
311  *  Function:   - assign processes to dimensions
312  *          - get "best-balanced" grid
313  *          - greedy bin-packing algorithm used
314  *          - sort dimensions in decreasing order
315  *          - dimensions array dynamically allocated
316  *  Accepts:    - # of dimensions
317  *          - # of prime factors
318  *          - array of prime factors
319  *          - ptr to array of dimensions (returned value)
320  *  Returns:    - 0 or ERROR
321  */
322 static int assignnodes(int ndim, int nfactor, int *pfacts, int **pdims)
323 {
324   int *pmin;
325
326   if (0 >= ndim) {
327     return MPI_ERR_DIMS;
328   }
329
330   /* Allocate and initialize the bins */
331   int *bins = new int[ndim];
332
333   *pdims = bins;
334   int *p = bins;
335
336   for (int i = 0 ; i < ndim; ++i) {
337     *p = 1;
338     p++;
339   }
340   /* Loop assigning factors from the highest to the lowest */
341   for (int j = nfactor - 1; j >= 0; --j) {
342     int f = pfacts[j];
343     /* Assign a factor to the smallest bin */
344     pmin = bins;
345     p = pmin + 1;
346     for (int i = 1; i < ndim; ++i) {
347       if (*p < *pmin) {
348         pmin = p;
349       }
350       p++;
351     }
352     *pmin *= f;
353   }
354
355   /* Sort dimensions in decreasing order (O(n^2) for now) */
356   pmin = bins;
357   for (int i = 0; i < ndim - 1; ++i) {
358     p = pmin + 1;
359     for (int j = i + 1; j < ndim; ++j) {
360       if (*p > *pmin) {
361         int n = *p;
362         *p = *pmin;
363         *pmin = n;
364       }
365       p++;
366     }
367     pmin++;
368   }
369
370   return MPI_SUCCESS;
371 }
372
373 /*
374  *  getfactors
375  *
376  *  Function:   - factorize a number
377  *  Accepts:    - number
378  *          - # prime factors
379  *          - array of prime factors
380  *  Returns:    - MPI_SUCCESS or ERROR
381  */
382 static int getfactors(int num, int *nfactors, int **factors) {
383   if(num  < 2) {
384     (*nfactors) = 0;
385     (*factors) = nullptr;
386     return MPI_SUCCESS;
387   }
388   /* Allocate the array of prime factors which cannot exceed log_2(num) entries */
389   int sqrtnum = ceil(sqrt(double(num)));
390   int size = ceil(log(double(num)) / log(2.0));
391   *factors = new int[size];
392
393   int i = 0;
394   /* determine all occurrences of factor 2 */
395   while((num % 2) == 0) {
396     num /= 2;
397     (*factors)[i++] = 2;
398   }
399   /* determine all occurrences of uneven prime numbers up to sqrt(num) */
400   for(int d = 3; (num > 1) && (d < sqrtnum); d += 2) {
401     while((num % d) == 0) {
402       num /= d;
403       (*factors)[i++] = d;
404     }
405   }
406   /* as we looped only up to sqrt(num) one factor > sqrt(num) may be left over */
407   if(num != 1) {
408     (*factors)[i++] = num;
409   }
410   (*nfactors) = i;
411   return MPI_SUCCESS;
412 }
413