tutorial omp for c++ c multithreading openmp

c++ - omp - openmp tutorial



Rendimiento OpenMP (3)

En primer lugar, sé que este tipo de pregunta se hace con frecuencia, así que permítanme comenzar diciendo que leí todo lo que puedo y todavía no sé cuál es el trato.

He paralelizado un masivo exterior para bucle. La cantidad de iteraciones de bucle varía, generalmente entre 20-150, pero el cuerpo del bucle realiza una gran cantidad de trabajo, y requiere muchas rutinas locales de álgebra lineal intensiva (como el código es parte de la fuente y no es una dependencia externa) . Dentro del cuerpo del bucle hay más de 1000 llamadas a estas rutinas, pero todas son totalmente independientes entre sí, así que pensé que sería un candidato principal para el paralelismo. El código de bucle es C ++, pero llama a muchas subrutinas escritas en C.

El código se ve así;

<declare and initialize shared variables here> #ifdef _OPENMP #pragma omp parallel for / private(....)/ shared(....) / firstprivate(....) schedule(runtime) #endif for(tst = 0; tst < ntest; tst++) { // Lots of functionality (science!) // Calls to other deep functions which manipulate private variables only // Call to function which has 1000 loop iterations doing matrix manipulation // With no exaggeration, there are probably millions // of for-loop iterations in this body, in the various functions called. // They also do lots of mallocing and freeing // Finally generated some calculated_values shared_array1[tst] = calculated_value1; shared_array2[tst] = calculated_value2; shared_array3[tst] = calculated_value3; } // end of parallel and for // final tidy up

Creo que no debería haber ninguna sincronización, la única vez que los subprocesos acceden a una variable compartida son los shared_arrays , y acceden a puntos únicos en esos arreglos, indexados por tst .

La cosa es que, cuando subo el número de subprocesos (en un clúster de múltiples núcleos), las velocidades que estamos viendo (donde invocamos este bucle 5 veces) son las siguientes;

Elapsed time System time Serial: 188.149 1.031 2 thrds: 148.542 6.788 4 thrds: 309.586 424.037 # SAY WHAT? 8 thrds: 230.290 568.166 16 thrds: 219.133 799.780

Las cosas que pueden notarse son el salto masivo en el tiempo del sistema entre 2 y 4 subprocesos, y el hecho de que el tiempo transcurrido se duplica a medida que avanzamos de 2 a 4, y luego disminuye lentamente.

Lo he intentado con una amplia gama de parámetros OMP_SCHEDULE pero sin suerte. ¿Está esto relacionado con el hecho de que cada hilo está usando malloc / new y free / delete mucho? Esto siempre se ha ejecutado con 8GB de memoria, pero supongo que no es un problema. Francamente, el enorme aumento en el tiempo del sistema hace que parezca que los hilos pueden estar bloqueando, pero no tengo idea de por qué sucedería eso.

ACTUALIZACIÓN 1 Realmente pensé que el intercambio falso iba a ser el problema, por lo que reescribí el código para que los bucles almacenen sus valores calculados en arreglos de subprocesos locales, y luego copien estos arreglos en el arreglo compartido al final. Lamentablemente esto no tuvo ningún impacto, aunque casi no me lo creo.

Siguiendo el consejo de @ cmeerw, corrí strace -f, y después de toda la inicialización hay solo millones de líneas de

[pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58066] <... futex resumed> ) = -1 EAGAIN (Resource temporarily unavailable) [pid 58065] <... futex resumed> ) = -1 EAGAIN (Resource temporarily unavailable) [pid 57684] <... futex resumed> ) = 0 [pid 58067] <... futex resumed> ) = 0 [pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58066] <... futex resumed> ) = 0 [pid 57684] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...> [pid 58065] <... futex resumed> ) = 0 [pid 58067] <... futex resumed> ) = 0 [pid 57684] <... futex resumed> ) = -1 EAGAIN (Resource temporarily unavailable) [pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...> [pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58066] <... futex resumed> ) = -1 EAGAIN (Resource temporarily unavailable) [pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58065] <... futex resumed> ) = 0 [pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 57684] <... futex resumed> ) = 0 [pid 58067] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...> [pid 58066] <... futex resumed> ) = 0 [pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58067] <... futex resumed> ) = -1 EAGAIN (Resource temporarily unavailable) [pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...> [pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58065] <... futex resumed> ) = 0 [pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58066] <... futex resumed> ) = -1 EAGAIN (Resource temporarily unavailable) [pid 57684] <... futex resumed> ) = 0 [pid 58067] <... futex resumed> ) = 0 [pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58065] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...> [pid 58066] <... futex resumed> ) = 0 [pid 58065] <... futex resumed> ) = -1 EAGAIN (Resource temporarily unavailable) [pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...> [pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 58067] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...> [pid 58066] <... futex resumed> ) = -1 EAGAIN (Resource temporarily unavailable) [pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...> [pid 57684] <... futex resumed> ) = 0

