Descomposición de dominio y halos

💡 En simple

Imagina un mapa grande partido en pedazos, uno por persona. Para pintar el borde de tu pedazo necesitas ver un poquito del pedazo del vecino, así que copias esa franja en tu hoja: eso es el halo.

Si partes el mapa en más pedazos, cada uno pinta menos, pero hay más bordes que copiar y que actualizar por mensaje. Con hilos OpenMP dentro de un nodo, los hilos miran directo el mismo mapa: no copian franjas entre ellos.

Regiones de halo

Una región de halo es una copia local de datos que pertenecen a otro proceso y que hace falta para calcular (por ejemplo, las celdas vecinas en un stencil). Hay que actualizarlas con frecuencia (en cada iteración), con mensajes MPI.

Esto ya apareció en el parcial: el intercambio de halos en Foster (PCAM).

Según la lámina 12, con OpenMP dentro del nodo se reduce el tamaño de los halos que hay que almacenar: los hilos comparten la memoria del proceso y no necesitan copias entre ellos. Menos halo significa menos memoria y menos comunicación.

Cuánto halo hay (lámina 13)

Malla 2D de M×N celdas por proceso, con una celda de halo alrededor:

Procesos	Celdas por proceso	Celdas de halo por proceso
P	M × N	2M + 2N
4P	(M/2) × (N/2)	M + N

Al pasar de P a 4P procesos:

• cada proceso calcula un cuarto de las celdas;
• pero su halo solo se reduce a la mitad.

En general, si el número de procesos crece como O(P), el halo por proceso baja solo como O(√P). La proporción halo / trabajo empeora al dividir más fino.

Cómo leerlo: a la izquierda un proceso con un bloque de 8 × 8 celdas (celeste) y su halo alrededor (rojo, 2M + 2N = 32 celdas; las esquinas no hacen falta en un stencil de 5 puntos). A la derecha el mismo dominio partido en 4 procesos: cada uno calcula 16 celdas (un cuarto) pero guarda 16 de halo (solo la mitad). La proporción halo/trabajo pasó de 32/64 = 0.5 a 16/16 = 1.

Descomposición de dominio y celdas de halo

Una malla de 12×12 se reparte entre P procesos MPI. Cada proceso guarda una copia del borde de sus vecinos (halo) y la actualiza por mensajes en cada iteración.

procesos MPI en el nodo:

P = 1 (1 proceso + hilos)P = 4P = 9P = 16

celdas por proceso6×6 = 36

halo por proceso24

halo total en el nodo96

halo / celdas67 %

celdas propiashalo (copia del vecino)

Con 4 procesos cada uno computa 36 celdas (1/4 del total), pero el halo por proceso solo bajó a 24: el halo total del nodo es 96, 2× el de un solo proceso. El trabajo se divide entre P, pero el halo por proceso solo entre √P.

En 3D: un cubo de n³ celdas con 1 celda de halo

n = 10

cubo con halo12³ = 1728

celdas de halo728

% de halo42 %

Valores de la lámina: 10³ → 12³ (728 celdas, 42 %), 20³ → 22³ (2648, 25 %), 40³ → 42³ (10 088, 14 %). Cuanto más pequeño el subdominio de cada proceso, mayor es la fracción de memoria gastada en halos.

En 3D (lámina 14)

Un subdominio de n³ celdas con una capa de halo ocupa (n + 2)³:

Subdominio	Con halo	Celdas de halo	% halo
10³ = 1000	12³ = 1728	728	42 %
20³ = 8000	22³ = 10 648	2648	25 %
40³ = 64 000	42³ = 74 088	10 088	14 %

% halo = ((n+2)^3 - n^3) / (n+2)^3

Con subdominios chicos (muchos procesos MPI), casi la mitad de la memoria se va en copias.

Por qué el híbrido ayuda

En un nodo de c núcleos con un dominio de L×L celdas:

• MPI puro: c procesos, cada uno con un bloque de (L/√c)×(L/√c) y un halo de 4L/√c ⇒ halo total en el nodo ≈ 4L·√c.
• Híbrido (1 proceso × c hilos): un solo bloque L×L ⇒ halo ≈ 4L.

El híbrido guarda y comunica √c veces menos halo (con c = 16, 4 veces menos).

La lámina 15 lo muestra en un caso real: la descomposición de dominio del código Smilei (simulación de plasmas Particle-in-Cell, Derouillat et al. 2017), donde los dominios MPI cambian de forma para seguir la carga de partículas.

Ejemplo: ecuación de Poisson 3D con Jacobi (láminas 24–25)

