enviar bloques de matriz 2D en C usando MPI

¿Cómo se envían bloques de matriz 2-D a diferentes procesadores? Supongamos que el tamaño de matriz 2D es 400×400 y quiero enviar bloques de tamaños 100X100 a diferentes procesadores. La idea es que cada procesador realice cálculos en su bloque separado y envíe su resultado al primer procesador para obtener el resultado final.
Estoy usando MPI en progtwigs C.

Permítanme comenzar diciendo que, en general, en realidad no desean hacer esto: dispersar y recostackr grandes cantidades de datos de algún proceso “maestro”. Normalmente, usted quiere que cada tarea se desarrolle en su propia pieza del rompecabezas, y debe apuntar a que nunca un procesador necesite una “vista global” de los datos completos; tan pronto como lo requiera, limita la escalabilidad y el tamaño del problema. Si está haciendo esto para E / S – un proceso lee los datos, luego los dispersa, luego los reúne para la escritura, querrá examinar eventualmente MPI-IO.

Sin embargo, para llegar a su pregunta, MPI tiene formas muy agradables de extraer datos arbitrarios de la memoria y distribuirlos entre un conjunto de procesadores. Lamentablemente, eso requiere una cantidad considerable de conceptos de MPI: tipos de MPI, extensiones y operaciones colectivas. Muchas de las ideas básicas se discuten en la respuesta a esta pregunta: MPI_Type_create_subarray y MPI_Gather .

Actualización : bajo la fría luz del día, esto es mucho código y no mucha explicación. Así que déjame expandir un poco.

Considere una matriz global entera 1d que la tarea 0 tiene que desea distribuir a una serie de tareas MPI, para que cada una obtenga una pieza en su matriz local. Supongamos que tiene 4 tareas y la matriz global es [01234567] . Puede hacer que la tarea 0 envíe cuatro mensajes (incluido uno para sí mismo) para distribuir esto, y cuando sea el momento de volver a armar, reciba cuatro mensajes para agruparlos de nuevo; pero eso obviamente consume mucho tiempo en una gran cantidad de procesos. Existen rutinas optimizadas para este tipo de operaciones: operaciones de dispersión / recostackción. Entonces en este caso 1d harías algo como esto:

 int global[8]; /* only task 0 has this */ int local[2]; /* everyone has this */ const int root = 0; /* the processor with the initial global data */ if (rank == root) { for (int i=0; i<7; i++) global[i] = i; } MPI_Scatter(global, 2, MPI_INT, /* send everyone 2 ints from global */ local, 2, MPI_INT, /* each proc receives 2 ints into local */ root, MPI_COMM_WORLD); /* sending process is root, all procs in */ /* MPI_COMM_WORLD participate */ 

Después de esto, los datos de los procesadores se verían como

 task 0: local:[01] global: [01234567] task 1: local:[23] global: [garbage-] task 2: local:[45] global: [garbage-] task 3: local:[67] global: [garbage-] 

Es decir, la operación de dispersión toma la matriz global y envía fragmentos 2-int contiguos a todos los procesadores.

Para volver a montar la matriz, utilizamos la operación MPI_Gather() , que funciona exactamente igual, pero a la inversa:

 for (int i=0; i<2; i++) local[i] = local[i] + rank; MPI_Gather(local, 2, MPI_INT, /* everyone sends 2 ints from local */ global, 2, MPI_INT, /* root receives 2 ints each proc into global */ root, MPI_COMM_WORLD); /* recv'ing process is root, all procs in */ /* MPI_COMM_WORLD participate */ 

y ahora los datos se ven como

 task 0: local:[01] global: [0134679a] task 1: local:[34] global: [garbage-] task 2: local:[67] global: [garbage-] task 3: local:[9a] global: [garbage-] 

Gather recupera todos los datos, y aquí a tiene 10 porque no creo que mi formateo sea lo suficientemente cuidadoso al comenzar este ejemplo.

