C parallèle OpenMP tri à bulles

J'ai une mise en œuvre parallèle de la bulle algorithme de tri(Odd-Même la transposition de tri) en C, en utilisant OpenMP. Cependant, après je l'ai testé il est plus lent que la version de série(environ 10%) même si j'ai un 4 cœurs du processeur ( 2 x réel 2 en raison de l'hyperthreading d'Intel). J'ai vérifié pour voir si les carottes sont effectivement utilisés et je peux les voir à 100% lors de l'exécution du programme. Donc je pense que j'ai fait une erreur dans la mise en œuvre de l'algorithme.

J'utilise linux avec le noyau 2.6.38-8-générique.

C'est de cette façon que je compile:

gcc -o bubble-sort bubble-sort.c -Wall -fopenmp ou

gcc -o bubble-sort bubble-sort.c -Wall -fopenmp pour la version de série

C'est la façon dont je cours:

./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;

}

Plus tard edit:

Il semble bien fonctionner maintenant, après j'ai fait les modifications que vous avez suggéré. Il a également échelles assez bonne(je l'ai testé sur 8 cœurs physiques trop -> il a pris 21s pour un ensemble de 150k de chiffres, ce qui est beaucoup moins que sur un seul cœur). Cependant si j'ai mis le OMP_SCHEDULE variable d'environnement me le rendement diminue...

J'ai pas assez solidement sur 1 core avec mon cpu quadcore. Aussi, ce que lorsque vous envisagez de faire scanf dans une boucle for parallèle?
Soupir. Oublier le 1 chose: c'est en raison de pragma être ignorées silencieusement sans -fopenmp drapeau de compilation. Je suis bête
J'ai oublié de supprimer la section parallèle dans le scanf pour la boucle(utilisé une ancienne version de code). Ce n'est pas la façon dont je l'ai testé.

OriginalL'auteur Dan Lincan | 2011-11-03

  1. 3

    Vous devriez profil et vérifier où les threads passer le temps.

    Une des raisons possibles est que des régions parallèles sont constamment créés et détruits; selon OpenMP mise en œuvre, elle pourrait conduire à la re-création du pool de thread, mais bon implémentations devraient probablement gérer ce cas.

    Quelques petites choses à raser:

    - ok semble complètement inutile, il vous suffit de modifier la condition de sortie de boucle pour i<n-1;

    explicites de la barrière n'est pas nécessaire, tout d'abord, vous mettre en parallèle les régions de sorte qu'il n'a pas de sens; et le second, parallèle OpenMP les régions et les boucles ont implicite des barrières à la fin;

    - combiner au moins deux conséquente des régions parallèles à l'intérieur de la boucle 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 ) {...}
}

    OriginalL'auteur Alexey Kukanov