Se resuelve la ecuación de Poisson en el cubo [0,1]³ con valor 0 en el borde:

∂²u/∂x² + ∂²u/∂y² + ∂²u/∂z² = f(x, y, z)

La malla es regular (h = hx = hy = hz). El método de Jacobi calcula cada celda de la iteración n+1 con sus 6 vecinas de la iteración n:

u[i][j][k] (n+1) = 1/6 · ( u[i+1][j][k] + u[i-1][j][k]
                         + u[i][j+1][k] + u[i][j-1][k]
                         + u[i][j][k+1] + u[i][j][k-1]
                         - h² · f[i][j][k] )          (todo en la iteración n)

Es un stencil de 7 puntos: cada celda necesita sus vecinas, así que en los bordes de cada subdominio hacen falta halos y en cada iteración se intercambian con MPI. La forma típica de paralelizarlo en híbrido:

for (iter = 0; iter < max_iter; iter++) {
    intercambiar_halos(u);                 /* MPI, entre procesos (solo el hilo maestro) */
    #pragma omp parallel for collapse(2)   /* OpenMP, dentro del proceso */
    for (i = 1; i <= nx; i++)
        for (j = 1; j <= ny; j++)
            for (k = 1; k <= nz; k++)
                u_new[i][j][k] = (u[i+1][j][k] + u[i-1][j][k] + u[i][j+1][k]
                                + u[i][j-1][k] + u[i][j][k+1] + u[i][j][k-1]
                                - h*h*f[i][j][k]) / 6.0;
    intercambiar(u, u_new);
}

(Esquema propio para ilustrar; no es código de clase.)

En el IBM Blue Gene (10 240 nodos × 4 núcleos), las versiones optimizadas (“new”) de MPI y de MPI + OMP escalan casi linealmente, y la híbrida nueva queda un poco por encima.

Ejercicio

Cada proceso tiene un subdominio 3D de 30³ celdas con 1 capa de halo. ¿Qué porcentaje de su memoria es halo? Si se usan 8 veces más procesos (cada uno con 15³), ¿cuánto queda?

Ver solución

• 30³ = 27 000 y 32³ = 32 768 ⇒ halo = 5768 ⇒ 5768 / 32 768 ≈ 17.6 %.
• 15³ = 3375 y 17³ = 4913 ⇒ halo = 1538 ⇒ 1538 / 4913 ≈ 31.3 %.

Con 8 veces más procesos, el trabajo por proceso cae 8 veces, pero el halo por proceso solo ≈ 3.75 veces (5768 → 1538): la fracción de halo casi se duplica.

Errores típicos

• Suponer que el halo baja al mismo ritmo que el trabajo. El trabajo baja como 1/P y el halo solo como 1/√P (en 2D).
• Actualizar los halos una sola vez al inicio: hay que intercambiarlos en cada iteración, porque los valores del vecino cambian.
• Contar las esquinas en un stencil de 5 puntos: no se usan. Sí hacen falta en uno de 9 puntos.

Práctica extra

Malla de 1000 × 1000 por proceso con P procesos. ¿Cómo cambia la razón halo/trabajo al pasar a 4P y a 16P (repartiendo el mismo dominio total)?

Ver solución

• P: halo 2·1000 + 2·1000 = 4000, trabajo 10⁶ → 0.004.
• 4P: bloques de 500 × 500 → halo 2000, trabajo 250 000 → 0.008.
• 16P: bloques de 250 × 250 → halo 1000, trabajo 62 500 → 0.016.

Cada vez que se multiplica por 4 el número de procesos, la proporción de comunicación se duplica. Por eso OpenMP dentro del nodo (menos procesos, bloques más grandes) ayuda.

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. Al pasar de P a 4P procesos en 2D, el halo por proceso…

a) se divide entre 4b) se divide entre 2c) no cambiad) se duplica

2. Un cubo de 10³ con una capa de halo tiene aproximadamente…

a) 10 % de halob) 25 % de haloc) 42 % de halod) 73 % de halo

3. ¿Por qué el híbrido reduce la memoria de halos?

a) porque comprime los datosb) porque los hilos de un proceso comparten memoria y no necesitan copias entre ellosc) porque usa menos nodosd) porque no usa MPI

4. El método de Jacobi para Poisson 3D usa…

a) solo la celda propiab) las 6 vecinas de la iteración anteriorc) todas las celdas del dominiod) las vecinas de la misma iteración

Fuente ·U4.5 Paralelismo-hibrido.pdf (láminas 12–15, 24–25)