Envío de columnas de una matriz usando MPI_Scatter

6 minutos de lectura

avatar de usuario
sombrero

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.

  • +1 por decir que es tarea. 🙂

    – resolver acertijos

    8 de septiembre de 2012 a las 3:54

  • @hattenn Por favor, no use el [homework] etiqueta por más tiempo. Está en desuso. ver la etiqueta en sí para confirmar esto

    – Andrés Barbero

    22 de noviembre de 2012 a las 1:42

avatar de usuario
Jonathan Dursi

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.

  • Esta es una de las respuestas más claras que he recibido en stackoverflow, muchas gracias. Todo está claro ahora. Votaría 100 veces si pudiera 🙂

    – sombrero

    28 mayo 2012 a las 18:05

  • El Centro de Cómputo Paralelo de Edimburgo nos proporcionó un ejemplo de dispersión 2d de una matriz que usaba el obsoleto MPI_Type_create_struct con MPI_UB pseudo type para establecer el límite superior para que sea igual al tamaño de un elemento de matriz (y dijeron que esto era un truco horrible). Me pregunto por qué no usaron MPI_Type_create_resized() en cambio, debería haberse implementado en Sun MPI alrededor de 2003.

    -Hristo Iliev

    28 mayo 2012 a las 18:18

  • Creo que a veces las personas que dan charlas actualizan sus diapositivas con mucha menos frecuencia que los desarrolladores actualizan su código; Sé que a veces he sido culpable de usar ejemplos algo desactualizados mucho más allá de su fecha de caducidad.

    – Jonathan Dursi

    28 mayo 2012 a las 18:23

  • Quiero decir que el curso se dio en 2003. Espero que lo hayan actualizado mientras tanto. Sin embargo, +1 por la explicación clara.

    -Hristo Iliev

    28 mayo 2012 a las 22:19


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad