src/smpi/smpi_topo.cpp

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