0

Quite similar to that question Sorting an array in openmp which has several hundred views but no correct answer. Therefore I give it another try asking here again. I am aware of the overhead and uselessness of this regarding speedup or performance. It simply is a small example to get into openMP. The fact that is is insertSort is given by my courseinstructor.

Here is my code:

std::vector<int> insertionSort(std::vector<int> a) {
    int i, j, k;
    #pragma omp parallel for private(i,j,k)
    for(i = 0; i < a.size(); i++) {
    #pragma omp critical
        k = a[i];
        for (j = i; j > 0 && a[j-1] > k; j--)

        #pragma omp critical
        {
            a[j] = a[j-1];
            a[j] = k;
        }
    }
 return a;
 }

I understand that the critical aspect is the race-condition between threads accessing (reading and writing) elements of a - that is, why I put a critical section arround all of them. That does not seem to be sufficient. What am I missing here. Without the pragmas, the sorting is correct.

Improve this question
2
  • As I responded to the question you have referred to, insertion sort is inherently serial, iterations of the outer loop cannot be performed out of order. Adding critical sections is not enough. Commented Jan 14, 2015 at 22:20
  • Another similar question: stackoverflow.com/questions/13905410/insertion-sort-in-openmp Commented Jan 14, 2015 at 23:08
Related questions
2
Sorting an array in openmp
5
C OpenMP parallel bubble sort
0
Racing conditions in quicksort written in C parallelized with OpenMP
Load 7 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.