Etapa final — ruta de estudio

💡 En simple

Esta sección crece semana a semana. Lo del parcial (U1–U3) sigue en su lugar del menú, porque el final se apoya en eso: MPI, speedup, eficiencia, DAG e isoeficiencia se siguen usando en todos los ejercicios. Aquí se agrega solo lo nuevo.

La pista más fuerte para lo que viene es la PD05 del ciclo pasado, que el profesor subió en la semana 12: EDP con MPI (3 pts), OpenMP con tareas y su DAG (2.5 pts) y escalabilidad de ordenamientos (1.5 pts). La ruta de abajo sigue ese orden de puntos.

Ruta recomendada para la PD05

Ordenada por peso en el modelo 2026-I. Cada paso dice qué deberías poder hacer al terminarlo.

#	Estudia	Para poder…	Peso en la PD05 2026-I
0	Repaso exprés: DAG · isoeficiencia · bloqueante vs no bloqueante · tareas OpenMP	usar las herramientas del parcial sin dudar	(base de todo)
1	EDP y diferencias finitas	discretizar una EDP y escribir la fórmula del stencil	3 pts
2	Laplace/Jacobi en paralelo	repartir la malla, intercambiar halos sin deadlock y verificar	↑
3	Onda y tsunami	resolver el ejercicio 1 completo: código, tiempos y gráfica	↑
4	Simulacro PD05	DAG con anti-dependencias, sections vs tasks, T∞ y Smáx	2.5 pts
5	Bases y ranking → Quicksort → Bitónico	explicar y trazar los algoritmos de ordenamiento paralelo	1.5 pts
6	Escalabilidad de ordenamientos	sacar la isoeficiencia de una Tp dada y comparar	↑
7	Búsqueda: modelos → DFS y B&B → PWS y DTS → Participación 9	contar pasos en un árbol con PWS y DTS, y sacar S y E	nuevo (no estaba en la PD05 2026-I)

Cómo comprobar que lo dominas: sin mirar la solución, resuelve (a) la práctica 1 de Jacobi en paralelo, (b) el DAG del simulacro, y (c) la isoeficiencia de T_p = (n/p) log n + log² p. Si los tres te salen solos, estás listo para la PD05.

Unidad 5: Análisis y programación de algoritmos paralelos

Objetivos que da el profesor en las láminas de U5:

#	Objetivo	Estado
1	Algoritmos naturalmente (“vergonzosamente”) paralelos	ya visto en el parcial: Random y Montecarlo, Mandelbrot
2	Ecuaciones diferenciales parciales	✅ U5.1 (semana 11)
3	Algoritmos de ordenamiento en paralelo	✅ U5.2 (semanas 11–12)
4	Algoritmos de búsqueda en paralelo	✅ U5.3 (semana 13) + participación 9
5	Algoritmos de grafos en paralelo	⏳ todavía no hay material

La lámina 36 de U5.2 menciona además una Unidad 6: Performance (minimizar la comunicación), que aún no ha llegado.

Unidad 4: Comunicación y coordinación

#	Objetivo	Dónde estudiarlo
1	Paso de mensajes: MPI, punto a punto, colectivas	MPI básico · Colectivas (del parcial)
2	Blocking vs non-blocking	Bloqueante vs no bloqueante (del parcial)
3	Tipos MPI	Tipos derivados (del parcial)
4	Memoria compartida: OpenMP, constructores y cláusulas	secciones 7 y 8 del menú
5	Programación híbrida	MPI + OpenMP · Dominio y halos

Avance por semana

Semana	Material	Estado
9	U4.1, U4.2, U4.3 Paralelismo compartido (OpenMP) + 12 programas de clase	✅ agregado
10	U4.4 OpenMP (modelo de memoria, locks), U4.5 Paralelismo híbrido + 7 programas de teoría + simulacro PC4 (9 programas)	✅ agregado
11	U5.1 EDP (+ laplace_sec/omp/mpi.cpp), U5.2 Ordenamiento, matvec_hibrido.cpp, peekaboo_mpi_omp.cpp	✅ agregado
12	PD05 2026-I (modelo de examen), U5.2 (misma versión)	✅ agregado: simulacro resuelto
13	U5.3 Búsqueda + participación 9 (PWS vs DTS)	✅ agregado: 5 páginas, simulador del árbol, código verificado
14 en adelante	grafos, performance	⏳ pendiente

Sobre el código

Todos los programas se compilaron y ejecutaron: los de clase y las soluciones propias (onda con MPI, sections vs tasks, quicksort con tareas y bitónico con OpenMP). Las salidas y los tiempos de estas páginas son medidos, en una laptop de 8 núcleos (12 hilos), no en Khipu: los números absolutos cambiarán en otra máquina, las tendencias no. Donde un código de clase tiene un detalle que falla (por ejemplo, laplace_mpi.cpp con p = 3), está marcado.

EDP (semana 11)

EDP y diferencias finitasTipos de EDP, Taylor, stencil de 5 puntos, Jacobi vs Gauss-Seidel, T = k·m·N² (k medido).

Laplace/Jacobi en paraleloLos 3 códigos de clase, halos con Send/Recv, el bug con p = 3, el deadlock latente, franjas vs bloques.

Onda y tsunamiEjercicio 1 de la PD05: código MPI verificado, tiempos para p = 1..8, curvas por K.

Ordenamiento (semanas 11–12)

Bases y rankingTabla de complejidad corregida, comparar-intercambiar, comparar-dividir, ranking PRAM.

Quicksort paralelo y HyksortSuma de prefijos para particionar, O(log² p), n > p, quicksort con OpenMP tasks medido.

Mergesort odd-even y bitónicoBatcher con ejemplo, red bitónica interactiva, bitónico OpenMP vs std::sort.

Escalabilidad de ordenamientosIsoeficiencia malla vs hipercubo vs Hyksort (PD05 ej. 3), cruce en p = 2¹⁶.

Búsqueda (semana 13)

Modelos, lineal y binariaBúsqueda vs optimización, REDUCE_OR, búsqueda p-aria interactiva: S = log p.

DFS, branch and bound e IDA*DFS con tareas, B&B en el ejemplo de PLE verificado (13 → 9 nodos), IDA*, tabla de la lámina 23.

Repartir el árbol: PWS, DTS, clustersp = b^k, Powley-Korf vs Kumar-Rao, Cuadro 2, simulador del árbol.

Balance de carga dinámicountied y taskyield, ARR vs GRR vs polling aleatorio.

Participación 9 resueltaPWS = 35, DTS = 13 pasos, S y E, análisis y variantes.

Examen

Simulacro PD05 (2026-I resuelta)Los 3 ejercicios: tsunami, DAG + sections vs tasks medido, bitónico y Hyksort. Checklist.

Simulacro PC4 (OpenMP)Histograma, palo roto, critical/atomic/reduction.

OpenMP e híbrido (semanas 9–10)

Memoria compartida y fork-joinQué es OpenMP, OMP vs MPI, compilar, primera condición de carrera.

Tareas e ICVstask, depend, taskwait, taskgroup: base del ejercicio 2 de la PD05.

Repaso OpenMPTodo OpenMP en una página para la última vuelta.

MPI + OpenMPPeekaboo, modos, Slurm en Khipu y el matriz × vector híbrido de la semana 11.

Fuente ·U5.1 Algoritmos-EDP.pdf · U5.2 Algoritmos-ordenamiento.pdf · U5.3 Algoritmos-busqueda.pdf · 2026I-CS4052-PD5.pdf · U4.1–U4.5 · semana_9/ · semana_10/ · semana_11/