Rendimiento terrible: un problema simple de sobrecarga, ¿o hay un error en el programa?

Question

Tengo aquí lo que entiendo es una construcción OpenMP relativamente simple. El problema es que el programa se ejecuta entre 100 y 300 veces más rápido con 1 hilo en comparación con 2 hilos. El 87% del programa se gasta en gomp_send_wait() y otro 9.5% en gomp_send_post.

El programa da resultados correctos, pero me pregunto si hay un error en el código que está causando algún conflicto de recursos, o si simplemente es que la sobrecarga de la creación del hilo no vale la pena por un bucle de fragmento tamaño 4. p varía de 17 a 1000, dependiendo del tamaño de la molécula que estamos simulando.

Mis números son para el peor de los casos, cuando p es 17 y el tamaño de fragmento 4. El rendimiento es el mismo si estoy usando programación estática, dinámica o guiada. Con p=150 y el tamaño de fragmento 75, el programa sigue siendo 75x-100x más lento que el serial.

... 
    double e_t_sum=0.0; 
    double e_in_sum=0.0; 

    int nthreads,tid; 

    #pragma omp parallel for schedule(static, 4) reduction(+ : e_t_sum, e_in_sum) shared(ee_t) private(tid, i, d_x, d_y, d_z, rr,) firstprivate(V_in, t_x, t_y, t_z) lastprivate(nthreads) 
    for (i = 0; i < p; i++){ 
     if (i != c){ 
      nthreads = omp_get_num_threads();    
      tid = omp_get_thread_num(); 

      d_x = V_in[i].x - t_x; 
      d_y = V_in[i].y - t_y; 
      d_z = V_in[i].z - t_z; 


      rr = d_x * d_x + d_y * d_y + d_z * d_z; 

      if (i < c){ 

       ee_t[i][c] = energy(rr, V_in[i].q, V_in[c].q, V_in[i].s, V_in[c].s); 
       e_t_sum += ee_t[i][c]; 
       e_in_sum += ee_in[i][c];  
      } 
      else{ 

       ee_t[c][i] = energy(rr, V_in[i].q, V_in[c].q, V_in[i].s, V_in[c].s); 
       e_t_sum += ee_t[c][i]; 
       e_in_sum += ee_in[c][i];  
      } 

      // if(pid==0){printf("e_t_sum[%d]: %f\n", tid, e_t_sum[tid]);} 

     } 
    }//end parallel for 


     e_t += e_t_sum; 
     e_t -= e_in_sum;    

... 

Answer 1

Creo que usted debe tratar de mover a cabo todas aquellas ramas (es decir IFS) dentro del bucle, y lo hacen en dos bucles separados, uno para i < c, y otro para i> c. Esto beneficiaría en gran medida incluso el código de un solo subproceso, pero debería proporcionarle más paralelismo, incluso si, como dijo, la sobrecarga de creación de subprocesos puede ser mayor que los beneficios para n pequeños.

Answer 2

Metiu tiene razón. No puede esperar un buen rendimiento de un bucle que tenga enunciados condicionales. Esto es solo una mala codificación. Incluso para el rendimiento escalar.

Su jefe necesita comprender que OpenMP y la paralelización en general no son mágicos. Para obtener un buen rendimiento de un código paralelizado, primero se debe optimizar el código básico para el rendimiento escalar.

No es necesario eliminar las pruebas. El ciclo necesita ser reestructurado. Y el rendimiento escalar se beneficiará también.

Answer 3

Parece que piensas que es un hecho que si ejecutas un código de serie en modo multitheaded tiene que funcionar mejor. Eso no es un hecho. Y, a menudo no es verdad. La paralelización de un ciclo para ejecutar en múltiples hilos o múltiples procesadores no siempre da como resultado un mejor rendimiento. En la mayoría de los casos, se necesita cierta reestructuración. En su caso, el código ni siquiera es un buen código de serie.

Cualquier libro sobre optimización de código serial tiene como regla número 1 para bucles: eliminar todas las operaciones condicionales. Pruebas cuestan Algunos compiladores (por cierto, nunca dices qué OS/compilador/procesador estás usando ... sí importa) pueden intentar optimizar el código condicional. Algunos compiladores (como el compilador C de Sun) incluso le permiten ejecutar el programa en modo "recopilar" donde genera información de perfil de tiempo de ejecución sobre la frecuencia con la que se toman las ramas de un condicional y luego le permite volver a compilar en un modo que utiliza los datos recopilados para optimizar el código generado (Consulte la opción -xprofile)

