Paralelismo

El panorama general y el vocabulario

Piensa en una cocina. Un cocinero que hace 100 sándwiches los hace de uno en uno. Cuatro cocineros en cuatro mesas los hacen juntos. El sándwich es el trabajo, cada cocinero es un trabajador (worker), y trabajan en paralelo porque todos cocinan en el mismo instante.

Palabras que vas a encontrar

El speed-up es "cuántas veces más rápido". Si un trabajo tarda 120 segundos solo y 20 segundos con ayudantes, el speed-up es 6. Buena parte de esta área explica por qué ese número suele ser menor que el número de ayudantes.

Paralelismo de datos y paralelismo de tareas

Hay dos grandes formas de cortar un trabajo en pedazos. En el álbum de cromos, puedes darle a cada amigo una parte de los cromos (el mismo oficio, cromos distintos). O puedes darle a cada amigo una tarea distinta: uno recorta, uno pega, uno escribe las etiquetas.

¿Cuándo se puede repartir un bucle?

Un bucle (loop) puede convertirse en paralelismo de datos cuando sus iteraciones son independientes: ninguna lee un valor que otra escribe. Entonces las vueltas pueden correr en cualquier orden, incluso al mismo tiempo. El tamaño y la duración de las vueltas solo afectan el rendimiento, no la corrección.

El paralelismo de tareas tiene un techo

Digamos que tres tareas independientes tardan 6 s, 3 s y 3 s. Cada una corre en su núcleo. El tiempo total es el de la tarea más larga, 6 s, incluso en una máquina de 16 núcleos. El speed-up es 12 / 6 = 2. Solo dividir los datos dentro de las tareas usaría los otros núcleos.

Las tareas también pueden depender unas de otras. La cadena más larga de tareas dependientes es el camino crítico. Ningún número de procesadores hace el programa más rápido que esa cadena. Ejemplo: A (4 s), B (3 s) y D (5 s) son libres, C (2 s) necesita A y B, E (1 s) necesita C y D. La cadena A, C, E tarda 4 + 2 + 1 = 7 s. El trabajo total es 15 s, así que el mejor speed-up es 15 / 7, cerca de 2,1.

A(4) --\
         +--> C(2) --\
B(3) --/             +--> E(1)
D(5) ---------------/

cadena más larga: A -> C -> E = 7 s

Tres trampas

• Pedazos desiguales. Contar primos por división cuesta más para números grandes. Si 4 trabajadores reciben 4 bloques iguales de números, el que tomó el bloque más alto termina último y los demás quedan parados.
• Pedazos demasiado pequeños. Crear una tarea para cada una de 10 millones de iteraciones diminutas cuesta más que el trabajo mismo. Agrupa las iteraciones en bloques. Eso es granularidad.
• Demasiados hilos. Si 8 peticiones inician 8 hilos cada una en una máquina de 8 núcleos, 64 hilos pelean por 8 núcleos. Esto se llama oversubscription (exceso de hilos). Agrega cambios de contexto y pelea de caché, sin velocidad extra. Usa un solo pool de trabajadores del tamaño del número de núcleos.

Speed-up, eficiencia y escalabilidad

¿Cómo decimos que un programa paralelo es "bueno"? Midiéndolo. Dos números hacen casi todo el trabajo.

• Speed-up: S(N) = T(1) / T(N). Es el tiempo con 1 trabajador dividido por el tiempo con N trabajadores, ambos en tiempo de reloj (wall-clock). El sueño es S(N) = N, el speed-up lineal.
• Eficiencia: E(N) = S(N) / N. Dice cuánto de cada trabajador se convirtió en ganancia. Con speed-up lineal, E vale 1, o 100%.

Ejemplo: un programa tarda 120 s con 1 trabajador y 20 s con 8. El speed-up es 120 / 20 = 6. La eficiencia es 6 / 8 = 75%. Una cuarta parte de la capacidad pagada no se convirtió en ganancia: 120 s de trabajo ocuparon 8 x 20 = 160 s de trabajadores.

La eficiencia suele caer

Una tabla de speed-ups engaña, porque el speed-up sigue subiendo mientras cada nuevo trabajador ayuda menos. Mira la eficiencia:

Escalabilidad fuerte y débil

