Computación Paralela y Distribuida

Dos etapas

Final · U4 en adelante (en construcción)Semana 9: OpenMP — fork-join, for y schedule, sincronización, alcance de datos y tareas, con 6 playgrounds y el código de clase ejecutado.

Parcial · U1–U3Flynn, Foster, DAG, performance, PRAM, diseño de algoritmos y MPI, con exámenes previos resueltos.

Todo el contenido sale de las notas, slides, exámenes previos y código de clase del Prof. José Fiestas. Cada página cita su fuente al pie.

Cómo usar esta web

1. Repasa la teoría por unidad (barra lateral). Cada página sigue el mismo orden: teoría breve → avisos «en el examen» / «error común» → playground → ejercicio con solución desplegable → quiz corto.
2. Juega con los playgrounds. Mueve los sliders hasta poder predecir el resultado antes de verlo. Ahí es cuando lo entendiste.
3. Practica con exámenes previos. En Solvers por arquetipo está la plantilla paso a paso; en PD02 previos los enunciados con la solución oficial oculta.
4. Cierra con flashcards (banco de preguntas). El progreso queda guardado en este navegador.
5. Imprime el formulario la noche anterior.

Mapa: temas × arquetipos de examen

Los 4 PD02 previos (2025-I, 2025-II S01/S02, 2026-I) son variaciones de 6 arquetipos. Todos terminan pidiendo lo mismo: $S(n,p)$, $E(n,p)$ y escalabilidad fuerte/débil.

Arquetipo	Qué te dan	Temas que necesitas	Apareció en
A PRAM de operación global	suma, norma-p, normalización	PRAM, comunicación lineal/árbol	2025-I, 2025-II S01, S02
B Filas vs bloques	dos fórmulas de $T_p$	escalabilidad, matriz-vector	2025-II S01, S02
C DAG desde código + barreras	función con tareas que comparten arrays	DAG, Brent	2025-II S01, S02 (y PD01)
D FLOPs dados (N-Body)	$V(n,p)\approx\dfrac{\gamma N^{2+x}}{\alpha N^{2+x}/p+\beta\log p}$	FLOPs, N-Body	2025-I, 2026-I
E Recurrencia D&V / árbol	quicksort, árbol 2-3, mergesort	D&V y teorema maestro, prefix sum	2025-I, 2026-I, P1
F Matmul en memoria compartida	pseudocódigo por proceso $P_{i,j}$	EREW/CREW/CRCW	2026-I
MPI (U3)	código C++/MPI	bloqueo y deadlock, tipos	PD03, U3.5 repaso

Estrategia

El cierre de todo ejercicio es el mismo: $W$ y $T_\infty$ por separado → Brent → $S$ → $E=O\!\left(\dfrac{1}{1+p\cdot\text{algo}}\right)$ → fuerte (¿$E\to0$ con $n$ fijo?) y débil (¿qué $n=f(p)$ mantiene $E$ constante?). Ver el checklist de cierre.

Playgrounds

Amdahl vs GustafsonSliders f_s y p, techo 1/f_s, ley generalizada α.

DAG: work / spanDAGs reales del curso, camino crítico, cota de Brent y Gantt.

Prefix sum paso a pasoUp-sweep / down-sweep, quién lee y escribe, ¿EREW o CREW?

Brent y escalabilidadW(n), T∞(n) → S, E, isoeficiencia (reproduce P1).

Simulador de mensajes MPIAnillos Send/Ssend/Isend, ping-pong, deadlock del PD03.

Colectivas: lineal vs árbolBcast/Scatter/Gather/Reduce/Allreduce con costo α y β.

Tipos derivados MPIcontiguous, vector, indexed y struct sobre la matriz.

Matriz × vectorFilas / columnas / bloques + datos medidos de la práctica 3.

Montecarlo πSemillas, leapfrog, splitting, Reduce y convergencia.

MandelbrotEstático vs work pool: carga por proceso.

Teorema maestroa, b, f(n) → caso y resultado, árbol de recursión.

Animaciones (▶ play, pausa y velocidad)

Flynn en movimientoFlujos de instrucción y de datos viajando a las unidades de proceso.

Foster P → C → A → MMalla con canales: franjas de filas vs bloques 2D y cuánto se comunica cada uno.

Halo exchange (PD01)Suavizado 1D: intercambio de bordes y cómputo local, iteración por iteración.

Carrera Amdahl / Gustafson1 procesador vs p: la parte secuencial no se encoge.

Escrituras CRCWComún, arbitrario, prioritario, combinado; OR y máximo en O(1).

Matmul: ¿EREW o CREW?Accesos de (i+j+k) mod n vs bucle ingenuo; expansión + reducción.

BSP y LogPSupersteps w + gh + L con desbalance; reducción con L, o, g.

Mergesort paraleloÁrbol que divide y combina; span O(n) vs O(log² n).

Simulación N-BodyCuerpos repartidos entre procesos y p óptimo cómputo vs comunicación.

π medido (np 1–128)Tiempos reales: speedup, eficiencia y FLOP/s según N.

Struct y paddingRelleno, MPI_Get_address y create_struct generado.

Fuente ·estudio/00_Indice_y_Formulario.md · estudio/08_Solvers_Examenes_Previos.md