C OpenMP параллельная пузырьковая сортировка - PullRequest
Новая
       10

C OpenMP параллельная пузырьковая сортировка

5 голосов
/ 03 ноября 2011

У меня есть реализация алгоритма параллельной пузырьковой сортировки ( Odd-Even транспонированная сортировка ) в C с использованием OpenMP.Однако после того, как я проверил его, он работает медленнее, чем серийная версия (примерно на 10%), хотя у меня есть 4-ядерный процессор (2 реальных x 2 из-за гиперпоточности Intel).Я проверил, действительно ли используются ядра, и могу видеть их на 100% каждое при запуске программы.Поэтому я считаю, что допустил ошибку в реализации алгоритма.

Я использую linux с ядром 2.6.38-8-generic.

Вот как я компилирую:

gcc -o bubble-sort bubble-sort.c -Wall -fopenmp или

gcc -o bubble-sort bubble-sort.c -Wall -fopenmp для серийной версии

Вот как я запускаю:

./bubble-sort < in_10000 > out_10000

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

int main()
{
        int i, n, tmp, *x, changes;
        int chunk;
        scanf("%d ", &n);
        chunk = n / 4;
        x = (int*) malloc(n * sizeof(int));
        for(i = 0; i < n; ++i)
            scanf("%d ", &x[i]);
    changes = 1;
    int nr = 0;
    while(changes)
    {
    #pragma omp parallel private(tmp)
    {
            nr++;
            changes = 0;
            #pragma omp for \
                    reduction(+:changes)
            for(i = 0; i < n - 1; i = i + 2)
            {
                    if(x[i] > x[i+1] )
                    {
                            tmp = x[i];
                            x[i] = x[i+1];
                            x[i+1] = tmp;
                            ++changes;
                    }
            }
            #pragma omp for \
                    reduction(+:changes)
            for(i = 1; i < n - 1; i = i + 2)
            {
                    if( x[i] > x[i+1] )
                    {
                            tmp = x[i];
                            x[i] = x[i+1];
                            x[i+1] = tmp;
                            ++changes;
                    }
            }
    }
    }

    return 0;

}

Позднее редактирование:

Кажется, теперь это работает хорошо после того, как я внес изменения, которые вы предложили.Он также неплохо масштабируется (я также тестировал на 8 физических ядрах -> взял 21 с для набора чисел 150 000, что намного меньше, чем на одном ядре).Однако, если я сам установлю переменную среды OMP_SCHEDULE, производительность снизится ...

1 Ответ

3 голосов
/ 04 ноября 2011

Вы должны профилировать его и проверить, где потоки проводят время.

Одной из возможных причин является то, что параллельные области постоянно создаются и разрушаются;в зависимости от реализации OpenMP это может привести к воссозданию пула потоков, хотя в этом случае, вероятно, должны быть реализованы хорошие реализации.

Некоторые мелочи, которые нужно сбрить:
- ok кажется совершенно ненужным,вы можете просто изменить условие выхода из цикла на i<n-1;
- явный барьер не нужен - сначала вы помещаете его из параллельных областей, чтобы он не имел смысла;и, во-вторых, параллельные области и циклы OpenMP имеют неявные барьеры на конце;
- объединяет по крайней мере две последовательные параллельные области внутри цикла while: 

#pragma omp parallel private(tmp)
{
    #pragma omp for bla-bla
    for (i=0; i<n-1; i+=2 ) {...}

    #pragma omp for bla-bla
    for (i=1; i<n-1; i+=2 ) {...}
}
...