Ejemplo de escalabilidad débil: 1 trabajador resuelve un problema de tamaño n en 50 s. 8 trabajadores resuelven un problema de tamaño 8n en 62,5 s. La eficiencia débil es 50 / 62,5 = 80%. El speed-up escalado (tiempo que un trabajador tardaría en el problema grande, dividido por el tiempo real) es 8 x 0,8 = 6,4.

Compara con la base correcta

El programa paralelo con 1 trabajador ya paga por dividir y esperar. Si divides por ese tiempo, el programa parece mejor de lo que es. Este repositorio usa el mejor programa secuencial como base (speed-up absoluto). Ejemplo: el secuencial tarda 10 s, el paralelo tarda 12,5 s con 1 hilo y 3,125 s con 4 hilos. Contra sí mismo, 12,5 / 3,125 = 4 parece perfecto. El speed-up real es 10 / 3,125 = 3,2.

¿Puede el speed-up superar N?

A veces sí, y se llama speed-up superlineal. Ocurre cuando el trabajo paralelo se vuelve más barato, y no solo repartido. La causa más común es la caché: el arreglo completo no cabe en la caché de un núcleo, pero un octavo sí, así que cada núcleo lee de memoria rápida. Otra causa es una búsqueda en la que un trabajador encuentra la respuesta pronto y detiene a los demás.

Leyes de Amdahl y de Gustafson

Estás haciendo una pizza. La masa debe reposar 10 minutos, y solo una persona puede esperarla. Diez cocineros no hacen que la masa repose más rápido. Esa espera es la parte serial. El resto (cortar los ingredientes) se puede repartir.

Ley de Amdahl

Llama s a la porción del tiempo secuencial que no se puede paralelizar (0,1 es 10%). Solo la otra parte, 1 - s, se reduce cuando añadimos N trabajadores:

S(N) = 1 / ( s + (1 - s) / N )

N -> muy grande:   S -> 1 / s

El término (1 - s) / N es la parte paralela una vez repartida entre N trabajadores, como fracción del tiempo original. El speed-up nunca pasa de 1 / s. Con s = 10%, el techo es 10, incluso con mil procesadores, porque el 10% serial sigue corriendo en un solo trabajador.

Practica con números:

1. 80% paralelo, 4 procesadores: el tiempo pasa a ser 0,2 + 0,8 / 4 = 0,4, así que el speed-up es 2,5.
2. Un programa de 100 s con 10 s de trabajo serial debe terminar en 25 s. Entonces 10 + 90 / N es como máximo 25, luego N es al menos 6 (no los 4 de la estimación lineal).
3. Fracción serial del 25%: con 8 procesadores S es 2,91, con 16 es 3,37. El doble de hardware, solo cerca de 16% más de velocidad. Cerca del límite, cada nuevo trabajador devuelve menos.

Ley de Gustafson

Gustafson mira la misma historia desde otro lado. Cuando tenemos más trabajadores, normalmente no corremos el mismo problema pequeño más rápido: corremos un problema mayor en el mismo tiempo (una imagen más nítida, un mapa del clima más fino). La parte paralela crece con el problema, la parte serial casi no. El speed-up escalado es:

S(N) = s' + (1 - s') * N

s' = fracción serial medida en la ejecución PARALELA

Ejemplo: una ejecución en 16 procesadores gasta 10% del tiempo en código serial. S = 0,1 + 0,9 x 16 = 14,5.

¿Se contradicen las dos leyes?

No. Son el mismo cálculo con la fracción serial medida sobre bases distintas. Amdahl mide s sobre el tiempo de la ejecución secuencial. Gustafson mide s' sobre el tiempo de la ejecución paralela y reconstruye lo que tardaría un procesador. El vínculo es s = s' / (s' + (1 - s') x N). Una fracción que parece grande en tiempo paralelo es pequeña en tiempo secuencial.

Ajustar la ley a números reales

La métrica de Karp-Flatt da vuelta a Amdahl. A partir de un speed-up medido S en N procesadores, entrega la fracción serial que lo explicaría: s = (1/S - 1/N) / (1 - 1/N). Ejemplo: S = 4 con N = 8 da (0,25 - 0,125) / 0,875, cerca de 14%.

