How to parallelize do while and while loop in openmp?

Question

I am trying to learn concurrent programming using OpenMP, and I'm interested in parallelizing the following do while with multiple while loops inside it:

 do { while(left < (length - 1) && data[left] <= pivot) left++; while(right > 0 && data[right] >= pivot) right--; /* swap elements */ if(left < right){ temp = data[left]; data[left] = data[right]; data[right] = temp; } } while(left < right); 

I really did not understand how to parallelize the while and do while loops, could not find any resource where it specifically describes how to parallelize the while and do while loops. I found instructions for for loops, but I could not make any assumptions for while and do while loops. So, could you describe how I can parallelize these loops that I presented here?

EDIT

I converted the do while to the following code where only the for loop is used.

 for(i = 1; i<length-1; i++) { if(data[left] > pivot) { i = length; } else { left = i; } } for(j=length-1; j > 0; j--) { if(data[right] < pivot) { j = 0; } else { right = j; } } /* swap elements */ if(left < right) { temp = data[left]; data[left] = data[right]; data[right] = temp; } int leftCopy = left; int rightCopy = right; for(int leftCopy = left; leftCopy<right;leftCopy++) { for(int new_i = left; new_i<length-1; new_i++) { if(data[left] > pivot) { new_i = length; } else { left = new_i; } } for(int new_j=right; new_j > 0; new_j--) { if(data[right] < pivot) { new_j = 0; } else { right = new_j; } } leftCopy = left; /* swap elements */ if(left < right) { temp = data[left]; data[left] = data[right]; data[right] = temp; } } 

This code works fine and gives the correct result, but when I tried to parallelize parts of the above code, changing the first two for to the following:

 #pragma omp parallel default(none) firstprivate(left) private(i,tid) shared(length, pivot, data) { #pragma omp for for(i = 1; i<length-1; i++) { if(data[left] > pivot) { i = length; } else { left = i; } } } #pragma omp parallel default(none) firstprivate(right) private(j) shared(length, pivot, data) { #pragma omp for for(j=length-1; j > 0; j--) { if(data[right] < pivot) { j = 0; } else { right = j; } } } 

Speed ​​is worse than unparalleled code. Please help me identify my problem.

thanks

Answer 1

First of all, sorting algorithms are very difficult to parallelize with parallel OpenMP loops. This is due to the fact that the loop counter is not deterministic, but depends on the input setpoints that are read at each iteration.

I don’t think that loop conditions like data[left] <= pivot will work well, since the OpenMP library does not know exactly how to divide the iteration space between the streams.

If you are still interested in parallel sorting algorithms, I suggest you read the literature first to see those algorithms that are really worth implementing because of their scalability. If you just want to learn OpenMP, I suggest you start with simpler algorithms such as bucket-sort , where the number of buckets is well known and does not change often.

As for the example that you are trying to parallelize, while loops are not directly supported by OpenMP, because the number of iterations (the number of loop attempts) is not deterministic (otherwise they can be easily converted to loops). Therefore, iterations cannot be distributed between threads. Also, usually when the loops check the condition using the last result of the iteration. This is called Read-after-Write or true-dependency and cannot be parallelized.

The slowdown problem can be reduced if you try to minimize the number of omp parallel sentences. Also, try moving them out of all your loops. These sentences can create and join additional flows which are used in parallel parts of the code, which is expensive.

You can still synchronize threads inside parallel blocks so that the result is similar. In fact, all threads are waiting for each other at the end of the omp for clause by default, so this makes things even easier.

 #pragma omp parallel default(none) firstprivate(right,left) private(i,j) shared(length, pivot, data) { #pragma omp for for(i = 1; i<length-1; i++) { if(data[left] > pivot) { i = length; } else { left = i; } } #pragma omp for for(j=length-1; j > 0; j--) { if(data[right] < pivot) { j = 0; } else { right = j; } } } // end omp parallel