Repartir bucles — omp for y schedule

💡 En simple

Tienes 16 cajas que cargar y 4 personas. Puedes asignar de antemano 4 cajas a cada una (static), o dejar las cajas en una pila y que cada quien tome otra cuando termina la suya (dynamic). Lo primero no cuesta organizar, pero si algunas cajas pesan más, alguien termina mucho después. Lo segundo se adapta, pero cada “voy por otra” cuesta un poco.

En una frase: #pragma omp for reparte las vueltas de un bucle entre los hilos que ya existen; schedule decide cómo.

El constructor for

#pragma omp for va dentro de una región parallel y reparte las iteraciones del bucle que le sigue. No crea hilos: usa el equipo existente. Es paralelismo de datos (cada hilo, un trozo del arreglo).

#pragma omp parallel private(f, i)
{
    f = 7;
    #pragma omp for
    for (i = 0; i < 20; i++)
        a[i] = b[i] + f * (i - 1);
}

Atajo combinado (región + reparto en una línea): #pragma omp parallel for.

Cláusulas de for: private, firstprivate, lastprivate, reduction, schedule(kind[, chunk]), collapse(n), ordered, nowait.

Requisito

Las iteraciones deben ser independientes: ninguna puede necesitar el resultado de otra (si a[i] depende de a[i-1], repartirlas da resultados erróneos).

schedule: cómo se reparten

Tipo	Qué hace	Cuándo conviene
static	Bloques contiguos casi iguales, decididos antes de empezar	Iteraciones de costo parecido
static, c	Bloques de c en turno rotativo (hilo 0, 1, …, 0, 1, …)	Costo que crece o varía de forma regular
dynamic, c	Cada hilo libre pide el siguiente bloque de c (por defecto c = 1)	Costos irregulares o impredecibles
guided, c	Como dynamic, pero los bloques empiezan grandes y se achican hasta c	Irregular, con menos pedidos que dynamic
runtime	Lo decide la variable de entorno OMP_SCHEDULE al ejecutar	Probar sin recompilar
auto	Lo decide el compilador / runtime	—

Cómo leerlo: cada fila es un schedule distinto para el mismo bucle de 16 iteraciones y 4 hilos; el número y el color dicen qué hilo ejecuta cada iteración. static y static, 2 son fijos (siempre igual). dynamic y guided dependen de quién termina primero, así que la fila es una corrida posible. En guided los bloques empiezan grandes (aprox. iteraciones que faltan / hilos) y se achican; el tamaño exacto depende de la implementación.

¿Qué hilo hace cada iteración? #pragma omp for schedule(static)

Cada bloque es un chunk (grupo de iteraciones seguidas). El ancho es lo que tarda. Pulsa «Ejecutar» para ver a los hilos trabajar.

staticstatic, chunkdynamic, chunkguided, chunk

iteraciones N = 16hilos = 4chunk = 3costo de pedir un chunk = 0.15

costo de cada iteración:

uniformecrecientealeatorioun pico

▶︎ Ejecutar

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

tiempo total (el hilo más lento)4

ideal (reparto perfecto)4

eficiencia100%

chunks repartidos4

carga por hilo4 · 4 · 4 · 4

Sin chunk, static parte las 16 iteraciones en 4 bloques contiguos casi iguales, decididos antes de empezar. Perfecto si todas cuestan lo mismo; si el costo crece, el último hilo carga con lo pesado.

En el examen…

• static = sin costo de reparto, pero se desbalancea si las iteraciones cuestan distinto.
• dynamic = se balancea solo, pero paga un costo por cada pedido (por eso dynamic,1 con costos iguales puede ser más lento que static).
• guided = término medio: pocos pedidos grandes al inicio, pequeños al final para balancear.

Usa el playground: con costo «creciente», compara static (el último hilo carga lo pesado) con static,1 o dynamic.

Lo que imprime Ejemp02_omp_for.cpp

Ejemp02_omp_for.cpp

#define N 1 << 4                         // 16 iteraciones
#pragma omp parallel private(id)
{
    // particione N equitativamente entre hilos
    #pragma omp for schedule(static) private(i)
    for (i = 0; i < N; i++) {
        id = omp_get_thread_num();
        c[i] = a[i] + b[i];
        printf(" %i \t %i\n", id, i);
    }
    #pragma omp for
    for (i = 0; i < N; i++)
        c[i] *= 2;
}

Ejecutado con 4 hilos (las líneas salen desordenadas, pero el reparto siempre es el mismo):

hilo  iteraciones
 0    0 1 2 3
 1    4 5 6 7
 2    8 9 10 11
 3    12 13 14 15

Cambia el pragma por schedule(static, 3), schedule(dynamic) o schedule(dynamic, 3) (están comentados en el archivo) y compara con el playground.

nowait y collapse

• nowait: quita la barrera implícita al final del for. Los hilos que terminan siguen con lo próximo sin esperar.
• collapse(n): junta n bucles anidados en uno solo con más iteraciones, para repartir mejor (útil si el bucle externo tiene pocas vueltas).

