src/smpi/mpi/smpi_topo.cpp

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