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