Luego observa cómo se comporta s cuando N crece. Si se mantiene constante, la velocidad perdida viene de código realmente serial. Si crece (5% con 2 procesadores, 8% con 4, 14% con 8), la causa es overhead: espera, pelea de caché, carga desbalanceada. Acortar el código serial no lo arreglaría.

Fork-join y robo de trabajo

La profesora te pide sumar todos los números de una lista larga. Cortas la lista en dos y le pides a un amigo que sume una mitad mientras tú sumas la otra. Luego esperas al amigo y sumas las dos respuestas. Acabas de hacer fork-join.

• Fork: una tarea crea subtareas que pueden correr en paralelo.
• Join: la tarea espera a que todas terminen antes de continuar.
• Cada fork tiene su join, así que el programa vuelve a ser secuencial en puntos claros, y el resultado es fácil de razonar.

El join también es una regla de seguridad. Cuando retorna, todo lo que hizo el otro trabajador ya ocurrió y es visible. Si lees la cuenta parcial del amigo antes del join, puedes obtener un valor a medias o una data race.

suma(0..800)
  fork -> suma(0..400)    suma(400..800)
            fork            fork
          200  200        200  200
          (hojas: se suman con un bucle simple)
  join <- suma las dos mitades

El cutoff (tamaño del grano)

Seguimos dividiendo hasta que un pedazo es menor que un límite llamado cutoff, y entonces lo sumamos con un bucle simple. Cutoff demasiado pequeño: se gasta más tiempo creando y planificando tareas que sumando. Cutoff demasiado grande: pocas tareas, y algunos núcleos se quedan sin nada. Un buen grano cuesta mucho más que el overhead de una tarea y aun así produce muchas más tareas que núcleos.

División estática y dinámica

Imagina una imagen de 8 filas. Las filas 0 a 3 cuestan 2 ms cada una, las filas 4 a 7 cuestan 10 ms cada una. Dos trabajadores:

La forma dinámica cuesta un acceso al contador compartido por pedazo, un precio pequeño por el equilibrio.

Robo de trabajo (work stealing)

Los pools modernos (fork-join de Java, Rayon en Rust, Go, Cilk) usan work stealing. Cada trabajador tiene su propia lista de tareas, una deque. Trabaja desde su extremo, de la tarea más nueva a la más vieja (LIFO). Cuando su lista se vacía, roba una tarea de otro trabajador, por el extremo opuesto, la tarea más antigua.

¿Por qué la tarea más antigua? En una recursión de divide y vencerás, la tarea más antigua suele ser la mayor, así que un robo trae mucho trabajo. La tarea más nueva es pequeña y sus datos aún están calientes en la caché del dueño. Otra ventaja: con una única cola central, todos los trabajadores pelean por la misma puerta. Con robo, el camino normal es local, y los trabajadores hablan entre sí solo cuando alguien queda ocioso.

Trabajo y span

• Trabajo (work) T1: el tiempo con 1 procesador (la suma de todas las operaciones).
• Span Tinf: el tiempo con procesadores ilimitados (el camino crítico).
• Un planificador voraz (greedy) garantiza Tp <= T1 / P + Tinf. Ningún planificador supera max(T1 / P, Tinf).
• Paralelismo es T1 / Tinf. Limita el speed-up para cualquier número de procesadores.

Ejemplos: T1 = 240 s y Tinf = 6 s con P = 8 da como máximo 240 / 8 + 6 = 36 s. T1 = 1.000 s y Tinf = 10 s tiene paralelismo 100, así que 100 procesadores bastan para acercarse al límite y los otros 900 de una máquina de 1.000 procesadores se desperdician.

Reducciones y ordenamiento paralelos

Una reducción (reduction) exprime muchos valores en uno solo: la suma de una lista, el número mayor, la cuenta de primos. De forma secuencial recorres la lista con un total corriente. En paralelo, le das a cada trabajador un bloque (chunk), cada uno reduce su bloque en una variable local, y al final se combinan los resultados parciales.

Como cada trabajador escribe solo en su parcial, nadie pelea durante el trabajo.

¿Qué operadores son seguros?

Una reducción por bloques calcula (a op b) op (c op d) en lugar de ((a op b) op c) op d. Ambas coinciden para cualquier entrada solo si el operador es asociativo: la agrupación no importa.

