Saltar a contenido

OpenMP en C++

Lo que se vio en la sesión: cómo repartir un ciclo entre hilos escribiendo una línea, qué protege cada directiva, cuánto cobra, y cómo comprobar que el programa de verdad usó los hilos que uno pidió. Las diapositivas están en el Campus Virtual; aquí quedan las cuentas, las mediciones y el código que se corrió.

El recorrido manda sobre el número de hilos

Dos ciclos que escriben la misma matriz de 10 000 por 10 000 y solo se diferencian en cuál índice va por fuera:

// A, por filas
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        arr[i][j] = i + j;

// B, por columnas
for (int j = 0; j < n; j++)
    for (int i = 0; i < n; i++)
        arr[i][j] = i + j;
Recorrido Tiempo
A, por filas 6,7 s
B, por columnas 126,7 s

Casi diecinueve veces, sin tocar un solo hilo. La memoria no entrega enteros sueltos: entrega líneas de 64 bytes. Un int ocupa 4, así que en cada línea caben 16 enteros. El recorrido A pide arr[0][0], falla, trae la línea y acierta en los quince accesos siguientes; vuelve a fallar en el dieciseisavo. El recorrido B salta 40 000 bytes entre un acceso y el siguiente: cada uno cae en una línea distinta y los dieciséis enteros que se trajeron se desperdician.

Paso A, por filas Caché B, por columnas Salto Caché
1 arr[0][0] fallo arr[0][0] 0 B fallo
2 arr[0][1] acierto arr[1][0] 40 000 B fallo
16 arr[0][15] acierto arr[15][0] 600 000 B fallo
17 arr[0][16] fallo arr[16][0] 640 000 B fallo

Esa es la cuenta que conviene tener a mano: 64 ÷ 4 = 16. Con double, de 8 bytes, serían 8 por línea.

Falsa compartición

La línea también es la unidad con que el hardware mantiene la coherencia entre núcleos. Dos hilos que escriben posiciones distintas del mismo arreglo (uno arr[0] a arr[7], el otro arr[8] a arr[15]) caen en la misma línea de 64 bytes. Cada escritura de uno invalida la copia del otro, y los dos se pasan la línea de un lado a otro sin compartir un solo dato.

No da resultados malos, da lentitud: un programa paralelo que corre más lento que el secuencial sin que nadie toque la misma variable. Se evita dando a cada hilo un bloque contiguo grande, acumulando en una variable local y combinando al final, o separando los acumuladores a una línea completa de distancia.

Una directiva, no una biblioteca

OpenMP se escribe como anotaciones sobre el código que ya existe:

#pragma omp parallel for reduction(+ : c)
for (int i = 0; i < n; i++)
    c += a[i] * b[i];

Un compilador que no sepa de OpenMP descarta la #pragma y deja el ciclo secuencial. El mismo archivo produce las dos versiones según la bandera:

g++ -O2 -Wall -Wextra equipo.cpp -o secuencial           # un hilo
g++ -O2 -Wall -Wextra -fopenmp equipo.cpp -o paralelo    # equipo de hilos

De ahí salen dos ventajas: no hay dos copias del programa que mantener sincronizadas, y donde no haya soporte el código sigue compilando y dando el mismo resultado, solo que más lento.

-Wall -Wextra van siempre. En paralelismo los errores caros son los que el compilador señala y nadie lee: una variable sin usar que delata un private mal puesto, un índice con signo distinto, una #pragma que no aplica a la línea que sigue.

Cuántos hilos arrancan

El equipo arranca por defecto con tantos hilos como hilos lógicos tenga la máquina. En la del salón, seis núcleos físicos con dos hilos cada uno:

./entorno
omp_get_max_threads() = 12
omp_get_dynamic()     = 0
omp_get_schedule()    = dynamic, trozo 1

