 Algorithmique Numérique Distribuée Public GIT Repository
1 /* Copyright (c) 2014-2017. 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->index(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 = xbt_new(int, newNDims);
116     newPeriodic = xbt_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   return new Topo_Cart(getComm(), newNDims, newDims, newPeriodic, 0, newcomm);
129 }
131 int Topo_Cart::coords(int rank, int maxdims, int coords[]) {
132   int nnodes = nnodes_;
133   for (int i = 0; i< ndims_; i++ ) {
134     nnodes    = nnodes /dims_[i];
135     coords[i] = rank / nnodes;
136     rank      = rank % nnodes;
137   }
138   return MPI_SUCCESS;
139 }
141 int Topo_Cart::get(int maxdims, int* dims, int* periods, int* coords) {
142   int ndims=ndims_ < maxdims ?ndims_ : maxdims;
143   for(int i = 0 ; i < ndims ; i++) {
144     dims[i] =dims_[i];
145     periods[i] =periodic_[i];
146     coords[i] =position_[i];
147   }
148   return MPI_SUCCESS;
149 }
151 int Topo_Cart::rank(int* coords, int* rank) {
152   int ndims =ndims_;
153   *rank = 0;
154   int multiplier = 1;
156   for (int i=ndims-1; i >=0; i-- ) {
157     int coord = coords[i];
159     /* The user can give us whatever coordinates he wants. If one of them is out of range, either this dimension is
160      * periodic, and we consider the equivalent coordinate inside the bounds, or it's not and then it's an error
161      */
162     if (coord >=dims_[i]) {
163       if (periodic_[i] ) {
164         coord = coord %dims_[i];
165       } else {
166         // Should I do that ?
167         *rank = -1;
168         return MPI_ERR_ARG;
169       }
170     } else if (coord <  0) {
171       if(periodic_[i]) {
172         coord = coord %dims_[i];
173         if (coord)
174           coord =dims_[i] + coord;
175       } else {
176         *rank = -1;
177         return MPI_ERR_ARG;
178       }
179     }
181     *rank += multiplier * coord;
182     multiplier *=dims_[i];
183   }
184   return MPI_SUCCESS;
185 }
187 int Topo_Cart::shift(int direction, int disp, int *rank_source, int *rank_dest) {
189   int position[ndims_];
191   if(ndims_ == 0) {
192     return MPI_ERR_ARG;
193   }
194   if (ndims_ < direction) {
195     return MPI_ERR_DIMS;
196   }
198   this->coords(getComm()->rank(), ndims_, position);
199   position[direction] += disp;
201   if(position[direction] < 0 ||
202       position[direction] >=dims_[direction]) {
203     if(periodic_[direction]) {
204       position[direction] %=dims_[direction];
205       this->rank(position, rank_dest);
206     } else {
207       *rank_dest = MPI_PROC_NULL;
208     }
209   } else {
210     this->rank(position, rank_dest);
211   }
213   position[direction] = position_[direction] - disp;
214   if(position[direction] < 0 || position[direction] >=dims_[direction]) {
215     if(periodic_[direction]) {
216       position[direction] %=dims_[direction];
217       this->rank(position, rank_source);
218     } else {
219       *rank_source = MPI_PROC_NULL;
220     }
221   } else {
222     this->rank(position, rank_source);
223   }
225   return MPI_SUCCESS;
226 }
228 int Topo_Cart::dim_get(int *ndims) {
229   *ndims =ndims_;
230   return MPI_SUCCESS;
231 }
233 // Everything below has been taken from ompi, but could be easily rewritten (and partially was to follow sonar rules).
235 /*
236  * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana
237  *                         University Research and Technology
238  *                         Corporation.  All rights reserved.
239  * Copyright (c) 2004-2005 The University of Tennessee and The University
240  *                         of Tennessee Research Foundation.  All rights
241  *                         reserved.
242  * Copyright (c) 2004-2014 High Performance Computing Center Stuttgart,
243  *                         University of Stuttgart.  All rights reserved.
244  * Copyright (c) 2004-2005 The Regents of the University of California.
245  *                         All rights reserved.
246  * Copyright (c) 2012      Los Alamos National Security, LLC.  All rights
247  *                         reserved.
248  * Copyright (c) 2014      Intel, Inc. All rights reserved
250  *
252  *
254  */
256 /*
257  * This is a utility function, no need to have anything in the lower layer for this at all
258  */
259 int Topo_Cart::Dims_create(int nnodes, int ndims, int dims[])
260 {
261   /* Get # of free-to-be-assigned processes and # of free dimensions */
262   int freeprocs = nnodes;
263   int freedims = 0;
264   int *p = dims;
265   for (int i = 0; i < ndims; ++i) {
266     if (*p == 0) {
267       ++freedims;
268     } else if ((*p < 0) || ((nnodes % *p) != 0)) {
269       return  MPI_ERR_DIMS;
271     } else {
272       freeprocs /= *p;
273     }
274     p++;
275   }
277   if (freedims == 0) {
278     if (freeprocs == 1) {
279       return MPI_SUCCESS;
280     }
281     return MPI_ERR_DIMS;
282   }
284   if (freeprocs == 1) {
285     for (int i = 0; i < ndims; ++i) {
286       if (*dims == 0) {
287         *dims = 1;
288       }
289       dims++;
290     }
291     return MPI_SUCCESS;
292   }
294   /* Factor the number of free processes */
295   int nfactors;
296   int *factors;
297   int err = getfactors(freeprocs, &nfactors, &factors);
298   if (MPI_SUCCESS != err)
299     return  err;
301   /* Assign free processes to free dimensions */
302   int *procs;
303   err = assignnodes(freedims, nfactors, factors, &procs);
304   if (MPI_SUCCESS != err)
305     return err;
307   /* Return assignment results */
308   p = procs;
309   for (int i = 0; i < ndims; ++i) {
310     if (*dims == 0) {
311       *dims = *p++;
312     }
313     dims++;
314   }
316   delete[] factors;
317   delete[] procs;
319   /* all done */
320   return MPI_SUCCESS;
321 }
323 }
324 }
326 /*
327  *  assignnodes
328  *
329  *  Function:   - assign processes to dimensions
330  *          - get "best-balanced" grid
331  *          - greedy bin-packing algorithm used
332  *          - sort dimensions in decreasing order
333  *          - dimensions array dynamically allocated
334  *  Accepts:    - # of dimensions
335  *          - # of prime factors
336  *          - array of prime factors
337  *          - ptr to array of dimensions (returned value)
338  *  Returns:    - 0 or ERROR
339  */
340 static int assignnodes(int ndim, int nfactor, int *pfacts, int **pdims)
341 {
342   int *pmin;
344   if (0 >= ndim) {
345     return MPI_ERR_DIMS;
346   }
348   /* Allocate and initialize the bins */
349   int *bins = new int[ndim];
351   *pdims = bins;
352   int *p = bins;
354   for (int i = 0 ; i < ndim; ++i) {
355     *p = 1;
356     p++;
357   }
358   /* Loop assigning factors from the highest to the lowest */
359   for (int j = nfactor - 1; j >= 0; --j) {
360     int f = pfacts[j];
361     /* Assign a factor to the smallest bin */
362     pmin = bins;
363     p = pmin + 1;
364     for (int i = 1; i < ndim; ++i) {
365       if (*p < *pmin) {
366         pmin = p;
367       }
368       p++;
369     }
370     *pmin *= f;
371   }
373   /* Sort dimensions in decreasing order (O(n^2) for now) */
374   pmin = bins;
375   for (int i = 0; i < ndim - 1; ++i) {
376     p = pmin + 1;
377     for (int j = i + 1; j < ndim; ++j) {
378       if (*p > *pmin) {
379         int n = *p;
380         *p = *pmin;
381         *pmin = n;
382       }
383       p++;
384     }
385     pmin++;
386   }
388   return MPI_SUCCESS;
389 }
391 /*
392  *  getfactors
393  *
394  *  Function:   - factorize a number
395  *  Accepts:    - number
396  *          - # prime factors
397  *          - array of prime factors
398  *  Returns:    - MPI_SUCCESS or ERROR
399  */
400 static int getfactors(int num, int *nfactors, int **factors) {
401   if(num  < 2) {
402     (*nfactors) = 0;
403     (*factors) = nullptr;
404     return MPI_SUCCESS;
405   }
406   /* Allocate the array of prime factors which cannot exceed log_2(num) entries */
407   int sqrtnum = ceil(sqrt(num));
408   int size = ceil(log(num) / log(2));
409   *factors = new int[size];
411   int i = 0;
412   /* determine all occurrences of factor 2 */
413   while((num % 2) == 0) {
414     num /= 2;
415     (*factors)[i++] = 2;
416   }
417   /* determine all occurrences of uneven prime numbers up to sqrt(num) */
418   for(int d = 3; (num > 1) && (d < sqrtnum); d += 2) {
419     while((num % d) == 0) {
420       num /= d;
421       (*factors)[i++] = d;
422     }
423   }
424   /* as we looped only up to sqrt(num) one factor > sqrt(num) may be left over */
425   if(num != 1) {
426     (*factors)[i++] = num;
427   }
428   (*nfactors) = i;
429   return MPI_SUCCESS;
430 }