c++ - dollars - openmp fortran

OpenMP Dynamic vs Programación guiada

Question

Estoy estudiando la programación de OpenMP y específicamente los diferentes tipos. Entiendo el comportamiento general de cada tipo, pero sería útil aclarar cuándo elegir entre dynamic programación dynamic y guided .

Los documentos de Intel describen dynamic programación dynamic :

Use la cola de trabajo interna para dar un bloque de iteraciones de bucle del tamaño de un trozo a cada hilo. Cuando finaliza un hilo, recupera el siguiente bloque de iteraciones de bucle desde la parte superior de la cola de trabajo. De forma predeterminada, el tamaño del fragmento es 1. Tenga cuidado al usar este tipo de programación debido a la sobrecarga adicional involucrada.

También describe la programación guided :

Similar a la programación dinámica, pero el tamaño del trozo comienza en grande y disminuye para manejar mejor el desequilibrio de carga entre iteraciones. El parámetro chunk opcional los especifica el tamaño mínimo que se debe usar. Por defecto, el tamaño del fragmento es aproximadamente loop_count / number_of_threads.

Dado que la programación guided disminuye dinámicamente el tamaño de la porción en el tiempo de ejecución, ¿por qué usaría dynamic programación dynamic ?

He investigado esta pregunta y encontré esta tabla de Dartmouth :

guided se enumera como de high sobrecarga, mientras que dynamic tiene mediana sobrecarga.

Esto inicialmente tenía sentido, pero luego de una investigación adicional leí un artículo de Intel sobre el tema. A partir de la tabla anterior, la programación guided teórica me llevaría más tiempo debido al análisis y los ajustes del tamaño del trozo en tiempo de ejecución (incluso cuando se usa correctamente). Sin embargo, en el artículo de Intel dice:

Los horarios guiados funcionan mejor con tamaños de trozos pequeños como límite; Esto le da la mayor flexibilidad. No está claro por qué empeoran en tamaños de trozos más grandes, pero pueden tomar demasiado tiempo cuando se limitan a tamaños de trozos grandes.

¿Por qué el tamaño del fragmento se relaciona con la toma guided más larga que la dynamic ? Tendría sentido que la falta de "flexibilidad" causara una pérdida de rendimiento al bloquear el tamaño del trozo demasiado alto. Sin embargo, no lo describiría como "gastos generales", y el problema del bloqueo desacreditaría la teoría anterior.

Por último, se afirma en el artículo:

Los horarios dinámicos dan la mayor flexibilidad, pero tienen el mayor impacto de rendimiento cuando se programan incorrectamente.

Tiene sentido que dynamic programación dynamic sea ​​más óptima que la static , pero ¿por qué es más óptima que la guided ? ¿Es sólo la sobrecarga que estoy cuestionando?

Esta publicación de SO un tanto relacionada explica NUMA relacionada con los tipos de programación. Es irrelevante para esta pregunta, ya que la organización requerida se pierde por el comportamiento de "primer orden de llegada" de estos tipos de programación.

dynamic programación dynamic puede ser coalescente, lo que provoca una mejora en el rendimiento, pero la misma hipótesis debería aplicarse a la guided .

Este es el momento de cada tipo de programación en diferentes tamaños de trozos del artículo de Intel como referencia. Solo se trata de grabaciones de un programa y algunas reglas se aplican de manera diferente por programa y máquina (especialmente con la programación), pero deben proporcionar las tendencias generales.

EDITAR (núcleo de mi pregunta):

• ¿Qué afecta el tiempo de ejecución de la programación guided ? ¿Ejemplos específicos? ¿Por qué es más lento que dynamic en algunos casos?
• ¿Cuándo preferiría guided sobre dynamic o viceversa?
• Una vez que se haya explicado esto, ¿las fuentes anteriores respaldan su explicación? ¿Se contradicen en absoluto?

Answer 1

¿Qué afecta el tiempo de ejecución de la programación guiada?

Hay tres efectos a considerar:

1. Balance de carga

El objetivo principal de la programación dinámica / guiada es mejorar la distribución del trabajo en el caso de que no cada iteración de bucle contenga la misma cantidad de trabajo. Fundamentalmente:

• schedule(dynamic, 1) proporciona un equilibrio de carga óptimo
• dynamic, k siempre tendrá un equilibrio de carga igual o mejor que el guided, k

El estándar exige que el tamaño de cada fragmento sea proporcional al número de iteraciones no asignadas dividido por el número de subprocesos en el equipo, disminuyendo a k .