Se cambia por variable de entorno, que es lo más usado, o desde el programa con omp_set_num_threads(4). Hay dos preguntas distintas que se confunden: omp_get_max_threads() responde cuántos hilos usaría la próxima región y se puede llamar desde código secuencial; omp_get_num_threads() responde cuántos hay en la región donde se ejecuta la llamada, y fuera de una región vale 1 siempre.

OMP_DYNAMIC=true autoriza a la biblioteca a usar menos hilos de los pedidos si la máquina está cargada, y entonces dos corridas idénticas dan tiempos distintos. Para medir se deja en false.

Las directivas de la sesión

#pragma omp parallel { ... }        // región paralela
#pragma omp parallel for            // reparte las iteraciones del ciclo
#pragma omp parallel for reduction(<op> : <variable>)

Variables. Qué ve cada hilo lo deciden tres cláusulas:

Cláusula ¿Copia por hilo? ¿Valor al entrar? ¿Se ve afuera?
shared no el de afuera sí
private sí sin inicializar no
firstprivate sí el de afuera no

El error común es leer una variable private suponiendo que trae el valor que tenía antes de la región. No lo trae: llega sin inicializar. Para eso está firstprivate.

Carreras de datos. Tres mecanismos, de menor a mayor costo:

Mecanismo Cuándo aplica Costo
reduction acumular con un operador asociativo el menor: sin bloqueos dentro del ciclo
atomic una sola lectura y escritura sobre un escalar bajo, lo resuelve el hardware
critical varias instrucciones que van juntas alto: serializa el bloque entero

Un critical dentro de un ciclo caliente puede dejar el programa más lento que la versión secuencial, porque los hilos hacen fila en cada iteración.

Tareas y sincronización. sections reparte tareas distintas entre hilos: procesar audio, video y subtítulos a la vez. barrier hace que todos esperen, single deja que uno cualquiera ejecute un bloque y master que lo haga el principal.

Reparto de iteraciones. schedule elige cómo se reparten, y con carga desigual la diferencia se nota:

Política Tiempo
static 57,05 ms
dynamic, 2 49,83 ms
guided 58,93 ms
dynamic, 1000 66,26 ms

Carga uniforme, static, que no cuesta nada decidir. Carga variable, dynamic, que entrega trabajo a quien se desocupa. Y el tamaño del trozo importa: con 1000 los últimos hilos se quedan con un bloque enorme mientras los demás esperan.

Ciclos anidados. El anidamiento viene apagado: una región dentro de otra corre con un equipo de un hilo. Se habilita con OMP_MAX_ACTIVE_LEVELS=2, pero con doce núcleos un equipo externo de doce que abre doce cada uno pide 144 hilos a una máquina que puede correr doce. Lo habitual es collapse(2), que funde los dos ciclos y reparte el producto entre un solo equipo.

La reducción de una matriz, medida

Sumar los 10⁸ elementos de una matriz de 10 000 por 10 000:

Versión Tiempo
Sin OpenMP 237,78 ms
OpenMP, recorrido por filas 47,72 ms
OpenMP, recorrido por columnas 140,24 ms

La versión paralela por columnas es tres veces más lenta que la paralela por filas. Los hilos no arreglan el patrón de acceso: lo multiplican.

Dos errores que dejan el programa mudo

Vectores de 10⁸ elementos, cuatro hilos:

Escritura Resultado Tiempo
#pragma omp parallel for reduction(+ : suma) 10 000 000 000 31 ms
#pragma omp parallel reduction(+ : suma) 40 000 000 000 120 ms
#pragma parallel reduce(suma : +) 10 000 000 000 73 ms

El primero es el correcto. El segundo olvidó el for: cada hilo recorre el ciclo completo, el resultado sale multiplicado por cuatro y el programa hace cuatro veces el trabajo. El tercero invirtió la sintaxis, el compilador no reconoce la directiva y la descarta en silencio: el resultado es correcto y el tiempo es el del secuencial.

Ninguno de los dos falla ni avisa por su cuenta. Lo que los delata es revisar el valor y compilar con -Wall -Wextra. El segundo es el que más caro sale: el resultado está bien y nadie sospecha, hasta que alguien cronometra.

