Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Algoritmos paralelos para la Multiplicacin de Matrices
Gins David Guerrero Hernndez
Universidad de Murcia - UM
18 de diciembre de 2008
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
ndice
1
3 4 5
Introduccin Importancia Consideraciones Caractersticas Secuencial Paralelizar Tipos Secuencial Bloques Cannon Fox DNS Conclusiones Trabajo Bibliografa
Gins David Guerrero Hernndez Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Importancia Consideraciones Caractersticas Secuencial
Importancia de la Multiplicacin de Matrices (MM)
Aparece en un gran nmero de algoritmos en el lgebra lineal (sistemas de ecuaciones, calculo de estructuras, determinantes...). Las ideas de optimizacin pueden ser usadas para otros problemas. Los algoritmos de la MM son los ms estudiados en la computacin de altas prestaciones. Se utiliza como benchmark de bajo nivel.
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Importancia Consideraciones Caractersticas Secuencial
Consideraciones iniciales a tener en cuenta
Por simplicidad, todo el tiempo trabajaremos con matrices cuadradas de tamao n x n. Consideramos que el nmero de procesadores de los que disponen las msquinas paralelas es p . Las matrices a multiplicar sern A y B , ambas tratadas como matrices densas (con pocos 0s), el resultado lo almacenaremos en la matriz C . Tp se corresponde con el tiempo que emplean p para resolver el problema. En el coste de las comunicaciones el tiempo para transmitir n datos entre dos procesadores conectados es dada por ts + ntw donde ts el el tiempo empleado para establecer la comunicacin y tw es el tiempo que tarda para transmitir un dato.
Gins David Guerrero Hernndez Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Importancia Consideraciones Caractersticas Secuencial
Caractersticas de la MM
Hay diversas caractersticas por las que la MM es apropiada para mquinas paralelas: Cada elemento que se calcula de la matriz resultado C (C(i ,j ) ) es independiente de todos los dems elementos. Siguen el modelo SPMD (Single Progam - Multiple Data).
La cantidad y el tipo de operaciones a realizar es independiente de los datos mismos. Regularidad de la organizacin de los datos y de las operaciones que se realizan sobre los datos.
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Importancia Consideraciones Caractersticas Secuencial
Algoritmo secuencial
Bsicamente est formado por tres bucles for. Cdigo for (i = 0; i < n; i++) { for (j = 0; i < n; j++) { C[i][j] = 0; for (k = 0; k < n; k++) { C[i][j] += A[i][k] * B[k][j] } } } O (n3 ).
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Tipos de Algoritmos Paralelos
Segn en el tipo de mquinas donde vaya a ser ejecutado podemos encontrar: Algoritmos Paralelos para Multiprocesadores.
Simple basado en el secuencial. Divide y Vencers recursivo. Paralelizacin del mtodo de Strassen.
Algoritmos Paralelos para Multicomputadores.
Simple basado en el secuencial. Con particionamiento en bloques. Cannon. Fox. DNS.
Los algoritmos nuevos que se presentan son los pertenecientes al segundo bloque, por lo que centraremos nuestro estudio en estos.
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Algoritmo simple basado en el secuencial
Podemos basarnos en el cdigo secuencial. Es fcilmente paralelizable. Cada procesador tendr en memoria un conjunto de las de la matriz A y la matriz B por completo. El uso de memoria es muy ineciente.
P1 P1 P2 P2 P1 P1 P2 P2 P1 P1 P2 P2 P1 P1 P2 P2 P1 P1 P1 P2 P2 P1 P1 P2 P2 P1 P1 P2 P2
P1 P2
P1 P2 P2
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Divisin en Bloques I
Estamos ante una topologa lgica en malla de dos dimensiones, donde p(i ,j ) el procesador de la la i y columna j y que la matrices estn dividas en bloques. Las matrices sern dividas en bloques de tamao
n p
n p.
Cada procesador calcular un bloque de C . Cada procesador tendr p submatrices correspondientes a la la de bloques de la matriz A y otras tantas correspondientes a la columna de bloques de la matriz B para as poder calcular un bloque de C . El uso de memoria, aunque mejor que el algoritmo anterior, sigue siendo ineciente.
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Divisin en Bloques II
Los pasos que sigue el algoritmo son:
1 2
Inicialmente cada procesador tiene los bloques A(i ,j ) y B(i ,j ) El procesador que est situado en la la (i , j ) enva su bloque de A a todos los elementos de la la i de la malla, y el bloque de B a todos los elementos de la columna j . Finalmente se realiza la multiplicacin con los bloques de la la de bloques i de A y los bloques de la columna j de B , para as obtener el bloque C(i ,j ) .
n3 p n + log pts + 2 p tw
P1 P2 P3 P2 P3 P1 P3 P2 P4 P4 P1 P2 2
Tp =
P1 P2 P3 P4 P1
P3
P4
P4
A
Gins David Guerrero Hernndez
C
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Algoritmo de Cannon I
Es una versin del anterior algoritmo que hace un uso ms eciente de la memoria. Nuevamente estamos ante una topologa lgica de malla de 2 dimensiones. Se basa en ir desplazando bloques de la matriz A hacia el procesador de la izquierda y los de la matriz B hacia el de arriba. En cada paso un procesador slo tiene un bloque de A y otro de B en memoria.
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Algoritmo de Cannon II
1 2
El procesador p(i ,j ) tiene los bloques A(i ,j ) y B(i ,j ) . El bloque correspondiente a la la i-sima de A se enva cclicamente al procesador que est i las a la izquierda en la malla, y la columna j-sima de B se enva cclicamente j columnas hacia arriba. As pues el bloque A(i ,j ) ser enviado al procesador (i , (j + i )mod p ). Cada procesador multiplica su par de bloques.
Repetir
4
p 1 veces:
De igual modo que en el punto 2, cada bloque de A se enva al procesador que se encuentra a la izquierda en la malla, y cada bloque de B al de arriba. Cada procesador multiplica su nuevo par de bloques, y suma el resultado al anterior.
n3 p
Tp =
n2 + 2 pts + 2 p tw
Algoritmos paralelos para la Multiplicacin de Matrices
Gins David Guerrero Hernndez
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Ejemplo I
3 2 3 2 1 2 0 4 1 2 0 4 2 2 1 4 8 8 12 10 8 21 12
1 3
17 11
A
Paso 1
3 2 3 2 1 2 0 4 1 2 1 3 0 4 2 2 1 4
B
Paso 2
3 1 1 2 4 3 0 2 2
2 1 3
4 2 0
4 2 1
B
Paso 3
3 1 1 2 4 3 0 2 2 2 1 3 4 2 0 4 2 1
6 1 3
8 8 0
0 4 2
A
Gins David Guerrero Hernndez
C
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Ejemplo II
Paso 4
2 4 3 0 2 2 3 1 1 1 3 2 2 0 4 2 1 4 6 1 3 8 8 0 0 4 2
B
Paso 5
2 4 3
0 2 2
3 1 1
1 3 2
2 0 4
2 1 4
8 13 9
8 6 8
6 5 6
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Ejemplo III
Paso 4
0 2 2 3 1 1 2 4 3 3 2 1 0 4 2 1 4 2 8 13 9 8 8 8 6 5 6
B
Paso 5
0 2 2
3 1 1
2 4 3
3 2 1
0 4 2
1 4 2
8 17 11
8 12 10
8 21 12
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Algoritmo de Fox
En este algoritmo mantiene la losofa del algoritmo anterior. El algoritmo consiste en los siguientes pasos:
1
El procesador p(i ,j ) tiene los bloques A(i ,j ) y B(i ,j ) .
Repetir
2
p:
La la i-sima de la malla de procesadores recibe el bloque A(i ,(i +j )mod p ) en la j-sima iteracin. Multiplicar el bloque recibido de A por el bloque residente de B. Enviar el bloque de B al procesador directamente precedente en la la del procesador, y recibir un bloque de B desde el procesador de la la posterior.
n3 p n + pts + 2 p tw
2
Tp =
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Ejemplo I
3 2 3 2 1 2 0 4 1 2 0 4 2 2 1 4 8 8 12 10 8 21 12
1 3
17 11
A
Paso 1
3 2 3 2 1 2 0 4 1 2 1 3 0 4 2 2 1 4
B
Paso 2
3 1 1 3 1 1 3 1 1
2 1 3
0 4 2
2 2 4
B
Paso 3
3 1 1 3 1 1 3 1 1 2 1 3 0 4 2 2 1 4
6 1 3
0 4 2
6 1 4
A
Gins David Guerrero Hernndez
C
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Ejemplo II
Paso 4
3 2 3 3 2 3 3 2 3 1 3 2 4 2 0 1 4 2 6 1 3 0 4 2 6 1 4
B
Pasos 2 y 3
2 4 3
2 4 3
2 4 3
1 3 2
4 2 0
1 4 2
8 13 9
8 12 2
8 17 10
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Ejemplo III
Paso 4
2 4 3 2 4 3 2 4 3 3 2 1 2 0 4 4 2 1 8 13 9 8 12 2 8 17 10
B
Pasos 2 y 3
0 2 2
0 2 2
0 2 2
3 2 1
2 0 4
4 2 1
8 17 11
8 12 10
8 21 12
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Algoritmo DNS I
Usa un particionamiento 3D. Visualiza el algoritmo de multiplicacin de matrices como un cubo, las matrices A y B estn en dos caras ortogonales y la matriz C resultante la almacena en otra cara. Cada nodo en el cubo representa una operacin de suma-multiplicacin. Originalmente necesita n x n x n procesadores. Hay variaciones del algoritmo que permiten llevar a cabo el algoritmo con un menor nmero de procesadores.
La variacin ms comn usa n2 p n3 procesadores. La variacin GK usa 1 p n3 procesadores.
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Algoritmo DNS II
El algoritmo, que puede ser observado grcamente en las siguientes transparencias, est divido en las siguientes etapas:
1
2 3
Los elementos de las matrices A y B son distribuidos en los p procesadores. Se multiplican los elementos que contiene cada procesador. Se suman todos los resultados parciales (situados a lo largo de la dimensin k en la posterior gura).
En la versin original realiza el cmputo en un O (log n). En la versin que permite ms de un elemento por procesador: 3 p n3 Tp = n p + 5 log n2 + 2 p (ts + tw ) En la versin GK: 3 5 Tp = n p + 3 log pts +
5 n2 ts 3 2 p3
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Algoritmo DNS III
(a) Distribucin inicial de la matriz A y B
(b) Despus de mover A(i ,j ) desde P(i ,j ,0) a P(i ,j ,j )
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Tipos Secuencial Bloques Cannon Fox DNS
Algoritmo DNS IV
(a) Despus de hacer broadcast A(i ,j ) a lo largo de j
(b) Distribucin correspondiente a B
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Conclusiones
Se puede comprobar que hay gran cantidad de algoritmos creados para realizar de manera lo ms ptima posible la multiplicacin de matrices. Adems de los algoritmos presentados hay muchos otros (Arreglo Sistlico, Berntsen...). Muchos de los algoritmos que nos podemos encontrar son variaciones de los estudiados para adaptarlos a un tipo de mquina paralela concreta. Todos los algoritmos paralelos comparten caractersticas comunes:
Adoptan el modelo de procesamiento SPMD. Asumen que los nodos de procesamiento son homogneos y aprovechan esta homogeneidad para obtener balance de carga.
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Trabajo a realizar
Una vez adquiridos los conocimientos bsicos sobre la paralelizacin de la MM el trabajo que se va a realizar ser: Implementacin en MPI:
Algoritmo de Cannon. Algoritmo de Fox.
Implementacin en OpenMP:
Algoritmo simple a partir del Algoritmo Secuencial.
Estudio Terico-Prctico comparando:
1 2 3
Cannon vs Fox. Simple vs Cannon. Simple vs Fox.
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
Introduccin Paralelizar Conclusiones Trabajo Bibliografa
Bibliografa
Ananth Grama, Anshul Gupta, Vipin Kumar, George Karypis. Introduction to Parallel Computing: Design and Analysis of Algorithms Ranshul Gupta, Vipin Kumar. Scalability of Parallel Algorithms for Matrix Multiplication Zhiao Shi. Parallel Matrix Multiplication Karen Walters. Numerical Linear Algebra
Gins David Guerrero Hernndez
Algoritmos paralelos para la Multiplicacin de Matrices
