Enviando columnas de una matriz usando MPI_Scatter

Question

Estoy tratando de escribir un programa de multiplicación de matriz-vector usando MPI. Estoy intentando enviar columnas de la matriz para separar procesos y calcular el resultado localmente. Al final hago un MPI_Reduce usando la operación MPI_SUM.

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

MPI_Scatter - sending columns of 2D array

Jonathan Dursi sugirió el uso de nuevos tipos de datos MPI y esto es lo que he hecho, adaptando su código para 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. ¿Cómo se almacena MPI_Type_vector en la memoria?
2. ¿Cómo funciona MPI_Type_create_resized() y qué hace exactamente?

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

Answer 1

Hay una larga descripción de este problema en my answer a this question: el hecho de que muchas personas tengan estas preguntas es una prueba de que no es obvio y las ideas tardan en acostumbrarse.

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

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

Se crea un nuevo tipo que describe una disposición de memoria donde cada stride artículos, hay un bloque de blocklength artículos sacó, y un total de count de estos bloques. Los elementos aquí están en unidades de lo que sea old_type. Así, por ejemplo, si se llama a (nombrar los parámetros aquí, que no se puede hacer realidad en C, pero :)

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

Entonces newtype describiría una disposición en la memoria de esta manera:

|<----->| block length 

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

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

    count = 3 

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

Ok, por lo que en su caso se llama

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

que se llevará a count = N bloques, cada uno del tamaño de blocklength=1MPI_DOUBLE s, con un espacio entre el inicio de cada bloque de stride=NMPI_DOUBLE s. En otras palabras, tomará cada N'th doble, un total de N veces; perfecto para extraer una columna de una matriz NxN (almacenada contiguamente) de dobles. Una comprobación útil es ver la cantidad de datos que se están pasando por alto (count*stride = N*N que es el tamaño completo de la matriz, verificar) y la cantidad de datos que realmente se incluyen (count*blocksize = N, que es del tamaño de una columna, verificar.)

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

Quiere llamar al MPI_Scatter, que envía el primer tipo (por ejemplo) al procesador 0, el siguiente tipo al procesador 1, etc. Si lo hace con un simple conjunto de 1d, es fácil averiguar dónde El tipo de datos "siguiente" es; si está dispersando 1 int en cada procesador, la int "siguiente" comienza inmediatamente después de que finaliza la primera int.

Sin embargo, su nueva columna de coltype tiene un total extent que va desde el inicio de la columna para N*NMPI_DOUBLE s tarde - si MPI_Scatter sigue la misma lógica (lo hace), sería empezar a buscar la columna "siguiente" fuera de la memoria de matrices por completo, y así sucesivamente con la siguiente y siguiente. No solo no obtendría la respuesta que deseaba, probablemente el programa se bloquee.

La manera 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 el inicio de una columna y el inicio de la siguiente columna; es decir, exactamente uno MPI_DOUBLE. Esto no afecta la cantidad de datos enviados, que sigue siendo el valor de 1 columna de datos; solo afecta el cálculo "siguiente en 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 se bloquee.

Cuando tiene diseños de datos más complicados, como en los 2d-blocks de un ejemplo de 2d-array vinculado al anterior, entonces no hay un solo paso entre los "siguientes" elementos; usted todavía necesita hacer el truco de cambio de tamaño para hacer que el tamaño sea una unidad útil, pero luego necesita usar MPI_Scatterv en lugar de dispersar para especificar explícitamente las ubicaciones desde donde enviar.