Saltar a contenido

Resumen integral: Limitaciones fundamentales en sistemas paralelos y paralelización

Conceptos fundamentales vistos en clase

1. El fin de la Ley de Moore y sus causas

La Ley de Moore, formulada en 1965, predecía que el número de transistores en un chip se duplicaría cada 18-24 meses. Esta ley se cumplió fielmente durante casi 50 años, pero a partir de mediados de la década de 2010, dejó de aplicarse.

Causas fundamentales del fin de la Ley de Moore:

  1. Límites cuánticos: a escalas de 5-7 nanómetros, los efectos cuánticos como el tunelaje de electrones hacen que sea imposible mantener transistores en estado apagado. Los electrones, operando bajo mecánica cuántica, pueden atravesar barreras de energía que clásicamente deberían ser infranqueables.

  2. Disipación térmica extrema: la densidad de potencia en chips modernos es insostenible. La potencia consumida escala según:

\[P = C \times V^2 \times f\]

Donde \(C\) es capacitancia, \(V\) es voltaje y \(f\) es frecuencia. Reducir tamaño de transistores requiere mayor densidad, mayor voltaje para operar confiablemente, y mayor frecuencia para mantener rendimiento. El resultado es crecimiento exponencial de calor.

  1. Variabilidad de manufactura: en procesos nanométricos, pequeñas variaciones en fabricación (~1-2 átomos) causan diferencias significativas en comportamiento de transistores, reduciendo yield (porcentaje de chips funcionales).

  2. Costo prohibitivo: equipos litográficos para procesos menores de 5 nm cuestan $100+ millones, con ROI (retorno de inversión) que se ha vuelto negativo.

Implicación: el crecimiento exponencial que caracterizó 50 años de computación ha terminado. La industria debe buscar mejoras a través de arquitectura, no solo reducción de tamaño.

2. Estabilización de tasas de reloj (Frequency Wall)

Las tasas de reloj (GHz) de procesadores de consumo se han mantenido entre 3-4 GHz desde aproximadamente 2005-2010, sin incremento significativo.

Causa fundamental:

La relación entre potencia, voltaje y frecuencia es cuadrática en voltaje. Para aumentar frecuencia sin aumentar disipación térmica exponencialmente: - No se puede aumentar voltaje (cuadrático, inmanejable) - No se puede aumentar frecuencia mucho (lineal pero limitado por temperatura)

Ejemplo cuantitativo:

Procesador actual: 3.5 GHz, 95W

Si duplicamos frecuencia a 7 GHz (mismo voltaje):
P = 95W × (7/3.5) = 190W (duplicamos potencia)

Con mejor arquitectura y fabricación se puede llegar a 5 GHz:
P = 95W × (5/3.5) ≈ 135W (aceptable)

Pero no a 7-8 GHz con arquitectura tradicional.

Consecuencia: las mejoras de rendimiento en los últimos 15-20 años no vienen de velocidad de reloj, sino de: - Más núcleos (paralelización) - Mejor predicción de ramas - Mejor caché - Mejor pipeline - Ejecución especulativa más sofisticada

3. Memory Wall: El cuello de botella de memoria

El Memory Wall es un problema arquitectónico fundamental: la brecha de velocidad entre CPU y memoria es insalvable con enfoque de mejora tradicional.

Brecha de velocidad relativa:

Registros CPU:         1 ciclo
L1 Cache:              4 ciclos (~4x más lento)
L2 Cache:              10 ciclos (~10x)
L3 Cache:              40 ciclos (~40x)
Memoria RAM:           100-300 ciclos (~100-300x)
SSD:                   100,000+ ciclos (~100,000x)

La brecha se ha AUMENTADO con el tiempo:

1994: CPU 100MHz, RAM 60ns
      Brecha: 6x

2024: CPU 4GHz (0.25ns/ciclo), RAM 60ns
      Brecha: 240x

Mejorar CPU sin mejorar memoria = EMPEORA la relación

Observación de Wulf (1994):

