EJERCICIOS PROPUESTOS

• Implementar los algoritmos paralelos de cálculo de todos los caminos más cortos que han sido descritos previamente. Se aconseja realizar cambios sobre la clase Graph, que encapsula la gestión del grafo etiquetado, para implementar todas las operaciones de comunicación dentro de dicha clase. Por tanto, la clase encapsularía un grafo distribuido entre los procesadores en base a una determinada distribución (por bloques de filas para la descomposición unidimensional, o por bloques cuadrados para la descomposición bidimensional). Se debe crear un directorio diferente para cada versión paralela (Floyd_1, Floyd_2). Cada directorio mantendrá los mismos archivos que se usan en la versión secuencial pero con diferente código. De esa forma el Makefile se puede reutilizar y se percibe claramente la diferencia entre versiones.
• Realizar medidas de tiempo de ejecución sobre los algoritmos implementados. Para medir tiempos de ejecución, podemos utilizar la función MPI_Wtime. Para asegurarnos de que todos los procesadores comienzan su computación al mismo tiempo, podemos utilizar MPI_Barrier. Las medidas deberán excluir las fases de entrada/salida. Deberán realizarse las siguientes medidas:

(A) Medidas para el algoritmo secuencial (P=1).
(B) Medidas para el algoritmo paralelo (P=4). Las medidas deberán excluir las fases de entrada/salida, así como la fase de distribución inicial de la matriz A desde P0 y la fase de reunión del resultado en P0.
Las medidas deberán realizarse para diferentes tamaños de problema, para así poder comprobar el efecto de la granularidad sobre el rendimiento de los algoritmos. Se presentará una tabla con el siguiente formato:

Suponiendo que las P tareas se ejecutan sobre P procesadores conectados todos con todos, y que las operaciones colectivas se han implementado siguiendo algoritmos que asumen un hipercubo como topología de conexión, obtener fórmulas de tiempo de ejecución para los algoritmos implementados en base a parámetros del problema y a parámetros que caracterizan la arquitectura (tc=tiempo que lleva una comparación, ts=tiempo de inicialización de envío, tw=tiempo de transferencia por palabra).