c++ - omp - ¿Cuál es la diferencia entre el horario "estático" y el "dinámico" en OpenMP?

openmp tutorial

Question

Empecé a trabajar con OpenMP usando C ++.

Tengo dos preguntas:

1. ¿Qué es #pragma omp for schedule ?
2. ¿Cuál es la diferencia entre dynamic y static ?

Por favor, explica con ejemplos.

Answer 1

Creo que el malentendido proviene del hecho de que te pierdes el punto acerca de OpenMP. En una oración, OpenMP te permite ejecutar tu programa más rápido al habilitar el paralelismo. En un programa, el paralelismo se puede habilitar de muchas maneras y uno de los es mediante el uso de subprocesos. Supongamos que tiene y matriz:

[1,2,3,4,5,6,7,8,9,10]

y desea incrementar todos los elementos en 1 en esta matriz.

Si vas a usar

#pragma omp for schedule(static, 5)

significa que a cada uno de los hilos se le asignarán 5 iteraciones contiguas. En este caso, el primer hilo tendrá 5 números. El segundo tomará otros 5 y así sucesivamente hasta que no haya más datos para procesar o se alcance el número máximo de hilos (generalmente igual a la cantidad de núcleos). El intercambio de la carga de trabajo se realiza durante la compilación.

En caso de

#pragma omp for schedule(dynamic, 5)

El trabajo se compartirá entre hilos, pero este procedimiento ocurrirá en tiempo de ejecución. Por lo tanto, implica más gastos generales. El segundo parámetro especifica el tamaño del fragmento de los datos.

Al no estar familiarizado con OpenMP, me arriesgo a suponer que el tipo dinámico es más apropiado cuando el código compilado se ejecutará en el sistema que tiene una configuración diferente a aquella en la que se compiló el código.

Recomendaría la siguiente página donde se discuten las técnicas utilizadas para paralelizar el código, las precondiciones y las limitaciones.

https://computing.llnl.gov/tutorials/parallel_comp/

Enlaces adicionales :
http://en.wikipedia.org/wiki/OpenMP
Diferencia entre el horario estático y dinámico en openMP en C
http://openmp.blogspot.se/

Answer 2

El esquema de particionamiento de bucle es diferente. El planificador estático dividiría un ciclo sobre N elementos en subconjuntos M, y cada subconjunto contendría estrictamente elementos N / M.

El enfoque dinámico calcula el tamaño de los subconjuntos sobre la marcha, lo que puede ser útil si los tiempos de cálculo de los subconjuntos varían.

El enfoque estático debería usarse si los tiempos de cálculo varían poco.

Answer 3

Otros han contestado la mayor parte de la pregunta, pero me gustaría señalar algunos casos específicos en los que un tipo de programación particular es más apropiado que los otros. Programa controla cómo las iteraciones de bucle se dividen entre hilos. Elegir el horario correcto puede tener un gran impacto en la velocidad de la aplicación.

static horario static significa que los bloques de iteraciones se asignan de forma estática a los hilos de ejecución en una operación de todos contra todos. Lo bueno de la programación estática es que el tiempo de ejecución de OpenMP garantiza que si tiene dos bucles separados con el mismo número de iteraciones y los ejecuta con el mismo número de subprocesos usando programación estática, cada subproceso recibirá exactamente el mismo rango de iteración ( s) en ambas regiones paralelas. Esto es bastante importante en los sistemas NUMA: si toca alguna memoria en el primer ciclo, residirá en el nodo NUMA donde estaba el subproceso que se está ejecutando. Luego, en el segundo ciclo, el mismo subproceso podría acceder a la misma ubicación de memoria más rápido, ya que residirá en el mismo nodo NUMA.

Imagine que hay dos nodos NUMA: nodo 0 y nodo 1, por ejemplo, una placa Intel Nehalem de dos sockets con CPU de 4 núcleos en ambos sockets. Entonces, los hilos 0, 1, 2 y 3 residirán en el nodo 0 y los hilos 4, 5, 6 y 7 residirán en el nodo 1:

|             | core 0 | thread 0 |
| socket 0    | core 1 | thread 1 |
| NUMA node 0 | core 2 | thread 2 |
|             | core 3 | thread 3 |

|             | core 4 | thread 4 |
| socket 1    | core 5 | thread 5 |
| NUMA node 1 | core 6 | thread 6 |
|             | core 7 | thread 7 |

Cada núcleo puede acceder a la memoria desde cada nodo NUMA, pero el acceso remoto es más lento (1.5x - 1.9x más lento en Intel) que el acceso al nodo local. Ejecutas algo como esto:

char *a = (char *)malloc(8*4096);

#pragma omp parallel for schedule(static,1) num_threads(8)
for (int i = 0; i < 8; i++)
   memset(&a[i*4096], 0, 4096);

4096 bytes en este caso es el tamaño estándar de una página de memoria en Linux en x86 si no se usan páginas grandes. Este código pondrá a cero toda la matriz de 32 KiB a . La llamada malloc() solo reserva espacio de direcciones virtual pero no "toca" la memoria física (este es el comportamiento predeterminado a menos que se use alguna otra versión de malloc , por ejemplo, una que ponga a cero la memoria como lo hace calloc() ). Ahora esta matriz es contigua pero solo en la memoria virtual. En la memoria física, la mitad estaría en la memoria conectada al zócalo 0 y la otra mitad en la memoria conectada al zócalo 1. Esto es así porque diferentes partes se ponen a cero por hilos diferentes y esos hilos residen en diferentes núcleos y hay algo llamado primer toque Política NUMA que significa que las páginas de memoria se asignan en el nodo NUMA en el que reside el hilo que primero "tocó" la página de memoria.