¿Alguien tiene alguna idea de lo que significa? ¿Parece que los subprocesos cambian de contexto con demasiada frecuencia, o simplemente bloquean y desbloquean? Cuando strace la misma implementación con OMP_NUM_THREADS establecido en 0, no obtengo nada de esto en absoluto. Para algunas comparaciones, el archivo de registro generado cuando se usa 1 subproceso es de 486 KB, y el archivo de registro generado cuando se usan 4 subprocesos es de 266 MB.

En otras palabras, la versión paralela invoca 4170104 líneas adicionales de archivo de registro ...

ACTUALIZACIÓN 2

Como lo sugirió Tom, intenté enlazar hilos a procesadores específicos en vano. Estamos en OpenMP 3.1, así que configuro la variable de entorno usando la export OMP_PROC_BIND=true . Archivo de registro del mismo tamaño y mismo período de tiempo.

ACTUALIZACIÓN 3

La trama se complica. Habiendo perfilado solo en el clúster hasta ahora, instalé GNU GCC 4.7 a través de Macports y compilado (con openMP) en mi Macbook por primera vez (el GCC-4.2.1 de Apple lanza un error de compilación cuando OpenMP está habilitado, por lo que no había compilado y ejecutado en paralelo localmente hasta ahora). En el Macbook, ves básicamente la tendencia que esperas

C-code time Serial: ~34 seconds 2 thrds: ~21 seconds 4 thrds: ~14 seconds 8 thrds: ~12 seconds 16 thrds: ~9 seconds

Vemos rendimientos decrecientes hacia los extremos, aunque esto no es sorprendente ya que un par de conjuntos de datos que estamos repitiendo en esta prueba tienen <16 miembros (por lo tanto, estamos generando 16 subprocesos para, digamos un for-loop con 7 iteraciones).

Entonces, la pregunta sigue siendo: ¿POR QUÉ el rendimiento del clúster se degrada tan gravemente? Voy a probar en un linuxbox de Quadcore diferente esta noche. El clúster se compila con GNU-GCC 4.6.3, pero no puedo creer que en sí mismo va a hacer tal diferencia.

Ni ltrace ni GDB están instalados en el clúster (y no puedo acceder a ellos por varios motivos). Si mi linuxbox ofrece un rendimiento similar al de un clúster, ejecutaré el análisis de ltrace correspondiente allí.

ACTUALIZACIÓN 4

Oh mi. Duelo inicié mi Macbook Pro en Ubuntu (12.04) y volví a ejecutar el código. Todo se ejecuta (lo cual es un tanto tranquilizador) pero veo el mismo comportamiento extraño y de mal rendimiento que veo en los clústeres y la misma serie de millones de llamadas futex . Dado que la única diferencia entre mi máquina local en Ubuntu y en OSX es el software (y estoy usando el mismo compilador y bibliotecas, ¡probablemente no hay implementaciones de glibc diferentes para OSX y Ubuntu!) Ahora me pregunto si esto es algo. para ver cómo Linux programa / distribuye los hilos. En cualquier caso, estar en mi máquina local hace que todo sea un millón de veces más fácil, así que voy a seguir adelante y hacer un ltrace -f y ver qué puedo encontrar. Escribí un trabajo alrededor de los clusters que forks() el proceso por separado y dan un 1/2 perfecto en el tiempo de ejecución, por lo que definitivamente es posible hacer que el paralelismo funcione ...

Así que después de un perfil bastante extenso (gracias a este gran post para obtener información sobre gprof y muestreo de tiempo con gdb) que involucró escribir una función de envoltorio grande para generar un código de nivel de producción para el perfil, se hizo evidente que, en la mayoría de los casos, abortó el código en ejecución con gdb y corrió hacia backtrace la pila estaba en una llamada STL <vector> , manipulando un vector de alguna manera.

El código pasa algunos vectores a la sección parallel como variables privadas, que parecían funcionar bien. Sin embargo, después de extraer todos los vectores y reemplazarlos con arreglos (y algunos otros juegos de jiggery-pokery para hacer ese trabajo) vi una aceleración significativa. Con los conjuntos de datos pequeños y artificiales, la velocidad es casi perfecta (es decir, al duplicar la cantidad de subprocesos la mitad del tiempo), mientras que con los conjuntos de datos reales la velocidad no es tan buena, pero esto tiene mucho sentido como en el contexto de cómo funciona el código.