A. Jay Wulf demostró que aproximadamente el 20% de todas las instrucciones ejecutadas son accesos a memoria. Esto significa que 1 de cada 5 instrucciones es un acceso a memoria que requiere esperar datos.

Datos modernos (2023): - Programas típicos: 25-35% de instrucciones son accesos a memoria - Programas científicos: 40-60% son accesos a memoria - Programas de big data: 60-80% son accesos a memoria

Implicación crítica: por más que mejoremos el procesador, siempre hay un límite fundamental en rendimiento impuesto por velocidad de memoria. Incluso con infinitos núcleos, si 30% del tiempo se gasta esperando RAM, el máximo speedup es ~3.3x.

// Ejemplo de programa memory-bound
def procesarMillonesDeElementos(arr: Array[Long]): Long = {
  var suma = 0L
  // El 95% del tiempo se gasta aquí: esperando datos de RAM
  for (i <- 0 until 1000000) {
    suma += arr(i)  // Cada acceso requiere ~100 ciclos de CPU si falla caché
  }
  suma
}

// Una CPU 10x más rápida apenas mejora porque está esperando memoria
// La solución real: mejor algoritmo, mejor localidad, mejor caché

4. LP Wall: Límite de paralelismo a nivel de instrucción

El LP Wall (Instruction-Level Parallelism Wall) es el límite de cuánto paralelismo se puede extraer dentro de un único hilo de ejecución, mediante técnicas como ejecución especulativa y pipelining.

4.1 Ejecución especulativa

La ejecución especulativa intenta ejecutar instrucciones que se predice que serán necesarias, antes de que la condición se resuelva.

// Código con rama condicional
if (valor > threshold) {
  resultado = costosaComputacion()  // Operación costosa: ~100 ciclos
} else {
  resultado = 0
}

// Sin ejecución especulativa:
// 1. CPU evalúa: valor > threshold      (~4 ciclos)
// 2. CPU espera resultado               (~96 ciclos de nada)
// 3. CPU ejecuta rama correcta          (~100 ciclos si true, ~1 si false)
// Total si true: 200+ ciclos

// Con ejecución especulativa:
// 1. CPU predice resultado de condición (basado en histórico)
// 2. MIENTRAS se evalúa condición, simultáneamente ejecuta costosaComputacion()
// 3. Si predicción correcta: resultado listo cuando se confirma, gana 100 ciclos
// 4. Si predicción incorrecta: descarta trabajo especulativo, vuelve atrás (peor)
// Total si predicción correcta: ~100 ciclos (ocultó latencia)

Ventaja: en ramas que se predice correctamente >95% del tiempo (loops, sentencias if típicas), se oculta la latencia de decisión.

Desventaja: predicción incorrecta cuesta ciclos valiosos en especulación fallida. Además, vulnerabilidades como Spectre y Meltdown explotan la especulación para leer memoria no autorizada.

4.1.2 Ejecución

4.2 Pipeline (encauzamiento)

El pipeline divide la ejecución de una instrucción en múltiples etapas especializadas, permitiendo que diferentes instrucciones estén en diferentes etapas simultáneamente.

Arquitectura típica de 5 etapas:
1. Fetch (F):   Buscar instrucción de memoria
2. Decode (D):  Decodificar y obtener operandos
3. Execute (E): Ejecutar operación aritmética
4. Memory (M):  Acceder a memoria si es necesario
5. Write (W):   Escribir resultado en registro

Sin pipeline (ejecución secuencial):
Ciclo 1: Instr1[F][D][E][M][W] = 5 ciclos
Ciclo 6: Instr2[F][D][E][M][W] = 5 ciclos
Total: 10 ciclos para 2 instrucciones

Con pipeline de 5 etapas (superposición):
Ciclo 1: [F1]
Ciclo 2: [D1][F2]
Ciclo 3: [E1][D2][F3]
Ciclo 4: [M1][E2][D3][F4]
Ciclo 5: [W1][M2][E3][D4][F5]
Ciclo 6:     [W2][M3][E4][D5]

Total: 6 ciclos para 5 instrucciones (1 instrucción por ciclo en estado estable)