Prueba con la resta en [8, 4, 2, 1]: secuencial ((8 - 4) - 2) - 1 = 1. En dos bloques, (8 - 4) - (2 - 1) = 3. Distinto, así que la resta no se puede reducir en paralelo.

La reducción en árbol

Con procesadores ilimitados, combina los valores en pares, luego los pares de pares, y así sucesivamente. El número de valores se reduce a la mitad en cada paso.

8 valores:  a b c d e f g h
paso 1:     ab  cd  ef  gh
paso 2:      abcd    efgh
paso 3:        abcdefgh

El número de pasos (la profundidad) es ceil(log2 n). El total de operaciones sigue siendo n - 1, igual que en la forma secuencial. Para 1.000 valores: 10 pasos y 999 operaciones.

Suma de prefijos (scan)

La suma de prefijos da en cada posición i la combinación de los elementos de 0 a i. El bucle usual usa el resultado anterior, así que parece imposible de paralelizar. Con un operador asociativo se resuelve en dos pasadas sobre un árbol: el up-sweep guarda la suma de cada bloque, y el down-sweep entrega a cada posición la suma de todo lo que está a su izquierda. El trabajo es O(n) y la profundidad O(log n): para n = 8, 3 niveles en cada pasada.

Merge sort en paralelo

El merge sort es natural para el paralelismo. El arreglo se corta por la mitad, y las dos mitades se ordenan sin tocarse, así que pueden ser dos tareas paralelas. La dependencia aparece solo en la mezcla (merge), que necesita ambas mitades listas.

Pero si cada merge es secuencial, el camino crítico tiene un merge completo por nivel: n + n/2 + n/4 + ..., menos que 2n. Para n = 1.024 el trabajo es cerca de 1.024 x 10 = 10.240 y el span cerca de 2.047, así que el mejor speed-up queda cerca de 5, sin importar cuántos procesadores tengas. Para ir más allá, hay que paralelizar el propio merge.

Sample sort

Con p trabajadores, el sample sort usa p - 1 valores llamados separadores (splitters) para dividir la entrada en p cubetas, una por trabajador. Cada uno ordena su cubeta, y las cubetas unidas en orden ya están ordenadas. El tiempo paralelo es el de la cubeta mayor, así que unos separadores malos lo arruinan todo. La solución: tomar una muestra aleatoria de los datos, ordenarla y usar sus cuantiles como separadores. Así las cubetas quedan con tamaños casi iguales.

Map-reduce y otros patrones paralelos

Un patrón es una receta que la gente reutiliza. Imagina una escuela que cuenta los votos por la mejor fruta. Varios ayudantes leen unas cuantas papeletas cada uno y anotan "banana: 1" por cada una (eso es map). Luego todas las notas de "banana" van a la misma caja (eso es shuffle), y un ayudante por caja las suma (eso es reduce).

MapReduce paso a paso

entrada map (muchas máquinas)    shuffle        reduce

libro 1 -> (el,1)(gato,1)(el,1) -+
libro 2 -> (gato,1)(se sentó,1) -+--> el: [1,1]    -> el: 2
libro 3 -> (el,1)(tapete,1)     -+    gato: [1,1]  -> gato: 2
                                      se sentó: [1] -> se sentó: 1

• Map aplica la misma función a cada registro y emite cero o más pares clave-valor. Los registros no dependen unos de otros, así que corren en cualquier orden en tantas máquinas como tengas.
• Shuffle mueve y agrupa los pares para que todos los valores de una clave lleguen al mismo lugar. Una función de partición (a menudo un hash de la clave) elige el reducer. Suele ser el paso que más usa la red.
• Reduce se llama una vez por clave, con todos los valores de esa clave. Claves distintas se pueden reducir en paralelo.

El combiner

Mandar un millón de pares (el, 1) por la red es una tontería. Un combiner es un pequeño reduce que corre dentro de cada tarea map, antes del shuffle. Con 3 tareas map que emiten 1.000 pares cada una, con 50 palabras distintas, el combiner deja solo 50 registros por tarea, así que 150 registros van al shuffle en lugar de 3.000. Solo es válido cuando la operación es asociativa y conmutativa, como la suma. Un promedio no se puede combinar así, a menos que lleves también la cuenta.