Parece que, por el motivo que sea (¿tal vez algunas variables estáticas o globales en la implementación de STL<vector> ?) Cuando hay bucles que se mueven a través de cientos de miles de iteraciones en paralelo, hay un bloqueo de nivel profundo, que ocurre en Linux (Ubuntu 12.01). y CentOS 6.2) pero no en OSX.

Estoy realmente intrigado en cuanto a por qué veo esta diferencia. ¿Podría haber alguna diferencia en la forma en que se implementa la STL (la versión de OSX se compiló bajo GNU GCC 4.7, como lo fueron las de Linux), o tiene que ver con el cambio de contexto (como sugiere Arne Babenhauserheide)?

En resumen, mi proceso de depuración fue el siguiente;

  • Perfil inicial desde R para identificar el problema.

  • Asegurado que no había variables static actuando como variables compartidas

  • Perfilado con strace -f y ltrace -f que fue realmente útil para identificar el bloqueo como el culpable

  • Perfilado con valgrind para buscar cualquier error.

  • Probé una variedad de combinaciones para el tipo de programa (automático, guiado, estático, dinámico) y tamaño de trozo.

  • Intenté enlazar hilos a procesadores específicos.

  • Se evitó el uso compartido falso al crear búferes de subprocesos locales para los valores, y luego implementar un evento de sincronización único al final del for-loop

  • Se eliminaron todos los mallocing y freeing de la región paralela; no ayudaron con el problema, pero proporcionaron un pequeño aumento de velocidad general

  • Probado en varias arquitecturas y sistemas operativos, no me ayudó mucho al final, pero demostró que se trataba de un problema de Linux vs. OSX y no de una computadora o computadora de escritorio.

  • Creación de una versión que implemente la concurrencia mediante una llamada fork() , que tiene la carga de trabajo entre dos procesos. Esto redujo a la mitad el tiempo tanto en OSX como en Linux, lo cual fue bueno

  • Construyó un simulador de datos para replicar las cargas de datos de producción.

  • perfilado gprof

  • gdb tiempo de muestreo de perfiles (abortar y retroceder)

  • Comentar operaciones vectoriales

  • Si esto no hubiera funcionado, el enlace de Arne Babenhauserheide parece que podría tener algunas cosas cruciales sobre problemas de fragmentación de memoria con OpenMP

Dado que los subprocesos en realidad no interactúan, puede cambiar el código a multiprocesamiento. Al final, solo se enviaría un mensaje y se garantizaría que los subprocesos no necesitan sincronizar nada.

Aquí está el código Python3.2 que básicamente lo hace (es probable que no quiera hacerlo en Python por razones de rendimiento) o que ponga el bucle for en una función C y se enlace con cython. Lo verá en el código. Por eso lo muestro en Python de todos modos):

from concurrent import futures from my_cython_module import huge_function parameters = range(ntest) with futures.ProcessPoolExecutor(4) as e: results = e.map(huge_function, parameters) shared_array = list(results)

Eso es. Aumente la cantidad de procesos a la cantidad de trabajos que puede colocar en el clúster y deje que cada proceso simplemente envíe y supervise un trabajo para escalar a cualquier número de llamadas.

Enormes funciones sin interacción y pequeños valores de entrada casi requieren un multiprocesamiento. Y tan pronto como tenga eso, cambiar a MPI (con una escala casi ilimitada) no es demasiado difícil.

Desde el punto de vista técnico, los conmutadores de contexto AFAIK en Linux son bastante caros (kernel monolítico con mucha memoria en el espacio del kernel), mientras que son mucho más baratos en OSX o en Hurd (Mach microkernel). Eso podría explicar la enorme cantidad de tiempo del sistema que ves en Linux pero no en OSX.

Es difícil saber con certeza lo que está sucediendo sin un perfil significativo, pero la curva de rendimiento parece indicar un falso intercambio ...

los subprocesos usan objetos diferentes, pero esos objetos están lo suficientemente cerca en la memoria como para caer en la misma línea de caché, y el sistema de caché los trata como un único bulto que está protegido de manera efectiva por un bloqueo de escritura de hardware que solo un núcleo puede contener hora

Gran artículo sobre el tema en el Dr. Dobbs

http://www.drdobbs.com/go-parallel/article/217500206?pgno=1

En particular, el hecho de que las rutinas estén haciendo mucho malloc / free podría llevar a esto.

Una solución es usar un asignador de memoria basado en grupo en lugar del asignador predeterminado, de modo que cada subproceso tiende a asignar memoria desde un rango de direcciones físico diferente.