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