OpenMP: ¿Cuál es el beneficio de las paralelizaciones de anidamiento?

Question

Por lo que entiendo, #pragma omp parallel y sus variaciones básicamente ejecutan el siguiente bloque en varios subprocesos concurrentes, que corresponde al número de CPU. Al tener paralelizaciones anidadas - paralelas para dentro de paralelo para, funciones paralelas dentro de funciones paralelas, etc. - ¿qué ocurre en la paralelización interna?

Soy nuevo en OpenMP, y el caso que tengo en mente es probablemente bastante trivial: multiplicar un vector con una matriz. Esto se hace en dos bucles anidados. Suponiendo que el número de CPU es menor que el número de elementos en el vector, ¿hay algún beneficio al tratar de ejecutar el bucle interno en paralelo? ¿El número total de subprocesos será mayor que el número de CPU o el bucle interno se ejecutará secuencialmente?

Answer 1

(1) Anidado en el paralelismo OpenMP: http://docs.oracle.com/cd/E19205-01/819-5270/aewbc/index.html

Es necesario activar el paralelismo anidado estableciendo OMP_NESTED o omp_set_nested porque muchas implementaciones desactivar esta función por defecto, aunque algunas implementaciones no apoyaron plenamente el paralelismo anidado . Si está activado, siempre que se encuentre con parallel for, OpenMP creará la cantidad de hilos definidos en OMP_NUM_THREADS. Entonces, si el paralelismo de 2 niveles, el número total de hilos sería N^2, donde N = OMP_NUM_THREADS.

Tal paralelismo anidado causará sobresuscripción, (es decir, el número de hilos ocupados es mayor que los núcleos), lo que puede degradar la aceleración. En un caso extremo, donde el paralelismo anidado se llama de manera recursiva, los hilos pueden estar hinchados (por ejemplo, creando hilos de 1000s), y la computadora simplemente pierde el tiempo para el cambio de contexto. En tal caso, puede controlar el número de subprocesos dinámicamente configurando omp_set_dynamic.

(2) Un ejemplo de multiplicación de la matriz-vector: el código se vería así:

// Input: A(N by M), B(M by 1) 
// Output: C(N by 1) 
for (int i = 0; i < N; ++i) 
    for (int j = 0; j < M; ++j) 
    C[i] += A[i][j] * B[j]; 

En general, la paralelización de bucles internos mientras que los bucles exteriores son posibles es malo debido a la bifurcación/unión por encima de los hilos. (aunque muchas implementaciones OpenMP preproducen hilos, todavía requiere que algunos despachen tareas a hilos y para invocar barreras implícitas al final de paralelo-for)

Su preocupación es el caso de dónde N < # de CPU. Sí, claro, en este caso, la aceleración estaría limitada por N, y dejar que el paralelismo anidado definitivamente tenga beneficios.

Sin embargo, entonces el código provocaría sobresuscripción si N es suficientemente grande. Solo estoy pensando en las siguientes soluciones:

• Cambiando la estructura del bucle de modo que exista solo un bucle de 1 nivel.(Parece posible)
• Especializando el código: si N es pequeño, haga el paralelismo anidado; de lo contrario, no haga eso.
• paralelismo anidado con omp_set_dynamic. Pero, por favor, asegúrese de que omp_set_dynamic controla el número de subprocesos y la actividad de los subprocesos. Las implementaciones pueden variar.

Answer 2

Para algo así como el álgebra lineal densa, donde todo el paralelismo potencial ya se encuentra desnudo en un lugar en bucles agradables y anchos, no necesita paraísismo anidado, si desea protegerse contra el caso de tener (por ejemplo) matrículas realmente estrechas donde la dimensión inicial puede ser más pequeña que la cantidad de núcleos, entonces todo lo que necesita es la directiva collapse que, teóricamente, aplana los múltiples bucles en uno solo.

El paralelismo anidado es para aquellos casos en que el paralelismo no está completamente expuesto a la vez; digamos que desea hacer 2 evaluaciones de funciones simultáneas, cada una de las cuales puede utilizar 4 núcleos, y tiene un sistema de 8 núcleos. Usted llama a la función en una sección paralela, y dentro de la definición de la función hay un adicional, por ejemplo, paralelo para.

Answer 3

En el nivel externo, use la cláusula NUM_THREADS (num_groups) para establecer el número de subprocesos que se utilizarán. Si su bucle externo tiene un recuento N, y la cantidad de procesadores o núcleos es num_cores, use num_groups = min (N, num_cores). En el nivel interno, debe establecer el número de subprocesos para cada grupo de subprocesos de modo que la cantidad total de subprocesos sea igual a la cantidad de núcleos. Entonces, si num_cores = 8, N = 4, entonces num_groups = 4. En el nivel inferior cada subhilo debería usar 2 hilos (ya que 2 + 2 + 2 + 2 = 8) así que use la cláusula NUM_THREADS (2). Puede recopilar la cantidad de subhilos en una matriz con un elemento por subproceso de región exterior (con elementos num_groups).

Esta estrategia siempre hace un uso óptimo de sus núcleos. Cuando N < num_cores ocurre cierta paralelización anidada. Cuando N> = num_cores, la matriz de recuentos de subhebra contiene todos los 1 y, por lo tanto, el ciclo interno es efectivamente serial.