Ventaja: aumenta throughput de instrucciones por ciclo de ~0.2 (sin pipeline) a ~1.0 (con pipeline).

Desventaja: pipeline hazards - dependencias entre instrucciones causan pipeline stalls donde el pipeline se vacía:

// Data hazard: lectura-después-escritura (RAW - Read-After-Write)
var x = 0
x = x + 1  // Ciclo 1-5: [F][D][E][M][W]
           // Write en ciclo 5, dato disponible después
y = x + 2  // Ciclo 2-6: [F][D (ESPERA - x aún no disponible)][...]
           // Sin forwarding: 4 ciclos de stall
           // Con forwarding: 0-1 ciclos de stall

Límite fundamental: incluso con técnicas avanzadas de predicción, especulación y pipelining, el promedio de instrucciones por ciclo (IPC) en procesadores modernos es ~3-4, no 6-8 como sería ideal.

5. Paralelización: División de tareas y dependencias

La paralelización implica dividir una tarea en subtareas que se ejecutan simultáneamente. Sin embargo, las dependencias entre tareas limitan cuánto paralelismo es posible.

Ley de Amdahl: predice el speedup máximo:

\[S = \frac{1}{(1-p) + \frac{p}{n}}\]

Donde: - \(p\) = fracción paralelizable - \(n\) = número de procesadores - \((1-p)\) = fracción secuencial (no paralelizable)

Con recursos infinitos (\(n \to \infty\)):

\[S_{\max} = \frac{1}{1-p}\]

Ejemplo: - Si \(p = 0.9\) (90% paralelizable), speedup máximo = 1/0.1 = 10x, incluso con infinitos procesadores - Si \(p = 0.99\) (99% paralelizable), speedup máximo = 1/0.01 = 100x

6. Tres factores críticos en paralelización

Work (W): cantidad total de operaciones (constante, independiente de paralelización)

Span (S): camino crítico - la cadena más larga de dependencias. Es el tiempo mínimo posible incluso con infinitos procesadores.

Comunicación (C): costo de sincronización, locks, y comunicación entre procesos. En memoria compartida, incluye cache coherency y memory barriers.

La latencia real es:

\[L_{\text{real}} = \frac{W}{n} + S + C\]

Donde \(n\) es número de procesadores.

Implicación: aunque paralelicemos, si \(S\) es grande (muchas dependencias), ganancia es limitada.

// Bajo span: altamente paralelizable
def sumaParalela(arr: Array[Int]): Int = {
  // Dividir recursivamente: arr[0..n/2] en paralelo con arr[n/2..n]
  // Span: O(log n)
  // Speedup: puede ser linear hasta ~log n procesadores
  arr.par.sum
}

// Alto span: difícil de paralelizar
def fibonaciSecuencial(n: Int): Long = {
  // fib(n) depende de fib(n-1) que depende de fib(n-2)...
  // Span: O(n)
  // Speedup: limitado a ~2x incluso con muchos procesadores
  if (n <= 1) n else fibonaciSecuencial(n-1) + fibonaciSecuencial(n-2)
}

7. Recursos compartidos: Localidad de memoria

En sistemas paralelos, la memoria es un recurso crítico compartido.

Localidad espacial: si se accede a dirección \(x\), es probable que se acceda a \(x+1, x+2, \ldots\) pronto. Los accesos secuenciales son eficientes.

Localidad temporal: si se accede a dirección \(x\) en tiempo \(t\), es probable que se acceda a \(x\) nuevamente poco después. Reutilizar datos es eficiente.

Tiempo promedio de acceso a memoria (AMAT):

\[\text{AMAT} = h \times T_c + (1-h) \times T_m\]

Donde: - \(h\) = hit ratio (probabilidad de cache hit) - \(T_c\) = latencia de caché (~4 ciclos) - \(T_m\) = latencia de memoria (~100 ciclos)

Ejemplo: - Con \(h = 0.95\) (95% hits): AMAT = 0.95 × 4 + 0.05 × 100 = 8.8 ciclos - Con \(h = 0.50\) (50% hits): AMAT = 0.50 × 4 + 0.50 × 100 = 52 ciclos

