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