Fallos y claves calientes

• Reejecución. Si un trabajador muere en medio de una tarea map, el master corre la misma tarea en otro nodo. Es seguro porque la entrada no cambia y la función map es pura (misma entrada, misma salida, sin efectos secundarios). Se llama tarea idempotente. Un map que escribe en una base de datos o lee el reloj podría duplicar o alterar resultados.
• Clave caliente (hot key). Si una clave concentra el 55% de todos los pares, un reducer recibe esa parte y la fase termina cuando él termina. Duplicar el número de reducers solo redistribuye las otras claves. Soluciones: un combiner, o dividir la clave caliente en subclaves y sumar en dos etapas.

Otros patrones

Ejemplo de scatter-gather: una búsqueda envía una consulta a 20 particiones del índice y espera a todas. Diecinueve responden en 20 ms y una en 200 ms. La unión tarda 5 ms. La respuesta llega después de 205 ms, porque un ayudante lento decide.

Ejemplo de stencil: a[i] = (a[i-1] + a[i+1]) / 2 escrito en el mismo arreglo falla cuando los hilos dividen el rango de índices, porque una celda puede tener ya el valor nuevo cuando su vecina la lee. El double buffering hace que el resultado no dependa del orden.

Determinismo y reproducibilidad

Si le pides "2 + 2" a una calculadora diez veces, siempre da 4. Un programa paralelo determinista es así: su salida depende solo de la entrada. El planificador puede intercalar los hilos de forma distinta en cada ejecución, pero todos los caminos llevan a la misma respuesta. Eso permite probar la versión paralela comparándola con la secuencial.

Data race y condición de carrera

Una data race ocurre cuando dos hilos tocan la misma posición de memoria, al menos uno escribe, y nada ordena los accesos (ni lock, ni operación atómica, ni join). El valor final depende de la suerte. En C y C++ el comportamiento queda indefinido. Rust seguro rechaza ese código al compilar.

Una condición de carrera (race condition) es más amplia: un resultado que depende de cómo se intercalan los hilos. Puedes tener una race condition sin data race. Mira este código de comprobar-y-actuar, donde cada método bloquea la cuenta por dentro:

// dos hilos ejecutan esto a la vez, el saldo empieza en 100
if acct.Balance() >= 100 { // bloquea, lee, desbloquea
	acct.Withdraw(100) // bloquea, resta, desbloquea
}

Los dos hilos ven 100, los dos retiran, y el saldo termina en -100. La decisión tomada en la comprobación ya no era verdadera cuando se ejecutó la acción. La solución es hacer que la comprobación y la acción sean un único paso atómico (una sola sección crítica, o un método que comprueba y retira).

Por qué las sumas paralelas son exactamente iguales, o no

Contar primos con contadores locales y sumarlos después del join da exactamente la respuesta secuencial con cualquier número de hilos. La suma de enteros es asociativa y conmutativa, así que la agrupación no importa. Comparar por igualdad exacta es válido.

Los números decimales (coma flotante, como double) son distintos. Cada suma redondea su resultado al valor más cercano que el computador puede guardar, así que (a + b) + c puede diferir de a + (b + c). Toma [1e16, -1e16, 1.0], donde los vecinos de 1e16 están a 2 de distancia. De izquierda a derecha: (1e16 - 1e16) + 1 = 1. Dividiendo en [1e16] y [-1e16, 1.0]: el segundo parcial es -1e16 + 1, que se redondea de vuelta a -1e16, y el total es 0. Otra respuesta, y muy distinta.

Números aleatorios y orden de la salida

• Números aleatorios. En una simulación Monte Carlo con tareas repartidas dinámicamente, ata la aleatoriedad al índice de la tarea, no al hilo. Cada tarea crea su generador con una semilla calculada a partir de la semilla base y de su índice, de preferencia con un generador hecho para flujos independientes.
• Orden de la salida. Los trabajadores terminan en un orden impredecible. Haz que cada resultado lleve su posición lógica: escribe el resultado i en la posición i, o devuelve parciales con su índice y combínalos en orden de índice después del join. El orden de ejecución queda libre, y el orden de la salida queda fijo.

El tiempo no es determinista

