⚡ High-Performance Computing (HPC)

De cache-aware y multihilo a SIMD, GPUs y clusters distribuidos — cómo exprimir cada ciclo de la máquina.

📚 Contenido

6.1 Panorama de HPC 6.2 Cache-Aware Algorithms 6.3 Shared-Memory Parallelism 6.4 SIMD Vectorization 6.5 GPU Computing 6.6 Distributed Algorithms 6.7 Case Studies en HPC 6.8 Advanced Topics & optimización extrema 📝 Quiz

📈 6.1 Panorama de HPC

            Idea base: HPC = resolver problemas muy grandes (o muy urgentes) explotando al máximo la jerarquía de memoria, los núcleos CPU, las instrucciones vectoriales, las GPUs y hasta clusters completos.
        

En este módulo vamos a conectar tus algoritmos con la arquitectura real donde corren:

Cache-aware: orden de acceso a memoria importa (y mucho).
Shared-memory: varios hilos dentro del mismo proceso / máquina.
SIMD: una sola instrucción opera sobre varios datos a la vez.
GPU: miles de hilos ligeros para workloads masivamente paralelos.
Distributed: varios nodos conectados por red (latencia + fallos).

Capa	Ejemplo	Qué optimiza
Localidad & cache	Bucle sobre matrices reordenado	Menos cache misses
Multihilo (CPU)	OpenMP en for paralelo	Speedup ≈ núm. núcleos
SIMD	Vectorizar suma de arreglos	Más datos por instrucción
GPU	Multiplicar matrices grandes	Massive throughput
Distribuido	MPI en cluster	Escalar a docenas / cientos de nodos

🧠 6.2 Cache-Aware Algorithms

            Regla de oro: la CPU es rápida, la RAM es lenta. Gana quien reutiliza datos que ya están en cache.
        

Conceptos clave

Localidad espacial: si accedes a A[i], probablemente accederás a A[i+1].
Localidad temporal: accedes varias veces al mismo dato en poco tiempo.
Cache line: bloque de bytes que se traen de una sola vez (ej. 64B).
Cache-aware algorithm: reordena los bucles / estructuras para minimizar misses (tiling / blocking).

