src/smpi/mpi/smpi_topo.cpp

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