Envío de columnas de una matriz usando MPI_Scatter

Estoy tratando de escribir un programa de multiplicación de matrices y vectores usando MPI. Estoy tratando de enviar columnas de la matriz para separar procesos y calcular localmente el resultado. al final hago un MPI_Reduce utilizando MPI_SUM operación.

Enviar filas de una matriz es fácil ya que C almacena matrices en orden de fila principal, pero las columnas no lo son (si no las envía una por una). Leí la pregunta aquí:

MPI_Scatter: envío de columnas de matriz 2D

Jonathan Dursi sugirió usar nuevos tipos de datos MPI y esto es lo que hice al adaptar su código a mis propias necesidades:

  double matrix[10][10];
  double mytype[10][10];
  int part_size; // stores how many cols a process needs to work on
  MPI_Datatype col, coltype;
  // ...
  MPI_Type_vector(N, 1, N, MPI_DOUBLE, &col);
  MPI_Type_commit(&col);
  MPI_Type_create_resized(col, 0, 1*sizeof(double), &coltype);
  MPI_Type_commit(&coltype);
  // ...
  MPI_Scatter(matrix, part_size, coltype,
              mypart, part_size, coltype,
              0, MPI_COMM_WORLD);

  // calculations...
  MPI_Reduce(local_result, global_result,
             N, MPI_DOUBLE,
             MPI_SUM,
             0, MPI_COMM_WORLD);

Esto funciona perfectamente, pero no puedo decir que realmente entiendo cómo funciona.

1. Como es MPI_Type_vector almacenado en la memoria?
2. Cómo MPI_Type_create_resized() funciona y que hace exactamente?

Tenga en cuenta que soy un principiante total en MPI. Gracias por adelantado.

Hay una descripción larga de este problema en mi respuesta a esta pregunta: el hecho de que muchas personas tengan estas preguntas es una prueba de que no es obvio y que lleva un tiempo acostumbrarse a las ideas.

Lo importante que debe saber es qué diseño de memoria describe el tipo de datos MPI. La secuencia de llamadas a MPI_Type_vector es:

int MPI_Type_vector(int count,
                   int blocklength,
                   int stride, 
                   MPI_Datatype old_type,
                   MPI_Datatype *newtype_p)

Crea un nuevo tipo que describe un diseño de memoria donde cada stride elementos, hay un bloque de blocklength artículos retirados, y un total de count de estos bloques. Los artículos aquí están en unidades de cualquier old_type era. Entonces, por ejemplo, si llamó (nombrando los parámetros aquí, lo que en realidad no puede hacer en C, pero 🙂

 MPI_Type_vector(count=3, blocklength=2, stride=5, old_type=MPI_INT, &newtype);

Luego newtype describiría un diseño en la memoria como este:

   |<----->|  block length

   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   | X | X |   |   |   | X | X |   |   |   | X | X |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

   |<---- stride ----->|

   count = 3

donde cada cuadrado es un trozo de memoria de tamaño entero, presumiblemente 4 bytes. Tenga en cuenta que la zancada es la distancia en números enteros desde el comienzo de un bloque hasta el comienzo del siguiente, no la distancia entre bloques.

Ok, entonces en tu caso llamaste

  MPI_Type_vector(N, 1, N, MPI_DOUBLE, &col);

que tomará count = N bloques, cada uno de tamaño blocklength=1 MPI_DOUBLEs, con un espacio entre el inicio de cada bloque de stride=N MPI_DOUBLEs. En otras palabras, tomará cada N-ésimo doble, un total de N veces; perfecto para extraer una columna de una matriz NxN (almacenada contiguamente) de dobles. Una verificación útil es ver cuántos datos se están transfiriendo (count*stride = N*N cuál es el tamaño completo de la matriz, verifique) y cuántos datos se incluyen realmente (count*blocksize = Nque es el tamaño de una columna, verifique).

Si todo lo que tuviera que hacer fuera llamar a MPI_Send y MPI_Recv para intercambiar columnas individuales, habría terminado; podría usar este tipo para describir el diseño de la columna y estaría bien. Pero hay una cosa más.

Quieres llamar MPI_Scatter, que envía el primer tipo de columna (digamos) al procesador 0, el siguiente tipo de columna al procesador 1, etc. Si está haciendo eso con una matriz 1d simple, es fácil averiguar dónde está el “siguiente” tipo de datos; si está dispersando 1 int a cada procesador, el “siguiente” int comienza inmediatamente después de que finaliza el primer int.

Pero su nueva columna coltype tiene un total grado que va desde el inicio de la columna hasta N*N MPI_DOUBLEs más tarde, si MPI_Scatter sigue la misma lógica (lo hace), comenzaría a buscar la columna “siguiente” fuera de la memoria de matrices por completo, y así sucesivamente con el siguiente y el siguiente. No solo no obtendría la respuesta que deseaba, sino que el programa probablemente fallaría.

La forma de solucionar esto es decirle a MPI que el “tamaño” de este tipo de datos para calcular dónde se encuentra el “siguiente” es el tamaño en la memoria entre donde comienza una columna y comienza la siguiente columna; es decir, exactamente uno MPI_DOUBLE. Esto no afecta la cantidad de datos enviados, que sigue siendo 1 columna de datos; solo afecta el cálculo del “siguiente en la línea”. Con columnas (o filas) en una matriz, puede enviar este tamaño para que sea el tamaño de paso apropiado en la memoria, y MPI elegirá la siguiente columna correcta para enviar. Sin este operador de cambio de tamaño, su programa probablemente fallaría.

Cuando tiene diseños de datos más complicados, como en los bloques 2d de un ejemplo de matriz 2d vinculado anteriormente, entonces no hay un tamaño de paso único entre los elementos “siguientes”; todavía necesita hacer el truco de cambio de tamaño para que el tamaño sea una unidad útil, pero luego necesita usar MPI_Scatterv en lugar de dispersión para especificar explícitamente las ubicaciones desde las que enviar.