U4.3 — nowait válido aun con dependencia entre bucles

#pragma omp parallel
{
    #pragma omp for schedule(static) nowait
    for (i = 0; i < n; i++) c[i] = (a[i] + b[i]) / 2.0f;
    #pragma omp for schedule(static) nowait
    for (i = 0; i < n; i++) z[i] = sqrtf(c[i]);
    #pragma omp for schedule(static) nowait
    for (i = 1; i <= n; i++) y[i] = z[i-1] + a[i];
}

¿Por qué ahí sí se puede usar nowait?

z[i] necesita c[i]. Como los dos bucles usan static con el mismo número de iteraciones, el mismo hilo calcula c[i] y luego z[i]: no necesita esperar a nadie. Con dynamic esto no está garantizado y nowait daría resultados erróneos.

U4.3 — collapse(2) + lastprivate

#pragma omp for collapse(2) lastprivate(jlast, klast)
for (k = 1; k <= 2; k++)
    for (j = 1; j <= 3; j++) { jlast = j; klast = k; }
#pragma omp single
printf("%d %d\n", klast, jlast);      // imprime: 2 3

Se forma un solo bucle de 2 × 3 = 6 iteraciones. lastprivate deja los valores de la última iteración secuencial (k = 2, j = 3).

Ejercicio

En la lámina 21 de U4.1 aparece #pragma omp parallel for … schedule(static, chunk) seguido de un bloque con #pragma omp section. ¿Qué está mal y cómo se corrige?

Ver solución

parallel for debe ir directamente antes de un bucle for, no de un bloque { }, y section solo tiene sentido dentro de sections. Lo correcto es poner el for inmediatamente después:

#pragma omp parallel for shared(a, b, c, chunk) private(i) schedule(static, chunk)
for (i = 0; i < N; i++)
    c[i] = a[i] + b[i];

(Respuesta propia: la lámina lo muestra así, sin marcarlo como error.)

Errores típicos

• Pensar que dynamic siempre es mejor: cada pedido de bloque cuesta. Con iteraciones de costo parecido, static gana.
• Usar nowait entre bucles dependientes con dynamic o con distinto número de iteraciones: el hilo que calcula c[i] ya no es necesariamente el que calcula z[i].
• Paralelizar un bucle con dependencia entre iteraciones (a[i] = a[i-1] + …): ningún schedule lo arregla, el resultado es incorrecto.
• Olvidar que schedule(runtime) toma el valor de OMP_SCHEDULE al ejecutar.

Práctica extra

1. Bucle de 12 iteraciones, 3 hilos, schedule(static, 2). ¿Qué iteraciones hace cada hilo?

Ver solución

Bloques de 2 por turnos: hilo 0 → 0, 1, 6, 7 · hilo 1 → 2, 3, 8, 9 · hilo 2 → 4, 5, 10, 11.

2. 16 iteraciones, 4 hilos, la iteración i cuesta i unidades (costo creciente). Calcula el tiempo con static y con static, 1 (sin overhead) y el speedup de cada uno.

Ver solución

Trabajo total: 0 + 1 + … + 15 = 120.

• static: hilo 0 → 0+1+2+3 = 6, hilo 1 → 22, hilo 2 → 38, hilo 3 → 12+13+14+15 = 54. T = 54, S = 120/54 = 2.22.
• static, 1: hilo 0 → 0+4+8+12 = 24, hilo 1 → 28, hilo 2 → 32, hilo 3 → 36. T = 36, S = 120/36 = 3.33.

El ideal sería 120/4 = 30. Repartir por turnos mezcla iteraciones baratas y caras en cada hilo.

Autoevaluación

0/6 correctas · 0 respondidas Reiniciar

1. #pragma omp for fuera de una región parallel…

a) crea hilos nuevosb) se ejecuta con un solo hilo (no hay equipo que repartir)c) da error de compilación siempred) equivale a parallel for

2. 16 iteraciones, 4 hilos, schedule(static): el hilo 2 hace…

a) 2, 6, 10, 14b) 8–11c) las que alcanced) 0–3

3. Iteraciones de costo muy variable e impredecible. Mejor opción:

a) staticb) dynamic (o guided)c) collapsed) ordered

4. nowait en un for…

a) quita la barrera implícita finalb) evita crear hilosc) hace el bucle atómicod) ordena las iteraciones

5. schedule(static, 2) con 3 hilos y 12 iteraciones: el hilo 0 hace…

a) 0–3b) 0,1, 6,7c) 0,1,2,3d) 0, 3, 6, 9

6. collapse(2) sirve para…

a) fusionar dos bucles anidados en un espacio de iteraciones más grandeb) usar 2 hilosc) repartir de a 2d) ejecutar 2 veces

Fuente ·U4.1 Paralelismo compartido-OMP.pdf (láminas 13–17, 21) · U4.3 Paralelismo compartido-OMP.pdf (nowait, collapse) · semana_9/Ejemp02_omp_for.cpp