Aun cuando el resultado sea idéntico, el tiempo varía: 410 ms en una ejecución, 470 ms en la siguiente. Cambian el planificador, la carga de la máquina, el estado de la caché y la frecuencia de la CPU. Un benchmark reproducible usa la misma entrada y la misma máquina, deja fuera el calentamiento (warm-up), repite la ejecución varias veces, informa la dispersión junto con el valor central y registra la máquina, las versiones y el comando exacto.

Falso compartir (false sharing) y efectos de cache

La memoria es lenta, así que cada núcleo guarda una pequeña copia rápida de lo que usa, llamada caché. Pero la caché no guarda variables sueltas. Guarda bloques llamados líneas de caché, normalmente de 64 bytes. Toca un byte y entra el bloque entero de 64 bytes.

Falso compartir (false sharing)

Cuando un núcleo escribe en una línea, las copias de esa línea en los otros núcleos se invalidan (se tiran) para que todos sigan coherentes. Si variables de hilos distintos están en la misma línea, los núcleos se la quitan unos a otros, aunque no compartan ningún dato real. Esto es el falso compartir.

una línea de caché de 64 bytes (8 contadores de 8 bytes)
[c0][c1][c2][c3][c4][c5][c6][c7]
  ^   ^   ^   ^   ^   ^   ^   ^
  8 hilos en 8 núcleos, cada uno suma en su ci
  -> la línea rebota entre los núcleos

Contando quién estorba a quién: el desplazamiento en bytes dividido por 64 da la línea. 16 contadores de 8 bytes que empiezan en el límite de una línea: los contadores 0 a 7 están en la línea 0 y 8 a 15 en la línea 1. El hilo 3 pelea con los otros 7 hilos de su grupo, y los dos grupos no se molestan entre sí.

Cómo detectarlo

La firma: sin locks, todos los núcleos al 100%, tiempo paralelo igual o peor que el secuencial (por ejemplo 2,0 s con 1 hilo y 3,1 s con 4), y una mejora drástica (a 0,52 s) cuando solo separas los contadores 64 bytes. Los núcleos están ocupados, pero esperando que la línea vuelva.

Cómo arreglarlo

• Acumula en una variable local dentro del bucle caliente y entrega el total una vez, al terminar el bucle. La línea que modifica el trabajador pasa a ser solo suya, y la unión ocurre una vez por trabajador.
• Rellena o alinea cada contador en su propia línea, por ejemplo con alignas(64) en C++. El precio es memoria: 8 bytes pasan a ser 64, así que un arreglo de 8 de esas structs crece de 64 a 512 bytes.

Localidad espacial

Como un fallo (miss) carga una línea entera, usar datos vecinos es barato. Una matriz de 1024 x 1024 enteros de 4 bytes guardada por filas: un fallo trae 16 enteros, así que recorrer fila por fila falla 1 vez de cada 16, cerca de 65.536 fallos en total (1.048.576 / 16). Recorrer por columnas salta 4.096 bytes en cada paso. Si la caché no aguanta las 1.024 líneas de una columna, cada acceso falla: 16 veces más.

Limitado por CPU frente a limitado por memoria

Un bucle que cuenta primos casi no usa memoria, y cada núcleo trae su propio poder de cálculo, así que escala casi linealmente (7,6 veces con 8 hilos). Un bucle que suma un arreglo de 16 GiB depende del rendimiento de los canales de memoria, un recurso compartido por todos los núcleos. Cuando se satura, más hilos solo se reparten el mismo ancho de banda: 2,9 veces con 4 hilos y ninguna mejora con 8.

SIMD y vectorización

El paralelismo también vive dentro de un núcleo. Imagina un sello que imprime 8 puntos a la vez en lugar de 1. Eso es SIMD, de Single Instruction, Multiple Data (una instrucción, varios datos). Un registro vectorial guarda varios números del mismo tipo, y una instrucción suma, multiplica o compara todos juntos.

Es independiente de los hilos, y los dos se pueden combinar. En la taxonomía de Flynn:

Carriles (lanes)

El número de elementos por instrucción (los lanes) es el ancho del registro dividido por el ancho del elemento. Un registro de 256 bits y floats de 32 bits dan 256 / 32 = 8 lanes. Ese también es el techo de la ganancia del cuerpo del bucle. En la práctica se gana menos por el bucle de resto, el acceso a memoria y la menor frecuencia en algunas CPU.

