P2b · Secciones críticas, reducción y falsa compartición

Contenidos del programa: §20.2 · contenidos 2.5 y 2.6 Horas de laboratorio: 4 · Modalidad: individual

1. Objetivo

Contrastar las tres estrategias de acumulación sobre un dato compartido: sección crítica, operación atómica y reduction—, medir su coste, y provocar y medir experimentalmente el fenómeno de la falsa compartición.

Al terminar de la práctica el estudiante es capaz de: identificar qué sincronización corresponde a cada situación, distinguir true sharing de false sharing, y medir el coste de cada uno.

2. Antes de empezar

Las tres secciones siguientes comparten el mismo esqueleto. La diferencia está en una línea, y esa línea es justamente lo que la práctica mide.

3. Parte A · Comparar las tres estrategias

A.1 El programa de referencia

/* Sistemas Paralelos - TEL420
 * Estudiante: NOMBRE COMPLETO
 * RU / CI: XXXXXXXX
 * Practica: P2b - critical vs atomic vs reduction
 */
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

#define N 5000000

int main(int argc, char **argv) {
    if (argc < 2) { fprintf(stderr, "uso: %s critical|atomic|reduction\n", argv[0]); return 1; }
    const char *modo = argv[1];
    double *a = malloc(N * sizeof(double));
    for (int i = 0; i < N; i++) a[i] = 1.0;

    double total = 0.0;
    double t0 = omp_get_wtime();

    if (strcmp(modo, "critical") == 0) {
        for (int i = 0; i < N; i++) {
            #pragma omp critical
            { total += a[i]; }
        }
    } else if (strcmp(modo, "atomic") == 0) {
        #pragma omp parallel for
        for (int i = 0; i < N; i++) {
            #pragma omp atomic
            total += a[i];
        }
    } else if (strcmp(modo, "reduction") == 0) {
        #pragma omp parallel for reduction(+:total)
        for (int i = 0; i < N; i++) total += a[i];
    } else {
        fprintf(stderr, "modo desconocido\n"); return 1;
    }

    double t1 = omp_get_wtime();
    printf("%-10s : %.4f s   total = %.1f\n", modo, t1 - t0, total);
    free(a);
    return 0;
}

gcc -O2 -fopenmp sincronizacion.c -o sincronizacion
for m in critical atomic reduction; do
  for h in 1 2 4 8; do
    printf "%2d hilos  " $h
    OMP_NUM_THREADS=$h ./sincronizacion $m
  done
done

A.2 Qué observar

Nota.

El dato clave de esta parte es el tiempo con 1 hilo de cada variante. Con un solo hilo hay sincronización pero no competencia. La diferencia entre ese valor y el de 8 hilos mide cuánto paralelismo se pierde por culpa de la sincronización, no por culpa del hardware.

4. Parte B · Provocar y medir la falsa compartición

B.1 Las dos versiones

/* Sistemas Paralelos - TEL420
 * Estudiante: NOMBRE COMPLETO
 * Practica: P2b - false sharing
 */
#include <stdio.h>
#include <omp.h>

#define REPETICIONES 20000
#define ITERACIONES  2000

/* Cada hilo tiene su propio contador, pero TODOS en la misma linea de 64 bytes */
struct sin_alinear { int valor; };
static struct sin_alinear contadores[8];

/* Relleno de 64 bytes: cada contador cae en su propia linea */
struct alineado { int valor; char relleno[64 - sizeof(int)]; };
static struct alineado contadores_alineados[8];

int main(void) {
    /* --- version A: sin alinear --- */
    double t0 = omp_get_wtime();
    for (int rep = 0; rep < REPETICIONES; rep++) {
        #pragma omp parallel
        {
            int tid = omp_get_thread_num();
            #pragma omp atomic
            contadores[tid].valor++;
        }
    }
    double t1 = omp_get_wtime();

    /* --- version B: alineada --- */
    double t2 = omp_get_wtime();
    for (int rep = 0; rep < REPETICIONES; rep++) {
        #pragma omp parallel
        {
            int tid = omp_get_thread_num();
            #pragma omp atomic
            contadores_alineados[tid].valor++;
        }
    }
    double t3 = omp_get_wtime();

    printf("sin alinear : %.4f s\n", t1 - t0);
    printf("alineada    : %.4f s\n", t3 - t2);
    printf("mejora      : %.2f veces\n", (t1 - t0) / (t3 - t2));
    return 0;
}

gcc -O2 -fopenmp false_sharing.c -o false_sharing
for h in 1 2 4 8; do
  echo "=== $h hilos ==="
  OMP_NUM_THREADS=$h ./false_sharing
done

B.2 Confirmación de que las variables están en la misma línea

# Direcciones de cada contador: si caen en el mismo múltiplo de 64, comparten linea
./false_sharing & sleep 1
cat /proc/$!/maps 2>/dev/null | head

Más sencillo, y suficiente para la práctica:

cat > direcciones.c <<'EOF'
#include <stdio.h>
struct sin_alinear { int valor; };
static struct sin_alinear c[8];
int main(void) {
    for (int i = 0; i < 8; i++)
        printf("contador %d en %p   linea %lu\n", i, (void*)&c[i],
               ((unsigned long)&c[i]) / 64);
    return 0;
}
EOF
gcc -O0 direcciones.c -o direcciones && ./direcciones

Si todas las líneas salen iguales, la compartición está confirmada.

B.3 Las tres formas de corregirlo

Mida las tres y compárelas.

5. Evidencias requeridas

N°	Evidencia
1	Salida de los tres modos de la Parte A, con 1, 2, 4 y 8 hilos
2	Tabla de tiempos de la Parte A con las columnas , y
3	Salida de false_sharing con 1, 2, 4 y 8 hilos
4	Salida del programa direcciones que demuestra la compartición de línea
5	Código de las tres correcciones de la Parte B, con su tiempo medido

Todas las capturas con la marca de personalización del apartado 4.2 de 00-marco/glosario-y-convenciones.md.

6. Estructura del informe

Formato PDF, máximo 3 páginas.

Sección	Contenido
1. Portada	Datos institucionales, nombre, RU, fecha
2. Parte A: sincronización	Tabla de las tres estrategias, y de cada una
3. Parte B: falsa compartición	Tabla de tiempos y demostración de la compartición de línea
4. Análisis	Cuantificación de la pérdida por sincronización y por falsa compartición
5. Conclusiones	Qué estrategia usar en cada situación, con argumentos

7. Criterios de evaluación

Rúbrica completa: ../rubrica-informe-optimizacion.md.

8. Preguntas de análisis

1. ¿Por qué reduction es tan superior a critical para una suma? Explique en términos de qué ocurre en la memoria.
2. Si en lugar de sumar se quisiera calcular el máximo, ¿qué cambiaría en el diseño de la reducción?
3. En la Parte B, ¿el problema es true sharing o false sharing? Justifique con las direcciones obtenidas en la evidencia 4.
4. La mejora de la versión alineada, ¿es constante al aumentar el número de hilos? Si no lo es, ¿por qué?
5. ¿Cuándo sería incorrecto usar atomic en lugar de reduction?

Práctica derivada de 00-marco/programa-docente-TEL420-V2.docx, apartado 20.2, contenidos 2.5 y 2.6.