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