Cuando n no es múltiplo del ancho, el compilador hace dos bucles: el bucle vectorial corre floor(n / 8) veces y el bucle de resto atiende los últimos n mod 8 elementos uno a uno. Para 1.003 floats: 125 iteraciones vectoriales (1.000 elementos) y 3 escalares. En arreglos cortos el resto puede ocultar la ganancia del SIMD.

Auto-vectorización

El compilador puede hacerlo solo. Analiza un bucle escalar y, si puede probar que el resultado no cambia, emite instrucciones vectoriales. Tú ayudas manteniendo el bucle simple: iteraciones independientes, sin llamadas a funciones opacas, sin duda sobre el solapamiento de arreglos.

Qué bloquea la vectorización

• Dependencia entre iteraciones (loop-carried). En a[i] = a[i-1] + b[i] cada elemento necesita el que se acaba de escribir (una suma de prefijos), así que 8 elementos no se pueden calcular juntos. En cambio a[i] = a[i+1] + b[i] está bien: el valor leído es siempre el original.
• Aliasing de punteros. Con float *dst, const float *src, el compilador debe admitir que los dos pueden solaparse, lo que crearía una dependencia. Añade una comprobación en tiempo de ejecución, o quitas la duda con el calificador restrict en C. Las porciones &mut y & de Rust ya garantizan que no hay solapamiento.
• Ramas por elemento. Un vector tiene un solo flujo de control, así que if (a[i] > 0) b[i] = a[i] * 2 se convierte en dato: la comparación construye una máscara, el trabajo se hace en todos los lanes, y la máscara decide qué se guarda (if-conversion). El costo es hacer trabajo que se descarta, así que la ganancia baja cuando la rama es cara y rara vez se toma.

// vectoriza: las iteraciones son independientes
for (int i = 0; i < n; i++) c[i] = a[i] + b[i];

// no vectoriza: cada paso necesita el resultado anterior
for (int i = 1; i < n; i++) a[i] = a[i - 1] + b[i];

Fundamentos de computación en GPU

Una CPU es como 8 profesores muy inteligentes: cada uno resuelve rápido problemas difíciles y distintos. Una GPU (unidad de procesamiento gráfico) es como un estadio lleno de miles de alumnos, cada uno simple, a quienes se les manda hacer el mismo cálculo pequeño al mismo tiempo sobre números distintos.

El kernel

En la CPU escribes for (i = 0; i < n; i++) out[i] = f(in[i]). En la GPU escribes solo el cuerpo, como una función llamada kernel, y la lanzas sobre un espacio de índices de n posiciones. Cada hilo recibe su índice de hilo, que hace el papel de i, y atiende un elemento. Esto solo es correcto cuando las iteraciones son independientes, la misma condición del paralelismo de datos en la CPU.

Por qué duelen las ramas y los punteros encadenados

Una GPU agrupa hilos que ejecutan la misma instrucción juntos, como los lanes de un vector. Si una rama manda la mitad del grupo por un lado y la otra mitad por el otro, el hardware recorre los dos caminos uno tras otro, y el rendimiento cae. Los núcleos simples tampoco tienen la predicción de saltos ni las cachés grandes con que una CPU absorbe código irregular.

¿Vale la pena el viaje?

La GPU tiene su propia memoria. Los datos deben copiarse allí y de vuelta, e iniciar un kernel tiene un costo fijo. Así que el tiempo en la GPU tiene tres partes: cálculo, transferencia, lanzamiento.

Ejemplo: la CPU cuesta 40 ns por elemento. La GPU calcula en 4 ns por elemento, copiar cuesta 6 ns por elemento, y el lanzamiento cuesta 30 ms fijos. La ganancia por elemento es 40 - (4 + 6) = 30 ns. El punto de equilibrio es 30 ms / 30 ns = 1.000.000 de elementos. Por debajo, gana la CPU. Si la copia costara más que el ahorro en cálculo, la GPU nunca valdría la pena.

