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) const
 242 {
 243   *ndims =ndims_;
 244   return MPI_SUCCESS;
 245 }
 246
 247 // Everything below has been taken from ompi, but could be easily rewritten (and partially was to follow sonar rules).
 248
 249 /*
 250  * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana
 251  *                         University Research and Technology
 252  *                         Corporation.  All rights reserved.
 253  * Copyright (c) 2004-2005 The University of Tennessee and The University
 254  *                         of Tennessee Research Foundation.  All rights
 255  *                         reserved.
 256  * Copyright (c) 2004-2014 High Performance Computing Center Stuttgart,
 257  *                         University of Stuttgart.  All rights reserved.
 258  * Copyright (c) 2004-2005 The Regents of the University of California.
 259  *                         All rights reserved.
 260  * Copyright (c) 2012      Los Alamos National Security, LLC.  All rights
 261  *                         reserved.
 262  * Copyright (c) 2014      Intel, Inc. All rights reserved
 263  * $COPYRIGHT$
 264  *
 265  * Additional copyrights may follow
 266  *
 267  * $HEADER$
 268  */
 269
 270 /*
 271  * This is a utility function, no need to have anything in the lower layer for this at all
 272  */
 273 int Topo_Cart::Dims_create(int nnodes, int ndims, int dims[])
 274 {
 275   /* Get # of free-to-be-assigned processes and # of free dimensions */
 276   int freeprocs = nnodes;
 277   int freedims = 0;
 278   const int* p  = dims;
 279   for (int i = 0; i < ndims; ++i) {
 280     if (*p == 0) {
 281       ++freedims;
 282     } else if ((*p < 0) || ((nnodes % *p) != 0)) {
 283       return  MPI_ERR_DIMS;
 284
 285     } else {
 286       freeprocs /= *p;
 287     }
 288     p++;
 289   }
 290
 291   if (freedims == 0) {
 292     if (freeprocs == 1) {
 293       return MPI_SUCCESS;
 294     }
 295     return MPI_ERR_DIMS;
 296   }
 297
 298   if (freeprocs == 1) {
 299     for (int i = 0; i < ndims; ++i) {
 300       if (*dims == 0) {
 301         *dims = 1;
 302       }
 303       dims++;
 304     }
 305     return MPI_SUCCESS;
 306   }
 307
 308   /* Factor the number of free processes */
 309   int nfactors;
 310   int *factors;
 311   int err = getfactors(freeprocs, &nfactors, &factors);
 312   if (MPI_SUCCESS != err)
 313     return  err;
 314
 315   /* Assign free processes to free dimensions */
 316   int *procs;
 317   err = assignnodes(freedims, nfactors, factors, &procs);
 318   if (MPI_SUCCESS != err)
 319     return err;
 320
 321   /* Return assignment results */
 322   p = procs;
 323   for (int i = 0; i < ndims; ++i) {
 324     if (*dims == 0) {
 325       *dims = *p++;
 326     }
 327     dims++;
 328   }
 329
 330   delete[] factors;
 331   delete[] procs;
 332
 333   /* all done */
 334   return MPI_SUCCESS;
 335 }
 336
 337 }
 338 }
 339
 340 /*
 341  *  assignnodes
 342  *
 343  *  Function:   - assign processes to dimensions
 344  *          - get "best-balanced" grid
 345  *          - greedy bin-packing algorithm used
 346  *          - sort dimensions in decreasing order
 347  *          - dimensions array dynamically allocated
 348  *  Accepts:    - # of dimensions
 349  *          - # of prime factors
 350  *          - array of prime factors
 351  *          - ptr to array of dimensions (returned value)
 352  *  Returns:    - 0 or ERROR
 353  */
 354 static int assignnodes(int ndim, int nfactor, const int* pfacts, int** pdims)
 355 {
 356   int *pmin;
 357
 358   if (0 >= ndim) {
 359     return MPI_ERR_DIMS;
 360   }
 361
 362   /* Allocate and initialize the bins */
 363   int *bins = new int[ndim];
 364
 365   *pdims = bins;
 366   int *p = bins;
 367
 368   for (int i = 0 ; i < ndim; ++i) {
 369     *p = 1;
 370     p++;
 371   }
 372   /* Loop assigning factors from the highest to the lowest */
 373   for (int j = nfactor - 1; j >= 0; --j) {
 374     int f = pfacts[j];
 375     /* Assign a factor to the smallest bin */
 376     pmin = bins;
 377     p = pmin + 1;
 378     for (int i = 1; i < ndim; ++i) {
 379       if (*p < *pmin) {
 380         pmin = p;
 381       }
 382       p++;
 383     }
 384     *pmin *= f;
 385   }
 386
 387   /* Sort dimensions in decreasing order (O(n^2) for now) */
 388   pmin = bins;
 389   for (int i = 0; i < ndim - 1; ++i) {
 390     p = pmin + 1;
 391     for (int j = i + 1; j < ndim; ++j) {
 392       if (*p > *pmin) {
 393         int n = *p;
 394         *p = *pmin;
 395         *pmin = n;
 396       }
 397       p++;
 398     }
 399     pmin++;
 400   }
 401
 402   return MPI_SUCCESS;
 403 }
 404
 405 /*
 406  *  getfactors
 407  *
 408  *  Function:   - factorize a number
 409  *  Accepts:    - number
 410  *          - # prime factors
 411  *          - array of prime factors
 412  *  Returns:    - MPI_SUCCESS or ERROR
 413  */
 414 static int getfactors(int num, int *nfactors, int **factors) {
 415   if(num  < 2) {
 416     (*nfactors) = 0;
 417     (*factors) = nullptr;
 418     return MPI_SUCCESS;
 419   }
 420   /* Allocate the array of prime factors which cannot exceed log_2(num) entries */
 421   int sqrtnum = ceil(sqrt(double(num)));
 422   int size = ceil(log(double(num)) / log(2.0));
 423   *factors = new int[size];
 424
 425   int i = 0;
 426   /* determine all occurrences of factor 2 */
 427   while((num % 2) == 0) {
 428     num /= 2;
 429     (*factors)[i++] = 2;
 430   }
 431   /* determine all occurrences of uneven prime numbers up to sqrt(num) */
 432   for(int d = 3; (num > 1) && (d < sqrtnum); d += 2) {
 433     while((num % d) == 0) {
 434       num /= d;
 435       (*factors)[i++] = d;
 436     }
 437   }
 438   /* as we looped only up to sqrt(num) one factor > sqrt(num) may be left over */
 439   if(num != 1) {
 440     (*factors)[i++] = num;
 441   }
 442   (*nfactors) = i;
 443   return MPI_SUCCESS;
 444 }
 445