Parallelize selection sort using OpenMP

Question

I need to implement an algorithm for parallel selection sort using OpenMP, although I couldn't find much information either on SO or on the Internet in general.

Here's my serial code:

void selectionsort(int* arr, int size)
{
    for (int i = size - 1; i > 0; --i)
    {
        int max = i;
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] > arr[max])
            {
                max = j;
            }
        }
        swap(arr[i], arr[max]);
    }
}

Does anybody know how to implement this type of sorting algorithm in parallel? At least in theory?

Classic approach for parallel sorting may be to sort [0, SIZE/N] [ SIZE/N, 2 * SIZE / N] .... And then merge the result. Another solution is to use the pragma omp on the inner loop which could be parallelized easily. — P. Brunet
– P. Brunet, Commented Jan 12, 2016 at 19:55
Maybe the reason you can't find much information is because it's such a bad idea! — Jim Cownie
– Jim Cownie, Commented Jan 13, 2016 at 10:06

Gabriel Garcia · Accepted Answer · 2016-01-13 12:36:53Z

Since the outer for can't be parallelized due to the constant changes in the array, we need to parallelize the inner for.

So we need to use the max reduction, but since we just don't need the maximum value we also need the index of this maximum value, we need to declare a new reduction (Only available in OpenMP 4.0) that receives a struct, here it is fully functional:

#include <stdio.h>
#include <omp.h>

struct Compare { int val; int index; };
#pragma omp declare reduction(maximum : struct Compare : omp_out = omp_in.val > omp_out.val ? omp_in : omp_out)

void selectionsort(int* arr, int size)
{
    for (int i = size - 1; i > 0; --i)
    {
        struct Compare max;
        max.val = arr[i];
        max.index = i;
        #pragma omp parallel for reduction(maximum:max)
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] > max.val)
            {
                max.val = arr[j];
                max.index = j;
            }
        }
        int tmp = arr[i];
        arr[i] = max.val;
        arr[max.index] = tmp;
    }
}

int main()
{
        int x[10] = {8,7,9,1,2,5,4,3,0,6};
        selectionsort(x, 10);

        for (int i = 0; i < 10; i++)
                printf("%d\n", x[i]);
        return 0;
}

Antonio Toncetti · Accepted Answer · 2019-12-08 14:59:18Z

The solution posted by Gabriel Garcia works only for arrays of natural numbers.

If you use this array you get a wrong result:

int x[10] = {-8,-7,-9,-1,-2,-5,-4,-3,0,-6};

The reduction declaration:

#pragma omp declare reduction(maximum : struct Compare : omp_out = omp_in.val > omp_out.val ? omp_in : omp_out)

does not specify an initializer-clause and therefore at every iteration of the parallel loop the max.val and max.index are initialized to 0 even though we initialize them before the loop.

Refer to user defined reduction syntax for more information.

The correct declaration should be:

#pragma omp declare reduction(maximum : \
                              struct Compare : \
                              omp_out = omp_in.val > omp_out.val ? omp_in : omp_out) \
                              initializer(omp_priv=omp_orig)

You can also do a 'minimum' reduction in the same way if you prefer (obviously, changing the indexes and relationship symbols).

Collectives™ on Stack Overflow

Parallelize selection sort using OpenMP

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related