Amdahl sigue valiendo para cualquier acelerador. Un programa tarda 100 s: 80 s en un kernel y 20 s que deben quedarse en la CPU. El kernel se vuelve 20 veces más rápido (4 s), y las transferencias suman 6 s. Nuevo tiempo: 20 + 4 + 6 = 30 s, speed-up 3,33. Sin las transferencias serían 24 s y 4,17. El límite con un kernel infinitamente rápido es 100 / 20 = 5. La transferencia es un nuevo término serial que no existía en la versión secuencial.

Memoria compartida y distribuida

Dos formas de organizar ayudantes. En un salón de clases con una pizarra grande, todos leen y escriben en la misma pizarra. Eso es memoria compartida. En un grupo de amigos en casas distintas, cada uno tiene su cuaderno, y se llaman por teléfono para intercambiar información. Eso es memoria distribuida.

Los hilos comparten, los procesos en otros nodos envían

Los hilos de un proceso comparten el heap y las variables globales; cada uno tiene solo su pila y sus registros. La comunicación es directa, y las escrituras concurrentes exigen sincronización. En memoria distribuida cada proceso ve solo su memoria. Quien tiene el dato lo envía y quien lo necesita lo recibe. Tú decides qué, a quién y cuándo, y pagas el costo de copiarlo por la red.

Ejemplo: sumar 1.000.000 de enteros de 8 bytes con 4 trabajadores. Con hilos, cada uno recibe un puntero y una longitud: no se copia ni un byte. Con paso de mensajes, un master envía un cuarto a cada trabajador: 4 mensajes de 2.000.000 de bytes cada uno, 8.000.000 de bytes de ida, más 4 respuestas de 8 bytes, 32 bytes de vuelta, en 8 mensajes.

UMA y NUMA

La memoria compartida tiene dos formas. En UMA (acceso uniforme a memoria) toda CPU tarda lo mismo en alcanzar cualquier dirección. En NUMA (no uniforme) cada nodo tiene CPU y un banco de memoria cercanos. El acceso local es rápido, y leer una página que vive en otro nodo es más lento. El programa sigue siendo correcto, pero el rendimiento depende de mantener los datos cerca de quien los usa.

Por qué las máquinas distribuidas llegan a más procesadores

En memoria compartida, cada nueva CPU compite por el mismo bus, el mismo ancho de banda de memoria y el mismo tráfico de coherencia de caché. En memoria distribuida cada nodo es un computador completo, así que no hay un único punto de contención. El precio: toda cooperación cuesta mensajes, así que el algoritmo debe comunicarse poco.

Memoria compartida distribuida (DSM)

Una DSM basada en páginas crea la ilusión de memoria compartida sobre mensajes. Tocar una página ausente provoca un fallo (page fault), y el manejador busca la página en otro nodo. La unidad es la página entera, así que dos variables x e y sin relación en la misma página, escritas por los nodos A y B, hacen que la página rebote por la red. Es falso compartir otra vez, a mayor escala, y se llama thrashing.

Programas híbridos

Muchos programas mezclan ambos: procesos con paso de mensajes entre nodos (por ejemplo MPI) e hilos dentro de cada nodo. Cada capa trae sus propios bugs. Una data race solo puede ocurrir donde la memoria es común, es decir, entre hilos del mismo proceso. Un deadlock no necesita memoria común: dos procesos que hacen cada uno un receive bloqueante del otro antes de enviar esperarán para siempre.

Juntando todo

Este repositorio midió estas ideas en el mini-proyecto scaling-by-cores: cuenta primos y renderiza una imagen de Mandelbrot en Rust, Go y C++ con 1, 2, 4 y 8 trabajadores, con división estática y dinámica. Las 72 ejecuciones imprimieron exactamente los mismos resultados que los programas secuenciales (una reducción determinista y un escritor por píxel).

El mismo código, solo cambió la división, y el speed-up se duplicó. La división estática dio las filas caras del medio a pocos trabajadores y los demás esperaron. La ley de Amdahl leyó esa espera como código serial: una fracción serial ajustada cercana al 30%, en un programa que casi no tiene ninguna. Con la división dinámica cayó por debajo del 7%. La lección: antes de culpar a Amdahl, comprueba que cada trabajador esté ocupado hasta el final.

Una lista de revisión para un programa paralelo lento

Qué herramienta para qué problema