En parallèle de Fusion-Tri en OpenMP

J'ai vu un algorithme parallèle de fusion de tri dans une cette papier. C'est le code:

void mergesort_parallel_omp (int a[], int size, int temp[], int threads) 
{  
    if ( threads == 1)       { mergesort_serial(a, size, temp); }
    else if (threads > 1) 
    {
         #pragma omp parallel sections
         {
          #pragma omp section
             mergesort_parallel_omp(a, size/2, temp, threads/2);
          #pragma omp section
             mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2, threads - threads/2);
         }
merge(a, size, temp); 
    } //threads > 1
}

Je l'exécute sur un multicœur. Ce qui se passe, c'est que dans les feuilles de l'arbre, 2 threads s'exécutent en parallèle. Après, ils ont fini leur travail 2 autres threads de début et ainsi de suite. Même si nous avons la liberté de cœurs pour tous les nœuds feuilles.

Je pense que la raison est ce OpenMP code ne crée pas de parallèle régions à l'intérieur des régions parallèles. Suis-je la corriger?

OriginalL'auteur towi_parallelism | 2012-12-10

  1. 7

    "Je pense que la raison en est que OpenMP ne peut pas créer des régions parallèles à l'intérieur des régions parallèles"

    Vous pouvez avoir parallèle région de région parallèle.

    Parallèle OpenMP les régions peuvent être imbriquées à l'intérieur les uns des autres. Si imbriquée
    le parallélisme est désactivé    , puis la nouvelle équipe créé par un fil
    la rencontre d'une structure parallèle à l'intérieur d'une région parallèle se compose
    seulement de la rencontre de fil. Si imbriquée parallélisme est activé,
    ensuite, la nouvelle équipe peut comprendre plus d'un thread (source).

    Afin d'exécuter votre code correctement, vous devez appeler omp_set_nested(1) et omp_set_num_threads(2).

    Imbriquée parallélisme peut être activée ou désactivée par le paramètre de la
    OMP_NESTED variable d'environnement ou de l'appel de omp_set_nested() la fonction

    Merci beaucoup pour la réponse. J'ai résolu le problème. Cependant, je ne comprends pas pourquoi j'ai besoin d'ajouter le "omp_set_num_threads(2) de la partie". Je veux dire, pourquoi faut-il ajouter?
    Np, de vous souhaiter la bienvenue. En voyant cet algorithme j'irait avec la variable de fils (la variable que vous transmettez à votre mergesort_parallel_omp fonction) égale à la num_of_cores (par exemple 2,4,8,16) et j'aurais la force de chaque région parallèle à seulement créer deux thread à chaque fois un pour chaque section (omp_set_num_threads(2)). Néanmoins, il y a peut-être un moyen plus efficace.
    Lors de la première discussion de niveau master va créer un autre fil de discussion, un thread exécute la première récursivité appeler et on va exécuter la deuxième appel. Ensuite, chaque thread va créer (deuxième niveau) d'un fil en plus, et chaque thread va rester avec une récursivité appel, cela va jusqu'à ce que les threads == 1
    Merci. Je sais comment il fonctionne. Ma question est à propos de la fonction de fusion. Imaginez que nous sommes dans la 2ème niveau. Donc, nous avons 2 fils et 4 travailleurs qui travaillent à leafs. Quand un groupe de 2 terminé leur travail, ils sont nécessaires pour être fusionnées. Ceux maître threads qui sont responsables de la fusion de commencer à travailler en même temps? Je veux dire, est la fonction de fusion et d'utiliser le parallélisme?
    yep, à la fin, chaque capitaine de chaque équipe va exécuter la fusion(a, taille, temp);

    OriginalL'auteur dreamcrash

  2. 2

    La réponse moderne à cette question est d'utiliser des tâches au lieu de sections. Les tâches ont été ajoutées dans OpenMP 3.0 (2009) et de travailler mieux et plus facilement que imbriquée parallélisme et les sections, car imbriqués parallélisme peut conduire à la surcharge (plus actif de threads que de Processeurs disponibles), ce qui provoque une dégradation significative des performances. Avec des tâches, vous avez une équipe de threads correspondant au nombre de Processeurs et la volonté de travailler sur les tâches. Si vous n'avez pas besoin de manipuler avec la threads paramètre. Une solution simple ressemble à ceci:

    //span parallel region outside once outside
void mergesort_omp(...) {
    #pragma omp parallel
    #pragma omp single
    mergesort_parallel_omp(...)
}


void mergesort_parallel_omp (int a[], int size, int temp[]) 
{  
    #pragma omp task
    mergesort_parallel_omp(a, size/2, temp);

    mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2);

    #pragma omp taskwait
    merge(a, size, temp); 
}

    Cependant, il peut toujours être difficile de créer des tâches de trop petits morceaux de travail, il est utile de limiter le parallélisme sur la base du travail de précision, par exemple en tant que tel:

    void mergesort_parallel_omp (int a[], int size, int temp[]) 
{  
    if (size < size_threshold) {
        mergesort_serial(a, size, temp);
        return;
    }
    #pragma omp task
    mergesort_parallel_omp(a, size/2, temp);

    mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2);

    #pragma omp taskwait
    merge(a, size, temp); 
}

    OriginalL'auteur Zulan

  3. 0

    Peut-être que je suis totalement à côté de la question ici... mais êtes-vous conscient que vous devez définir la variable d'environnement OMP_NUM_THREADS si vous voulez exécuter sur plus de 2 threads?

    Je pense qu'il n'est pas nécessaire de le faire. omp_set_num_threads(2) vous permet d'avoir 2 fils imbriquée à l'intérieur de chaque région et il peut atteindre jusqu'à tout nombre désiré en fonction du paramètre "threads" vous d'abord passer à la fonction.

    OriginalL'auteur steffen