Parallel Bubble Sort is blocked

user_7153354 0
Viewed 292

My OpenMP program blocks on the first "for" loop of the following code, without any apparent reason. I'm simply trying to parallelize a Bubble Sort.

Below is a complete code reproducing the issue :

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <omp.h>

static int N_THREADS;
#define CHUNK_SIZE (size/N_THREADS)

void
parallel_bubble_sort(uint64_t *T, const uint64_t size)
{
    register bool swapped;
    register uint64_t swap;
    register int i,j;

    #pragma omp parallel private(swap,i,j)
    do {
        swapped = false;

        #pragma omp for schedule(static) reduction(||:swapped)
        for (j=0; j<N_THREADS; j++)
        for (i=j*CHUNK_SIZE+1; i<=(j+1)*CHUNK_SIZE-1; i++)
        if (T[i-1] > T[i]) {
            swap = T[i-1];
            T[i-1] = T[i];
            T[i] = swap;
            swapped = true;
        }

        #pragma omp for schedule(static) reduction(||:swapped)
        for (i=CHUNK_SIZE-1; i<size-CHUNK_SIZE; i+=CHUNK_SIZE)
        if (T[i] > T[i+1]) {
            swap = T[i];
            T[i] = T[i+1];
            T[i+1] = swap;
            swapped = true;
        }
    } while(swapped);
}

int main ()
{
    uint64_t i;
    uint64_t N = 1024;
    N_THREADS = omp_get_max_threads();

    uint64_t *X = (uint64_t *) malloc(N * sizeof(uint64_t));
    for (i = 0 ; i < N ; i++) X[i] = N-i;

    parallel_bubble_sort(X, N);
    free(X);
}

Some additional context:

  • T* is a pointer to an array of type uint64_t
  • size is the size of the array
  • CHUNK_SIZE is simply size/NUM_THREADS (which is also the default chunk size value OpenMP uses in the static scheduling mode, so I should get the same behavior if I remove this from the clause)

Regarding the logic behind the code:

  • In the first loop, I divide my array into chunks, and I propagate bubbles separately without overlap between threads
  • In the second loop, I make sure the bubbles propagate at the borders

More details about the issue I have while executing:

  • My program is stuck on the first "for" loop. I have localized where the program blocks using #pragma omp single, and a simple print statement.
openmp parallel-processing sorting c algorithm
2 Answers

The cause of the deadlock is a data race condition in your outermost loop:

do {
   swapped = false;  // <--- here
   ...
} while(swapped);    // <--- here

The race happens becase there is no guarantee that all threads will arrive at the instruction implementing the while(swapped) conditional at the same time. Imagine you have two threads. Thread 0 finishes the second parallel loop, sees that swapped is true, passes through the loop conditional and then starts again the loop body by setting swapped to false. If thread 1 reaches the the conditional before thread 0 was able to set swapped to false, it too will start a new iteration. But if arrives a bit too late, swapped will be false and the loop will terminate. As a result, thread 1 will not join the parallel loop and thread 0 will forever wait at the implicit synchronisation barrier.

The solution is to make sure that all threads have a consistent view of what the value of swapped is when they make a decision whether to start a new iteration or not. The simplest solution is to insert a barrier right before setting swapped to false:

do {
   #pragma omp barrier
   swapped = false;
   ...
} while(swapped);

Also, having all threads reset swapped is not really necessary and it may possibly (not sure about it) go against the OpenMP spec that forbids concurrent access to the original variable before the reduction is complete. I'm not sure if it applies to modifications before the reduction region (as I wasn't sure a couple of years ago) and there was a paragraph deleted from the OpenMP 4.5 spec regarding concurrent access, but just to be safe, I'd give the assingment the single treatment:

do {
   #pragma omp barrier
   #pragma omp single
   swapped = false;
   ...
} while(swapped);
user_13744370

Note that omp_get_max_threads() evaluates to the maximum number of threads that might be assigned to any team executing a parallel region, but in general, you are not guaranteed to get that number of threads in a given parallel region. Even if you request a specific number of threads via a num_threads clause to an OMP directive, you may still get fewer. Although in your particular program, you should get the full number of threads, it's poor form to depend on that.

Instead, use omp_get_num_threads() inside the parallel region to determine how many threads are actually in the team executing the region. I suggest also using omp_get_thread_num() to get the present thread's number within the team, which will allow you to schedule your loop iterations manually, as is most appropriate when the algorithm actually depends on how they are scheduled, as yours does. Also, do make use of the fact that variables declared inside the parallel region are automatically private with respect to the threads executing that region. Combined with declaring your variables in the narrowest scope, that will reduce the number of data-sharing clauses you require.

But none of that resolves your issue for me. What does resolve it (after applying the above) is moving the omp parallel directive from before the do to between the do and its associated block. This should be interpreted as calling for the block to be executed in parallel, but not the do itself. And that should not be a problem for you, because you want a barrier at the end of each execution of the block anyway. You also need a barrier between your two inner loop nests to avoid data races.

Putting all that together, plus a bit more reorganization, yields this, which works* for me:

void parallel_bubble_sort(uint64_t *T, const uint64_t size) {
    bool swapped;

    do {
        swapped = false;
        #pragma omp parallel
        {
            register uint64_t swap;
            register int i;
            int n_threads = omp_get_num_threads();
            int thread_num = omp_get_thread_num();
            int chunk_size = size / n_threads;

            for (i = thread_num * chunk_size + 1;
                    i < (thread_num + 1) * chunk_size;
                    i++) {
                if (T[i - 1] > T[i]) {
                    swap = T[i - 1];
                    T[i - 1] = T[i];
                    T[i] = swap;
                    swapped = true;
                }
            }
            #pragma omp barrier

            if (i < size && T[i - 1] > T[i]) {
                swap = T[i - 1];
                T[i - 1] = T[i];
                T[i] = swap;
                swapped = true;
            }
        }
    } while(swapped);
}

* It "works" to the (incomplete) extent to which the algorithm is correct. The algorithm as written is not correct unless the array size is a multiple of the number of threads executing the parallel region. My machine has 12 logical cores (6 physical), and 1024 is not a multiple of 6. When I run the program above, then, I end up with a few trailing elements going unsorted. Similar could happen on any machine, because, again, you're not in general certain to get the full number of cores your request. Fixing that issue is left as an exercise.

user_24022720
Related