Introducción del módulo

El módulo 1 explicó por qué paralelizar. Este módulo explica cómo: cómo se escribe software que usa varios núcleos de la misma computadora y, sobre todo, cómo se hace sin introducir errores.

La diferencia con el módulo 3 es fundamental. En OpenMP todos los hilos comparten un mismo espacio de direcciones: pueden leerse y escribirse las variables directamente, sin copiar nada. Esa comodidad es también su peligro. Dos hilos que escriben en la misma variable en el mismo instante producen un resultado que depende del orden de ejecución, y ese resultado cambia entre ejecuciones. Es el problema de la condición de carrera.

OpenMP es el estándar de facto para la programación en memoria compartida. No es una biblioteca con funciones que se llaman: es un conjunto de directivas que el preprocesador interpreta, y el resto del código sigue siendo C o C++ ordinario. Esa simplicidad es su ventaja y también su riesgo: es fácil escribir código paralelo que parece correcto y no lo es.

Competencia que se desarrolla (EC2). Implementar programas paralelos en memoria compartida utilizando OpenMP y técnicas de sincronización, optimizando el rendimiento mediante análisis de carga y detección de patologías de paralelismo.

2.1 Modelo de memoria compartida y concepto de hilos

En un programa secuencial hay un único hilo de ejecución. En un programa paralelo hay varios, y el sistema decide en qué núcleo físico se ejecuta cada uno en cada instante. El programador no controla esa asignación: controla la coherencia entre ellos.

Figura 2.1. Modelo de memoria compartida. Cada hilo tiene su propia caché privada, pero todas apuntan al mismo espacio de direcciones físico. El bus de coherencia mantiene esas cachés al día, y ese tráfico es el que se paga cuando dos hilos tocan la misma variable.

2.1.1 Hilo, proceso y núcleo

Conviene no confundir tres conceptos:

Un proceso es pesado porque implica tablas de paginación, descriptores de archivo y contexto propio. Un hilo es barato porque solo necesita su propio registro de instrucción y su pila. Por eso la programación paralela moderna usa muchos hilos sobre pocos procesos, y no al revés.

2.1.2 El espacio de direcciones compartido

La consecuencia práctica de compartir el espacio de direcciones es que cualquier hilo puede leer y escribir cualquier variable del programa sin ninguna función de paso de mensajes:

/* Los dos hilos suman al MISMO acumulador. No hay copias. */
float total = 0.0f;
#pragma omp parallel for reduction(+:total)
for (int i = 0; i < n; i++) total += a[i];

Ese total es una sola variable en una sola dirección de memoria. Las cachés privadas de los hilos pueden tener copias desactualizadas, y el bus de coherencia las sincroniza. Cuando el paralelismo es denso, ese tráfico de coherencia puede costar más que el propio cálculo.

Nota.

Todo lo que hay que recordar del módulo 1 sigue vigente. El Muro de Memoria y la jerarquía de caché no desaparecen al usar varios hilos: se amplifican. Si dos hilos leen datos lejanos, cada acceso paga la penalización de caché. Por eso el orden de recorrido de los datos y la localidad importa tanto en un programa paralelo como en uno secuencial.

2.2 Condiciones de carrera y problemas de sincronización

Una condición de carrera (race condition) se produce cuando el resultado de un programa depende del orden en que los hilos ejecutan sus instrucciones. Dos corridas del mismo binario pueden dar resultados distintos, y ambos son formalmente válidos.

Figura 2.2. Arriba, sin sincronización: el hilo 0 escribe 1, el hilo 1 escribe 2 y el hilo 0 lee 2. Abajo, con sección crítica: solo un hilo entra a la vez y el invariante se conserva.

2.2.1 Las tres condiciones de Bernstein

Un acceso concurrente a un dato compartido es una carrera si se cumplen las tres condiciones a la vez:

1. Dos hilos o más acceden al mismo dato.
2. Al menos uno de ellos escribe.
3. Los accesos no están sincronizados.

La tercera condición es la que se puede controlar. Si no hay sincronización, y las otras dos se dan, la carrera existe.

2.2.2 Ejemplo mínimo

#include <stdio.h>
#include <omp.h>

