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