Solución:
Creo que la razón es que OpenMP no puede crear regiones paralelas dentro de regiones paralelas.
Puede tener una región paralela de una región paralela.
Las regiones paralelas de OpenMP pueden estar anidados uno dentro del otro. Si el paralelismo anidado está deshabilitado, entonces el nuevo equipo creado por un hilo que encuentra una construcción paralela dentro de una región paralela consiste
solo del hilo de encuentro. Si el paralelismo anidado está habilitado, luego el nuevo equipo puede constar de más de un hilo (fuente).
Para ejecutar su código correctamente, debe llamar omp_set_nested(1) y omp_set_num_threads(2).
El paralelismo anidado se puede habilitar o deshabilitar configurando la variable de entorno OMP_NESTED o llamando a la función omp_set_nested ()
Para un mejor rendimiento en lugar de secciones, puede usar tareas de OpenMP (aquí se puede encontrar información detallada y ejemplos) de la siguiente manera:
void merge(int * X, int n, int * tmp) {
...
}
void mergeSort(int *X, int n, int *tmp)
{
if (n < 2) return;
#pragma omp task shared(X) if (n > TASK_SIZE)
mergeSort(X, n/2, tmp);
#pragma omp task shared(X) if (n > TASK_SIZE)
mergeSort(X+(n/2), n-(n/2), tmp + n/2);
#pragma omp taskwait
mergeSortAux(X, n, tmp);
}
int main()
{
...
#pragma omp parallel
{
#pragma omp single
mergesort(data, n, tmp);
}
}
El código secuencial del algoritmo de combinación proviene de la página web del Dr. Johnnie W. Baker. Sin embargo, el código que proporciono en esta respuesta tiene algunas correcciones y mejoras de rendimiento.
Un ejemplo completo de ejecución:
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <omp.h>
#define TASK_SIZE 100
unsigned int rand_interval(unsigned int min, unsigned int max)
{
// https://stackoverflow.com/questions/2509679/
int r;
const unsigned int range = 1 + max - min;
const unsigned int buckets = RAND_MAX / range;
const unsigned int limit = buckets * range;
do
{
r = rand();
}
while (r >= limit);
return min + (r / buckets);
}
void fillupRandomly (int *m, int size, unsigned int min, unsigned int max){
for (int i = 0; i < size; i++)
m[i] = rand_interval(min, max);
}
void mergeSortAux(int *X, int n, int *tmp) {
int i = 0;
int j = n/2;
int ti = 0;
while (i<n/2 && j<n) {
if (X[i] < X[j]) {
tmp[ti] = X[i];
ti++; i++;
} else {
tmp[ti] = X[j];
ti++; j++;
}
}
while (i<n/2) { /* finish up lower half */
tmp[ti] = X[i];
ti++; i++;
}
while (j<n) { /* finish up upper half */
tmp[ti] = X[j];
ti++; j++;
}
memcpy(X, tmp, n*sizeof(int));
}
void mergeSort(int *X, int n, int *tmp)
{
if (n < 2) return;
#pragma omp task shared(X) if (n > TASK_SIZE)
mergeSort(X, n/2, tmp);
#pragma omp task shared(X) if (n > TASK_SIZE)
mergeSort(X+(n/2), n-(n/2), tmp + n/2);
#pragma omp taskwait
mergeSortAux(X, n, tmp);
}
void init(int *a, int size){
for(int i = 0; i < size; i++)
a[i] = 0;
}
void printArray(int *a, int size){
for(int i = 0; i < size; i++)
printf("%d ", a[i]);
printf("n");
}
int isSorted(int *a, int size){
for(int i = 0; i < size - 1; i++)
if(a[i] > a[i + 1])
return 0;
return 1;
}
int main(int argc, char *argv[]) {
srand(123456);
int N = (argc > 1) ? atoi(argv[1]) : 10;
int print = (argc > 2) ? atoi(argv[2]) : 0;
int numThreads = (argc > 3) ? atoi(argv[3]) : 2;
int *X = malloc(N * sizeof(int));
int *tmp = malloc(N * sizeof(int));
omp_set_dynamic(0); /** Explicitly disable dynamic teams **/
omp_set_num_threads(numThreads); /** Use N threads for all parallel regions **/
// Dealing with fail memory allocation
if(!X || !tmp)
{
if(X) free(X);
if(tmp) free(tmp);
return (EXIT_FAILURE);
}
fillupRandomly (X, N, 0, 5);
double begin = omp_get_wtime();
#pragma omp parallel
{
#pragma omp single
mergeSort(X, N, tmp);
}
double end = omp_get_wtime();
printf("Time: %f (s) n",end-begin);
assert(1 == isSorted(X, N));
if(print){
printArray(X, N);
}
free(X);
free(tmp);
return (EXIT_SUCCESS);
}
Un benchmark de had-doc en una máquina de 4 núcleos arroja los siguientes resultados:
100000000 elements
1 thread : Time: 11.052081 (s)
2 threads: Time: 5.907508 (s)
4 threads: Time: 4.984839 (s)
A overall Speed up of 2.21x
Las mejoras futuras estarán disponibles en GitHub.
Puede encontrar una versión avanzada de C ++ de la versión paralela aquí. El algoritmo final tiene el siguiente aspecto:
void mergeSortRecursive(vector<double>& v, unsigned long left, unsigned long right) {
if (left < right) {
if (right-left >= 32) {
unsigned long mid = (left+right)/2;
#pragma omp taskgroup
{
#pragma omp task shared(v) untied if(right-left >= (1<<14))
mergeSortRecursive(v, left, mid);
#pragma omp task shared(v) untied if(right-left >= (1<<14))
mergeSortRecursive(v, mid+1, right);
#pragma omp taskyield
}
inplace_merge(v.begin()+left, v.begin()+mid+1, v.begin()+right+1);
}else{
sort(v.begin()+left, v.begin()+right+1);
}
}
}
}
void mergeSort(vector<double>& v) {
#pragma omp parallel
#pragma omp single
mergeSortRecursive(v, 0, v.size()-1);
}
Una aceleración reportada de 6.61x para 48 hilos.
La respuesta moderna a esta pregunta es utilizar tareas en lugar de secciones. Las tareas se agregaron en OpenMP 3.0 (2009) y funcionan mejor / más fácilmente que el paralelismo y las secciones anidados, porque el paralelismo anidado puede llevar a una sobre suscripción (más subprocesos activos que CPU disponibles), lo que causa una degradación significativa del rendimiento. Con las tareas, tiene un equipo de subprocesos que coinciden con el número de CPU y trabajarán en las tareas. Por lo que no necesita el manejo manual con el threads parámetro. Una solución simple se ve así:
// span parallel region outside once outside
void mergesort_omp(...) {
#pragma omp parallel
#pragma omp single
mergesort_parallel_omp(...)
}
void mergesort_parallel_omp (int a[], int size, int temp[])
{
#pragma omp task
mergesort_parallel_omp(a, size/2, temp);
mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2);
#pragma omp taskwait
merge(a, size, temp);
}
Sin embargo, aún puede ser problemático crear tareas para fragmentos de trabajo demasiado pequeños, por lo que es útil limitar el paralelismo en función de la granularidad del trabajo, por ejemplo, como tal:
void mergesort_parallel_omp (int a[], int size, int temp[])
{
if (size < size_threshold) {
mergesort_serial(a, size, temp);
return;
}
#pragma omp task
mergesort_parallel_omp(a, size/2, temp);
mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2);
#pragma omp taskwait
merge(a, size, temp);
}