int main(void) {
    int contador = 0;

    #pragma omp parallel for reduction(+:contador)
    for (int i = 0; i < 1000000; i++) {
        contador++;           /* versión CORRECTA: reduction serializa la suma */
    }
    printf("contador = %d\n", contador);   /* siempre 1000000 */

    int compartido = 0;
    #pragma omp parallel
    {
        #pragma omp atomic
        compartido++;         /* versión correcta también, pero otra estrategia */
    }
    printf("compartido = %d\n", compartido);

    return 0;
}

Quitar reduction de la primera línea produce un programa que compila sin avisos y devuelve un número distinto en cada ejecución. Ese es el peor tipo de error: no hay diagnóstico.

2.2.3 La clase de error shared, private y firstprivate

Las variables de un programa parallel se clasifican por su ámbito dentro de la región paralela:

Declarar mal un ámbito es la causa más frecuente de resultados incorrectos. private sobre una variable que se pretendía acumulada, o shared sobre una que se pretendía privada, producen fallos que aparecen de forma intermitente.

2.3 Directivas y cláusulas de OpenMP

OpenMP se organiza en directivas que se aplican con #pragma omp. La forma más común combina una directiva de control y una cláusula que modifica su comportamiento.

Figura 2.3. La directiva parallel for abre una región paralela y reparte automáticamente las iteraciones del bucle entre los hilos. El cuerpo se ejecuta una vez por iteración, pero en el hilo que toca.

2.3.1 Directivas más usadas

2.3.2 Cláusulas más usadas

Cláusula	Aplica a	Significado
schedule(...)	for	Cómo se reparten las iteraciones (sección 2.4).
shared(...)	parallel, for	Variables de ámbito compartido.
private(...)	parallel, for	Variables con copia por hilo.
reduction(...)	for	Combina valores de todos los hilos al terminar.
num_threads(k)	parallel	Número de hilos de la región.
default(...)	parallel	Ámbito por omisión de las variables.
if(cond)	parallel, for	Ejecuta en paralelo solo si se cumple la condición.
nowait	for	El hilo no espera en la barrera implícita.
collapse(k)	for	Paraleliza también los bucles internos.

2.3.3 Compilar y ejecutar

gcc -O2 -fopenmp programa.c -o programa       # compilar con soporte OpenMP
OMP_NUM_THREADS=8 ./programa                   # ejecutar con 8 hilos
export OMP_NUM_THREADS=8                      # o fijar la variable de entorno
export OMP_SCHEDULE="dynamic,4"               # forzar una política de reparto
export OMP_DISPLAY_ENV=TRUE                    # mostrar las variables efectivas

Nota.

-fopenmp en el compilador y no solo en el enlazador. Si se compila sin la opción, el programa funciona pero todas las directivas se ignoran: el código se ejecuta secuencialmente sin ningún aviso. Es la causa número uno de «mi programa paralelo va igual de lento».

2.4 Paralelización de bucles: distribución de trabajo y scheduling

La cláusula schedule decide cómo se reparten las iteraciones de un bucle. Elegir mal la política es una de las causas más comunes de rendimiento pobre.

Figura 2.4. schedule(static): cada hilo recibe un bloque fijo de iteraciones. No hay gestión de cola, pero si el coste por iteración es irregular, los bloques se descompensan.

Figura 2.5. schedule(dynamic): cada hilo toma una iteración de una cola común y la marca como tomada. Equilibra muy bien la carga, al precio de un acceso a memoria compartida por iteración.

Figura 2.6. schedule(guided): el reparto empieza con bloques grandes y se reduce progresivamente. Combina poca gestión inicial con un buen equilibrio final.

2.4.1 Comparación de las políticas

Con chunk explícito, static divide en bloques round-robin, lo que suele repartir mejor que el reparto contiguo cuando las iteraciones contiguas tienen coste parecido:

/* 4 hilos, bloques de 8 iteraciones, reparto round-robin */
#pragma omp parallel for schedule(static, 8)
for (int i = 0; i < n; i++) { ... }

2.4.2 El límite de Amdahl aplicado a un bucle

La decisión de paralelizar un bucle se puede evaluar antes de escribirlo. Si el por ciento del tiempo del programa está dentro del bucle y el resto es secuencial, la ganancia máxima es:

Un bucle que representa el 5 % del tiempo total nunca puede dar más de , por muchos hilos que se empleen. Conviene medir dónde se va el tiempo antes de añadir directivas.