Mejorar hit ratio de 85% a 90% puede resultar en 20-50% de mejora en velocidad.

8. Patrones de paralelización

Los patrones codifican soluciones probadas a problemas paralelos comunes.

Map-Reduce: dividir datos en tareas independientes (map), procesar en paralelo, combinar resultados (reduce). Ideal para procesamiento masivo de datos sin dependencias.

Fork-Join: dividir recursivamente problema, resolver subproblemas en paralelo, combinar resultados. Ideal para divide-and-conquer.

Pipeline: organizar trabajo en etapas secuenciales, donde cada etapa procesa diferentes datos de etapa anterior. Ideal para streams de datos.

Aplicaciones prácticas fundamentales

1. Procesamiento de big data y análisis

Aplicación: análisis de logs de servidores, datos de redes sociales, sensores IoT.

Por qué es importante:

  • Datasets modernos: terabytes a petabytes de datos
  • Sin paralelización: análisis puede tomar días o semanas
  • Con paralelización (Map-Reduce, Spark): análisis en horas o minutos
  • Decisiones comerciales requieren análisis rápido

Ejemplo real: 

Facebook: 4+ petabytes de datos diarios
Sin paralelización: imposible procesar
Con Hadoop/Spark: análisis en tiempo real para recomendaciones

2. Machine Learning e Inteligencia Artificial

Aplicación: entrenamiento de redes neuronales profundas, optimización de hiperparámetros.

Por qué es importante:

  • Modelos modernos: 10+ billones de parámetros
  • Entrenamiento requiere gradientes de millones de muestras
  • Sin paralelización: entrenamiento toma meses
  • Con paralelización en GPUs/TPUs: entrenamiento en días/semanas
  • Modelos como GPT-4, BERT requieren paralelización masiva

Relación directa: - Algoritmos de optimización (SGD, Adam) son iterativos - Cada iteración depende de la anterior (span) - Paralelismo es a nivel de datos: diferentes samples procesados en paralelo

3. Simulaciones científicas

Aplicación: simulaciones de clima, dinámica de fluidos, modelado molecular, análisis estructural.

Por qué es importante:

  • Predicciones climáticas requieren simulación de atmósfera en grillas de ~1km
  • Simulación molecular: interacciones entre millones de átomos
  • Cada punto depende de puntos vecinos (dependencias espaciales)
  • Sin paralelización: simulación de un año de clima = años de computación
  • Con paralelización: semanas a meses en supercomputadoras

Ejemplo: 

Predicción del huracán:
- Grilla: 5000×5000×50 = 1.25 billones de puntos
- Cada punto requiere cálculos de física (temperatura, presión, viento)
- Dependencias: cada punto depende de vecinos
- Span: determinado por velocidad de propagación de información
- Con 1000 procesadores: speedup ~500-800x (no lineal por dependencias)

4. Criptografía y seguridad

Aplicación: búsqueda de claves, verificación de passwords, blockchain.

Por qué es importante:

  • Ataques de fuerza bruta: probar 2^256 combinaciones posibles
  • Sin paralelización: imposible en tiempo viable
  • Con paralelización: distribución de búsqueda entre máquinas

Relación: - Búsqueda es embarrassingly parallel (sin dependencias) - Ideal para paralelización masiva - Pero cada procesador tiene tarea independiente

5. Renderizado de gráficos y videojuegos

Aplicación: cálculo de píxeles en paralelo, física de colisiones, IA de enemigos.

Por qué es importante:

  • Cada píxel de imagen (~2 millones en 1080p) se calcula independientemente
  • Sin paralelización: imposible en tiempo real (60 FPS)
  • Con GPUs (miles de núcleos pequeños): renderizado en <16ms por frame

Relación a Memory Wall: - Acceso a texturas y modelos causa memory misses constantemente - Arquitectura GPU está optimizada para memory bandwidth, no latencia - Muchos pequeños hilos esconden latencia de memoria

6. Procesamiento de imágenes y visión por computadora