¿Qué sucede si la cantidad de puntos de datos no divide el número de procesos de manera uniforme, y necesitamos enviar diferentes números de elementos a cada proceso? Entonces necesita una versión generalizada de scatter, MPI_Scatterv() , que le permite especificar los recuentos para cada procesador y los desplazamientos: en qué parte de la matriz global comienza ese dato. Entonces digamos que tienes una matriz de caracteres [abcdefghi] con 9 caracteres, e ibas a asignar a cada proceso dos caracteres, excepto el último, que obtuvieron tres. Entonces necesitarías

 char global[9]; /* only task 0 has this */ char local[3]={'-','-','-'}; /* everyone has this */ int mynum; /* how many items */ const int root = 0; /* the processor with the initial global data */ if (rank == 0) { for (int i=0; i<8; i++) global[i] = 'a'+i; } int counts[4] = {2,2,2,3}; /* how many pieces of data everyone has */ mynum = counts[rank]; int displs[4] = {0,2,4,6}; /* the starting point of everyone's data */ /* in the global array */ MPI_Scatterv(global, counts, displs, /* proc i gets counts[i] pts from displs[i] */ MPI_INT, local, mynum, MPI_INT; /* I'm receiving mynum MPI_INTs into local */ root, MPI_COMM_WORLD); 

Ahora los datos se ven como

 task 0: local:[ab-] global: [abcdefghi] task 1: local:[cd-] global: [garbage--] task 2: local:[ef-] global: [garbage--] task 3: local:[ghi] global: [garbage--] 

Ahora ha usado scatterv para distribuir cantidades irregulares de datos. El desplazamiento en cada caso es dos * rango (medido en caracteres, el desplazamiento es en unidad de los tipos que se envían para una dispersión o recibido para un conjunto, no es generalmente en bytes o algo) desde el inicio de la matriz, y el los recuentos son {2,2,2,3}. Si hubiera sido el primer procesador que queríamos tener 3 caracteres, habríamos configurado conteos = {3,2,2,2} y los desplazamientos habrían sido {0,3,5,7}. Gatherv vuelve a funcionar exactamente igual pero al revés; los conjuntos de conteos y displs seguirían siendo los mismos.

Ahora, para 2D, esto es un poco más complicado. Si queremos enviar 2d sublockings de una matriz 2d, los datos que estamos enviando ahora ya no son contiguos. Si estamos enviando (digamos) subbloques de 3x3 de una matriz de 6x6 a 4 procesadores, los datos que estamos enviando tienen agujeros en ella:

 2D Array --------- |000|111| |000|111| |000|111| |---+---| |222|333| |222|333| |222|333| --------- Actual layout in memory [000111000111000111222333222333222333] 

(Tenga en cuenta que toda la informática de alto rendimiento se reduce a la comprensión del diseño de los datos en la memoria).

Si queremos enviar los datos marcados como "1" a la tarea 1, debemos omitir tres valores, enviar tres valores, omitir tres valores, enviar tres valores, omitir tres valores y enviar tres valores. Una segunda complicación es cuando las subregiones se detienen y comienzan; tenga en cuenta que la región "1" no comienza donde la región "0" se detiene; después del último elemento de la región "0", la siguiente ubicación en la memoria está a medio camino a través de la región "1".

Primero abordemos el primer problema de diseño: cómo extraer solo los datos que queremos enviar. Siempre podríamos simplemente copiar todos los datos de región "0" en otra matriz contigua y enviar eso; si lo planificamos con cuidado, incluso podríamos hacerlo de tal manera que podamos llamar a MPI_Scatter sobre los resultados. Pero preferimos no tener que transponer toda nuestra estructura de datos principal de esa manera.

Hasta ahora, todos los tipos de datos MPI que hemos utilizado son simples: MPI_INT especifica (digamos) 4 bytes en una fila. Sin embargo, MPI le permite crear sus propios tipos de datos que describen diseños de datos arbitrariamente complejos en la memoria. Y este caso, subregiones rectangulares de una matriz, es lo suficientemente común como para que haya una llamada específica para eso. Para el caso bidimensional que describimos arriba,

  MPI_Datatype newtype; int sizes[2] = {6,6}; /* size of global array */ int subsizes[2] = {3,3}; /* size of sub-region */ int starts[2] = {0,0}; /* let's say we're looking at region "0", which begins at index [0,0] */ MPI_Type_create_subarray(2, sizes, subsizes, starts, MPI_ORDER_C, MPI_INT, &newtype); MPI_Type_commit(&newtype); 

