src/smpi/mpi/smpi_topo.cpp

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