Распараллелить сортировку выбором с помощью OpenMP

Мне нужно реализовать алгоритм параллельной сортировки выбором с использованием OpenMP, хотя я не смог найти много информации ни на SO, ни в Интернете вообще.

Вот мой серийный код:

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]);
    }
}

Кто-нибудь знает, как реализовать этот тип алгоритма сортировки параллельно? Хотя бы в теории?


c++ openmp sorting parallel-processing selection-sort
person Denis Yakovenko    schedule 12.01.2016    source источник
comment
Классический подход для параллельной сортировки может заключаться в сортировке [0, SIZE/N] [SIZE/N, 2 * SIZE/N].... А затем объединить результат. Другим решением является использование pragma omp во внутреннем цикле, который можно легко распараллелить.   -  person P. Brunet    schedule 12.01.2016
comment
Может быть, причина, по которой вы не можете найти много информации, в том, что это такая плохая идея!   -  person Jim Cownie    schedule 13.01.2016

Ответы (2)


arrow_upward
4
arrow_downward

Поскольку внешний for не может быть распараллелен из-за постоянных изменений в массиве, нам нужно распараллелить внутренний for.

Итак, нам нужно использовать максимальное сокращение, но поскольку нам просто не нужно максимальное значение, нам также нужен индекс этого максимального значения, нам нужно объявить новое сокращение (доступно только в OpenMP 4.0), которое получает структуру, здесь он полностью функционален:

#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;
}
person Gabriel Garcia    schedule 13.01.2016

arrow_upward
3
arrow_downward

Решение, опубликованное Габриэлем Гарсией, работает только для массивов натуральных чисел.

Если вы используете этот массив, вы получите неверный результат:

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

Декларация о сокращении:

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

не определяет предложение-инициализатора, поэтому на каждой итерации параллельного цикла max.val и max.index инициализируются равными 0 даже хотя мы инициализируем их перед циклом.

См. определяемый пользователем синтаксис сокращения для получения дополнительной информации.

Правильное объявление должно быть:

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

Вы также можете сделать «минимальное» сокращение таким же образом, если хотите (очевидно, изменив индексы и символы отношений).

person Antonio Toncetti    schedule 08.12.2019