La actividad de esta semana constara de realizar un algoritmo en paralelo para posteriormente implementarlo en 3 lenguajes de programación, utilizando hilos y conocimiento básico, buscaremos un problema que pueda ser secuencial y tratar de implementarlo para que sea de forma paralela, a lo que este se refiere es a que, si un problema debe conllevar una cierta cantidad de pasos de forma secuencial, también pueda ser realizada de forma paralela y al final reunir los resultados, obteniendo el mismo resultado pero el tiempo de realización sera menor.
Algunas Técnicas básicas en las que nos basaremos para la creación de un algoritmo paralelo.
Divide and Conquer(Divide y Vencerás):
1. Dividir.- Dividir el problema original en subproblemas mas pequeñas que serán mas fáciles de realizar.
2. Vencerás.- Resolver los subproblemas
3. Unir.- Combinar las soluciones
Generalmente este paradigma conduce a algoritmos mas simples y eficientes.
como generalmente los subproblemas en que se divide son independientes se puede resolver por paralelos.
Consideraciones iniciales a tener en cuenta
- Por simplicidad, todo el tiempo trabajaremos con matrices cuadradas de tamaño n x n.
- Consideramos que el número de procesadores de los que disponen las máquinas paralelas es p.
- Las matrices a multiplicar serán A y B, ambas tratadas como matrices densas , 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 comunicación y tw es el tiempo que tarda para transmitir un dato.
Básicamente está formado por tres bucles for.
Código
División de bloques
Las matrices serán dividas en bloques de tamaño √n
Cada procesador calculará un bloque de C.
Cada procesador tendrá √p submatrices correspondientes a la fila 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 ineficiente.
Algoritmo de Cannon I
Utiliza una malla con conexiones entre los
elementos de cada lado (toro) para desplazar los elementos de A hacia la
izquierda y los de B hacia arriba.
El algoritmo sigue los siguientes pasos:
1. El procesador Pij tiene los elementos aij y bij.
2. La fila i-ésima de A se desplaza i posiciones a la izquierda, y la columna j-ésima de B se desplaza j posiciones hacia arriba, y todo esto teniendo en cuenta que el elemento que sale por un extremo entra por el otro. Con este paso se consigue que el procesador Pij
contenga los elementos aij+i y bi+jj, que son necesarios para calcular cij.
Cada procesador multiplica su par de elementos.
3. Cada procesador multiplica su par de elementos.
4. Cada fila de A se desplaza una posición a la izquierda, y cada columna de B una posición hacia arriba.
5. Cada procesador multiplica su nuevo par de elementos, y suma el resultado al anterior.
6. Se repiten los pasos 4 y 5 hasta terminar, es decir n – 1 desplazanientos
1. El procesador Pij tiene los elementos aij y bij.
2. La fila i-ésima de A se desplaza i posiciones a la izquierda, y la columna j-ésima de B se desplaza j posiciones hacia arriba, y todo esto teniendo en cuenta que el elemento que sale por un extremo entra por el otro. Con este paso se consigue que el procesador Pij
contenga los elementos aij+i y bi+jj, que son necesarios para calcular cij.
Cada procesador multiplica su par de elementos.
3. Cada procesador multiplica su par de elementos.
4. Cada fila de A se desplaza una posición a la izquierda, y cada columna de B una posición hacia arriba.
5. Cada procesador multiplica su nuevo par de elementos, y suma el resultado al anterior.
6. Se repiten los pasos 4 y 5 hasta terminar, es decir n – 1 desplazanientos
Datos de Entrada
Se crean 3 matrices y dos se llenan con números aleatorios.
Datos de Salida
La tercera matriz se llena con resultado de la multiplicación de las dos matrices y son los datos de salida.
Diagrama de flujo
No hay comentarios:
Publicar un comentario