Esto crea un tipo que selecciona solo la región "0" de la matriz global; podríamos enviar solo esa información a otro procesador

  MPI_Send(&(global[0][0]), 1, newtype, dest, tag, MPI_COMM_WORLD); /* region "0" */ 

y el proceso de recepción podría recibirlo en una matriz local. Tenga en cuenta que el proceso de recepción, si solo lo está recibiendo en una matriz de 3x3, no puede describir lo que está recibiendo como un tipo de newtype tipo; que ya no describe el diseño de la memoria. En cambio, solo está recibiendo un bloque de 3 * 3 = 9 enteros:

  MPI_Recv(&(local[0][0]), 3*3, MPI_INT, 0, tag, MPI_COMM_WORLD); 

Tenga en cuenta que también podríamos hacer esto para otras subregiones, ya sea creando un tipo diferente (con una matriz de start diferente) para los otros bloques, o simplemente enviando en el punto de inicio de un bloque en particular:

  MPI_Send(&(global[0][3]), 1, newtype, dest, tag, MPI_COMM_WORLD); /* region "1" */ MPI_Send(&(global[3][0]), 1, newtype, dest, tag, MPI_COMM_WORLD); /* region "2" */ MPI_Send(&(global[3][3]), 1, newtype, dest, tag, MPI_COMM_WORLD); /* region "3" */ 

