1 /* Copyright (c) 2014, 2017. The SimGrid Team.
2 * All rights reserved. */
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. */
7 #include "xbt/sysdep.h"
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);
28 Dist_Graph::~Dist_Graph()
33 delete[] out_weights_;
36 /*******************************************************************************
37 * Cartesian topologies
38 ******************************************************************************/
50 dims_ = new int[ndims];
51 periodic_ = new int[ndims];
52 position_ = new int[ndims];
55 /* reorder is ignored, don't know what would be the consequences of a dumb reordering but neither do I see the point of
57 Cart::Cart(MPI_Comm comm_old, int ndims, int dims[], int periods[], int reorder, MPI_Comm *comm_cart) : Cart(ndims) {
62 int rank = comm_old->rank();
66 for (int i = 0 ; i < ndims ; i++) {
70 *comm_cart = MPI_COMM_NULL;
73 oldGroup = comm_old->group();
74 newGroup = new simgrid::smpi::Group(newSize);
75 for (int i = 0 ; i < newSize ; i++) {
76 newGroup->set_mapping(oldGroup->index(i), i);
81 // FIXME : code duplication... See coords
83 for (int i=0; i<ndims; i++) {
85 periodic_[i] = periods[i];
86 nranks = nranks / dims[i];
87 /* FIXME: nranks could be zero (?) */
88 position_[i] = rank / nranks;
92 *comm_cart = new simgrid::smpi::Comm(newGroup, this);
95 *comm_cart = new simgrid::smpi::Comm(new simgrid::smpi::Group(MPI_COMM_SELF->group()), this);
97 *comm_cart = MPI_COMM_NULL;
103 Cart* Cart::sub(const int remain_dims[], MPI_Comm *newcomm) {
104 int oldNDims = ndims_;
106 int *newDims = nullptr;
107 int *newPeriodic = nullptr;
109 if (remain_dims == nullptr && oldNDims != 0) {
113 for (int i = 0 ; i < oldNDims ; i++) {
119 newDims = xbt_new(int, newNDims);
120 newPeriodic = xbt_new(int, newNDims);
122 // that should not segfault
123 for (int i = 0 ; j < newNDims ; i++) {
125 newDims[j] =dims_[i];
126 newPeriodic[j] =periodic_[i];
131 return new Cart(comm_, newNDims, newDims, newPeriodic, 0, newcomm);
134 int 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;
144 int 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++) {
148 periods[i] =periodic_[i];
149 coords[i] =position_[i];
154 int Cart::rank(int* coords, int* rank) {
160 for (int i=ndims-1; i >=0; i-- ) {
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
166 if (coord >=dims_[i]) {
168 coord = coord %dims_[i];
170 // Should I do that ?
174 } else if (coord < 0) {
176 coord = coord %dims_[i];
178 coord =dims_[i] + coord;
185 *rank += multiplier * coord;
186 multiplier *=dims_[i];
191 int Cart::shift(int direction, int disp, int *rank_source, int *rank_dest) {
193 int position[ndims_];
198 if (ndims_ < direction) {
202 this->coords(comm_->rank(),ndims_, position);
203 position[direction] += disp;
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);
211 *rank_dest = MPI_PROC_NULL;
214 this->rank(position, rank_dest);
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);
223 *rank_source = MPI_PROC_NULL;
226 this->rank(position, rank_source);
232 int Cart::dim_get(int *ndims) {
237 // Everything below has been taken from ompi, but could be easily rewritten (and partially was to follow sonar rules).
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
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
252 * Copyright (c) 2014 Intel, Inc. All rights reserved
255 * Additional copyrights may follow
262 * This is a utility function, no need to have anything in the lower layer for this at all
264 int Dims_create(int nnodes, int ndims, int dims[])
266 /* Get # of free-to-be-assigned processes and # of free dimensions */
267 int freeprocs = nnodes;
270 for (int i = 0; i < ndims; ++i) {
273 } else if ((*p < 0) || ((nnodes % *p) != 0)) {
283 if (freeprocs == 1) {
289 if (freeprocs == 1) {
290 for (int i = 0; i < ndims; ++i) {
299 /* Factor the number of free processes */
302 int err = getfactors(freeprocs, &nfactors, &factors);
303 if (MPI_SUCCESS != err)
306 /* Assign free processes to free dimensions */
308 err = assignnodes(freedims, nfactors, factors, &procs);
309 if (MPI_SUCCESS != err)
312 /* Return assignment results */
314 for (int i = 0; i < ndims; ++i) {
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
345 static int assignnodes(int ndim, int nfactor, int *pfacts, int **pdims)
353 /* Allocate and initialize the bins */
354 int *bins = new int[ndim];
359 for (int i = 0 ; i < ndim; ++i) {
363 /* Loop assigning factors from the highest to the lowest */
364 for (int j = nfactor - 1; j >= 0; --j) {
366 /* Assign a factor to the smallest bin */
369 for (int i = 1; i < ndim; ++i) {
378 /* Sort dimensions in decreasing order (O(n^2) for now) */
380 for (int i = 0; i < ndim - 1; ++i) {
382 for (int j = i + 1; j < ndim; ++j) {
399 * Function: - factorize a number
402 * - array of prime factors
403 * Returns: - MPI_SUCCESS or ERROR
405 static int getfactors(int num, int *nfactors, int **factors) {
408 (*factors) = nullptr;
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];
417 /* determine all occurrences of factor 2 */
418 while((num % 2) == 0) {
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) {
429 /* as we looped only up to sqrt(num) one factor > sqrt(num) may be left over */
431 (*factors)[i++] = num;