Aplicación: detección de objetos, reconocimiento facial, procesamiento de video.

Por qué es importante:

  • Video 4K: 8 megapíxeles × 30 fps × procesamiento por píxel
  • Sin paralelización: procesamiento en tiempo real es imposible
  • Con paralelización en GPU: procesamiento en tiempo real
  • Vigilancia, conducción autónoma, medicina requieren tiempo real

7. Análisis financiero

Aplicación: cálculo de riesgo de portafolios, simulación de Monte Carlo, backtesting de estrategias.

Por qué es importante:

  • Simulaciones de Monte Carlo: millones de iteraciones para precisión
  • Cada simulación es independiente (parallelizable)
  • Decisiones de inversión requieren análisis rápido
  • Mercados operan en milisegundos (high-frequency trading)

Relación entre conceptos: El sistema completo

Estos conceptos no existen aislados. Forman un sistema completo que determina rendimiento:

┌─────────────────────────────────────────────────────────┐
│  LÍMITES FUNDAMENTALES DE HARDWARE                      │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  Ley de Moore:              [FIN - límite cuántico]    │
│  ↓ No se puede mejorar densidad de transistores        │
│                                                         │
│  Frequency Wall:            [ESTABILIZADO a 3-4 GHz]   │
│  ↓ No se puede mejorar velocidad de reloj              │
│                                                         │
│  LP Wall:                   [IPC limitado a ~3-4]      │
│  ├─ Ejecución especulativa mejora pero no infinito    │
│  ├─ Pipeline ayuda pero tiene hazards                 │
│  ↓ No se puede mejorar paralelismo de instrucción     │
│                                                         │
│  Memory Wall:               [100-300x más lenta]       │
│  ↓ 25-35% de instrucciones esperan datos RAM          │
│                                                         │
│  ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─│
│  ÚNICA SOLUCIÓN: PARALELIZACIÓN (múltiples núcleos)   │
│  ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─│
│                                                         │
│  Ley de Amdahl:             $S = \frac{1}{(1-p)+\frac{p}{n}}$
│  ├─ Factor paralelizable p limita speedup            │
│  ├─ Span determina camino crítico                    │
│  ├─ Comunicación introduce overhead                 │
│  ↓ Speedup sublineal, nunca lineal en realidad       │
│                                                         │
│  Recursos compartidos:      Acceso a caché/memoria   │
│  ├─ Localidad espacial/temporal crítica              │
│  ├─ False sharing causa invalidación de caché        │
│  ↓ Sincronización requiere coordinar accesos         │
│                                                         │
│  Patrones:                  Soluciones probadas       │
│  ├─ Map-Reduce para datos sin dependencias           │
│  ├─ Fork-Join para divide-and-conquer                │
│  ├─ Pipeline para streams                           │
│  ↓ Abstracción de complejidad de paralelización     │
│                                                         │
└─────────────────────────────────────────────────────────┘

Frase de motivación

Los límites que hemos estudiado no son debilidades del sistema computacional actual: son realidades físicas que definen el terreno de juego. La Ley de Moore no puede revertirse, el Memory Wall no desaparecerá, y el LP Wall es insuperable dentro de un hilo único. Pero estos límites no son obstáculos para ingenieros competentes; son invitaciones a la creatividad. Porque mientras la velocidad de un solo procesador está congelada en 3-4 GHz, puedes paralelizar. Mientras la memoria es lenta, puedes optimizar localidad. Mientras las dependencias limitan paralelismo, puedes reorganizar algoritmos. Los sistemas que escalan a petabytes de datos, que entrenan inteligencia artificial con billones de parámetros, que predicen huracanes, que aseguran tu dinero en transacciones financieras, que generan películas en tiempo real: todos ellos fueron construidos por ingenieros que entendieron estas limitaciones y las convirtieron en oportunidades. Dominar estos conceptos significa que tienes acceso a técnicas que literalmente multiplican la capacidad de cómputo disponible. Eso no es solo aprender teoría; es aprender a pensar como arquitecto de sistemas que mueven economías y resuelven los problemas más complejos de la humanidad.