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