Multiplicación Matríz-Vector
Chapter 8
Bosquejo
• El algoritmo secuencial
• El diseño, analisis, y la implantación de tres programas paralelos– Rowwise block striped– Columnwise block striped– Checkerboard block
• Matríces con mucho ceros (“sparse”)
Algoritmo Secuencial
6 -1 5 2
3 7 -2 1
2 6 6 7
5 -3 2 1
4
9
2
1
=
27
72
77
-1
=
Algoritmo Secuencail (cont)• Entrada: una matríz
mXn a[0..m-1,0..n-1] y un vector b[0..n-1]
• Salida: El producto a b = c[0..m-1]
• for i←0 to m-1 do c[i] ←0 for j←0 to n-1 do c[i] ← c[i] + a[i,j] endfor endfor
Complexidad:
O(mn)
Algoritmo I (Rowwise block striped matrix)
• Descomposición de dominio
• Una tarea primitive está asociada con
- una fila de la matríz y
- la vector entera
Un Paso del Algoritmo Paralelo
Fila i de A
b
Fila i of A
bci
Producto interior
Fila i de A
b c
Comunicación All-gather
Aglomeración y Asignación de Procesos
• Un número estático de tareas
• Un patron regular de comunicaciones (all-gather)
• El tiempo de computación por tarea es constante
• Estrategia:
– Aglomerar grupos de filas
Bloque Vectorial a Vector Replicado
• Se unen los bloques de cada proceso y se manda el resultado a cada proceso mediante Allgatherv
MPI_Allgatherv
MPI_Allgatherv
int MPI_Allgatherv ( void *send_buffer, int send_cnt, MPI_Datatype send_type, void *receive_buffer, int *receive_cnt, int *receive_disp, MPI_Datatype receive_type, MPI_Comm communicator)
Ejemplo de MPI_Allgatherv
Función create_mixed_xfer_arrays
• Una función para computar los argumentos • Primer arreglo
– La cantidad de elementos contribuidos por cada proceso
– Usa el macro BLOCK_SIZE
• Secundo arreglo– Primera posición del buffer donde recibe– Presumir que los buffers están en el orden de rango
Función replicate_block_vector
• Crear espacio para el vector entero
• Crear arreglos “mixed transfer”
• Hacer llamada a MPI_Allgatherv
Rowwise block striped matrix-vector multiplication
• /*
/* This program multiplies a matrix and a vector input from a separate files.
The result vector is printed to standard output Data distribution of matrix: rowwise block striped Data distribution of vector: replicated */ #include <stdio.h> #include <mpi.h> #include "../MyMPI.h" /* Change these two definitions when the matrix and vector
element types change */ typedef double dtype; #define mpitype MPI_DOUBLE
Matrix-vector multiplication(cont)
int main (int argc, char *argv[]) { dtype **a; /* First factor, a matrix */ dtype *b; /* Second factor, a vector */ dtype *c_block; /* Partial product vector */ dtype *c; /* Replicated product vector */ double max_seconds; double seconds; /* Elapsed time for matrix-vector multiply */ dtype *storage; /* Matrix elements stored here */ int i, j; /* Loop indices */ int id; /* Process ID number */ int m; /* Rows in matrix */ int n; /* Columns in matrix */ int nprime; /* Elements in vector */ int p; /* Number of processes */ int rows; /* Number of rows on this process */ int its;
Matrix-Vector Multiplication(cont)
MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &id); MPI_Comm_size (MPI_COMM_WORLD, &p);
read_row_striped_matrix (argv[1], (void *) &a, (void *) &storage, mpitype, &m, &n, MPI_COMM_WORLD); rows = BLOCK_SIZE(id,p,m); print_row_striped_matrix ((void **) a, mpitype, m, n, MPI_COMM_WORLD);
read_replicated_vector (argv[2], (void *) &b, mpitype, &nprime, MPI_COMM_WORLD); print_replicated_vector (b, mpitype, nprime, MPI_COMM_WORLD);
Matrix-Vector Multiplication (cont)
c_block = (dtype *) malloc (rows * sizeof(dtype)); c = (dtype *) malloc (n * sizeof(dtype)); MPI_Barrier (MPI_COMM_WORLD); seconds = - MPI_Wtime(); for (i = 0; i < rows; i++) { c_block[i] = 0.0; for (j = 0; j < n; j++) c_block[i] += a[i][j] * b[j]; }
replicate_block_vector (c_block, n, (void *) c, mpitype, MPI_COMM_WORLD); MPI_Barrier (MPI_COMM_WORLD); seconds += MPI_Wtime();
Matrix-Vector Multiplication(cont)
print_replicated_vector (c, mpitype, n, MPI_COMM_WORLD);
MPI_Allreduce (&seconds, &max_seconds, 1, mpitype, MPI_MAX, MPI_COMM_WORLD); if (!id) { printf ("MV1) N = %d, Processes = %d, Time = %12.6f sec,", n, p, max_seconds); printf ("Mflop = %6.2f\n", 2*n*n/(1000000.0*max_seconds)); } MPI_Finalize(); return 0;}
Analisis de Complexidad
• Complexidad del algoritmo secuencial: (n2)
• Complexidad computacional del algoritmo paralelo: (n2/p)
• Complexidad de comunicación de all-gather: (log p + n)
• Complexidad General: (n2/p + log p)
Analisis de Complexidad de All-gather
• Una manera eficiente para efectuar All-gather es llevar a cabo las comunicaciones en forma de un hipercubo.
• Un hipercubo es una red con 2n nodos numerados en binario tal que hay un arco entre dos nodos si y solo si los números binarios asociados difieren en exactamente una posición.
Complexidad de All-gather
• All-gather se puede efectuar en log p pasos mediante una red hipercubo de p=2n procesos. La demostración es por inducción en n:
• Si n=1, All-gather se puede efectuar haciendo un intercambio.
• Supongamos que All-gather se puede efectuar en n=log p pasos en un hipercubo de tamaño p=2n. Sea R un hipercubo con p=2n+1 procesos. Entonces R se puede particionar en dos hipercubos, cada uno de tamaño 2n y por la hipotesis de inducción All-gather se puede efectuar en cada una de estas subredes en n pasos. Luego, en un paso mas de intercambios, todo proceso contendrá todos los datos originales.
Complexidad de All-gather (cont)
Enviar un mensaje que contiene n datos requiere tiempo λ + n/β donde
• λ es latencia (el tiempo que se necesita para iniciar un mensaje) y
• β ancho de banda (el número de datos que se puede enviar por un canal en una unidad de tiempo)
Complexidad de All-gather (cont)
• La cantidad de datos que se intercambian se dobla en cada uno de los log p pasos
• El tiempo total para efectuar All-gather es
Σi (λ + 2i-1n/β ) donde i varia de 1 a log p. Pero
Σi (λ + 2i-1n/β ) = λ log p + (p-1)n/ β
Complexidad de Comunicaciones
En el algoritmo para multiplicar una matriz por un vector utilizando descomposición de filas, la cantidad de datos envueltos en All-gather es n/p .
La complexidad de comunicaciones en el algoritmo de es
(log p + n)
Multiplicación Matríz Vector
Descomposición Checkerboard
Diseño del Algoritmo
• Asociar una tarea primitiva con cada elemento de la matríz A
• Cada tarea primitive hace una multiplicación• Aglomerar tareas primitivas en bloques
rectangulares• Procesos constituyen una parrilla bidimensional• Distribuir el vector b en los procesos de la
primera columna de la parrilla
La Tareas después de la Aglomeración
Los Pasos del Algoritmo
Redistribuir el Vector b
• Paso 1: Mover b de la primera columna a la primera fila– Si p es es un cuadrado
• Procesos en la primera columna envian sus pedazos de b a procesos de la primera fila
– Si p no es un cuadrado• Acumula (“gather”) b en el proceso (0, 0)• El process (0,0) emite (“broadcasts” a los
procesos en la primera fila• Paso 2: Los procesos de la primera fila esparce b dentro
de las columnas
Comunicadores
• Queremos procesos en una parrilla virtual de dos dimensiones
• Necesitamos crear comunicadores para hacer esto
• Necesitamos hacer broadcasts y reduciones dentro de subconjuntos de procesos
Comunicadores
• Un comunicador consiste de
• un grupo de procesos
• un contexto
• una topología
Para Crear una Parrilla Vitual de Procesos
• MPI_Dims_create– parametros de entrada
• número de procesos en la parrilla deseada• número de dimensiones• Devuelve el número de procesos en cada dim
• MPI_Cart_create– Crea un comunicador con una topología
cartesiana
MPI_Dims_create
• int MPI_Dims_create(
int nodes, /*el número de procesos en
la parrilla*/
int dims, /* el número de dimensiones */
int *tamano/* el tamano de cada
dimension*/)
MPI_Cart_create
MPI_Cart_create( MPI_Comm com_viejo, int dims, int *size,/*un arreglo de tamano dims*/ int *periodico, /*un arreglo de tamano dims, periodico[j]=1 si se desea “wraparound” en la dimension j*/ int reordenar, /*0 si rango en el nuevo comunicador es lo mismo como en el viejo*/ MPI_Comm *com_cart)
Dos Funciones Relacionadas con Parrillas
• MPI_Cart_rank– Devuelve el rango del proceso, dada las
coordenadas del proceso en un comunicador cartesiano
• MPI_Cart_coords– Devuelve las coordenadas cartesianas de un
proceso, dado su rango.
MPI_Cart_rank
int MPI_Cart_rank (
MPI_Comm com,
int *coords,
int *rango)
MPI_Cart-coords
int MPI_Cart_coords (
MPI_Comm com,
/* In - Communicator */
int rango,
int dims,
int *coords)
Ejemplo#include <stdio.h>#include <mpi.h>int main (int argc, char **argv){ MPI_Comm com_cart; int id; int p; int size[2]; int periodo[2]; int coords[2]; MPI_Init (&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &p); size[0]=size[1]=0; MPI_Dims_create(p,2,size); MPI_Cart_create(MPI_COMM_WORLD,2,size,periodo,1,&com_cart); MPI_Comm_rank(com_cart,&id); MPI_Cart_coords(com_cart,id,2,coords); printf("id=%d, (%d,%d)\n",id,coords[0],coords[1]); return 0}
MPI_Comm_split
• MPI_Comm_split(MPI_Comm com_viejo, int particion,int orden_rango, MPI_Comm *com_nuevo)Particiona un comunicador existente
com_viejo en una o mas particiones. Se agrupan todos los procesos que tienen
el mismo número particion El rango en el nuevo comunicator se da por
orden_nuevo
Ejemplo
• En el ejemplo anterior, se puede hacer un comunicador de la primera columna de com_cart:
• MPI_Comm_split(com_cart,coords[1]==0, coords[0],&com_col)
Leer un vector b de un archivo y distribuirlo en com_col
• Hacer uso de read_block_vector en MyMPI.c
Analisis de Complexidad(presumiendo que m=n)
• Cada proceso hace su parte de la computación: (n2/p)
• Redistribuir b: (n / p + log p(n / p )) = (n log p / p)
• Reducción de los vectores de resultados parciales: (n log p / p)
• La complexidad paralela total: (n2/p + n log p / p)
Analisis de Isoeficiencia
• Complexidad Secuencial: (n2)
• Complexidad de comunicación:(n log p / p)
• La función de Isoeficiencia:n2 Cn p log p n C p log p
• M(n)=n2 M(C p log p)/p = C2 log2 p
Comparación de los tres Métodos
Algoritmo Complexidad Isoeficiencia
Rowwise Block-Striped
(n2/p + n+log p) C2 p
Columnwise Block-Striped
(n2/p + nlog p) C p
Checkerboard (n2/p + n log p/ p) C2 log2 p