TEL-420 Sistemas Paralelos P3b taller colectivas · M3
Inicio/Módulo M3/Guías/P3b taller colectivas/
M3 Guía de Práctica / Taller
Descargar .md

P3b · Taller de operaciones colectivas y cálculo paralelo distribuido

Contenido del programa: §20.3 · contenidos 3.4 y 3.5 Horas de laboratorio: 4 · Modalidad: individual

1. Objetivo

Diseñar e implementar algoritmos paralelos en memoria distribuida empleando las rutinas de comunicación colectiva de MPI (MPI_Bcast, MPI_Scatter, MPI_Gather, MPI_Reduce y MPI_Allreduce), aplicándolas al cálculo de Pi mediante el método estocástico de Monte Carlo y a la multiplicación de matrices dividida por bloques de filas, comparando la aceleración y la complejidad teórica de comunicación frente a bucles punto a punto.

2. Requisitos previos

  • Haber estudiado los apartados 3.4 y 3.5 del contenido del módulo 3.
  • Comprender la diferencia entre operaciones uno-a-todos, todos-a-uno y todos-a-todos.

3. Ejercicios guiados

Ejercicio 1: Monte Carlo distribuido para aproximación de Pi

Implementar el cálculo estocástico de \pi:

  1. El proceso 0 recibe por línea de comandos el número total de dardos N_{total} y lo difunde a todos los procesos mediante MPI_Bcast.
  2. Cada proceso calcula su porción local de muestras: N_{local} = N_{total} / p.
  3. Manejo crítico de números aleatorios: Cada proceso debe inicializar su generador con una semilla independiente basada en su rango (srand(time(NULL) + rank * 1000) o generador reentrante erand48) para evitar que todos generen los mismos puntos.
  4. Cada proceso cuenta cuántos puntos caen dentro del círculo unitario ([x^2 + y^2 \le 1.0]).
  5. Se agregan los aciertos locales mediante MPI_Reduce con la operación MPI_SUM hacia el proceso 0.
  6. El proceso 0 calcula la aproximación final: \pi \approx 4 \times \frac{\text{aciertos\_totales}}{N_{total}} y mide el tiempo total de ejecución con MPI_Wtime().

Ejercicio 2: Multiplicación de Matrices $C = A \times B$ distribuida

  1. El proceso 0 inicializa dos matrices densas cuadradas A y B de dimensión N \times N.
  2. Particionar A por filas contiguas: cada proceso recibe N / p filas completas de A mediante MPI_Scatter.
  3. Transmitir la matriz B completa a todos los procesos mediante MPI_Bcast.
  4. Cada proceso calcula su bloque local de filas de la matriz resultante C_{local}.
  5. Recombinar la matriz C completa en el proceso 0 utilizando MPI_Gather.
  6. Validar numéricamente que el resultado coincide elemento a elemento con la versión secuencial con un margen |C_{mpi}[i][j] - C_{seq}[i][j]| < 10^{-9}.

4. Preguntas de reflexión técnica

  1. ¿Por qué es más eficiente MPI_Bcast que un bucle for con p-1 llamadas a MPI_Send?
  2. Si la matriz B fuera demasiado grande para caber en la memoria de un solo nodo (N = 100.000), ¿por qué falla este esquema y qué algoritmo alternativo se debe emplear (ej. Algoritmo de Cannon o Fox)?