Multiplicación de Matrices Algoritmos Paralelos

Multiplicación
de Matrices
Algoritmos Paralelos
Presenta
LUCVAZQU

Algoritmo Secuencial
 Sea

una matriz A de dimensiones l x m y
una matriz B de dimensiones m x n,
entonces el productoA x B es una matriz
C de dimensiones l x n.

Algoritmo Secuencial
 Claramente

la
complejidad de
este algoritmo es
θ(n³) para matrices
de n x n.

Algoritmos para arreglos deprocesadores
 Están

basados en el algoritmo secuencial.
 Usan una topología de tipo malla ***.
 Siguen el modelo Single Instruction
Multiple Data
 n³ multiplicaciones necesarias
 Eficiencia entiempo : θ(n) usando n²
procesadores
 El procesador P(i,j) contiene aij y bij

Algoritmo Paralelo
Se deben multiplicar todos los
pares a(i,k) x b(k,j)

Se desplaza i
posiciones a
laizquierda

Se desplaza i
posiciones hacia
arriba

Malla Colapsada

Multiplicación de Matrices en
el Hipercubo usando el
modelo SIMD






Matrices de n x n pueden ser multiplicadasen
tiempo θ(log n) usando n³
Durante la primera fase los elementos a(i,j) y
b(i,j) son enviados al resto de los
procesadores(usando broadcast).
En la segunda fase las n³ multiplicaciones secalculan simultáneamente.
En la tercera fase el algoritmo enruta y suma
los productos.

Primera fase

Primera fase

Segunda Fase

Tercera fase

Algoritmos para
Multiprocesadores
Estrategia

de diseño: si balancear la
carga no es problema entonces
maximizar la granularidad.
 Granularidad: cantidad de trabajo
realizado en las interacciones entre
procesadores.Algoritmos para
Multiprocesadores (UMA)

Multiplicación de Matrices por
bloques (NUMA)
 Se

necesita que las matrices a y b sean
de dimensiones n x n, donde n=2k
 Entonces a y b se puedenrepresentar en
4 bloques mas pequeños de tamaño k x k

Multiplicación de Matrices por bloques (NUMA)

Paso 1: calcular C(i,j) = A(i,1)x B(1,i)

 Paso

2 Calcular C(i,j)=C(i,j)+A(i,2)B(2,i)...