Langue C
  1. Langue C
  3. OpenMP – Pourquoi le nombre de comparaisons diminue-t-il?
Intereting Posts
Lecture des données correctes du bracelet NFC avec NXP Mifare Ultralight en C Cas par défaut dans une condition de commutation Faciliter l’utilisation du C ++ dans une implémentation C existante Méta Programmation Macro Traiter le dépassement numérique pour le sortingangle pascal Zip fichier en utilisant le programme C Existe-t-il un moyen de connaître la taille d’un pointeur transmis à un __free_hook sous Linux? ndk-stack ne peut pas obtenir la stack complète Relier statiquement ncurses au programme Comment entrer en mode C99 dans Codeblocks10.05? pointeur qui pend, raison du changement de valeur après free ()? Utiliser volatil longtemps comme un atome Comment déclarer un tableau avec une taille arbitraire Comment puis-je obtenir les 8 bits inférieurs de l’int? strncpy ou strlcpy dans mon cas

OpenMP – Pourquoi le nombre de comparaisons diminue-t-il?

J’ai l’algorithme suivant: 

int hostMatch(long *comparisons) { int i = -1; int lastI = textLength-patternLength; *comparisons=0; #pragma omp parallel for schedule(static, 1) num_threads(1) for (int k = 0; k <= lastI; k++) { int j; for (j = 0; j  i) i = k; } return i; }

Lors du changement de num_threads les résultats suivants sont obtenus pour le nombre de comparaisons:

  • 01 = 9949051000
  • 02 = 4992868032
  • 04 = 2504446034
  • 08 = 1268943748
  • 16 = 776868269
  • 32 = 449834474
  • 64 = 258963324

Pourquoi le nombre de comparaisons n’est-il pas constant? C’est intéressant car le nombre de comparaisons est réduit de moitié avec le doublement du nombre de threads. Existe-t-il une sorte de condition de concurrence pour (*comparisons)++ où OMP ignore simplement l’incrément si la variable est utilisée?

Ma compréhension actuelle est que les itérations de la boucle k sont divisées de manière presque égale entre les threads. Chaque itération a un entier privé j ainsi qu’une copie privée de l’entier k et une boucle for non parallèle qui ajoute aux comparaisons jusqu’à ce qu’elle se termine.

Vous l’avez dit vous-même (*comparisons)++; a une condition de course. C’est une section critique qui doit être sérialisée (je ne pense pas que (* le pointeur) ++ soit une opération atomique).

Donc, fondamentalement, vous lisez deux fois la même valeur (c.-à-d. 2) avec deux threads, puis vous l’augmentez (3) et vous l’écrivez. Donc, vous obtenez 3 au lieu de 4. Vous devez vous assurer que les opérations sur les variables, qui ne sont pas dans la scope locale de votre fonction / boucle parallélisée, ne se chevauchent pas.

La manière naïve de contourner la condition de concurrence critique pour déclarer l’opération comme une atomic update : 

 #pragma omp atomic update (*comparisons)++;

Notez qu’une section critique ici est inutile et beaucoup plus chère. Une atomic update peut être déclarée sur une opération binary primitive ou unaire sur toute expression de valeur l de type scalaire.

Pourtant, cela n’est pas encore optimal car la valeur des *comparisons doit être déplacée constamment entre les caches de processeur et une instruction verrouillée coûteuse est exécutée. Au lieu de cela, vous devriez utiliser une réduction. Pour que vous ayez besoin d’une autre variable locale, le pointeur ne fonctionnera pas ici. 

 int hostMatch(long *comparisons) { int i = -1; int lastI = textLength-patternLength; long comparisons_tmp = 0; #pragma omp parallel for reduction(comparisons_tmp:+) for (int k = 0; k <= lastI; k++) { int j; for (j = 0; j < patternLength; j++) { comparisons_tmp++; if (textData[k+j] != patternData[j]) { j = patternLength+1; //break } } if (j == patternLength && k > i) i = k; } *comparisons = comparisons_tmp; return i; }

La schedule(static, 1) PS schedule(static, 1) semble être une mauvaise idée, car cela conduirait à des modèles d’access mémoire inefficaces sur textData . Laissez-le simplement de côté et laissez le compilateur faire son travail. Si une mesure montre que cela ne fonctionne pas efficacement, donnez-lui de meilleurs indices.