Tres formas de hacer lo mismo

std::thread TBB OpenMP
Líneas para el ejemplo 14 12 3
Control sobre los hilos total escaso por cláusulas
Balance de carga manual automático schedule
Reutiliza los hilos no sí sí
Dependencias solo el estándar biblioteca externa la bandera
Volver a secuencial reescribir reescribir quitar la bandera

Sobre un vector de un millón, cuatro hilos, el mejor de veinte repeticiones:

Enfoque Tiempo
Secuencial 0,13 ms
std::thread 0,21 ms
TBB parallel_reduce 0,09 ms
OpenMP 0,13 ms

std::thread resulta más lento que el secuencial porque crea y destruye cuatro hilos en cada llamada. El costo se ve mejor repitiendo mil veces el mismo ciclo: OpenMP tarda 24 ms y std::thread 116 ms, cinco veces más. OpenMP mantiene el equipo vivo entre regiones, y de ahí sale la recomendación de agrupar el trabajo en pocas regiones grandes en vez de abrir una por ciclo.

Hasta dónde sube

La integral de 4/(1+x²) entre 0 y 1 con mil millones de rectángulos: puro cálculo, sin tráfico de memoria que lo frene.

Hilos Tiempo Aceleración Eficiencia
1 1 253,6 ms 1,00 100 %
2 637,7 ms 1,97 98 %
4 346,8 ms 3,61 90 %
6 252,6 ms 4,96 83 %
9 227,5 ms 5,51 61 %
12 256,1 ms 4,89 41 %

Hasta seis hilos cada uno tiene su núcleo y la eficiencia se sostiene en 83 %. Del séptimo en adelante dos hilos comparten núcleo y la misma unidad de punto flotante: el tiempo sigue bajando un poco hasta nueve y después sube. El codo de la curva está donde se acaban los núcleos físicos, no donde se acaban los hilos lógicos. Conviene medirlo antes de prometer una aceleración.

La fórmula de Karp-Flatt estima qué fracción del programa es secuencial a partir de la aceleración observada: entre 1,7 % y 4,2 % hasta seis hilos, que es el código secuencial de verdad, y 13,2 % con doce, que ya no es código sino hardware compartido.

Y el techo lo pone Amdahl: con un 10 % secuencial, pasar de doce a sesenta y cuatro hilos gana un 54 % y el límite está en diez, por muchos núcleos que se compren.

Comprobar que hubo paralelismo

El barrido de uno a doce hilos sobre un binario compilado sin -fopenmp da doce tiempos iguales, alrededor de 1 290 ms. Eso no marca el límite de la máquina: marca que falta la bandera.

El valor de pi coincide hasta el décimo decimal entre corridas, pero los últimos bits cambian. La suma en punto flotante no es asociativa, y repartirla entre hilos cambia el orden en que se acumula:

secuencial = 16.695311365857272
paralela   = 16.695311365859137
diferencia = 1.87e-12

Con -ffast-math el compilador se autoriza a reordenar también la versión secuencial. En un cálculo que se compara contra un valor de referencia, esa bandera no va.

Mirar los hilos por dentro

Con el programa corriendo, Ctrl+C lo detiene y el depurador muestra el equipo completo:

g++ -std=c++17 -fopenmp -g -O0 -Wall -Wextra escalado.cpp -o escalado
OMP_NUM_THREADS=4 gdb ./escalado
(gdb) info threads
  Id   Target Id                        Frame
* 1    Thread ... (LWP 9828) "escalado" _Z8integrarv._omp_fn.0 () at escalado.cpp:14
  2    Thread ... (LWP 9831) "escalado" _Z8integrarv._omp_fn.0 () at escalado.cpp:14
  3    Thread ... (LWP 9832) "escalado" _Z8integrarv._omp_fn.0 () at escalado.cpp:14
  4    Thread ... (LWP 9833) "escalado" _Z8integrarv._omp_fn.0 () at escalado.cpp:14
