src/smpi/mpi/smpi_topo.cpp

   1 /* Copyright (c) 2014-2021. 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
  12 #include <algorithm>
  13 #include <vector>
  14
  15 /* static functions */
  16 static int assignnodes(int ndim, const std::vector<int>& factors, std::vector<int>& dims);
  17 static int getfactors(int num, std::vector<int>& factors);
  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         auto* 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   std::vector<int> newDims;
  96   std::vector<int> newPeriodic;
  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.resize(newNDims);
 109     newPeriodic.resize(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.data(), newPeriodic.data(), 0, newcomm);
 132   } else {
 133     *newcomm = getComm()->split(color, getComm()->rank());
 134     auto topo = std::make_shared<Topo_Cart>(getComm(), newNDims, newDims.data(), newPeriodic.data(), 0, nullptr);
 135     res       = topo.get();
 136     res->setComm(*newcomm);
 137     (*newcomm)->set_topo(topo);
 138   }
 139   return res;
 140 }
 141
 142 int Topo_Cart::coords(int rank, int /*maxdims*/, int coords[])
 143 {
 144   int nnodes = nnodes_;
 145   for (int i = 0; i< ndims_; i++ ) {
 146     nnodes    = nnodes /dims_[i];
 147     coords[i] = rank / nnodes;
 148     rank      = rank % nnodes;
 149   }
 150   return MPI_SUCCESS;
 151 }
 152
 153 int Topo_Cart::get(int maxdims, int* dims, int* periods, int* coords) {
 154   int ndims=ndims_ < maxdims ?ndims_ : maxdims;
 155   for(int i = 0 ; i < ndims ; i++) {
 156     dims[i] =dims_[i];
 157     periods[i] =periodic_[i];
 158     coords[i] =position_[i];
 159   }
 160   return MPI_SUCCESS;
 161 }
 162
 163 int Topo_Cart::rank(const int* coords, int* rank) {
 164   int ndims =ndims_;
 165   *rank = 0;
 166   int multiplier = 1;
 167
 168   for (int i=ndims-1; i >=0; i-- ) {
 169     int coord = coords[i];
 170
 171     /* The user can give us whatever coordinates he wants. If one of them is out of range, either this dimension is
 172      * periodic, and we consider the equivalent coordinate inside the bounds, or it's not and then it's an error
 173      */
 174     if (coord >=dims_[i]) {
 175       if (periodic_[i] ) {
 176         coord = coord %dims_[i];
 177       } else {
 178         // Should I do that ?
 179         *rank = -1;
 180         return MPI_ERR_ARG;
 181       }
 182     } else if (coord <  0) {
 183       if(periodic_[i]) {
 184         coord = coord %dims_[i];
 185         if (coord)
 186           coord =dims_[i] + coord;
 187       } else {
 188         *rank = -1;
 189         return MPI_ERR_ARG;
 190       }
 191     }
 192
 193     *rank += multiplier * coord;
 194     multiplier *=dims_[i];
 195   }
 196   return MPI_SUCCESS;
 197 }
 198
 199 int Topo_Cart::shift(int direction, int disp, int* rank_source, int* rank_dest)
 200 {
 201   if(ndims_ == 0) {
 202     return MPI_ERR_ARG;
 203   }
 204   if (ndims_ < direction) {
 205     return MPI_ERR_DIMS;
 206   }
 207
 208   std::vector<int> position(ndims_);
 209   this->coords(getComm()->rank(), ndims_, position.data());
 210   position[direction] += disp;
 211
 212   if(position[direction] < 0 ||
 213       position[direction] >=dims_[direction]) {
 214     if(periodic_[direction]) {
 215       position[direction] %=dims_[direction];
 216       this->rank(position.data(), rank_dest);
 217     } else {
 218       *rank_dest = MPI_PROC_NULL;
 219     }
 220   } else {
 221     this->rank(position.data(), rank_dest);
 222   }
 223
 224   position[direction] = position_[direction] - disp;
 225   if(position[direction] < 0 || position[direction] >=dims_[direction]) {
 226     if(periodic_[direction]) {
 227       position[direction] %=dims_[direction];
 228       this->rank(position.data(), rank_source);
 229     } else {
 230       *rank_source = MPI_PROC_NULL;
 231     }
 232   } else {
 233     this->rank(position.data(), rank_source);
 234   }
 235   return MPI_SUCCESS;
 236 }
 237
 238 int Topo_Cart::dim_get(int* ndims) const
 239 {
 240   *ndims =ndims_;
 241   return MPI_SUCCESS;
 242 }
 243
 244 // Everything below has been taken from ompi, but could be easily rewritten (and partially was to follow sonar rules).
 245
 246 /*
 247  * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana
 248  *                         University Research and Technology
 249  *                         Corporation.  All rights reserved.
 250  * Copyright (c) 2004-2005 The University of Tennessee and The University
 251  *                         of Tennessee Research Foundation.  All rights
 252  *                         reserved.
 253  * Copyright (c) 2004-2014 High Performance Computing Center Stuttgart,
 254  *                         University of Stuttgart.  All rights reserved.
 255  * Copyright (c) 2004-2005 The Regents of the University of California.
 256  *                         All rights reserved.
 257  * Copyright (c) 2012      Los Alamos National Security, LLC.  All rights
 258  *                         reserved.
 259  * Copyright (c) 2014      Intel, Inc. All rights reserved
 260  * $COPYRIGHT$
 261  *
 262  * Additional copyrights may follow
 263  *
 264  * $HEADER$
 265  */
 266
 267 /*
 268  * This is a utility function, no need to have anything in the lower layer for this at all
 269  */
 270 int Topo_Cart::Dims_create(int nnodes, int ndims, int dims[])
 271 {
 272   /* Get # of free-to-be-assigned processes and # of free dimensions */
 273   int freeprocs = nnodes;
 274   int freedims = 0;
 275   for (int i = 0; i < ndims; ++i) {
 276     if (dims[i] == 0) {
 277       ++freedims;
 278     } else if ((dims[i] < 0) || ((nnodes % dims[i]) != 0)) {
 279       return  MPI_ERR_DIMS;
 280
 281     } else {
 282       freeprocs /= dims[i];
 283     }
 284   }
 285
 286   if (freedims == 0) {
 287     if (freeprocs == 1) {
 288       return MPI_SUCCESS;
 289     }
 290     return MPI_ERR_DIMS;
 291   }
 292
 293   if (freeprocs == 1) {
 294     for (int i = 0; i < ndims; ++i) {
 295       if (dims[i] == 0) {
 296         dims[i] = 1;
 297       }
 298     }
 299     return MPI_SUCCESS;
 300   }
 301
 302   /* Factor the number of free processes */
 303   std::vector<int> factors;
 304   int err = getfactors(freeprocs, factors);
 305   if (MPI_SUCCESS != err)
 306     return  err;
 307
 308   /* Assign free processes to free dimensions */
 309   std::vector<int> procs;
 310   err = assignnodes(freedims, factors, procs);
 311   if (MPI_SUCCESS != err)
 312     return err;
 313
 314   /* Return assignment results */
 315   auto p = procs.begin();
 316   for (int i = 0; i < ndims; ++i) {
 317     if (dims[i] == 0) {
 318       dims[i] = *p++;
 319     }
 320   }
 321
 322   /* all done */
 323   return MPI_SUCCESS;
 324 }
 325
 326 }
 327 }
 328
 329 /*
 330  *  assignnodes
 331  *
 332  *  Function:   - assign processes to dimensions
 333  *          - get "best-balanced" grid
 334  *          - greedy bin-packing algorithm used
 335  *          - sort dimensions in decreasing order
 336  *          - dimensions array dynamically allocated
 337  *  Accepts:    - # of dimensions
 338  *          - std::vector of prime factors
 339  *          - reference to std::vector of dimensions (returned value)
 340  *  Returns:    - 0 or ERROR
 341  */
 342 static int assignnodes(int ndim, const std::vector<int>& factors, std::vector<int>& dims)
 343 {
 344   if (0 >= ndim) {
 345     return MPI_ERR_DIMS;
 346   }
 347
 348   /* Allocate and initialize the bins */
 349   dims.clear();
 350   dims.resize(ndim, 1);
 351
 352   /* Loop assigning factors from the highest to the lowest */
 353   for (auto pfact = factors.crbegin(); pfact != factors.crend(); ++pfact) {
 354     /* Assign a factor to the smallest bin */
 355     auto pmin = std::min_element(dims.begin(), dims.end());
 356     *pmin *= *pfact;
 357   }
 358
 359   /* Sort dimensions in decreasing order */
 360   std::sort(dims.begin(), dims.end(), std::greater<>());
 361
 362   return MPI_SUCCESS;
 363 }
 364
 365 /*
 366  *  getfactors
 367  *
 368  *  Function:   - factorize a number
 369  *  Accepts:    - number
 370  *              - reference to std::vector of prime factors
 371  *  Returns:    - MPI_SUCCESS or ERROR
 372  */
 373 static int getfactors(int num, std::vector<int>& factors)
 374 {
 375   factors.clear();
 376   if (num < 2) {
 377     return MPI_SUCCESS;
 378   }
 379
 380   /* determine all occurrences of factor 2 */
 381   while((num % 2) == 0) {
 382     num /= 2;
 383     factors.push_back(2);
 384   }
 385   /* determine all occurrences of uneven prime numbers up to sqrt(num) */
 386   for (int d = 3; (num > 1) && (d * d < num); d += 2) {
 387     while((num % d) == 0) {
 388       num /= d;
 389       factors.push_back(d);
 390     }
 391   }
 392   /* as we looped only up to sqrt(num) one factor > sqrt(num) may be left over */
 393   if(num != 1) {
 394     factors.push_back(num);
 395   }
 396   return MPI_SUCCESS;
 397 }