OpenMP implementation making my code slow

Question

I'm trying to make my quicksort work parallel by using openMP. After implementation of openMP my attempt to make quicksort work faster fails and my quicksort sorts array almost twice slower. My code with openMP implementation :

void quickSort( int a[], int l, int r) { int j; if( l < r ) { #pragma omp parallel { j = partition( a, l, r); #pragma omp sections { #pragma omp section { quickSort( a, l, j-1); } #pragma omp section { quickSort( a, j+1, r); } } } } }

Whole sorting happens in method partition and if its interesting for you how it works here comes code for it :

int partition( int a[], int l, int r) { int pivot, i, j, t; pivot = a[l]; i = l; j = r+1; while(1) { do ++i; while( a[i] <= pivot && i <= r ); do --j; while( a[j] > pivot ); if( i >= j ) break; t = a[i]; a[i] = a[j]; a[j] = t; } t = a[l]; a[l] = a[j]; a[j] = t; return j; }

I take time in my main before i call quickSort and i stops timer before printf in main. Amount of threads is defined to 10 (i have tried with 4,2 and 1 on my pc). My results after sorting a list with 1 000 000 random integers between 0 - 100:

time (without openMP) is betwen 6.48004 - 5.32001

with openMP time is betwen 11.8309 and 10.6239 (with 2-4 threads) How can this be true?

fgiesen.wordpress.com/2013/01/31/cores-dont-like-to-share maybe a starter. — akira
– akira, Commented Feb 8, 2013 at 12:48

akira · Accepted Answer · 2013-02-08 13:32:08Z

The general idea of quicksort is this:

[......................]

That list of elements are split into 2 tasks:

[..........][..........]

And each of the "tasks" is then split again and again and again:

[..][..][..][..][..][..]

Now, the CPU likes to work on data which is closely together. But, when each of your cores works on data PRETTY closeley together it might be the case that one core writes to a chunk of data that is on the same cacheline as the data on a different core. Since you do not want the cores to write into each others data the first write will make the data in the other cores invalid and thus the other cores have to fetch the chunk of ram again.

|--- cache line ---| [..][..][..][..][..][..] ^ ^ ^ ^ | | | | c1 c2 c3 c4

So, whichever core writes to data belonging into that cache line first invalidates the data of all the other cores. Since you make the little tasks [..] pretty close you increase the chance of lots of invalid cachelines and a lot of refetching data from the memory. The effect is much better explained over here

http://fgiesen.wordpress.com/2013/01/31/cores-dont-like-to-share

Read also http://lwn.net/Articles/252125/ , especially "3.3.4 Multi-Processor Support".

This whole invalidating the cache does not happen (that often) in your non-parallel version since there is only one core actively working on the data.

So, a possible solution is to not to split up the tasks until they are too small to be effectively worked on by the cores. Another effect you have to take into account: OpenMP has to do a bit of management overhead per task. If the tasks are too small, you also increase the overhead vs work ratio.

A OpenMP based quicksort the google spit out was:

http://berenger.eu/blog/c-openmp-a-shared-memory-quick-sort-with-openmp-tasks-example-source-code/

May that inspire you.

Collectives™ on Stack Overflow

OpenMP implementation making my code slow

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related