Comprender la cláusula de colapso en openmp

2 minutos de lectura

avatar de usuario
iomartin

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

COLAPSO: especifica cuántos bucles de un bucle anidado deben contraerse en un espacio de iteración grande y dividirse según la cláusula de planificación. La ejecución secuencial de las iteraciones en todos los bucles asociados determina el orden de las iteraciones en el espacio de iteraciones contraído.

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());

que 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é el collapse(2) cláusula. Esperaba tener el mismo resultado en las dos primeras columnas, pero ahora tengo el mismo número de 0‘arena 1está en la última columna. pero tengo

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

Entonces mis preguntas son:

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

  • Buena pregunta. Estás tratando de fusionar un bucle doble triangular. No creo que el colapso funcione para eso. Tiene que ser un bucle doble cuadrado. Otros en SO han dicho que el colapso funciona con bucles triangulares. No he leído las especificaciones. Si desea fusionar un bucle triangular, consulte esta pregunta. Aunque, ahora conozco una mejor manera de hacerlo usando variables de inducción.

    – bosón Z

    12 de febrero de 2015 a las 16:42


  • Pero si es un bucle doble cuadrado, ¿cuál es el beneficio de usar el colapso? Cada subproceso obtendrá el mismo número de iteraciones de cualquier manera.

    – iomartin

    12 de febrero de 2015 a las 16:47


  • Si tiene dos bucles anidados sobre n y m antes de colapsar cada subproceso obtiene n/nthreads iteraciones mientras que después de colapsar es n*m iteraciones Esto puede ayudar, por ejemplo, cuando n no es muy grande en relación con nthreads pero n*m es.

    – bosón Z

    12 de febrero de 2015 a las 16:53


  • Si usa C99, se ahorra el problema de privatizar sus índices de bucle… #pragma omp paralelo for for (int i = 0; i < 4; i++) for (int j = 0; j <= i; j++) printf("%d %d %d\n", i, j, omp_get_thread_num());

    –Jeff Hammond

    12 de febrero de 2015 a las 23:07

  • La salida no colapsada actual es incorrecta y muestra 5 salidas para cada subproceso; solo deben ser valores de bucle externo 0 y 2 para el subproceso #0 (es decir, 0 0 0, 2 0 0, 2 1 0) las otras salidas deben ser con subproceso #1.

    – ofrecer.sheffer

    12 de abril de 2017 a las 15:53

avatar de usuario
bosón z

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

Si la ejecución de cualquier bucle asociado cambia alguno de los valores utilizados para calcular cualquiera de los recuentos de iteraciones, 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 colapsar. El bucle exterior solo tiene cuatro iteraciones. Si tiene más de cuatro subprocesos, algunos se desperdiciarán. Pero cuando colapsa, los subprocesos se distribuirán entre 400 iteraciones, lo que probablemente sea mucho mayor que la cantidad de subprocesos. Otra razón para usar el colapso es si la carga no está bien distribuida. Si solo usó cuatro iteraciones y la cuarta iteración tomó la mayor parte del tiempo, los otros subprocesos esperan. Pero si usa 400 iteraciones, es probable que la carga se distribuya mejor.

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;

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

Finalmente, aquí hay un ejemplo que muestra cómo fusionar un bucle triangular que collapse no está definido para.


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

//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 de OP va de

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

para

(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 sigue funcionando.

Por ejemplo, n = 3 se asigna a partir de

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

para

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

Aquí hay un 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);
    }
}

  • @Gilles, ¿por qué agregaste el comentario? <!-- language-all: lang-c --> a mi respuesta? ¿Cuál es el punto de hacer eso? No me estoy quejando. Simplemente no sé para qué es.

    – bosón Z

    3 de diciembre de 2015 a las 21:28


  • Acabo de agregar la sugerencia de resaltado de sintaxis C como se describe aquí. De hecho, en mi navegador, todos sus fragmentos de código se mostraban en un gris sombrío. Ahora, al menos en mi navegador, pero supongo que en muchos otros también, la sintaxis C está coloreada. De acuerdo, los índices en los fragmentos de salida también lo son, lo que podría no ser deseado, pero se puede arreglar si lo desea. De todos modos, no quería entrometerme, pero pensé que una buena respuesta merece buenos colores… ¿Fui demasiado lejos?

    – Gilles

    4 de diciembre de 2015 a las 5:01


  • @Gilles, no estaba al tanto de eso. ¡Gracias! No me importa en absoluto que hayas mejorado mi respuesta.

    – bosón Z

    4 de diciembre de 2015 a las 8:16

  • Pero no entendí qué significa el parámetro. colapsar (2) ¿cuánto es 2?

    – N0rA

    5 de marzo de 2016 a las 16:04

  • @N0rA El número de bucles. collapse(n) colapsa lo siguiente n bucles anidados en un solo bucle paralelo compartido por los subprocesos.

    – Chris Swierczewski

    24/07/2017 a las 20:35

avatar de usuario
h2kyeong

Si su propósito es equilibrar la carga en filas crecientes, asumiendo que la carga de trabajo para cada elemento es regular o bien dispersa, entonces, ¿qué le parece doblar los índices de las filas por la mitad y olvidarse de la collapse ¿cláusula?

#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);
  }
}

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad