Parallel qsort using openMP

Question

I'm trying to parallelize qsort() function in c++ with openMP, but I have some problems. For of all, for a high number of element to sort (ex: V=1000) qsort doesn't work at all, I never exit this function (infinite loop). Then, I notice that my parallel version of qsort is much slower then the serial one. Anyone could help me? Here the code: https://dpaste.de/EaH0.

here the average of time elapsed where kruscalP is the parallel version: thanks

can you show us some code? we can't see what you are doing wrong. — Pandrei
– Pandrei, Commented Feb 20, 2014 at 9:55
here a code example: dpaste.de/A2p1 this algorithm order edges of a graph respect to their weights — Betelgeuse
– Betelgeuse, Commented Feb 20, 2014 at 10:07
It looks to me like you have a race condition when you do A[i] = A[i+1]. You need to change your algorithm or put your swap in a critical section. — Z boson
– Z boson, Commented Feb 20, 2014 at 10:13
you do know that by using OpenMP you are creating threads to runs your code in parallel. But you have no synchronization in your code. Because of that threads will read wrong data. Perhaps you should take a look a at a openMP tutorial to understand the problem — Pandrei
– Pandrei, Commented Feb 20, 2014 at 10:21
Please include the code in your question. External sites can go down or disappear, so it's better to have the code here — flipchart
– flipchart, Commented Feb 20, 2014 at 10:47

Z boson · Accepted Answer · 2014-02-20 10:23:00Z

1

You have multiple race conditions in your code when you write to A, exch0, and exch1 which are all shared. Not only can this hurt performance it likely will give the wrong result. Unfortunately, you have to use a critical section to fix this which will also likely hurt performance but at least it will give the right result.

#pragma omp for    
for (i = 0; i < N-1; i += 2) {
    #pragma critical
    {
        if (A[i].weight > A[i+1].weight) {
            temp = A[i];
            A[i] = A[i+1];
            A[i+1] = temp;
            exch0 = 1;
        }
    }
}

The same applies to the next for loop. If you want to do this efficiently you have to change your algorithm. Maybe consider merge sort.

answered Feb 20, 2014 at 10:23

Z boson

34k14 gold badges132 silver badges238 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Parallel qsort using openMP

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related