Finalmente, tenga en cuenta que aquí y aquí necesitamos trozos de memoria contiguos y globales; es decir, &(global[0][0]) y &(local[0][0]) (o, de forma equivalente, *global y *local punto a contiguo 6 * 6 y 3 * 3 fragmentos de memoria; No está garantizado por la forma habitual de asignar matrices multidireccionales dinámicas. Se muestra cómo hacerlo a continuación.

Ahora que entendemos cómo especificar subregiones, solo hay una cosa más para discutir antes de usar las operaciones de dispersión / recostackción, y ese es el "tamaño" de estos tipos. No podemos simplemente usar MPI_Scatter() (o incluso scatterv) con estos tipos todavía, porque estos tipos tienen una extensión de 16 enteros; es decir, donde terminan 16 enteros después de que comienzan, y donde terminan no se alinean muy bien con el lugar donde comienza el siguiente bloque, por lo que no podemos usar scatter, elegiría el lugar equivocado para comenzar a enviar datos. al próximo procesador

Por supuesto, podríamos usar MPI_Scatterv() y especificar los desplazamientos nosotros mismos, y eso es lo que haremos, excepto que los desplazamientos están en unidades del tamaño del tipo de envío, y eso tampoco nos ayuda; los bloques comienzan en desplazamientos de (0,3,18,21) enteros desde el inicio de la matriz global, y el hecho de que un bloque finalice 16 enteros desde donde comienza no nos permite express esos desplazamientos en múltiplos enteros en absoluto .

Para hacer frente a esto, MPI le permite establecer la extensión del tipo para los propósitos de estos cálculos. No trunca el tipo; simplemente se usa para determinar dónde comienza el próximo elemento dado el último elemento. Para tipos como estos con agujeros en ellos, con frecuencia es conveniente establecer la extensión para que sea algo más pequeña que la distancia en la memoria al final real del tipo.

Podemos establecer el scope de cualquier cosa que sea conveniente para nosotros. Podríamos simplemente hacer el entero de extensión 1, y luego establecer los desplazamientos en unidades de enteros. En este caso, sin embargo, me gusta establecer la extensión de 3 enteros, el tamaño de una sub-fila, de esa manera, el bloque "1" comienza inmediatamente después del bloque "0", y el bloque "3" comienza inmediatamente después del bloque " 2 ". Desafortunadamente, no funciona tan bien cuando se salta del bloque "2" al bloque "3", pero eso no se puede evitar.

Entonces, para dispersar los subbloques en este caso, haríamos lo siguiente:

  MPI_Datatype type, resizedtype; int sizes[2] = {6,6}; /* size of global array */ int subsizes[2] = {3,3}; /* size of sub-region */ int starts[2] = {0,0}; /* let's say we're looking at region "0", which begins at index [0,0] */ /* as before */ MPI_Type_create_subarray(2, sizes, subsizes, starts, MPI_ORDER_C, MPI_INT, &type); /* change the extent of the type */ MPI_Type_create_resized(type, 0, 3*sizeof(int), &resizedtype); MPI_Type_commit(&resizedtype); 

Aquí hemos creado el mismo tipo de bloque que antes, pero lo hemos redimensionado; no hemos cambiado donde el tipo "comienza" (el 0) pero hemos cambiado donde "termina" (3 ints). No mencionamos esto antes, pero se requiere MPI_Type_commit para poder usar el tipo; pero solo necesita asignar el tipo final que realmente usa, no ningún paso intermedio. Utiliza MPI_Type_free para liberar el tipo cuando haya terminado.

Así que ahora, finalmente, podemos dispersar los bloques: las manipulaciones de datos anteriores son un poco complicadas, pero una vez hecho, el scatterv se ve igual que antes:

 int counts[4] = {1,1,1,1}; /* how many pieces of data everyone has, in units of blocks */ int displs[4] = {0,1,6,7}; /* the starting point of everyone's data */ /* in the global array, in block extents */ MPI_Scatterv(global, counts, displs, /* proc i gets counts[i] types from displs[i] */ resizedtype, local, 3*3, MPI_INT; /* I'm receiving 3*3 MPI_INTs into local */ root, MPI_COMM_WORLD); 

Y ahora hemos terminado, después de un pequeño recorrido por scatter, gather y tipos derivados de MPI.

A continuación, se incluye un código de ejemplo que muestra tanto la operación de recostackción como la de dispersión, con matrices de caracteres. Ejecutando el progtwig:

 $ mpirun -n 4 ./gathervarray Global array is: 0123456789 3456789012 6789012345 9012345678 2345678901 5678901234 8901234567 1234567890 4567890123 7890123456 Local process on rank 0 is: |01234| |34567| |67890| |90123| |23456| Local process on rank 1 is: |56789| |89012| |12345| |45678| |78901| Local process on rank 2 is: |56789| |89012| |12345| |45678| |78901| Local process on rank 3 is: |01234| |34567| |67890| |90123| |23456| Processed grid: AAAAABBBBB AAAAABBBBB AAAAABBBBB AAAAABBBBB AAAAABBBBB CCCCCDDDDD CCCCCDDDDD CCCCCDDDDD CCCCCDDDDD CCCCCDDDDD 

y el código sigue.

 #include  #include  #include  #include "mpi.h" int malloc2dchar(char ***array, int n, int m) { /* allocate the n*m contiguous items */ char *p = (char *)malloc(n*m*sizeof(char)); if (!p) return -1; /* allocate the row pointers into the memory */ (*array) = (char **)malloc(n*sizeof(char*)); if (!(*array)) { free(p); return -1; } /* set up the pointers into the contiguous memory */ for (int i=0; i 

Me pareció más fácil comprobarlo de esa manera.

 #include  #include  #include  #include "mpi.h" /* This is a version with integers, rather than char arrays, presented in this very good answer: http://stackoverflow.com/a/9271753/2411320 It will initialize the 2D array, scatter it, increase every value by 1 and then gather it back. */ int malloc2D(int ***array, int n, int m) { int i; /* allocate the n*m contiguous items */ int *p = malloc(n*m*sizeof(int)); if (!p) return -1; /* allocate the row pointers into the memory */ (*array) = malloc(n*sizeof(int*)); if (!(*array)) { free(p); return -1; } /* set up the pointers into the contiguous memory */ for (i=0; i 

Salida:

 linux16:>mpicc -o main main.c linux16:>mpiexec -n 4 main Global array is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Local process on rank 0 is: | 1 2 | | 5 6 | Local process on rank 1 is: | 3 4 | | 7 8 | Local process on rank 2 is: | 9 10 | |13 14 | Local process on rank 3 is: |11 12 | |15 16 | Processed grid: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17