OpenMP recursion slower than without threads

First I show you what you do that you understand the changes better:

In each step you do this:

#pragma omp parallel shared(cM,cL,cH) //open a new parallel region (ie create threads) { #pragma omp single nowait //only one thread should do the following { #pragma omp task if(N > 4096) //create task cM=mult(t1,t2,0,N/2); #pragma omp task if(N > 4096) //create task cL=mult(a,b,0,N/2); #pragma omp task if(N > 4096) //create task cH=mult(a,b,N/2,N/2); } //after this line all threads are working on the same #pragma omp taskwait //before executing further the tasks should be finished } // close all threads created at this parallel 

what you inteded to do:

create some threads, once create the root of the recursion, every recursive call is a task, all should work on tasks, when all child-tasks are finished calculate result, take new task

in karatsubaMain() you should once create threads and one thread then inserts the root task:

double start = omp_get_wtime(); int* result; #pragma omp parallel shared(result, a, b, size) { #pragma omp single //also #pragma omp master usable here result = mult(a, b, 0, size); } double end = omp_get_wtime(); 

in mult() you shoudl only create tasks since this region is already processed by different threads in parallel:

for(int i = 0; i < N / 2; i++) { t1[i] = a[start + i] + a[start + i + N / 2]; t2[i] = b[start + i] + b[start + i + N / 2 ]; } #pragma omp task shared(cM) if(N > 4096) cM = mult(t1, t2, 0, N / 2); #pragma omp task shared(cL) if(N > 4096) cL = mult(a, b, 0, N / 2); #pragma omp task shared(cH) if(N > 4096) cH = mult(a, b, N / 2, N / 2); #pragma omp taskwait c[N - 1] = 0; 

in that way i was able to speed up a simplified version of your code (int-array insead of polynom) by about 15% with respect to sequential code.

general remark: most off the times it is not advisable to use nested parallel regions