La primera regla para optimizar el código paralelo es primero hacer la mejor optimización serial que pueda. Luego, paralelice los bucles.

Al mover los condicionales fuera del ciclo y, como sugiere Metiu, volver a escribir el código como dos bucles separados, le da al optimizador una mejor fuente para trabajar. El código de serie funciona mejor, y el código paralelizado es embarazosamente paralelo.

Aún así, los resultados pueden variar según el sistema operativo/compilador/plataforma.

Ver Using OpenMP y Solaris Application Programming

Answer 4

Esto se parece a un problema con la aplicación de OpenMP el compilador de GNU. Pruebe con un compilador diferente. Intel tiene un compilador de Linux del que debería poder descargar una copia e intentarlo aquí.

Otra cosa que noté es que las primeras variables privadas que parece ser bastante innecesarias. Puede haber una sobrecarga significativa al hacer copias privadas de la matriz V_in, que podría ser su problema.

Yo diría que es uno de esos 2 problemas que es su problema.

Answer 5

Primero, intente bombear el trozo más grande. La creación de subprocesos conlleva gastos generales, también se necesita elegir un nuevo trabajo para cada subproceso, y el tamaño de grano debe ser lo suficientemente grande para abrumarlo.

Una posibilidad más grande: la aplicación de la reducción de GOMP puede ser muy pobre (sugerido por los datos del perfil), y genera mensajes después de cada bloque, en lugar de acumularse dentro de cada hilo y luego proceder a su recogida al final. Intente asignar e_t_sum y e_in_sum como matrices con nthreads elementos cada uno, y agregue a e_t_sum[tid] dentro del ciclo, y luego repítelos para calcular la suma global después de que el ciclo paralelo haya finalizado.

Tenga en cuenta que esto introduce un posible problema de uso compartido falso en el que múltiples elementos de estas matrices se encontrarán en cachelines comunes, y múltiples procesadores escribirán en esta misma línea de caché. Si ejecuta esto en un conjunto de núcleos que comparten su caché, esto estará bien, pero apestará en cualquier otro lugar.

Otra posibilidad: Es posible que experimente la posibilidad de compartir sus actualizaciones falsas a los elementos de ee_t. Asegure la alineación de esta matriz y pruebe los tamaños de fragmentos que son múltiplos del tamaño de la línea de caché. Una sugerencia sutil de esta patología sería la parte del ciclo donde i > c toma desproporcionadamente más tiempo que la parte donde i < c.

Answer 6

En primer lugar, no creo que la optimización de su código de serie en este caso ayudará a responder su dilema OpenMP. No te preocupes por eso

OMI hay tres posibles explicaciones para la desaceleración:

1. Esto se puede explicar fácilmente una desaceleración. Los elementos de la matriz ee_t están llevando a compartir falsamente dentro de la línea de caché. El intercambio falso se produce cuando los núcleos terminan escribiendo en la misma línea de caché, no porque realmente comparten datos, pero cuando lo que están escribiendo los núcleos pasa a estar en la misma línea de caché (por lo que se llama , intercambio falso). Puedo explicar más si no encuentras compartir falso en google. Hacer alinear la línea de caché de los elementos ee_t puede ayudar mucho.

2. La sobrecarga del trabajo de desove es mayor que el beneficio de paralelismo. ¿Has probado menos de 8 núcleos? ¿Cómo es el rendimiento en 2 núcleos?

3. El número total de iteraciones es pequeño, digamos que tomamos 17 como ejemplo.Si lo divide en 8 núcleos, sufrirá problemas de desequilibrio de carga (especialmente porque algunas de sus iteraciones prácticamente no están haciendo ningún trabajo (cuando i == c). Al menos un núcleo tendrá que hacer 3 iteraciones, mientras que las demás lo harán do 2. Esto no explica una desaceleración, pero seguramente una razón por la aceleración no es tan alta como se puede esperar. Dado que sus iteraciones son de diferentes longitudes, utilizaría un horario dinámico con un tamaño de fragmento de 1 o utilizaría openmp. experimento con el tamaño del trozo, un trozo muy pequeño también dará lugar a la desaceleración.

quiero saber cómo va.