Insertion Trier dans OpenMP

Question

J'essaie d'écrire une solution OpenMP pour le tri par insertion mais j'ai des problèmes pour la faire fonctionner en parallèle et donner des résultats corrects :). Est-il possible de faire trier Insertion en parallèle.

Voici mon code:

void insertionsort(int *A, int num) 
{ 

// clock_t start, stop; 
// 
// start=clock(); 
int k; 
#pragma omp parallel for shared(A) private(k) 
for(int n = 1; n < num; n++) 
{ 
    int key = A[n]; 
    k = n; 
#pragma omp critical 

    for(;k>0 && A[k-1]> key;k--) 
    { 
     A[k] = A[k-1]; 
    } 



    A[k] = key; 


} 
// stop=clock(); 
// cas = (double)(stop-start)/CLOCKS_PER_SEC; 
} 

Answer 1

Vous ne pouvez pas paralléliser l'algorithme de tri par insertion de cette façon. Comme vous pouvez le voir à partir de la condition de la boucle intérieure A[k-1]> key;, cet algorithme suppose que pour une donnée key dans la position k du tableau, si la clé réelle est plus grande que les clés stockées sur la position précédente du tableau le swap devrait arrêter. Par conséquent, l'algorithme suppose que les clés sur les positions ci-dessous k sont déjà triées.

Lorsque vous introduisez parallélisation, avec deux fils, par exemple, du fil 0 commencera à partir du début du tableau, et le fil 1 commencera à partir de la moitié. Le problème est que la première moitié n'est pas triée, selon l'hypothèse faite par l'algorithme, donc cela va conduire à des problèmes.

Permettez-moi de vous donner un exemple, le tri d'un array = [-1,2,-3,4,-5,6,-7,8] avec 2 fils: Fixons une exécution donnée ordonnée (en réalité est non-déterministe)

• 1) Discussion 0 prend k = 1 et key = 2; état du réseau [-1,2,-3,4,-5,6,-7,8]
• 2) Le fil 1 prend k = 5 et la clé = 6; état du tableau [-1,2,-3,4,-5,6,-7,8]
• 3) Le fil 0 prend k = 2 et la clé = -3; état du réseau [-3,-1,2,4,-5,6,-7,8]
• 4) Le fil 1 prend k = 6 et la clé = -7; état du tableau [-7,-3,-1,2,4,-5,6,8]
• 5) Le fil 0 prend k = 3 et la clé = 2; état du réseau [-7,-3,-1,2,4,-5,6,8]
• 6) Le fil 1 prend k = 7 et la clé = 8; état du réseau [-7,-3,-1,2,4,-5,6,8]
• 7) Le fil 0 prend k = 4 et la clé = 4; état de la matrice [-7,-3,-1,2,4,-5,6,8]

résultat final: [-7,-3,-1,2,4,-5,6,8]

Sur la ligne 4 fil 1 prend la -7 clé de la position 6 et met à la fin du tableau de tamisage de tous les éléments à partir de positions 1 to 6 (inclus) d'une position vers le droit, alors maintenant -5 est sur l'ancienne position de -7. Depuis, l'ancienne position de -7 (6) ne sera plus jamais comparée -5 restera là intouchable. Par conséquent, rendant l'algorithme non trié.

Une solution simple mais médiocre consisterait à ajouter la clause OpenMP ordered à la construction parallel for. Mais, en utilisant cela, votre code serait fondamentalement séquentiel.

Une autre solution possible, bien que je ne suis pas 100% sûr qu'il peut tenir sur votre cas, serait de faire votre parallèle algorithme par échantillonnage régulier. Vous pouvez voir here un exemple de cette dernière technique s'appliquent sur quicksort.

La struct de votre algorithme n'est pas le meilleur à paralléliser directement et obtenir SpeedUp il.Comme chaque itération de la boucle interne est interdépendante, cela nécessitera l'utilisation de méthodes pour éviter l'exclusion mutuelle, ce qui entraînera des frais généraux. Vous disposez d'un algorithme de tri bien meilleur que vous pouvez directement paralléliser, généralement ceux qui utilisent une stratégie de division et de conquête, comme le tri par radix ou le tri rapide, entre autres.