(gdb) thread 3
(gdb) print i
$1 = 500000000
(gdb) print suma
$2 = 0

Tres cosas se leen ahí. La función se llama _omp_fn.0 porque el compilador extrae el cuerpo del ciclo paralelo a una función aparte, y es esa la que ejecutan los hilos. El i del tercer hilo vale 500 millones: con mil millones de iteraciones repartidas en cuatro tramos de 250 millones, a ese le tocó el tercero, que arranca en la mitad del recorrido. Y suma vale 0 porque cada hilo tiene su copia privada de la reducción: el total existe al cerrar la región, no antes.

El -g es el que deja los símbolos y el -O0 el que impide que el optimizador borre las variables; con -O2, print suma responde que el valor fue optimizado.

Para las carreras que no se manifiestan en cada corrida está ThreadSanitizer, que instrumenta cada acceso a memoria y señala archivo, línea y hilo de las dos operaciones en conflicto:

g++ -std=c++17 -fopenmp -fsanitize=thread -g -O1 -Wall -Wextra carrera.cpp -o carrera
OMP_NUM_THREADS=4 ./carrera
WARNING: ThreadSanitizer: data race (pid=22434)
  Write of size 8 at 0x7ffea2fdd5a0 by thread T2:
    #0 main._omp_fn.0 carrera.cpp:9
  Previous read of size 8 at 0x7ffea2fdd5a0 by main thread:
    #0 main._omp_fn.0 carrera.cpp:7
SUMMARY: ThreadSanitizer: data race carrera.cpp:9 in main._omp_fn.0

El programa corre entre cinco y quince veces más lento, así que se usa sobre entradas pequeñas.

Los contadores del procesador cuentan la otra mitad de la historia. Sobre la integral, con un hilo y con doce:

Contador 1 hilo 12 hilos
Tiempo transcurrido 3,803 s 0,850 s
CPU consumida (task-clock) 3 802 ms 7 078 ms
Instrucciones 36,00 × 10⁹ 36,09 × 10⁹
Ciclos 15,06 × 10⁹ 25,71 × 10⁹
Instrucciones por ciclo 2,39 1,40

Las instrucciones son casi las mismas; los ciclos suben un 71 %. Cada instrucción tarda más porque dos hilos comparten las unidades del núcleo. El usuario ve bajar el tiempo de 3,8 a 0,85 segundos; la máquina paga casi el doble de CPU. En un servidor con varios programas encima, esa segunda cifra es la que decide.

El perfilado con perf se trabaja completo en la sesión de herramientas de profiling en Linux.

Los apuntes del tablero

La hoja de la sesión, tal como quedó: los dos recorridos de la matriz con la cuenta de la línea de caché, el producto punto con la reducción marcada, la lista de directivas en el orden en que fueron saliendo y las banderas de aviso que se agregaron a la orden de compilación.

La segunda sesión del tema volvió sobre el modelo de memoria de un programa, que es lo que explica qué comparte un hilo y qué no: la pila de cada hilo, el montículo que todos ven y el código. Al lado, los contextos dentro del procesador, con la pila, la unidad aritmética, el contador de programa y el registro de instrucción, y las variables locales viviendo en el contexto.

Lo que quedó pendiente

Los ejercicios prácticos de OpenMP quedaron para la casa: reparto, schedule, histograma, carrera de datos y sections. Están en el Campus Virtual, traen Makefile y se compilan con make.

Las actividades del navegador siguen el orden de la sesión. En clase se alcanzaron las primeras: el orden del recorrido, cuántos hilos arrancan, la suma que se pierde y qué entra y qué sale de la región. Las que siguen —el reparto de iteraciones, las tres escrituras de la misma reducción, el mismo ciclo en tres bibliotecas, el codo de la curva y cómo comprobar que hubo paralelismo— conviene hacerlas antes de la práctica.

El código de la sesión está completo, con las órdenes de compilación y lo que imprime cada programa.