Tiempo ≈ (# operaciones CPU) + #misses × latenciaMemoria

En una multiplicación de matrices, sólo cambiar el orden de los bucles puede dar un speedup enorme sin cambiar la complejidad asintótica.

Visual: recorrido de una matriz 8×8 en memoria row-major

Supón una matriz double A[8][8] almacenada en row-major (como en C/C++). Cada cache line tiene 4 elementos.

Compara cuántos hits/misses produce cada patrón de acceso (aprox con cache lines de 4 elementos).

// Ejemplo C++: bucle "malo" vs "bueno" para row-major

// Malo: recorre por columnas (pésima localidad)
for (int j = 0; j < n; ++j)
    for (int i = 0; i < n; ++i)
        sum += A[i][j];

// Bueno: recorre por filas (contiguo en memoria)
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        sum += A[i][j];

👥 6.3 Shared-Memory Parallelism

            Modelo: varios hilos comparten el mismo espacio de memoria (mismo proceso, misma máquina).
        

Conceptos

Thread: unidad de ejecución con su propio stack pero memoria global compartida.
Speedup S(p): cuánto más rápido corre con p hilos respecto a 1.
Amdahl: hay una parte secuencial 1 − f que limita el speedup máximo.

S(p) = 1 / ((1 − f) + f / p)

Si f = 0.9 (90% paralelizable) el máximo speedup teórico es ≈ 10× aunque tengas 1,000 hilos.

Visual: efecto de Amdahl con f = 0.9

Selecciona núm. de hilos y observa speedup y eficiencia (S(p)/p).

// Pseudocódigo estilo OpenMP para shared-memory

#pragma omp parallel for num_threads(p)
for (int i = 0; i < n; ++i) {
    // Cada hilo procesa un chunk de la carga
    C[i] = A[i] + B[i];
}

📏 6.4 SIMD Vectorization

            SIMD = Single Instruction, Multiple Data: una instrucción opera sobre varios elementos en paralelo dentro de un registro vectorial (ej. 4 ó 8 doubles).
        

Escenario típico

Tienes un bucle muy simple sobre arreglos:

// Escalar
for (int i = 0; i < n; ++i)
    C[i] = A[i] + B[i];

Si el compilador vectoriza y tu ISA soporta registros de ancho 4 doubles, puedes hacer 4 sumas por instrucción.

Visual: 16 elementos, escalar vs SIMD ancho 4

Cada cuadro representa un elemento de un arreglo. Compara cuántos pasos se necesitan.

En escalar se procesan 16/16 elementos por paso; en SIMD ancho 4, 4 elementos por instrucción.

            Link con multihilo: puedes usar SIMD dentro de cada hilo. Tu assignment de "vectorization vs multicore" justamente compara ganar ancho horizontal (SIMD) vs más hilos (vertical).
        

🧮 6.5 GPU Computing

            GPU: muchos núcleos simples, organizados en warps / blocks, ideales para operaciones con la misma instrucción sobre muchos datos (dense linear algebra, imágenes, deep learning, etc.).
        

CPU vs GPU (intuición)

CPU: pocos núcleos muy potentes, buenos para control, branching complejo y poca latencia.
GPU: miles de threads ligeros, buena para throughput masivo pero sensible a accesos irregulares a memoria.

Visual: tiempo relativo CPU vs GPU según tamaño del problema

Valores ficticios pero típicos: para problemas pequeños, overhead de la GPU domina; para problemas grandes, la GPU gana.

Selecciona tamaño. Barras más bajas = mejor tiempo (normalizado).

// Pseudocódigo de multiplicación de vectores en GPU (estilo CUDA)

__global__ void vecAdd(float *A, float *B, float *C, int n) {
    int i = blockIdx.x * blockDim.x + threadIdx.x;
    if (i < n) C[i] = A[i] + B[i];
}

🌐 6.6 Distributed Algorithms

            Modelo: varios nodos (máquinas) con su propia memoria, comunicándose por red (MPI, sockets, etc.).
        

Retos principales

Latencia y ancho de banda de red.
Sincronización: barreras, colectivas (broadcast, reduce, all-reduce).
Fallos: qué pasa si un nodo cae a la mitad del cómputo.

Visual: mensaje viajando de nodo A a D

Tenemos una topología simple A → B → C → D. Cada "hop" añade latencia.

Observa cuántos saltos (hops) requiere llegar de A hasta D.

// Esquema de un broadcast simple (estilo MPI)

P0: tiene el dato x
P0 --envía x--> P1
P1 --envía x--> P2
P2 --envía x--> P3
// Latencia crece con la longitud de la cadena (peor que un árbol binario).

🧩 6.7 Case Studies en aplicaciones HPC

Aquí tienes algunos escenarios típicos donde se combina todo lo anterior:

Aplicación	Qué se usa	Notas de diseño
Entrenamiento de redes profundas	GPU + SIMD + distributed data-parallel	Batches grandes, kernels de BLAS altamente optimizados.
Simulación de fluidos (CFD)	Cache-aware stencils + MPI + multihilo	Localidad en grillas 3D, halos entre nodos.
Analytics sobre grandes datasets	Clusters Spark / MPI + vectorización	MapReduce, shuffles, cuidado con skew y IO.
Algoritmos de optimización masivos	SA / GA paralelos + GPU / cluster	Evaluación en paralelo de fitness de muchas soluciones.

            Conexión con tu curso: muchos de los algoritmos de módulos previos (A*, GA, SA, RL) pueden "escalar" usando las ideas de este módulo (vectorizar inner loops, paralelizar evaluaciones de fitness, distribuir simulaciones, etc.).
        

🚀 6.8 Advanced Topics & optimización extrema

Roofline model

Relaciona flops/byte (intensidad aritmética) con el techo teórico de rendimiento dado por ancho de banda de memoria y pico de cómputo.

Auto-tuning & profiling

Probar automáticamente diferentes tamaños de bloque, órdenes de bucles, parámetros.
Usar perfiles (perf, VTune, Nsight) para localizar hot spots y bottlenecks.

Trucos hardcore

Prefetch manual: pedir datos a la cache antes de usarlos.
SoA vs AoS: cambiar layouts de datos para mejorar vectorización.
Fusión / fission de bucles: reorganizar loops para mejorar localidad o paralelismo.

            Mensaje final: HPC no es un algoritmo aislado; es una forma de pensar: cómo mapear tu algoritmo a la máquina real para reducir latencias y aumentar paralelismo en todas las capas.
        