Nota.

Paralelizar el bucle equivocado es la forma más común de perder rendimiento. Si el 95 % del tiempo está en la entrada y la salida de datos y solo el 5 % en el bucle, paralelizar el bucle deja el tiempo intacto y añade el sobrecosto de crear los hilos. El perfilador resuelve esta duda en minutos; la intuición, no siempre.

2.5 Mecanismos de sincronización: secciones críticas, barreras y operaciones atómicas

Cuando el paralelismo es denso y los datos son pocos, se acumulan en una o pocas variables. La sincronización deja de ser el problema principal.

2.5.1 critical: exclusión mutua

#pragma omp critical
{
    /* Solo un hilo a la vez puede estar aquí dentro */
    total += a[i];
}

Todos los hilos compiten por el mismo cerrojo. Es correcto pero serializa esa parte del programa: si la sección crítica contiene el grueso del trabajo, no queda paralelismo útil.

Nota.

critical sin nombre serializa con TODAS las secciones críticas del programa. Si dos secciones críticas no están relacionadas, se bloquean entre sí sin necesidad. Se les da nombre para que sean independientes:

#pragma omp critical(mi_contador)
    total += a[i];

2.5.2 atomic: operación atómica

contador++;                       /* atómico solo para estas operaciones */
#pragma omp atomic
    total += a[i];                /*RW, +, -, *, /, ++, -- */

Una operación atómica es más rápida que una sección crítica cuando la operación es de las soportadas, porque no necesita el cerrojo completo. Pero el resultado sigue siendo secuencial: si cien mil hilos hacen atomic add sobre la misma variable, esa variable se convierte en el cuello de botella.

2.5.3 reduction: la solución habitual

Cuando el objetivo es acumular, reduction es lo correcto. OpenMP crea una copia privada de la variable en cada hilo, y al terminar la región las combina con el operador indicado:

double suma = 0.0;
#pragma omp parallel for reduction(+:suma)
for (int i = 0; i < n; i++) suma += a[i];
/* suma ya vale la suma real: no hubo conflicto */

Operadores habituales: + - * & | ^ && || y max min con la variante reduction(max:...).

/* Máximo y mínimo en paralelo, sin conflicto */
double mayor = -DBL_MAX, menor = DBL_MAX;
#pragma omp parallel for reduction(max:mayor, min:menor)
for (int i = 0; i < n; i++) {
    if (a[i] > mayor) mayor = a[i];
    if (a[i] < menor) menor = a[i];
}

2.5.4 barrier: punto de encuentro

#pragma omp parallel
{
    /* Fase 1: cada hilo calcula su parte */
    calcular_parte(k);

    #pragma omp barrier      /* nadie sigue hasta que todos terminen la fase 1 */

    /* Fase 2: trabajo que necesita el resultado completo */
    combinar_resultados();
}

La barrera sincroniza por definición: su tiempo se suma al total. Si los hilos llegan muy desbalanceados, la barrera solo amplifica el desequilibrio. La directiva nowait la omite cuando se sabe que no es necesaria.

2.5.5 master, single y ordered

#pragma omp parallel for ordered
for (int i = 0; i < n; i++) {
    calcular(i);
    #pragma omp ordered
    {
        printf("linea %d\n", i);   /* salida en orden determinista */
    }
}

2.6 Detección y eliminación de false sharing

El false sharing no es un error de corrección: los resultados son correctos. Es una pérdida de rendimiento, y por eso es más traicionero: nada falla, nada avisa, simplemente el programa va lento.

Figura 2.7. Dos variables que ningún hilo comparte entre sí caen, sin embargo, en la misma línea de 64 bytes. Cada escritura en una invalida la copia de la otra, y la línea viaja entre cachés sin detenerse.

2.6.1 Qué ocurre

La unidad de coherencia de la caché no es el byte: es la línea de caché, de 64 bytes en la arquitectura x86-64. Dos hilos que escriben en variables distintas de la misma línea se invalidan la caché mutuamente aunque no compartan el dato. El coste de cada invalidación es del orden de 100 ns de tráfico hacia el nivel compartido.

2.6.2 Cómo se reconoce

Las señales típicas, en este orden:

1. El programa paralelo es más lento que el secuencial en un bucle que solo suma contadores.
2. Reducir el número de variables compartidas por hilo mejora el resultado.
3. El perfilador muestra poco trabajo útil y mucho tráfico de coherencia.
4. Insertar relleno entre las variables hace desaparecer el problema.

2.6.3 Cómo se corrige

/* ANTES: dos contadores que caen en la misma línea de 64 bytes */
int contador_a = 0, contador_b = 0;

/* DESPUÉS: el relleno separa ambas variables en líneas distintas */
typedef struct { int valor; char relleno[64]; } contador_alineado;
contador_alineado contador_a = {0}, contador_b = {0};

Tres tácticas alternativas, en orden de preferencia:

/* Un acumulador por hilo: sin compartición durante el bucle */
int parcial[omp_get_max_threads()];
#pragma omp parallel
{
    int tid = omp_get_thread_num();
    int acc = 0;
    #pragma omp for schedule(static)
    for (int i = 0; i < n; i++) acc += a[i];
    parcial[tid] = acc;
}
int total = 0;
for (int k = 0; k < omp_get_max_threads(); k++) total += parcial[k];

Nota.

False sharing no es true sharing. En true sharing varios hilos necesitan la misma variable y la sincronización es necesaria: el coste es inevitable. En false sharing las variables son distintas y lo único que se comparte es la línea de caché: el coste se puede eliminar. Antes de optimizar, conviene determinar cuál de los dos casos es, porque la solución es opuesta en cada uno.

2.7 Herramientas de profiling y análisis de rendimiento

Un programa paralelo que no se mide no se puede optimizar: se corrige a ciegas. Y con OpenMP es frecuente que el código «optimizado» sea más lento que el original, precisamente porque se optimizó lo que no era el cuello de botella.

Figura 2.8. El ciclo de trabajo. Cada vuelta pasa por medir, localizar el cuello de botella, optimizar y volver a medir. Saltarse el paso de medir es la causa más común de optimizaciones que empeoran el código.

2.7.1 Herramientas disponibles

2.7.2 Cómo se usa perf en la práctica

# Resumen por función
perf stat ./programa

# Distribución del tiempo entre hilos
perf record -g ./programa && perf report

# Contadores de caché y ramas
perf stat -e cache-misses,cache-references,branch-misses ./programa

La métrica que más informa no es el tiempo total, sino la tasa de fallos de caché:

Un valor alto señala mala localidad de los datos; un valor bajo con ejecución lenta señala un cuello de botella de sincronización, no de datos.

2.7.3 Secuencia de trabajo recomendada

1. Medir la versión secuencial y registrar . Sin ese número no hay comparación posible.
2. Paralelizar de la forma más simple posible: schedule(static) y reduction. Cualquier otra cosa es prematura.
3. Medir y calcular y .
4. Perfilizar y localizar dónde se va el tiempo.
5. Optimizar solo eso, y volver al punto 3.

Nota.

La eficiencia decreciente es normal, no es un error. Al duplicar los hilos, la ganancia esperada se reduce: aparecen el Muro de Memoria, el tráfico de coherencia y el sobrecosto de la sincronización. Si la eficiencia baja del 50 %, el problema no suele estar en el algoritmo sino en la gestión de los datos compartidos.

Actividades teórico-prácticas

Actividades de la sección 2.2

Detección de la condición de carrera. El siguiente programa compila sin avisos y devuelve un resultado distinto en cada ejecución:

#include <omp.h>
#include <stdio.h>
int main(void) {
    int total = 0;
    #pragma omp parallel
    {
        for (int i = 0; i < 100000; i++) {
            total += 1;
        }
    }
    printf("total = %d (esperado 100000)\n", total);
    return 0;
}

1. Ejecute el programa diez veces con 8 hilos y registre los valores obtenidos.
2. Explique por qué los resultados difieren, citando las tres condiciones de Bernstein.
3. Corrija el programa de dos maneras distintas y justifique por qué cada una funciona.
4. Explique por qué el compilador no emite ningún aviso.

Actividades de la sección 2.4

Comparación de políticas de reparto. Con el código de referencia de 40-codigo/referencia/montecarlo/, mida el tiempo de ejecución con 1, 2, 4, 8 y 16 hilos usando schedule en sus variantes static, dynamic y guided.

