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"
9 #include "src/smpi/smpi_group.hpp"
14 typedef struct s_smpi_mpi_cart_topology {
20 } s_smpi_mpi_cart_topology_t;
22 typedef struct s_smpi_mpi_graph_topology {
27 } s_smpi_mpi_graph_topology_t;
29 typedef struct s_smpi_dist_graph_topology {
37 } s_smpi_mpi_dist_graph_topology_t;
39 typedef struct s_smpi_mpi_topology {
42 MPIR_Graph_Topology graph;
43 MPIR_Cart_Topology cart;
44 MPIR_Dist_Graph_Topology dist_graph;
46 } s_smpi_mpi_topology_t;
48 void smpi_topo_destroy(MPI_Topology topo) {
54 smpi_cart_topo_destroy(topo->topo.cart);
57 // This topology is not supported by SMPI yet
58 smpi_graph_topo_destroy(topo->topo.graph);
61 // This topology is not supported by SMPI yet
62 smpi_dist_graph_topo_destroy(topo->topo.dist_graph);
70 MPI_Topology smpi_topo_create(MPIR_Topo_type kind) {
71 MPI_Topology newTopo = static_cast<MPI_Topology>(xbt_malloc(sizeof(*newTopo)));
73 // Allocate and initialize the right topo should be done by the caller
77 void smpi_graph_topo_destroy(MPIR_Graph_Topology graph) {
79 delete[] graph->index;
80 delete[] graph->edges;
85 void smpi_dist_graph_topo_destroy(MPIR_Dist_Graph_Topology dist_graph) {
87 delete[] dist_graph->in;
88 delete[] dist_graph->in_weights;
89 delete[] dist_graph->out;
90 delete[] dist_graph->out_weights;
95 /*******************************************************************************
96 * Cartesian topologies
97 ******************************************************************************/
98 void smpi_cart_topo_destroy(MPIR_Cart_Topology cart) {
101 delete[] cart->periodic;
102 delete[] cart->position;
107 MPI_Topology smpi_cart_topo_create(int ndims) {
108 MPI_Topology newTopo = smpi_topo_create(MPI_CART);
109 MPIR_Cart_Topology newCart = static_cast<MPIR_Cart_Topology>(xbt_malloc(sizeof(*newCart)));
111 newCart->ndims = ndims;
112 newCart->dims = new int[ndims];
113 newCart->periodic = new int[ndims];
114 newCart->position = new int[ndims];
115 newTopo->topo.cart = newCart;
119 /* reorder is ignored, don't know what would be the consequences of a dumb reordering but neither do I see the point of
121 int smpi_mpi_cart_create(MPI_Comm comm_old, int ndims, int dims[], int periods[], int reorder, MPI_Comm *comm_cart) {
122 int retval = MPI_SUCCESS;
123 MPI_Topology newCart;
128 int rank = comm_old->rank();
132 for (int i = 0 ; i < ndims ; i++) {
135 if(rank >= newSize) {
136 *comm_cart = MPI_COMM_NULL;
139 newCart = smpi_cart_topo_create(ndims);
140 oldGroup = comm_old->group();
141 newGroup = new simgrid::SMPI::Group(newSize);
142 for (int i = 0 ; i < newSize ; i++) {
143 newGroup->set_mapping(oldGroup->index(i), i);
146 newCart->topo.cart->nnodes = newSize;
148 // FIXME : code duplication... See smpi_mpi_cart_coords
150 for (int i=0; i<ndims; i++) {
151 newCart->topo.cart->dims[i] = dims[i];
152 newCart->topo.cart->periodic[i] = periods[i];
153 nranks = nranks / dims[i];
154 /* FIXME: nranks could be zero (?) */
155 newCart->topo.cart->position[i] = rank / nranks;
156 rank = rank % nranks;
159 *comm_cart = new simgrid::SMPI::Comm(newGroup, newCart);
162 newCart = smpi_cart_topo_create(ndims);
163 *comm_cart = new simgrid::SMPI::Comm(new simgrid::SMPI::Group(MPI_COMM_SELF->group()), newCart);
165 *comm_cart = MPI_COMM_NULL;
171 int smpi_mpi_cart_sub(MPI_Comm comm, const int remain_dims[], MPI_Comm *newcomm) {
172 MPI_Topology oldTopo = comm->topo();
173 int oldNDims = oldTopo->topo.cart->ndims;
175 int *newDims = nullptr;
176 int *newPeriodic = nullptr;
178 if (remain_dims == nullptr && oldNDims != 0) {
182 for (int i = 0 ; i < oldNDims ; i++) {
188 newDims = xbt_new(int, newNDims);
189 newPeriodic = xbt_new(int, newNDims);
191 // that should not segfault
192 for (int i = 0 ; j < newNDims ; i++) {
194 newDims[j] = oldTopo->topo.cart->dims[i];
195 newPeriodic[j] = oldTopo->topo.cart->periodic[i];
200 return smpi_mpi_cart_create(comm, newNDims, newDims, newPeriodic, 0, newcomm);
203 int smpi_mpi_cart_coords(MPI_Comm comm, int rank, int maxdims, int coords[]) {
204 MPI_Topology topo = comm->topo();
205 int nnodes = topo->topo.cart->nnodes;
206 for (int i = 0; i< topo->topo.cart->ndims; i++ ) {
207 nnodes = nnodes / topo->topo.cart->dims[i];
208 coords[i] = rank / nnodes;
209 rank = rank % nnodes;
214 int smpi_mpi_cart_get(MPI_Comm comm, int maxdims, int* dims, int* periods, int* coords) {
215 MPI_Topology topo = comm->topo();
216 int ndims=topo->topo.cart->ndims < maxdims ? topo->topo.cart->ndims : maxdims;
217 for(int i = 0 ; i < ndims ; i++) {
218 dims[i] = topo->topo.cart->dims[i];
219 periods[i] = topo->topo.cart->periodic[i];
220 coords[i] = topo->topo.cart->position[i];
225 int smpi_mpi_cart_rank(MPI_Comm comm, int* coords, int* rank) {
226 MPI_Topology topo = comm->topo();
227 int ndims = topo->topo.cart->ndims;
232 for (int i=ndims-1; i >=0; i-- ) {
235 /* The user can give us whatever coordinates he wants. If one of them is out of range, either this dimension is
236 * periodic, and we consider the equivalent coordinate inside the bounds, or it's not and then it's an error
238 if (coord >= topo->topo.cart->dims[i]) {
239 if ( topo->topo.cart->periodic[i] ) {
240 coord = coord % topo->topo.cart->dims[i];
242 // Should I do that ?
246 } else if (coord < 0) {
247 if(topo->topo.cart->periodic[i]) {
248 coord = coord % topo->topo.cart->dims[i];
250 coord = topo->topo.cart->dims[i] + coord;
257 *rank += multiplier * coord;
258 multiplier *= topo->topo.cart->dims[i];
263 int smpi_mpi_cart_shift(MPI_Comm comm, int direction, int disp, int *rank_source, int *rank_dest) {
264 MPI_Topology topo = comm->topo();
265 int position[topo->topo.cart->ndims];
267 if(topo->topo.cart->ndims == 0) {
270 if (topo->topo.cart->ndims < direction) {
274 smpi_mpi_cart_coords(comm, comm->rank(), topo->topo.cart->ndims, position);
275 position[direction] += disp;
277 if(position[direction] < 0 ||
278 position[direction] >= topo->topo.cart->dims[direction]) {
279 if(topo->topo.cart->periodic[direction]) {
280 position[direction] %= topo->topo.cart->dims[direction];
281 smpi_mpi_cart_rank(comm, position, rank_dest);
283 *rank_dest = MPI_PROC_NULL;
286 smpi_mpi_cart_rank(comm, position, rank_dest);
289 position[direction] = topo->topo.cart->position[direction] - disp;
290 if(position[direction] < 0 || position[direction] >= topo->topo.cart->dims[direction]) {
291 if(topo->topo.cart->periodic[direction]) {
292 position[direction] %= topo->topo.cart->dims[direction];
293 smpi_mpi_cart_rank(comm, position, rank_source);
295 *rank_source = MPI_PROC_NULL;
298 smpi_mpi_cart_rank(comm, position, rank_source);
304 int smpi_mpi_cartdim_get(MPI_Comm comm, int *ndims) {
305 MPI_Topology topo = comm->topo();
307 *ndims = topo->topo.cart->ndims;
311 // Everything below has been taken from ompi, but could be easily rewritten (and partially was to follow sonar rules).
314 * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana
315 * University Research and Technology
316 * Corporation. All rights reserved.
317 * Copyright (c) 2004-2005 The University of Tennessee and The University
318 * of Tennessee Research Foundation. All rights
320 * Copyright (c) 2004-2014 High Performance Computing Center Stuttgart,
321 * University of Stuttgart. All rights reserved.
322 * Copyright (c) 2004-2005 The Regents of the University of California.
323 * All rights reserved.
324 * Copyright (c) 2012 Los Alamos National Security, LLC. All rights
326 * Copyright (c) 2014 Intel, Inc. All rights reserved
329 * Additional copyrights may follow
334 /* static functions */
335 static int assignnodes(int ndim, int nfactor, int *pfacts,int **pdims);
336 static int getfactors(int num, int *nfators, int **factors);
339 * This is a utility function, no need to have anything in the lower layer for this at all
341 int smpi_mpi_dims_create(int nnodes, int ndims, int dims[])
343 /* Get # of free-to-be-assigned processes and # of free dimensions */
344 int freeprocs = nnodes;
347 for (int i = 0; i < ndims; ++i) {
350 } else if ((*p < 0) || ((nnodes % *p) != 0)) {
360 if (freeprocs == 1) {
366 if (freeprocs == 1) {
367 for (int i = 0; i < ndims; ++i) {
376 /* Factor the number of free processes */
379 int err = getfactors(freeprocs, &nfactors, &factors);
380 if (MPI_SUCCESS != err)
383 /* Assign free processes to free dimensions */
385 err = assignnodes(freedims, nfactors, factors, &procs);
386 if (MPI_SUCCESS != err)
389 /* Return assignment results */
391 for (int i = 0; i < ndims; ++i) {
408 * Function: - assign processes to dimensions
409 * - get "best-balanced" grid
410 * - greedy bin-packing algorithm used
411 * - sort dimensions in decreasing order
412 * - dimensions array dynamically allocated
413 * Accepts: - # of dimensions
414 * - # of prime factors
415 * - array of prime factors
416 * - ptr to array of dimensions (returned value)
417 * Returns: - 0 or ERROR
419 static int assignnodes(int ndim, int nfactor, int *pfacts, int **pdims)
427 /* Allocate and initialize the bins */
428 int *bins = new int[ndim];
433 for (int i = 0 ; i < ndim; ++i) {
437 /* Loop assigning factors from the highest to the lowest */
438 for (int j = nfactor - 1; j >= 0; --j) {
440 /* Assign a factor to the smallest bin */
443 for (int i = 1; i < ndim; ++i) {
452 /* Sort dimensions in decreasing order (O(n^2) for now) */
454 for (int i = 0; i < ndim - 1; ++i) {
456 for (int j = i + 1; j < ndim; ++j) {
473 * Function: - factorize a number
476 * - array of prime factors
477 * Returns: - MPI_SUCCESS or ERROR
479 static int getfactors(int num, int *nfactors, int **factors) {
482 (*factors) = nullptr;
485 /* Allocate the array of prime factors which cannot exceed log_2(num) entries */
486 int sqrtnum = ceil(sqrt(num));
487 int size = ceil(log(num) / log(2));
488 *factors = new int[size];
491 /* determine all occurrences of factor 2 */
492 while((num % 2) == 0) {
496 /* determine all occurrences of uneven prime numbers up to sqrt(num) */
497 for(int d = 3; (num > 1) && (d < sqrtnum); d += 2) {
498 while((num % d) == 0) {
503 /* as we looped only up to sqrt(num) one factor > sqrt(num) may be left over */
505 (*factors)[i++] = num;