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