1. Calcule y para cada combinación.
2. Identifique en qué configuración la eficiencia es mínima y explique la causa.
3. Justifique el resultado con el modelo de la Ley de Amdahl, estimando la fracción secuencial .
4. Concluya qué política conviene para ese problema concreto y por qué.

Actividades de la sección 2.6

Confirmación experimental de la falsa compartición.

/* Version A: contadores que probablemente comparten linea */
int a = 0, b = 0;
for (int rep = 0; rep < 100000; rep++) {
    #pragma omp parallel for
    for (int i = 0; i < 10000; i++) a++;
}

/* Version B: contadores separados por relleno */
typedef struct { int v; char relleno[60]; } alineado;
alineado a = {0}, b = {0};
for (int rep = 0; rep < 100000; rep++) {
    #pragma omp parallel for
    for (int i = 0; i < 10000; i++) a.v++;
}

1. Mida el tiempo de ambas versiones con 2, 4 y 8 hilos.
2. Construya la tabla de tiempos y de speedup de cada versión.
3. Explique la diferencia observada en términos de invalidación de líneas de caché.
4. Identifique qué versión presenta true sharing y cuál false sharing, y justifíquelo.

Actividades de la sección 2.7

Análisis con perfilador. Elija uno de los programas anteriores y:

1. Ejecute el perfilador y presente la distribución del tiempo entre funciones.
2. Identifique el cuello de botella y justifíquelo con los datos del perfil, no con intuición.
3. Calcule la tasa de fallos de caché e interprete el valor obtenido.
4. Proponga una sola optimización, aplíquela y mida de nuevo.
5. Redacte una conclusión sobre si la optimización propuesta compensó el esfuerzo.

Evaluación global del módulo 2

Proyecto miniatura: optimización de multiplicación de matrices con OpenMP.

Implemente la multiplicación de matrices en tres versiones y compárelas:

1. Secuencial (), con el algoritmo clásico de tres bucles anidados.
2. OpenMP directa, con #pragma omp parallel for sobre el bucle externo.
3. OpenMP optimizada, con collapse, schedule adecuado y acceso a memoria por bloques.

Entregable: informe PDF de 4 páginas con la tabla de tiempos, el cálculo de y para , y , y la identificación documentada del cuello de botella en cada versión.

Criterios de evaluación.

Actividades autónomas del estudiante

1. Serie de programas OpenMP de complejidad creciente (entregable, fin de semana 5). Cinco programas: suma de vectores, búsqueda lineal, reducción de máximo, aplicación de una función sobre una matriz y un bucle con coste irregular. Cada uno debe compilar y ejecutarse sin errores.
2. Informe de optimización con gráficos comparativos (entregable, fin de semana 6). Comparar schedule(static), dynamic y guided sobre el mismo programa, con tablas y gráficos de y , y una explicación de la diferencia.
3. Lectura de la documentación oficial de OpenMP 5.1: los apartados 2.1 a 2.4 son de lectura obligatoria.
4. Análisis de código abierto que use OpenMP: identificar qué región paralela usa, qué cláusulas aplica y si el reparto de carga es adecuado para el problema.
5. Sesión de laboratorio con datos reales de rendimiento (semana 6): perfilado de uno de los programas anteriores con perf o VTune.

Nota.

Actividades relacionadas con la investigación: proyecto y resolución de problemas. Otro (apartado 20.2): proyecto miniatura de optimización del algoritmo de multiplicación de matrices con OpenMP y análisis iterativo de rendimiento. Actividades relacionadas con la interacción social: no se requieren para este módulo.

Bibliografía del módulo

• OpenMP Architecture Review Board. (2021). OpenMP application programming interface (Version 5.1). https://www.openmp.org/wp-content/uploads/OpenMP-API-Specification-5-1.pdf
• Pacheco, P. (2021). An introduction to parallel programming (2nd ed.). Morgan Kaufmann.
• Quinn, M. J. (2004). Parallel programming in C with MPI and OpenMP. McGraw-Hill.
• Grama, S., Gupta, A., Karypis, G., y Kumar, V. (2003). Introduction to parallel computing. Academic Press.
• Marlow, S. (2018). The OpenMP common core specification. En OpenMP Conference.

Documento derivado de 00-marco/programa-docente-TEL420-V2.docx, apartados 20.2 y 21. Las ocho figuras se generan con 90-build/generar_figuras_m2.py y son rotuladas en castellano.