example - Entendiendo la cláusula de colapso en openmp

openmp ubuntu

Question

Encontré un código OpenMP que tenía la cláusula de colapso, que era nueva para mí. Estoy tratando de entender lo que significa, pero no creo que haya comprendido completamente sus implicaciones; Una definición que encontré es:

COLLAPSE : especifica cuántos bucles en un bucle anidado se deben contraer en un gran espacio de iteración y se dividen según la cláusula de programación. La ejecución secuencial de las iteraciones en todos los bucles asociados determina el orden de las iteraciones en el espacio de iteración colapsado.

Pensé que entendía lo que eso significaba, así que probé el siguiente programa simple:

int i, j;
#pragma omp parallel for num_threads(2) private(j)
for (i = 0; i < 4; i++)
    for (j = 0; j <= i; j++)
        printf("%d %d %d/n", i, j, omp_get_thread_num());

El cual produjo

0 0 0
1 0 0
1 1 0
2 0 0
2 1 0
2 2 1
3 0 1
3 1 1
3 2 1
3 3 1

Luego agregué la cláusula de collapse(2) . Esperaba tener el mismo resultado en las dos primeras columnas, pero ahora tengo un número igual de 0 y 1 en la última columna. Pero tengo

0 0 0
1 0 0
2 0 1
3 0 1

Así que mis preguntas son:

1. ¿Qué está pasando en mi código?
2. ¿Bajo qué circunstancias debo usar el collapse ?
3. ¿Puede proporcionar un ejemplo que muestre la diferencia entre usar el collapse y no usarlo?

Answer 1

El problema con su código es que las iteraciones del bucle interno dependen del bucle externo. De acuerdo con la especificación OpenMP en la descripción de la sección sobre vinculación y la cláusula de collapse :

Si la ejecución de cualquier bucle asociado cambia alguno de los valores utilizados para calcular cualquiera de los recuentos de iteración, el comportamiento no se especifica.

Puede usar el colapso cuando este no es el caso, por ejemplo, con un bucle cuadrado

#pragma omp parallel for private(j) collapse(2)
for (i = 0; i < 4; i++)
    for (j = 0; j < 100; j++)

De hecho, este es un buen ejemplo para mostrar cuándo usar el colapso. El bucle exterior solo tiene cuatro iteraciones. Si tienes más de cuatro hilos, entonces algunos se perderán. Pero cuando colapsas, los hilos se distribuirán entre 400 iteraciones, lo que probablemente sea mucho mayor que el número de hilos. Otra razón para usar el colapso es si la carga no está bien distribuida. Si solo usaste cuatro iteraciones y la cuarta iteración tomó la mayor parte del tiempo, los otros hilos esperaron. Pero si usa 400 iteraciones, es probable que la carga esté mejor distribuida.

Puede fusionar un bucle a mano para el código anterior como este

#pragma omp parallel for
for(int n=0; n<4*100; n++) {
    int i = n/100; int j=n%100;

Here hay un ejemplo que muestra cómo fusionar a mano un bucle triplemente fusionado.

Finalmente, question hay un ejemplo que muestra cómo fusionar un bucle triangular para el cual no se define el collapse .

Aquí hay una solución que asigna un bucle rectangular al bucle triangular en la pregunta de OP. Esto se puede utilizar para fusionar el bucle triangular OPs.

//int n = 4;
for(int k=0; k<n*(n+1)/2; k++) {
    int i = k/(n+1), j = k%(n+1);
    if(j>i) i = n - i -1, j = n - j;
    printf("(%d,%d)/n", i,j);
}

Esto funciona para cualquier valor de n.

El mapa para la pregunta OPs va desde

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),
(3,0), (3,1), (3,2), (3,3),

a

(0,0), (3,3), (3,2), (3,1), (3,0),
(1,0), (1,1), (2,2), (2,1), (2,0),

Para valores impares de n, el mapa no es exactamente un rectángulo, pero la fórmula aún funciona.

Por ejemplo, n = 3 se asigna desde

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),

a

(0,0), (2,2), (2,1), (2,0),
(1,0), (1,1),

Aquí está el código para probar esto

#include <stdio.h>
int main(void) {
    int n = 4;
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            printf("(%d,%d)/n", i,j);
        }
    }
    puts("");
    for(int k=0; k<n*(n+1)/2; k++) {
        int i = k/(n+1), j = k%(n+1);
        if(j>i) i = n - i - 1, j = n - j;
        printf("(%d,%d)/n", i,j);
    }
}

Answer 2

Si su propósito es equilibrar la carga en filas cada vez mayores, suponiendo que la carga de trabajo para cada elemento sea regular o esté bien dispersa, ¿qué tal si dobla los índices de la fila a la mitad y se olvida de la cláusula de collapse ?

#pragma omp for
for (int iy0=0; iy0<n; ++iy0){
  int iy = iy0;
  if (iy0 >= n/2) iy = n-1 -iy0 +n/2;
  for (int ix=iy+1; ix<n; ++ix){
    work(ix, iy);
  }
}