src/smpi/smpi_topo.cpp

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