Chris@82: /*
Chris@82:  * Copyright (c) 2003, 2007-14 Matteo Frigo
Chris@82:  * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
Chris@82:  *
Chris@82:  * This program is free software; you can redistribute it and/or modify
Chris@82:  * it under the terms of the GNU General Public License as published by
Chris@82:  * the Free Software Foundation; either version 2 of the License, or
Chris@82:  * (at your option) any later version.
Chris@82:  *
Chris@82:  * This program is distributed in the hope that it will be useful,
Chris@82:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
Chris@82:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Chris@82:  * GNU General Public License for more details.
Chris@82:  *
Chris@82:  * You should have received a copy of the GNU General Public License
Chris@82:  * along with this program; if not, write to the Free Software
Chris@82:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
Chris@82:  *
Chris@82:  */
Chris@82: 
Chris@82: #include "ifftw-mpi.h"
Chris@82: 
Chris@82: INT XM(num_blocks)(INT n, INT block)
Chris@82: {
Chris@82:      return (n + block - 1) / block;
Chris@82: }
Chris@82: 
Chris@82: int XM(num_blocks_ok)(INT n, INT block, MPI_Comm comm)
Chris@82: {
Chris@82:      int n_pes;
Chris@82:      MPI_Comm_size(comm, &n_pes);
Chris@82:      return n_pes >= XM(num_blocks)(n, block);
Chris@82: }
Chris@82: 
Chris@82: /* Pick a default block size for dividing a problem of size n among
Chris@82:    n_pes processes.  Divide as equally as possible, while minimizing
Chris@82:    the maximum block size among the processes as well as the number of
Chris@82:    processes with nonzero blocks. */
Chris@82: INT XM(default_block)(INT n, int n_pes)
Chris@82: {
Chris@82:      return ((n + n_pes - 1) / n_pes);
Chris@82: }
Chris@82: 
Chris@82: /* For a given block size and dimension n, compute the block size 
Chris@82:    on the given process. */
Chris@82: INT XM(block)(INT n, INT block, int which_block)
Chris@82: {
Chris@82:      INT d = n - which_block * block;
Chris@82:      return d <= 0 ? 0 : (d > block ? block : d);
Chris@82: }
Chris@82: 
Chris@82: static INT num_blocks_kind(const ddim *dim, block_kind k)
Chris@82: {
Chris@82:      return XM(num_blocks)(dim->n, dim->b[k]);
Chris@82: }
Chris@82: 
Chris@82: INT XM(num_blocks_total)(const dtensor *sz, block_kind k)
Chris@82: {
Chris@82:      if (FINITE_RNK(sz->rnk)) {
Chris@82: 	  int i;
Chris@82: 	  INT ntot = 1;
Chris@82: 	  for (i = 0; i < sz->rnk; ++i)
Chris@82: 	       ntot *= num_blocks_kind(sz->dims + i, k);
Chris@82: 	  return ntot;
Chris@82:      }
Chris@82:      else
Chris@82: 	  return 0;
Chris@82: }
Chris@82: 
Chris@82: int XM(idle_process)(const dtensor *sz, block_kind k, int which_pe)
Chris@82: {
Chris@82:      return (which_pe >= XM(num_blocks_total)(sz, k));
Chris@82: }
Chris@82: 
Chris@82: /* Given a non-idle process which_pe, computes the coordinate
Chris@82:    vector coords[rnk] giving the coordinates of a block in the
Chris@82:    matrix of blocks.  k specifies whether we are talking about
Chris@82:    the input or output data distribution. */
Chris@82: void XM(block_coords)(const dtensor *sz, block_kind k, int which_pe, 
Chris@82: 		     INT *coords)
Chris@82: {
Chris@82:      int i;
Chris@82:      A(!XM(idle_process)(sz, k, which_pe) && FINITE_RNK(sz->rnk));
Chris@82:      for (i = sz->rnk - 1; i >= 0; --i) {
Chris@82: 	  INT nb = num_blocks_kind(sz->dims + i, k);
Chris@82: 	  coords[i] = which_pe % nb;
Chris@82: 	  which_pe /= nb;
Chris@82:      }
Chris@82: }
Chris@82: 
Chris@82: INT XM(total_block)(const dtensor *sz, block_kind k, int which_pe)
Chris@82: {
Chris@82:      if (XM(idle_process)(sz, k, which_pe))
Chris@82: 	  return 0;
Chris@82:      else {
Chris@82: 	  int i;
Chris@82: 	  INT N = 1, *coords;
Chris@82: 	  STACK_MALLOC(INT*, coords, sizeof(INT) * sz->rnk);
Chris@82: 	  XM(block_coords)(sz, k, which_pe, coords);
Chris@82: 	  for (i = 0; i < sz->rnk; ++i)
Chris@82: 	       N *= XM(block)(sz->dims[i].n, sz->dims[i].b[k], coords[i]);
Chris@82: 	  STACK_FREE(coords);
Chris@82: 	  return N;
Chris@82:      }
Chris@82: }
Chris@82: 
Chris@82: /* returns whether sz is local for dims >= dim */
Chris@82: int XM(is_local_after)(int dim, const dtensor *sz, block_kind k)
Chris@82: {
Chris@82:      if (FINITE_RNK(sz->rnk))
Chris@82: 	  for (; dim < sz->rnk; ++dim)
Chris@82: 	       if (XM(num_blocks)(sz->dims[dim].n, sz->dims[dim].b[k]) > 1)
Chris@82: 		    return 0;
Chris@82:      return 1;
Chris@82: }
Chris@82: 
Chris@82: int XM(is_local)(const dtensor *sz, block_kind k)
Chris@82: {
Chris@82:      return XM(is_local_after)(0, sz, k);
Chris@82: }
Chris@82: 
Chris@82: /* Return whether sz is distributed for k according to a simple
Chris@82:    1d block distribution in the first or second dimensions */
Chris@82: int XM(is_block1d)(const dtensor *sz, block_kind k)
Chris@82: {
Chris@82:      int i;
Chris@82:      if (!FINITE_RNK(sz->rnk)) return 0;
Chris@82:      for (i = 0; i < sz->rnk && num_blocks_kind(sz->dims + i, k) == 1; ++i) ;
Chris@82:      return(i < sz->rnk && i < 2 && XM(is_local_after)(i + 1, sz, k));
Chris@82: 
Chris@82: }