La implementación de OpenCC de GCC toma esto literalmente, ignorando lo proporcional . Por ejemplo, para 4 hilos, k=1 , tendrá 32 iteraciones como 8, 6, 5, 4, 3, 2, 1, 1, 1, 1 . Ahora, en mi humilde opinión, esto es realmente estúpido: da como resultado un desequilibrio de carga deficiente si las primeras iteraciones 1 / n contienen más de 1 / n del trabajo.

¿Ejemplos específicos? ¿Por qué es más lento que dinámico en algunos casos?

Ok, veamos un ejemplo trivial donde el trabajo interno disminuye con la iteración de bucle:

#include <omp.h>

void work(long ww) {
    volatile long sum = 0;
    for (long w = 0; w < ww; w++) sum += w;
}

int main() {
    const long max = 32, factor = 10000000l;
    #pragma omp parallel for schedule(guided, 1)
    for (int i = 0; i < max; i++) {
         work((max - i) * factor);
    }
}

La ejecución se ve así: ¹

Como puedes ver, guided hace realmente mal aquí. guided hará mucho mejor para diferentes tipos de distribuciones de trabajo. También es posible implementar guiado de forma diferente. La implementación en clang (que IIRC proviene de Intel), es mucho más sofisticada . Realmente no entiendo la idea detrás de la implementación ingenua de GCC. En mi opinión, efectivamente elimina el propósito de la reducción dinámica de la carga si le das 1/n trabajo al primer hilo.

2. arriba

Ahora, cada fragmento dinámico tiene algún impacto en el rendimiento debido al acceso al estado compartido. La sobrecarga de guided será ligeramente más alta por segmento que dynamic , ya que hay un poco más de cómputo por hacer. Sin embargo, guided, k tendrá menos segmentos dinámicos totales que dynamic, k .

La sobrecarga también dependerá de la implementación, por ejemplo, si utiliza atómica o bloqueos para proteger el estado compartido.

3. Efectos de caché y NUMA

Digamos que escribe a un vector de enteros en tu iteración de bucle. Si cada segunda iteración fuera ejecutada por un hilo diferente, cada segundo elemento del vector sería escrito por un núcleo diferente. Eso es realmente malo porque, al hacerlo, compiten líneas de caché que contienen elementos vecinos (intercambio falso). Si tienes tamaños de trozos pequeños y / o tamaños de trozos que no se alinean bien con los cachés, obtienes un mal rendimiento en los "bordes" de los trozos. Esta es la razón por la que normalmente prefiere tamaños de trozos grandes ( 2^n ). guided puede darle un tamaño de trozo más grande en promedio, pero no 2^n (o k*m ).

Esta respuesta (a la que ya hizo referencia), analiza en detalle la desventaja de la programación dinámica / guiada en términos de NUMA, pero esto también se aplica a la ubicación / cachés.

No adivinar, medir

Dados los diversos factores y la dificultad para predecir detalles específicos, solo puedo recomendar medir su aplicación específica, en su sistema específico, en su configuración específica, con su compilador específico. Desafortunadamente no hay portabilidad de rendimiento perfecto. Yo personalmente diría que esto es particularmente cierto para los guided .

¿Cuándo preferiría guiado sobre dinámico o viceversa?

Si tiene conocimiento específico sobre la sobrecarga / trabajo por iteración, diría que dynamic, k le da los resultados más estables al elegir una buena k . En particular, no depende tanto de cuán inteligente sea la implementación.

Por otro lado, guided puede ser una buena primera aproximación, con una relación razonable de equilibrio de sobrecarga / carga, al menos para una implementación inteligente. Tenga especial cuidado con la guided si sabe que los tiempos de iteración posteriores son más cortos.

Tenga en cuenta que también hay una schedule(auto) , que le da un control completo al compilador / tiempo de ejecución, y una schedule(runtime) , que le permite seleccionar la política de programación durante el tiempo de ejecución.

Una vez que se haya explicado esto, ¿las fuentes anteriores respaldan su explicación? ¿Se contradicen en absoluto?

Tome las fuentes, incluyendo esta respuesta, con un grano de sal. Ni el cuadro que publicaste, ni la imagen de mi línea de tiempo son números científicamente exactos. Hay una gran variación en los resultados y no hay barras de error, probablemente solo estarían por todos lados con estos pocos puntos de datos. Además, el cuadro combina los múltiples efectos que mencioné sin revelar el código de Work .

[De los documentos de Intel]

Por defecto, el tamaño del fragmento es aproximadamente loop_count / number_of_threads.

Esto contradice mi observación de que icc maneja mi pequeño ejemplo mucho mejor.

^{1: Uso de GCC 6.3.1, Score-P / Vampir para visualización, dos funciones de trabajo alternas para colorear.}