|             | core 0 | thread 0 | a[0]     ... a[4095]
| socket 0    | core 1 | thread 1 | a[4096]  ... a[8191]
| NUMA node 0 | core 2 | thread 2 | a[8192]  ... a[12287]
|             | core 3 | thread 3 | a[12288] ... a[16383]

|             | core 4 | thread 4 | a[16384] ... a[20479]
| socket 1    | core 5 | thread 5 | a[20480] ... a[24575]
| NUMA node 1 | core 6 | thread 6 | a[24576] ... a[28671]
|             | core 7 | thread 7 | a[28672] ... a[32768]

Ahora vamos a ejecutar otro ciclo como este:

#pragma omp parallel for schedule(static,1) num_threads(8)
for (i = 0; i < 8; i++)
   memset(&a[i*4096], 1, 4096);

Cada hilo accederá a la memoria física ya mapeada y tendrá la misma asignación de hilo a la región de memoria que la del primer ciclo. Significa que los subprocesos solo accederán a la memoria ubicada en sus bloques de memoria local, que será rápida.

Ahora imagina que se usa otro esquema de programación para el segundo ciclo: schedule(static,2) . Esto "cortará" el espacio de iteración en bloques de dos iteraciones y habrá 4 de tales bloques en total. Lo que sucederá es que tendremos el siguiente mapeo de ubicación de la memoria de hilo (a través del número de iteración):

|             | core 0 | thread 0 | a[0]     ... a[8191]  <- OK, same memory node
| socket 0    | core 1 | thread 1 | a[8192]  ... a[16383] <- OK, same memory node
| NUMA node 0 | core 2 | thread 2 | a[16384] ... a[24575] <- Not OK, remote memory
|             | core 3 | thread 3 | a[24576] ... a[32768] <- Not OK, remote memory

|             | core 4 | thread 4 | <idle>
| socket 1    | core 5 | thread 5 | <idle>
| NUMA node 1 | core 6 | thread 6 | <idle>
|             | core 7 | thread 7 | <idle>

Dos cosas malas suceden aquí:

• los subprocesos 4 a 7 permanecen inactivos y se pierde la mitad de la capacidad de cómputo;
• los hilos 2 y 3 acceden a la memoria no local y les tomará aproximadamente el doble de tiempo para terminar, durante ese tiempo los hilos 0 y 1 permanecerán inactivos.

Entonces, una de las ventajas de usar la programación estática es que mejora la localidad en el acceso a la memoria. La desventaja es que la mala elección de los parámetros de programación puede arruinar el rendimiento.

dynamic programación dynamic funciona según el orden de llegada. Dos ejecuciones con el mismo número de subprocesos podrían (y probablemente) producir asignaciones de "espacio de iteración" completamente diferentes -> "subprocesos", como se puede verificar fácilmente:

$ cat dyn.c
#include <stdio.h>
#include <omp.h>

int main (void)
{
  int i;

  #pragma omp parallel num_threads(8)
  {
    #pragma omp for schedule(dynamic,1)
    for (i = 0; i < 8; i++)
      printf("[1] iter %0d, tid %0d/n", i, omp_get_thread_num());

    #pragma omp for schedule(dynamic,1)
    for (i = 0; i < 8; i++)
      printf("[2] iter %0d, tid %0d/n", i, omp_get_thread_num());
  }

  return 0;
}

$ icc -openmp -o dyn.x dyn.c

$ OMP_NUM_THREADS=8 ./dyn.x | sort
[1] iter 0, tid 2
[1] iter 1, tid 0
[1] iter 2, tid 7
[1] iter 3, tid 3
[1] iter 4, tid 4
[1] iter 5, tid 1
[1] iter 6, tid 6
[1] iter 7, tid 5
[2] iter 0, tid 0
[2] iter 1, tid 2
[2] iter 2, tid 7
[2] iter 3, tid 3
[2] iter 4, tid 6
[2] iter 5, tid 1
[2] iter 6, tid 5
[2] iter 7, tid 4

(Se observa el mismo comportamiento cuando se usa gcc su lugar)

Si el código de ejemplo de la sección static se ejecutó con programación dynamic su lugar habrá solo 1/70 (1.4%) posibilidad de que la localidad original se conserve y 69/70 (98.6%) posibilidad de que ocurra acceso remoto. Este hecho a menudo se pasa por alto y, por lo tanto, se logra un rendimiento subóptimo.

Hay otra razón para elegir entre static programación static y dynamic : el equilibrio de la carga de trabajo. Si cada iteración es muy diferente del tiempo medio que debe completarse, puede producirse un desequilibrio laboral elevado en el caso estático. Tomemos como ejemplo el caso donde el tiempo para completar una iteración crece linealmente con el número de iteración. Si el espacio de iteración se divide estáticamente entre dos subprocesos, el segundo tendrá tres veces más trabajo que el primero y, por lo tanto, durante 2/3 del tiempo de cómputo, el primer subproceso estará inactivo. El horario dinámico introduce cierta sobrecarga adicional, pero en ese caso particular conducirá a una distribución de carga de trabajo mucho mejor. Un tipo especial de programación dynamic es el guided donde se dan bloques de iteración cada vez más pequeños a medida que avanza el trabajo.

Dado que el código precompilado podría ejecutarse en varias plataformas, sería bueno que el usuario final pueda controlar la programación. Es por eso que OpenMP proporciona la cláusula especial de schedule(runtime) . Con la programación en runtime el tipo se toma del contenido de la variable de entorno OMP_SCHEDULE . Esto permite probar diferentes tipos de programación sin recompilar la aplicación y también permite al usuario final ajustar su plataforma.