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