Parallel Selection sort with multithreading

Question

I have Selection sort function

inline void selection_sort(double* arrayPtr, int length_array)
{
    for (auto i = 0; i < length_array; i++)
    {
        for (auto j = i + 1; j < length_array; j++)
        {
            if (arrayPtr[i] > arrayPtr[j])
            {
                std::swap(arrayPtr[i], arrayPtr[j]);
            }
        }
    }
}

How to optimize it with multithreading?

I found solutions only for quicksort but these solutions did not help me.

user_1366871 · Answer

How to optimize it with multithreading? I found solutions only for quick sort but but these solutions did not help me.

You cannot find much information about it because it is not a good idea to do so. It will not be efficient, the parallelization of the selection sort has some of the same issues as the parallelization of the insert sort. Namely, this code:

for (auto i = 0; i < length_array; i++)
{
    for (auto j = i + 1; j < length_array; j++)
    {
        if (arrayPtr[i] > arrayPtr[j])
        {
            std::swap(arrayPtr[i], arrayPtr[j]);
        }
    }
}

You cannot efficiently parallelize the outer loop because of the interdependencies with the inner loop. So you are already limited on the number of parallel tasks and their granularity. Then you have the problem of the data dependencies during the swap phase which you also need to solve, and which will consequently also impair the speedups of the parallel version.

Algorithms like merge-sort are more parallelizable (i.e., their parallelization yields better speedups) due to their divide-and-conquer nature, where one can parallelize the recursive calls.

Notwithstanding, you can find in stackoverflow a parallel version of the selection sorting in OpenMP/C++. That being said the code runs is parallel, but I would suspect without much (if any) speedups.

user_5267751 · Answer

Disclaimer: this is only for the homework requirements. For all practical purposes std::sort is better.

Assume that the requirements is that the exact set of operations must be performed, but independent operations can be performed in any order.

Note that:

There are length_array passes through the array (indexed by i)
Each pass must be done sequentially.
However, observe that (informally) the first half of the second pass is independent of the second half of the first pass, both can be done in any order as long as the first half of the first pass is done.

Therefore one possible way to solve the problem is (be very careful with the offset errors, you have to work out the details)

Let thread 1 process the first half of the first pass.
Wait for both threads to finish the current step.
Let thread 1 process the second half of the first pass, while thread 2 concurrently process the first half of the second pass.
Wait for both threads to finish the current step.
Let thread 1 process the second half of the second pass, while thread 2 concurrently process the first half of the third pass.
Wait for both threads to finish the current step.
Repeat.
Special-case the last pass.
Handle the offset somehow.

Parallel Selection sort with multithreading

2 Answers