X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/05e606bc7ac2a616e8f741e382d3802898069e2f..e9f0018b823e34405847177b25a85d3facc30ae1:/src/smpi/smpi_topo.c

diff --git a/src/smpi/smpi_topo.c b/src/smpi/smpi_topo.c
index 56622b867e..55ba2b840b 100644
--- a/src/smpi/smpi_topo.c
+++ b/src/smpi/smpi_topo.c
@@ -1,134 +1,196 @@
+/* Copyright (c) 2014. The SimGrid Team.
+ * All rights reserved.                                                     */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
 #include "xbt/sysdep.h"
 #include "smpi/smpi.h"
 #include "private.h"
 
 #include <math.h>
 
-typedef struct s_smpi_mpi_topology {
-  int nnodes;
-  int ndims;
-  int *dims;
-  int *periodic;
-  int *position;
+typedef struct s_smpi_mpi_cart_topology {
+    int nnodes;
+    int ndims;
+    int *dims;
+    int *periodic;
+    int *position;
+} s_smpi_mpi_cart_topology_t;
+
+typedef struct s_smpi_mpi_graph_topology {
+    int nnodes;
+    int nedges;
+    int *index;
+    int *edges;
+} s_smpi_mpi_graph_topology_t;
+
+typedef struct s_smpi_dist_graph_topology {
+    int indegree;
+    int *in;
+    int *in_weights;
+    int outdegree;
+    int *out;
+    int *out_weights;
+    int is_weighted;
+} s_smpi_mpi_dist_graph_topology_t;
+
+typedef struct s_smpi_mpi_topology { 
+    MPIR_Topo_type kind;
+    union topo { 
+        MPIR_Graph_Topology graph;
+        MPIR_Cart_Topology  cart;
+        MPIR_Dist_Graph_Topology dist_graph;
+    } topo;
 } s_smpi_mpi_topology_t;
 
-
-
 void smpi_topo_destroy(MPI_Topology topo) {
-  if (topo) {
-    if(topo->dims) {
-      free(topo->dims);
+    if(topo == NULL) {
+        return;
     }
-    if(topo->periodic) {
-      free(topo->periodic);
+    switch (topo->kind) {
+    case MPI_GRAPH:
+        // Not implemented
+        // smpi_graph_topo_destroy(topo->topo.graph);
+        break;
+    case MPI_CART:
+        smpi_cart_topo_destroy(topo->topo.cart);
+        break;
+    case MPI_DIST_GRAPH:
+        // Not implemented
+        // smpi_dist_graph_topo_destroy(topo->topo.dist_graph);
+        break;
+    default:
+        return;
+        break;
     }
-    if(topo->position) {
-      free(topo->position);
+}
+
+MPI_Topology smpi_topo_create(MPIR_Topo_type kind) {
+    MPI_Topology newTopo = xbt_malloc(sizeof(*newTopo));
+    newTopo->kind = kind;
+    // Allocate and initialize the right topo should be done by the caller
+    return newTopo;
+}
+
+/*******************************************************************************
+ * Cartesian topologies
+ ******************************************************************************/
+void smpi_cart_topo_destroy(MPIR_Cart_Topology cart) {
+    if (cart) {
+        if(cart->dims) {
+            free(cart->dims);
+        }
+        if(cart->periodic) {
+            free(cart->periodic);
+        }
+        if(cart->position) {
+            free(cart->position);
+        }
+        free(cart);
     }
-    free(topo);
-  }
 }
 
-MPI_Topology smpi_topo_create(int ndims) {
-  MPI_Topology topo = xbt_malloc(sizeof(*topo));
-  topo->nnodes = 0;
-  topo->ndims = ndims;
-  topo->dims = xbt_malloc(ndims * sizeof(*topo->dims));
-  topo->periodic = xbt_malloc(ndims * sizeof(*topo->periodic));
-  topo->position = xbt_malloc(ndims * sizeof(*topo->position));
-  return topo;
+MPI_Topology smpi_cart_topo_create(int ndims) {
+    MPI_Topology newTopo = smpi_topo_create(MPI_CART);
+    MPIR_Cart_Topology newCart = xbt_malloc(sizeof(*newCart));
+    newCart->nnodes = 0;
+    newCart->ndims = ndims;
+    newCart->dims = xbt_malloc(ndims * sizeof(*newCart->dims));
+    newCart->periodic = xbt_malloc(ndims * sizeof(*newCart->periodic));
+    newCart->position = xbt_malloc(ndims * sizeof(*newCart->position));
+    newTopo->topo.cart = newCart;
+    return newTopo;
 }
 
 /* reorder is ignored, don't know what would be the consequences of a dumb
  * reordering but neither do I see the point of reordering*/
 int smpi_mpi_cart_create(MPI_Comm comm_old, int ndims, int dims[],
-                     int periods[], int reorder, MPI_Comm *comm_cart) {
-  int retval = MPI_SUCCESS;
-  int i;
-  MPI_Topology topo;
-  MPI_Group newGroup, oldGroup;
-  int rank, nranks,  newSize;
-
-
-
-  rank = smpi_comm_rank(comm_old);
-
- 
+                         int periods[], int reorder, MPI_Comm *comm_cart) {
+    int retval = MPI_SUCCESS;
+    int i;
+    MPI_Topology newCart;
+    MPI_Group newGroup, oldGroup;
+    int rank, nranks, newSize;
+  
+    rank = smpi_comm_rank(comm_old);
  
-  newSize = 1;
-  if(ndims != 0) {
-    topo = smpi_topo_create(ndims);
-    for (i = 0 ; i < ndims ; i++) {
-      newSize *= dims[i];
-    }
-    if(rank >= newSize) {
-      *comm_cart = MPI_COMM_NULL;
-      return retval;
-    }
-    oldGroup = smpi_comm_group(comm_old);
-    newGroup = smpi_group_new(newSize);
-    for (i = 0 ; i < newSize ; i++) {
-      smpi_group_set_mapping(newGroup, smpi_group_index(oldGroup, i), i);
-    }
+    newSize = 1;
+    if(ndims != 0) {
+        for (i = 0 ; i < ndims ; i++) {
+            newSize *= dims[i];
+        }
+        if(rank >= newSize) {
+            *comm_cart = MPI_COMM_NULL;
+            return retval;
+        }
+        newCart = smpi_cart_topo_create(ndims);
+        oldGroup = smpi_comm_group(comm_old);
+        newGroup = smpi_group_new(newSize);
+        for (i = 0 ; i < newSize ; i++) {
+            smpi_group_set_mapping(newGroup, smpi_group_index(oldGroup, i), i);
+        }
     
-    topo->nnodes = newSize;
+        newCart->topo.cart->nnodes = newSize;
 
-    memcpy(topo->dims, dims, ndims * sizeof(*topo->dims));
-    memcpy(topo->periodic, periods, ndims * sizeof(*topo->periodic));
-    
-    //  code duplication... See smpi_mpi_cart_coords
-    nranks = newSize;
-    for (i=0; i<ndims; i++)
-      {
-        topo->dims[i]     = dims[i];
-        topo->periodic[i] = periods[i];
-        nranks = nranks / dims[i];
-        /* FIXME: nranks could be zero (?) */
-        topo->position[i] = rank / nranks;
-        rank = rank % nranks;
-      }
+        /* memcpy(newCart->topo.cart->dims, dims, */
+        /*        ndims * sizeof(*newCart->topo.cart->dims)); */
+        /* memcpy(newCart->topo.cart->periodic, periods, */
+        /*        ndims * sizeof(*newCart->topo.cart->periodic)); */
     
-    *comm_cart = smpi_comm_new(newGroup, topo);      
-  }
-  else {
-    if (rank == 0) {
-      topo = smpi_topo_create(ndims);
-      *comm_cart = smpi_comm_new(smpi_comm_group(MPI_COMM_SELF), topo);
+        //  FIXME : code duplication... See smpi_mpi_cart_coords
+        nranks = newSize;
+        for (i=0; i<ndims; i++)
+        {
+            newCart->topo.cart->dims[i] = dims[i];
+            newCart->topo.cart->periodic[i] = periods[i];
+            nranks = nranks / dims[i];
+            /* FIXME: nranks could be zero (?) */
+            newCart->topo.cart->position[i] = rank / nranks;
+            rank = rank % nranks;
+        }
+
+        *comm_cart = smpi_comm_new(newGroup, newCart);
     }
     else {
-      *comm_cart = MPI_COMM_NULL;
+        if (rank == 0) {
+            newCart = smpi_cart_topo_create(ndims);
+            *comm_cart = smpi_comm_new(smpi_comm_group(MPI_COMM_SELF), newCart);
+        }
+        else {
+            *comm_cart = MPI_COMM_NULL;
+        }
     }
-  }
-  return retval;
+    return retval;
 }
 
 int smpi_mpi_cart_sub(MPI_Comm comm, const int remain_dims[], MPI_Comm *newcomm) {
-  MPI_Topology oldTopo = smpi_comm_topo(comm);
-  int oldNDims = oldTopo->ndims;
-  int i, j = 0, newNDims, *newDims = NULL, *newPeriodic = NULL;
+    MPI_Topology oldTopo = smpi_comm_topo(comm);
+    int oldNDims = oldTopo->topo.cart->ndims;
+    int i, j = 0, newNDims, *newDims = NULL, *newPeriodic = NULL;
   
-  if (remain_dims == NULL && oldNDims != 0) {
-    return MPI_ERR_ARG;
-  }
-  newNDims = 0;
-  for (i = 0 ; i < oldNDims ; i++) {
-    if (remain_dims[i]) newNDims++;
-  }
+    if (remain_dims == NULL && oldNDims != 0) {
+        return MPI_ERR_ARG;
+    }
+    newNDims = 0;
+    for (i = 0 ; i < oldNDims ; i++) {
+        if (remain_dims[i]) newNDims++;
+    }
   
-  if (newNDims > 0) {
-    newDims = malloc(newNDims * sizeof(*newDims));
-    newPeriodic = malloc(newNDims * sizeof(*newPeriodic));
-
-    // that should not segfault
-    for (i = 0 ; j < newNDims ; i++) {
-      if(remain_dims[i]) {
-        newDims[j] = oldTopo->dims[i];
-        newPeriodic[j] = oldTopo->periodic[i];
-        j++;
-      }
-    }
-  }
-  return smpi_mpi_cart_create(comm, newNDims, newDims, newPeriodic, 0, newcomm);
+    if (newNDims > 0) {
+        newDims = xbt_malloc(newNDims * sizeof(*newDims));
+        newPeriodic = xbt_malloc(newNDims * sizeof(*newPeriodic));
+
+        // that should not segfault
+        for (i = 0 ; j < newNDims ; i++) {
+            if(remain_dims[i]) {
+                newDims[j] = oldTopo->topo.cart->dims[i];
+                newPeriodic[j] = oldTopo->topo.cart->periodic[i];
+                j++;
+            }
+        }
+    }
+    return smpi_mpi_cart_create(comm, newNDims, newDims, newPeriodic, 0, newcomm);
 }
 
 
@@ -136,122 +198,126 @@ int smpi_mpi_cart_sub(MPI_Comm comm, const int remain_dims[], MPI_Comm *newcomm)
 
 int smpi_mpi_cart_coords(MPI_Comm comm, int rank, int maxdims,
                          int coords[]) {
-  int nnodes;
-  int i;
-  MPI_Topology topo = smpi_comm_topo(comm);
+    int nnodes;
+    int i;
+    MPI_Topology topo = smpi_comm_topo(comm);
   
-  nnodes = topo->nnodes;
-  for ( i=0; i < topo->ndims; i++ ) {
-    nnodes    = nnodes / topo->dims[i];
-    coords[i] = rank / nnodes;
-    rank      = rank % nnodes;
-  }
-  return MPI_SUCCESS;
+    nnodes = topo->topo.cart->nnodes;
+    for ( i=0; i < topo->topo.cart->ndims; i++ ) {
+        nnodes    = nnodes / topo->topo.cart->dims[i];
+        coords[i] = rank / nnodes;
+        rank      = rank % nnodes;
+    }
+    return MPI_SUCCESS;
 }
 
 int smpi_mpi_cart_get(MPI_Comm comm, int maxdims, int* dims, int* periods, int* coords) {
-  MPI_Topology topo = smpi_comm_topo(comm);
-  int i;
-  for(i = 0 ; i < maxdims ; i++) {
-    dims[i] = topo->dims[i];
-    periods[i] = topo->periodic[i];
-    coords[i] = topo->position[i];
-  }
-  return MPI_SUCCESS;
+    MPI_Topology topo = smpi_comm_topo(comm);
+    int i;
+    for(i = 0 ; i < maxdims ; i++) {
+        dims[i] = topo->topo.cart->dims[i];
+        periods[i] = topo->topo.cart->periodic[i];
+        coords[i] = topo->topo.cart->position[i];
+    }
+    return MPI_SUCCESS;
 }
 
 int smpi_mpi_cart_rank(MPI_Comm comm, int* coords, int* rank) {
-  MPI_Topology topo = smpi_comm_topo(comm);
-  int ndims = topo->ndims;
-  int multiplier, coord,i;
-  *rank = 0;
-  multiplier = 1;
-
-
-
-  for ( i=ndims-1; i >=0; i-- ) {
-    coord = coords[i];
-
-    /* Should we check first for args correction, then process,
-     * or check while we work (as it is currently done) ? */
-      if (coord >= topo->dims[i]) {
-        if ( topo->periodic[i] ) {
-        coord = coord % topo->dims[i];
-        }
-        else {
-          // Should I do that ?
-          *rank = -1; 
-          return MPI_ERR_ARG;
-        }
-      }
-      else if (coord <  0) {
-        if(topo->periodic[i]) {
-          coord = coord % topo->dims[i];
-          if (coord) coord = topo->dims[i] + coord;
+    MPI_Topology topo = smpi_comm_topo(comm);
+    int ndims = topo->topo.cart->ndims;
+    int multiplier, coord,i;
+    *rank = 0;
+    multiplier = 1;
+
+    for ( i=ndims-1; i >=0; i-- ) {
+        coord = coords[i];
+
+        /* The user can give us whatever coordinates he wants. If one of them is
+         * out of range, either this dimension is periodic, and then we
+         * consider the equivalent coordinate inside the bounds, or it is not
+         * and then it is an error
+         */
+        if (coord >= topo->topo.cart->dims[i]) {
+            if ( topo->topo.cart->periodic[i] ) {
+                coord = coord % topo->topo.cart->dims[i];
+            }
+            else {
+                // Should I do that ?
+                *rank = -1; 
+                return MPI_ERR_ARG;
+            }
         }
-        else {
-          *rank = -1;
-          return MPI_ERR_ARG;
+        else if (coord <  0) {
+            if(topo->topo.cart->periodic[i]) {
+                coord = coord % topo->topo.cart->dims[i];
+                if (coord) coord = topo->topo.cart->dims[i] + coord;
+            }
+            else {
+                *rank = -1;
+                return MPI_ERR_ARG;
+            }
         }
-      }
     
-      *rank += multiplier * coord;
-      multiplier *= topo->dims[i];
-  }
-  return MPI_SUCCESS;
+        *rank += multiplier * coord;
+        multiplier *= topo->topo.cart->dims[i];
+    }
+    return MPI_SUCCESS;
 }
 
 int smpi_mpi_cart_shift(MPI_Comm comm, int direction, int disp,
                         int *rank_source, int *rank_dest) {
-  MPI_Topology topo = smpi_comm_topo(comm);
-  int position[topo->ndims];
+    MPI_Topology topo = smpi_comm_topo(comm);
+    int position[topo->topo.cart->ndims];
 
 
-  if(topo->ndims == 0) {
-    return MPI_ERR_ARG;
-  }
-  if (topo->ndims < direction) {
-    return MPI_ERR_DIMS;
-  }
+    if(topo->topo.cart->ndims == 0) {
+        return MPI_ERR_ARG;
+    }
+    if (topo->topo.cart->ndims < direction) {
+        return MPI_ERR_DIMS;
+    }
 
-  smpi_mpi_cart_coords(comm, smpi_comm_rank(comm), topo->ndims, position);
-  position[direction] += disp;
+    smpi_mpi_cart_coords(comm, smpi_comm_rank(comm), topo->topo.cart->ndims,
+                         position);
+    position[direction] += disp;
 
-  if(position[direction] < 0 || position[direction] >= topo->dims[direction]) {
-    if(topo->periodic[direction]) {
-      position[direction] %= topo->dims[direction];
-      smpi_mpi_cart_rank(comm, position, rank_dest);
+    if(position[direction] < 0 ||
+       position[direction] >= topo->topo.cart->dims[direction]) {
+        if(topo->topo.cart->periodic[direction]) {
+            position[direction] %= topo->topo.cart->dims[direction];
+            smpi_mpi_cart_rank(comm, position, rank_dest);
+        }
+        else {
+            *rank_dest = MPI_PROC_NULL;
+        }
     }
     else {
-      *rank_dest = MPI_PROC_NULL;
+        smpi_mpi_cart_rank(comm, position, rank_dest);
     }
-  }
-  else {
-    smpi_mpi_cart_rank(comm, position, rank_dest);
-  }
 
-  position[direction] =  topo->position[direction] - disp;
-  if(position[direction] < 0 || position[direction] >= topo->dims[direction]) {
-    if(topo->periodic[direction]) {
-      position[direction] %= topo->dims[direction];
-      smpi_mpi_cart_rank(comm, position, rank_source);
+    position[direction] =  topo->topo.cart->position[direction] - disp;
+    if(position[direction] < 0 ||
+       position[direction] >= topo->topo.cart->dims[direction]) {
+        if(topo->topo.cart->periodic[direction]) {
+            position[direction] %= topo->topo.cart->dims[direction];
+            smpi_mpi_cart_rank(comm, position, rank_source);
+        }
+        else {
+            *rank_source = MPI_PROC_NULL;
+        }
     }
     else {
-      *rank_source = MPI_PROC_NULL;
+        smpi_mpi_cart_rank(comm, position, rank_source);
     }
-  }
-  else {
-    smpi_mpi_cart_rank(comm, position, rank_source);
-  }
 
-  return MPI_SUCCESS;
+    return MPI_SUCCESS;
 }
 
 int smpi_mpi_cartdim_get(MPI_Comm comm, int *ndims) {
-  MPI_Topology topo = smpi_comm_topo(comm);
+    MPI_Topology topo = smpi_comm_topo(comm);
 
-  *ndims = topo->ndims;
-  return MPI_SUCCESS;
+    *ndims = topo->topo.cart->ndims;
+    return MPI_SUCCESS;
 }
 
 
@@ -306,7 +372,7 @@ int smpi_mpi_dims_create(int nnodes, int ndims, int dims[])
         if (*p == 0) {
             ++freedims;
         } else if ((*p < 0) || ((nnodes % *p) != 0)) {
-          return  MPI_ERR_DIMS;
+            return  MPI_ERR_DIMS;
                  
         } else {
             freeprocs /= *p;
@@ -314,16 +380,16 @@ int smpi_mpi_dims_create(int nnodes, int ndims, int dims[])
     }
 
     if (freedims == 0) {
-       if (freeprocs == 1) {
-          return MPI_SUCCESS;
-       }
-       return MPI_ERR_DIMS;
+        if (freeprocs == 1) {
+            return MPI_SUCCESS;
+        }
+        return MPI_ERR_DIMS;
     }
 
     if (freeprocs == 1) {
         for (i = 0; i < ndims; ++i, ++dims) {
             if (*dims == 0) {
-               *dims = 1;
+                *dims = 1;
             }
         }
         return MPI_SUCCESS;
@@ -331,19 +397,19 @@ int smpi_mpi_dims_create(int nnodes, int ndims, int dims[])
 
     /* Factor the number of free processes */
     if (MPI_SUCCESS != (err = getfactors(freeprocs, &nfactors, &factors))) {
-      return  err;
+        return  err;
     }
 
     /* Assign free processes to free dimensions */
     if (MPI_SUCCESS != (err = assignnodes(freedims, nfactors, factors, &procs))) {
-      return err;
+        return err;
     }
 
     /* Return assignment results */
     p = procs;
     for (i = 0; i < ndims; ++i, ++dims) {
         if (*dims == 0) {
-           *dims = *p++;
+            *dims = *p++;
         }
     }
 
@@ -379,19 +445,19 @@ assignnodes(int ndim, int nfactor, int *pfacts, int **pdims)
     int *pmin;
           
     if (0 >= ndim) {
-       return MPI_ERR_DIMS;
+        return MPI_ERR_DIMS;
     }
 
     /* Allocate and initialize the bins */
     bins = (int *) malloc((unsigned) ndim * sizeof(int));
     if (NULL == bins) {
-       return MPI_ERR_NO_MEM;
+        return MPI_ERR_NO_MEM;
     }
     *pdims = bins;
 
     for (i = 0, p = bins; i < ndim; ++i, ++p) {
         *p = 1;
-     }
+    }
     
     /* Loop assigning factors from the highest to the lowest */
     for (j = nfactor - 1; j >= 0; --j) {
@@ -404,20 +470,20 @@ assignnodes(int ndim, int nfactor, int *pfacts, int **pdims)
             }
         }
         *pmin *= f;
-     }
+    }
     
-     /* Sort dimensions in decreasing order (O(n^2) for now) */
-     for (i = 0, pmin = bins; i < ndim - 1; ++i, ++pmin) {
-         for (j = i + 1, p = pmin + 1; j < ndim; ++j, ++p) {
-             if (*p > *pmin) {
+    /* Sort dimensions in decreasing order (O(n^2) for now) */
+    for (i = 0, pmin = bins; i < ndim - 1; ++i, ++pmin) {
+        for (j = i + 1, p = pmin + 1; j < ndim; ++j, ++p) {
+            if (*p > *pmin) {
                 n = *p;
                 *p = *pmin;
                 *pmin = n;
-             }
-         }
-     }
+            }
+        }
+    }
 
-     return MPI_SUCCESS;
+    return MPI_SUCCESS;
 }
 
 /*
@@ -453,7 +519,6 @@ getfactors(int num, int *nfactors, int **factors) {
         (*factors)[i++] = 2;
     }
     /* determine all occurences of uneven prime numbers up to sqrt(num) */
-    d = 3;
     for(d = 3; (num > 1) && (d < sqrtnum); d += 2) {
         while((num % d) == 0) {
             num /= d;