c++ - preferente - OpenMP: buenas estrategias para la búsqueda en profundidad

dfs algorithm

Question

Estoy escribiendo un programa en C ++ que hace una búsqueda de fuerza bruta para los recorridos cerrados de Knight . El código está aquí .

Me gustaría paralelizar esto usando OpenMP. Mi problema es hacer esto de una manera que cree un grado suficiente de paralelismo. Actualmente, la parte relevante de mi código se parece a esto

#pragma omp parallel for reduction(+:count) if (depth==4)
  for (size_t i=0;i<g.neighbours[last].size();i++){
    auto n = g.neighbours[last][i];
    // See if n can be used to extend or complete the tour

El if (depth==4) es mi intento de asegurarme de que no se creen demasiadas tareas paralelas pero, por otro lado, se crean suficientes para mantener todos los procesadores ocupados. La depth==2 configuración depth==2 no cambia el tiempo de ejecución del programa.

Esto no parece estar funcionando. Para un problema de 3x12, en mi procesador de doble núcleo, el tiempo total de CPU consumido por la versión OpenMP es de alrededor de 130s, mientras que una versión de un solo subproceso sin OpenMP tarda alrededor de 40 segundos de tiempo de CPU.

Agradecería las sugerencias sobre cómo usar OpenMP o las razones por las que no es adecuado para este problema.

ACTUALIZACIÓN: Gracias a @Zulan tengo una versión más nueva que utiliza tareas OpenMP con un rendimiento secuencial mucho más rápido y una buena paralelización.

Answer 1

En primer lugar, echemos un vistazo súper rápido a la ubicación de su aplicación, usando perf :

perf record ./knights_tour_omp 3 12
perf report

# Overhead  Command          Shared Object        Symbol                                                                                         
# ........  ...............  ...................  .................................................................................................
#
    53.29%  knights_tour_om  libc-2.19.so         [.] malloc                                                                                       
    23.16%  knights_tour_om  libc-2.19.so         [.] _int_free                                                                                    
    10.31%  knights_tour_om  libc-2.19.so         [.] _int_malloc                                                                                  
     4.78%  knights_tour_om  knights_tour_omp     [.] _Z13continue_tourIZ4mainEUlRKSt6vectorIiSaIiEEE_EmRK5GraphS4_RKS0_IcSaIcEEiiRT_.constprop.119
     2.64%  knights_tour_om  libc-2.19.so         [.] __memmove_ssse3_back                                                                         
     1.48%  knights_tour_om  libc-2.19.so         [.] malloc_consolidate                                                                 

Su aplicación pasa todo el tiempo asignando y liberando memoria. Si bien hay algunos informes de que malloc no está completamente bloqueado , tampoco parece paralelizarse bien.

No necesita mucha investigación adicional para descubrir que esto se debe a la copia de los vectores visited y de path para cada iteración. Afortunadamente DFS tiene la propiedad agradable, que no necesariamente necesita hacer eso, puede reutilizar el estado y restaurarlo:

visited[n] = 1;
path.emplace_back(n);
count += continue_tour(g, path, visited, depth+1,remain-1, cb);
visited[n] = 0;
path.pop_back();

Sin embargo, para el bucle paralelo, necesita hacer copias de trabajo para cada hilo, por lo que necesita hacer una ruta separada para este caso con el comportamiento original.

Este pequeño cambio ya reduce el tiempo de ejecución en serie de 22 s a 2.65 s. Además con 2 hilos baja a 2.0 s. Hay una aceleración, pero no es tan buena, ¿por qué? Para ilustrar eso, utilicé 4 hilos (en un sistema lo suficientemente grande). Aquí está la ejecución de la aplicación a lo largo del tiempo registrada con score-p , que se muestra en Vampir .

El rojo es trabajo real, el azul es una barrera implícita, lo que significa que los hilos están al ralentí. Siempre parece haber 3 o 1 hilo activo. La razón es simple: la mayor parte de la posición en el tablero tiene 4 o 2 vecinos, pero uno de ellos ya está visitado, por lo que esta iteración del bucle se completa al instante. Entonces, el trabajo real está en 3 o 1 iteración del ciclo. Esa es una coincidencia particularmente mala para 2 hilos. Con 3 hilos, el tiempo de ejecución baja a 1.7 s

Nota: Todo el tiempo con gcc 5.3 en un E5-2690 @ 2.90 GHz sin turbo. No se tuvo cuidado de compensar la varianza en tiempos de ejecución.

Teniendo en cuenta que un bucle único expone el paralelismo muy malo para ese problema, es posible que tenga la tentación de anidar bucles paralelos. Te animo a que lo pruebes, pero no creo que salga bien. Creo que las tareas funcionan bien en este contexto, porque las tareas pueden engendrar otras tareas. Por lo tanto, puede generar cada paso recursivo como una tarea y dejar que el tiempo de ejecución de OMP determine una buena programación. Pero asegúrese de limitarlo hasta una cierta depth , para que las tareas no sean demasiado cortas.

Quiero enfatizar la importancia de usar herramientas: tratar de resolver problemas de rendimiento sin herramientas de análisis de rendimiento es como resolver errores sin un depurador. perf está disponible para Linux y en su forma básica es extremadamente simple de usar. Sin embargo, es muy poderoso (aunque el uso avanzado puede tener algunos inconvenientes).

Una observación adicional: con OpenMP a menudo vale la pena probar diferentes compiladores. Por ejemplo, con el código de tarea (fijo), gcc no escala más allá de 4 hilos, mientras que el compilador de inteligencia / tiempo de ejecución omp proporciona una aceleración de hasta 24 hilos.