Bonjour,
Je dois effectuer un nombre très important de fois la boucle suivante avec un contrainte très forte sur le temps d'exécution:
for(i = 0 ; i < N ; i++){
yvar1[i] = yvar1[i] + yvar2[i] + yvar3[i];
yvar2[i] = yvar2[i] + 2.0 * yvar3[i];
}
où N est proche de 130000 et yvar* est un tableau de double.
Ce calcul est théoriquement trivialement parallélisable mais malheureusemnt je n'obtiens pas un bon speedup avec plus de deux threads. C'est probablement dû au fait que N n'est pas si grand et qu'on effectue beaucoup de lecture/écriture par rapport au nombre de calcul.
Avec le test suivant ( http://codeviewer.org/view/code:1397 )
compilé avec "cc -O3 -lpthread testPred.c -o testPred"
sur un "biprocesseur-quadricore-hyperthreadé (i.e. 16 coeurs logiques) Intel(R) Xeon(R) CPU E5530 @ 2.40GHz" j'obtiens les temps suivant:
[DEK328@PEGASE08 testParall]$ ./compile.sh && ./testPred
inplace sequential prediction : 0.440000 ms
inplace sequential prediction += : 0.356000 ms
outplace sequential prediction : 1.003000 ms
inplace parallel prediction += using 1 threads: 0.798000 ms
inplace parallel prediction += using 2 threads: 0.304000 ms
inplace parallel prediction += using 4 threads: 0.430000 ms
inplace parallel prediction += using 8 threads: 0.425000 ms
inplace parallel prediction += using 16 threads: 0.662000 ms
outplace parallel prediction using 1 threads: 0.475000 ms
outplace parallel prediction using 2 threads: 0.284000 ms
outplace parallel prediction using 4 threads: 0.414000 ms
outplace parallel prediction using 8 threads: 0.488000 ms
outplace parallel prediction using 16 threads: 0.577000 ms
On constate que dès qu'il y a plus de 2 threads, le speedup est très mauvais (même avec la version "outplace" où l'on ne devrait pas avoir de falsesharing). La meilleur combinaison mène à un temps de 0.28ms qui est malheureusement toujours trop élevé pour mes besoins.
On a constaté le même genre de mesure en utilisant d'autre langage (intel Fortran et OpenMP).
Plusieurs questions:
- qu'est-ce qui explique ce si mauvais speedup ?.
- y-a-t'il une autre technique qui améliorerait les performances ? Presque toutes les options sont ouvertes (hardware, algorithmiques, langages...)
- pourquoi est-ce que la version avec "yvar1[i] = yvar1[i] + ... " est moins performante que celle avec "yvar1[i] += ..." ? Le compilateur n'est-il pas assez intelligent pour remarquer que c'est la même chose ?
- par ailleurs connaîtriez-vous d'autres sites/forum où l'on s'intéresse à ce genre de question ?
Merci d'avance pour vos suggestions.
# Quelques commentaires
Posté par JoeltheLion (site web personnel) . Évalué à 9.
- Ton code a peut-être un problème de "pointer aliasing". A priori le compilateur n'a pas moyen d'être sûr que yvar1, yvar2 et yvar3 ne pointent pas à des endroits voisins en mémoire, et ne peut donc pas faire d'optimisations comme l'utilisation des instructions SIMD.
-Cela m'amène au deuxième point : as-tu regardé l'assembleur généré par le compilateur? Il n'y a pas besoin d'être un expert pour le faire, et ça peut être riche en enseignements: place le code critique entre deux commentaires assembleur ( __asm__("#before") par exemple, de mémoire), compile avec le bon flag gcc et c'est parti!
-En ce qui concerne la parallélisation par threads, vu le faible temps d'exécution de la boucle, je me demande si le coût de création des threads n'explique pas tout simplement la baisse des performances.
Bon courage! (et n'hésite pas à faire un journal quand tu auras réussi, c'est toujours intéressant ce genre de problèmes)
[^] # Re: Quelques commentaires
Posté par benoar . Évalué à 3.
Et commme indiqué en dessous, alloue tes tableaux statiquement. Tu auras donc quelque chose comme :
double yvar1[N];double yvar2[N];
...
Et pour la différence entre le += et le + seulement, c'est sûrement une histoire qui ressemble à l'aliasing, mais dans le cas du multithread : le compilo va dans le cas du + générer une variable intermédiaire entre l'accès à yvar1 et l'affectation, car il ne peut pas savoir si le tableau a changé entre deux. Dans le cas du +=, il doit générer une instruction qui fait l'addition "en place" dans le registre.
# += pdf multiplication
Posté par nicolas . Évalué à 4.
Ça n’est pas tout à fait la même chose :
a += b + c ⇔ a = a + (b + c)Il est possible que certains compilateurs fassent la distinction pour des raisons de précision numérique.⇎
a = a + b + c ⇔ a = (a + b) + c
Par contre je ne sais pas pourquoi ça impacterait les performances… si tu mets explicitement des parenthèses (dans les deux cas) ça change quelque chose ?
Pour les questions d’optimisations j’avais trouvé la lecture de [http://www.agner.org/optimize/optimizing_cpp.pdf] très instructive.
Mais j’ai constaté le même phénomène que toi, pour les « petites » (petite sur le nombre de ligne d’une itération, pas le nombre d’itération) boucles la parallélisation n’apporte aucun gain : sur-charge pour la gestion des threads (création ou réveil), mais surtout les boucles déjà optimisées qui partent en SIMD (surtout dans ton cas).
Petite question au passage : est-ce que mettre
yvar2[i] = yvar2[i] + (yvar3[i] + yvar3[i]);pour la deuxième ligne change quelque chose (avec et sans les parenthèses) ?# seul ?
Posté par Pierre Tramal (site web personnel) . Évalué à 1.
[^] # Re: seul ?
Posté par berti . Évalué à 2.
# à coté
Posté par fcartegnie . Évalué à 2.
Comme N est une constante, tu gagneras en vitesse en déclarant des tableaux.
(tu économise un lookup de pointeur)
gettimeofday(&t, NULL);
N'est pas thread safe
[^] # Re: à coté
Posté par fcartegnie . Évalué à 2.
N'est pas thread safe
Ignore cette remarque. Faut que je me reveille. &t
# creation des threads + cache
Posté par François Trahay (site web personnel) . Évalué à 4.
La création d'un thread est coûteuse. La création de 16 threads est encore plus coûteuse. Donc pour des traitements aussi courts (dans ton cas de l'ordre de 400 us), la création des threads prend beaucoup trop de temps. Si tu utilises OpenMP, tu peux évaluer le coût de la création des threads en faisant plusieurs mesures à la suite:
for (mesure=0; mesure<10; mesure++) {
start = get_time();
#pragma omp parallel for
for(i=0; i<N;i++) {
...
}
stop = get_time();
}
A la première mesure, le runtime OpenMP va créer un certain nombre de threads et paralléliser la boucle. A la fin de cette boucle, les threads ne seront pas détruits, et normalement la deuxième boucle devrait aller plus vite (les threads sont réutilisés).
Donc si dans ton application tu risques de faire plusieurs fois ce calcul, essaie de prendre en compte la création/destruction des threads.
Le deuxième problème que je vois est lié aux caches. Quand tu alloues et initialises les tableaux yvar*, ils se retrouvent dans le cache d'un des cœurs. Quand tu lances un thread pour qu'il fasse une partie du calcul, il faut que les données qu'il traite soient envoyées dans le cache qui va bien.
Si ce thread est 'proche' du cache où sont les données, ca se passe bien, mais si il faut faire transiter les données d'un processeur à l'autre, ca prend beaucoup de temps.
En fixant tes threads de calcul à la main, tu devrais pouvoir maitriser un peu mieux ces transferts de données. Pour ca, tu peux utiliser hwloc ( http://www.open-mpi.org/projects/hwloc/ )
[^] # Re: creation des threads + cache
Posté par berti . Évalué à 1.
La première exécution de cette boucle coûte chère et les suivantes moins chères. Malheureusement même lors de l'appel des boucles suivantes on n'obtient pas un bon speedup pour plus de deux threads (les résultats des boucles suivantes en OpenMP sont assez proche de ceux obtenus avec les pthreads). J'essaierai de poster les temps obtenus en OpenMP dès que j'aurai de nouveau accès à la machine sur laquelle j'ai fait mes tests.
En utilisant des pthreads je ne vois pas de différence entre un premier appel et les appels successifs. Néanmoins c'est la première fois que j'utilise ces pthreads. Est-il possible de garder ces threads "actifs" afin d'accélérer le prochain appel ?
Je vais jeter un coup d'oeuil à hwloc. Je vous tiendrai au courant des résultats.
[^] # Re: creation des threads + cache
Posté par François Trahay (site web personnel) . Évalué à 2.
Oui, il suffit de ne pas les tuer :) Par exemple, au lieu de faire:
pthread_create( &(threads[i]), NULL, predictInPlace, (void*) (&dataThreads[i]));
tu peux exécuter une fonction qui attend du travail :
pthread_create( &(threads[i]), NULL, traiter_un_job, (void*) (&dataThreads[i]));
void traiter_un_job(void* ptr) {
while(1) {
sem_wait(&truc_a_traiter);
predicInPlace(ptr);
sem_post(&traitement_terminee);
}
}
Une fois tes threads lancés, tu peux lancer un traitement en parallèle en appelant
sem_post(&truc_a_traiter);pour chaque thread que tu veux débloquer (attention, c'est fait à l'arrache, il y a des races conditions).Après, cette solution ressemble à ce que fait l'implémentation OpenMP, donc je pense qu'il vaut mieux laisser OpenMP gérer ce genre de cas. L'utilisation de pthreads n'apportera pas grand chose à moins de fixer les threads sur les cores qui vont bien, ce qu'OpenMP ne sait pas forcement faire.
[^] # Re: creation des threads + cache
Posté par FXB . Évalué à 1.
Bonjour
J'ai fait le test de l'auteur avec OPENMP, je l'ai porté en FORTRAN et utilisé un compilateur INTEL 11.1 qui est réputé comme un compilateur performant (openmp 3.0)
Dans ce cas, je voudrais signaler que j'observe le même comportement que lui avec pthreads
- J'ai fait attention d'exécuter le job plusieurs fois et de ne pas compter le premier appel. (les threads sont créées)
- Pour répondre à la localisation des données, j'ai utilisé une fonction du compilateur (variable d'envirronnement KMP_AFFINITY) qui permet de choisir de balancer les threads entre processeurs ou de remplir d'abord un processeur avant d'en remplir un suivant. J'ai bien sur désactivé l'hyperthreading pour ne pas véroler les performances.
J'ai donc une question pour vous. Pensez-vous que la vitesse du cache peut être en cause?
...et même une deuxième question: Avez-vous pu reproduire son problème sur vos machines?
Amicalement.
[^] # Re: creation des threads + cache
Posté par _Sil_ . Évalué à 1.
Intel(R) Xeon(R) CPU X3350 @ 2.66GHz
Les résultats sont assez aléatoires, même si rien d'autre de gourmand ne tourne.
inplace sequential prediction : 0.402000 ms
inplace sequential prediction += : 0.354000 ms
outplace sequential prediction : 1.446000 ms
inplace parallel prediction += using 1 threads: 2.075000 ms
inplace parallel prediction += using 2 threads: 0.966000 ms
inplace parallel prediction += using 4 threads: 0.837000 ms
inplace parallel prediction += using 8 threads: 1.835000 ms
inplace parallel prediction += using 16 threads: 0.755000 ms
outplace parallel prediction using 1 threads: 2.175000 ms
outplace parallel prediction using 2 threads: 1.123000 ms
outplace parallel prediction using 4 threads: 0.774000 ms
outplace parallel prediction using 8 threads: 0.853000 ms
outplace parallel prediction using 16 threads: 0.771000 ms
ou alors
inplace sequential prediction : 0.310000 ms
inplace sequential prediction += : 0.276000 ms
outplace sequential prediction : 1.365000 ms
inplace parallel prediction += using 1 threads: 2.280000 ms
inplace parallel prediction += using 2 threads: 1.083000 ms
inplace parallel prediction += using 4 threads: 0.632000 ms
inplace parallel prediction += using 8 threads: 0.507000 ms
inplace parallel prediction += using 16 threads: 0.610000 ms
outplace parallel prediction using 1 threads: 1.108000 ms
outplace parallel prediction using 2 threads: 1.177000 ms
outplace parallel prediction using 4 threads: 1.319000 ms
outplace parallel prediction using 8 threads: 0.628000 ms
outplace parallel prediction using 16 threads: 0.724000 ms
Je pense que les temps sont beaucoup trop court et la moindre préemption/interruption fausse le résultat.
Du coup je me demande si c'est pas simplement un patch RT la solution
[^] # Re: creation des threads + cache
Posté par François Trahay (site web personnel) . Évalué à 3.
Je n'ai pas teste sur une machine de calcul, uniquement sur mon portable (Core i5 M540 2.53GHz). J'ai le même genre de comportement.
Pensez-vous que la vitesse du cache peut être en cause?
Je pense que c'est quelque chose comme ca oui. Il est sans doute possible de paralléliser le code à peu près efficacement, mais ca risque de demander des bidouillages pas beaux pour un speedup à peine correct.
Du coup, si on revient à la question initiale, berti nous dit:
La meilleur combinaison mène à un temps de 0.28ms qui est malheureusement toujours trop élevé pour mes besoins.
Pourrais-tu nous expliquer tes besoins ? Pourquoi 280us c'est trop ? Est-ce parce que ce calcul est effectué plein de fois à la suite ? Est-ce dû à des contraintes temps-réel ?
[^] # Re: creation des threads + cache
Posté par khivapia . Évalué à 3.
# Google
Posté par barmic . Évalué à 3.
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
# Spécificité processeur
Posté par yellowiscool . Évalué à 3.
Par exemple, les processeurs G4 et G5 (power pc) possèdent un jeu d'instruction appelé altivec qui permet par exemple de faire des opérations sur 16 éléments à la fois.
Il existe un peu près la même chose avec les instructions sse* il me semble.
Envoyé depuis mon lapin.
# Assembleur
Posté par yellowiscool . Évalué à 1.
Par exemple, sur un processeur G4 ou G5 (power pc), le jeu d'instruction altivec permet de réaliser des opérations sur 16 éléments à la fois. Si c'est bien utilisé, ça peut faire des très grosses optimisations.
Envoyé depuis mon lapin.
[^] # Re: Assembleur
Posté par yellowiscool . Évalué à 2.
Envoyé depuis mon lapin.
[^] # Re: Assembleur
Posté par Krunch (site web personnel) . Évalué à 4.
http://en.wikipedia.org/wiki/SIMD
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
[^] # Re: Assembleur
Posté par _Sil_ . Évalué à 1.
yvar1[i] += yvar2[i] + yvar3[i];
4007f0: f2 0f 10 09 movsd (%rcx),%xmm1
...
4007f7: f2 0f 10 10 movsd (%rax),%xmm2
4007fb: 66 0f 16 49 08 movhpd 0x8(%rcx),%xmm1
400800: f2 0f 10 22 movsd (%rdx),%xmm4
400804: 66 0f 16 50 08 movhpd 0x8(%rax),%xmm2
400809: 66 0f 16 62 08 movhpd 0x8(%rdx),%xmm4
40080e: 66 0f 28 c1 movapd %xmm1,%xmm0
400812: 66 0f 28 ca movapd %xmm2,%xmm1
400816: 66 0f 58 cc addpd %xmm4,%xmm1
40081a: 66 0f 58 c1 addpd %xmm1,%xmm0
40081e: 66 0f 13 01 movlpd %xmm0,(%rcx)
400822: 66 0f 17 41 08 movhpd %xmm0,0x8(%rcx)
Il utilise bien les instructions SSE.
Par contre, si je comprend bien, il charge un couple de y1, y2,y3 dans les registres xmm1, xmm2 et xmm4.
Puis met xmm1 dans xmm0
Puis met xmm2 dans xmm1
Puis additionne xmm4 + xmm1 + xmm2.
Dites monsieur gcc, ca sert à quoi ce déplacement des registres 2 et 1 dans 1 et 0 ??
C'est probablement pour cela que tu vois une différence (injustifiable à mon avis) entre le "+=" et les "+" .
Il ne fait pas cette entourloupe pour pour la série de "+" .
[^] # Re: Assembleur
Posté par _Sil_ . Évalué à 1.
Je ne suis pas un grand spécialiste, mais il doit être difficile de faire beaucoup mieux ?
Le "problème" est bien a chercher dans l'overhead introduit par les threads.
yvar1Temp[i] = yvar1[i] + yvar2[i] + yvar3[i];
movsd (%r8),%xmm3
movhpd 0x8(%rcx,%rbx,1),%xmm1
movhpd 0x8(%r8),%xmm3
movapd %xmm1,%xmm0
addpd %xmm3,%xmm0
movsd 0x0(%rbp),%xmm3
movhpd 0x8(%rbp),%xmm3
addpd %xmm3,%xmm0
movlpd %xmm0,(%rdx,%rbx,1)
movhpd %xmm0,0x8(%rdx,%rbx,1)
[^] # Re: Assembleur
Posté par _Sil_ . Évalué à 1.
xmm4, xmm1 et xmm0 et non pas xmm4, xmm2 et xmm1 (ce qui de doute façon donnerait le même résultat !)
[^] # Re: Assembleur
Posté par _Sil_ . Évalué à 1.
-> Non, je sors.
# -funroll-loops
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 3.
En supposant qu'une itération de boucle soit executée dans un fil, alors un -funroll-loops devrait permettre d'avoir plus de code par thread, plus d'invariants pour les optimisations, un meilleur cache, et plus de succès auprès des femmes.
[^] # Re: -funroll-loops
Posté par briaeros007 . Évalué à 3.
D'autant qu'elle est très simple, et implique aussi qu'il n'y aura que peu de changement de contexte :
en pseudo code ca devrais un truc comme ça
int nb_thread=n;//on va créer n thread)
int size_tab=x;//la taille du tableau
int size_seg=x/n;//ne pas oublier les vérifs n>x, et si x n'est pas divisible par n. Bref gérer les effets de bords.
/* on lance les traitements*/
while (nb_thread>0)
{
create_thread(mon_thread_a_moi,nb_thread,(size_seg*nb_thread),size_seg*(nb_thread+1));//on créé un "thread a moi", en lui disant d'utiliser les indiques de départ (size_seg*nb_thread), et de fin size_seg*(nb_thread+1)
nb_thread--;
}
nb_thread=n;
/* on attend qu'ils soient terminées*/
while (nb_thread>0)
{
join(pid_thread(nb_thread));
}
void mon_thread_a_moi (int nb,int deb,int end)
{
while (end>=deb)
{
yvar1[end] = yvar1[end] + yvar2[end] + yvar3[end];
yvar2[end] = yvar2[end] + 2.0 * yvar3[end];
end--;
}
}
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.