ompi/mpi/c/dims

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
MPI_Dims_create
assignnodes
getfactors
   1 /*
   2  * Copyright (c) 2004-2007 The Trustees of Indiana University and Indiana
   3  *                         University Research and Technology
   4  *                         Corporation.  All rights reserved.
   5  * Copyright (c) 2004-2005 The University of Tennessee and The University
   6  *                         of Tennessee Research Foundation.  All rights
   7  *                         reserved.
   8  * Copyright (c) 2004-2014 High Performance Computing Center Stuttgart,
   9  *                         University of Stuttgart.  All rights reserved.
  10  * Copyright (c) 2004-2005 The Regents of the University of California.
  11  *                         All rights reserved.
  12  * Copyright (c) 2012      Los Alamos National Security, LLC.  All rights
  13  *                         reserved.
  14  * Copyright (c) 2014      Intel, Inc. All rights reserved
  15  * Copyright (c) 2015 Cisco Systems, Inc.  All rights reserved.
  16  * Copyright (c) 2015-2016 Research Organization for Information Science
  17  *                         and Technology (RIST). All rights reserved.
  18  * $COPYRIGHT$
  19  *
  20  * Additional copyrights may follow
  21  *
  22  * $HEADER$
  23  */
  24 
  25 #include "ompi_config.h"
  26 
  27 #include <math.h>
  28 
  29 #include "ompi/mpi/c/bindings.h"
  30 #include "ompi/runtime/params.h"
  31 #include "ompi/communicator/communicator.h"
  32 #include "ompi/errhandler/errhandler.h"
  33 
  34 #if OMPI_BUILD_MPI_PROFILING
  35 #if OPAL_HAVE_WEAK_SYMBOLS
  36 #pragma weak MPI_Dims_create = PMPI_Dims_create
  37 #endif
  38 #define MPI_Dims_create PMPI_Dims_create
  39 #endif
  40 
  41 static const char FUNC_NAME[] = "MPI_Dims_create";
  42 
  43 /* static functions */
  44 static int assignnodes(int ndim, int nfactor, int *pfacts,int **pdims);
  45 static int getfactors(int num, int *nfators, int **factors);
  46 
  47 
  48 /*
  49  * This is a utility function, no need to have anything in the lower
  50  * layer for this at all
  51  */
  52 int MPI_Dims_create(int nnodes, int ndims, int dims[])
  53 {
  54     int i;
  55     int freeprocs;
  56     int freedims;
  57     int nfactors;
  58     int *factors;
  59     int *procs;
  60     int *p;
  61     int err;
  62 
  63     OPAL_CR_NOOP_PROGRESS();
  64 
  65     if (MPI_PARAM_CHECK) {
  66         OMPI_ERR_INIT_FINALIZE(FUNC_NAME);
  67 
  68         if (0 > ndims) {
  69             return OMPI_ERRHANDLER_INVOKE (MPI_COMM_WORLD,
  70                                            MPI_ERR_DIMS, FUNC_NAME);
  71         }
  72 
  73         if ((0 != ndims) && (NULL == dims)) {
  74             return OMPI_ERRHANDLER_INVOKE (MPI_COMM_WORLD,
  75                                            MPI_ERR_ARG, FUNC_NAME);
  76         }
  77 
  78         if (1 > nnodes) {
  79             return OMPI_ERRHANDLER_INVOKE (MPI_COMM_WORLD,
  80                                            MPI_ERR_DIMS, FUNC_NAME);
  81         }
  82     }
  83 
  84     /* Get # of free-to-be-assigned processes and # of free dimensions */
  85     freeprocs = nnodes;
  86     freedims = 0;
  87     for (i = 0, p = dims; i < ndims; ++i,++p) {
  88         if (*p == 0) {
  89             ++freedims;
  90         } else if ((*p < 0) || ((nnodes % *p) != 0)) {
  91             return OMPI_ERRHANDLER_INVOKE (MPI_COMM_WORLD, MPI_ERR_DIMS,
  92                                            FUNC_NAME);
  93         } else {
  94             freeprocs /= *p;
  95         }
  96     }
  97 
  98     if (freedims == 0) {
  99        if (freeprocs == 1) {
 100           return MPI_SUCCESS;
 101        }
 102        return OMPI_ERRHANDLER_INVOKE(MPI_COMM_WORLD, MPI_ERR_DIMS,
 103                                      FUNC_NAME);
 104     }
 105 
 106     if (freeprocs == 1) {
 107         for (i = 0; i < ndims; ++i, ++dims) {
 108             if (*dims == 0) {
 109                *dims = 1;
 110             }
 111         }
 112         return MPI_SUCCESS;
 113     }
 114 
 115     /* Factor the number of free processes */
 116     if (MPI_SUCCESS != (err = getfactors(freeprocs, &nfactors, &factors))) {
 117        return OMPI_ERRHANDLER_INVOKE(MPI_COMM_WORLD, err,
 118                                      FUNC_NAME);
 119     }
 120 
 121     /* Assign free processes to free dimensions */
 122     if (MPI_SUCCESS != (err = assignnodes(freedims, nfactors, factors, &procs))) {
 123        free(factors);
 124        return OMPI_ERRHANDLER_INVOKE(MPI_COMM_WORLD, err,
 125                                      FUNC_NAME);
 126     }
 127 
 128     /* Return assignment results */
 129     p = procs;
 130     for (i = 0; i < ndims; ++i, ++dims) {
 131         if (*dims == 0) {
 132            *dims = *p++;
 133         }
 134     }
 135 
 136     free((char *) factors);
 137     free((char *) procs);
 138 
 139     /* all done */
 140     return MPI_SUCCESS;
 141 }
 142 
 143 /*
 144  *  assignnodes
 145  *
 146  *  Function:   - assign processes to dimensions
 147  *          - get "best-balanced" grid
 148  *          - greedy bin-packing algorithm used
 149  *          - sort dimensions in decreasing order
 150  *          - dimensions array dynamically allocated
 151  *  Accepts:    - # of dimensions
 152  *          - # of prime factors
 153  *          - array of prime factors
 154  *          - ptr to array of dimensions (returned value)
 155  *  Returns:    - 0 or ERROR
 156  */
 157 static int
 158 assignnodes(int ndim, int nfactor, int *pfacts, int **pdims)
 159 {
 160     int *bins;
 161     int i, j;
 162     int n;
 163     int f;
 164     int *p;
 165     int *pmin;
 166 
 167     if (0 >= ndim) {
 168        return MPI_ERR_DIMS;
 169     }
 170 
 171     /* Allocate and initialize the bins */
 172     bins = (int *) malloc((unsigned) ndim * sizeof(int));
 173     if (NULL == bins) {
 174        return MPI_ERR_NO_MEM;
 175     }
 176     *pdims = bins;
 177 
 178     for (i = 0, p = bins; i < ndim; ++i, ++p) {
 179         *p = 1;
 180      }
 181 
 182     /* Loop assigning factors from the highest to the lowest */
 183     for (j = nfactor - 1; j >= 0; --j) {
 184         f = pfacts[j];
 185         /* Assign a factor to the smallest bin */
 186         pmin = bins;
 187         for (i = 1, p = pmin + 1; i < ndim; ++i, ++p) {
 188             if (*p < *pmin) {
 189                 pmin = p;
 190             }
 191         }
 192         *pmin *= f;
 193      }
 194 
 195      /* Sort dimensions in decreasing order (O(n^2) for now) */
 196      for (i = 0, pmin = bins; i < ndim - 1; ++i, ++pmin) {
 197          for (j = i + 1, p = pmin + 1; j < ndim; ++j, ++p) {
 198              if (*p > *pmin) {
 199                 n = *p;
 200                 *p = *pmin;
 201                 *pmin = n;
 202              }
 203          }
 204      }
 205 
 206      return MPI_SUCCESS;
 207 }
 208 
 209 /*
 210  *  getfactors
 211  *
 212  *  Function:   - factorize a number
 213  *  Accepts:    - number
 214  *          - # prime factors
 215  *          - array of prime factors
 216  *  Returns:    - MPI_SUCCESS or ERROR
 217  */
 218 static int
 219 getfactors(int num, int *nfactors, int **factors) {
 220     int size;
 221     int d;
 222     int i;
 223     int sqrtnum;
 224 
 225     if(num  < 2) {
 226         (*nfactors) = 0;
 227         (*factors) = NULL;
 228         return MPI_SUCCESS;
 229     }
 230     /* Allocate the array of prime factors which cannot exceed log_2(num) entries */
 231     sqrtnum = ceil(sqrt(num));
 232     size = ceil(log(num) / log(2));
 233     *factors = (int *) malloc((unsigned) size * sizeof(int));
 234 
 235     i = 0;
 236     /* determine all occurences of factor 2 */
 237     while((num % 2) == 0) {
 238         num /= 2;
 239         (*factors)[i++] = 2;
 240     }
 241     /* determine all occurences of uneven prime numbers up to sqrt(num) */
 242     d = 3;
 243     for(d = 3; (num > 1) && (d < sqrtnum); d += 2) {
 244         while((num % d) == 0) {
 245             num /= d;
 246             (*factors)[i++] = d;
 247         }
 248     }
 249     /* as we looped only up to sqrt(num) one factor > sqrt(num) may be left over */
 250     if(num != 1) {
 251         (*factors)[i++] = num;
 252     }
 253     (*nfactors) = i;
 254     return MPI_SUCCESS;
 255 }
/* [<][>][^][v][top][bottom][index][help] */
root/ompi/mpi/c/dims_create.c

DEFINITIONS
