je cherche à ecrire en C une routine optimisée pour calculer un produit scalaire de deux vecteurs (de taille variable). Comme cette routine sera appelée plusieurs milliers (millions) de fois, je cherche à gagner le moindre cycle processeurs. Ma plate-forme est un athlon-XP (sans SSE2 donc). Pour l'instant j'ai 2 variantes:
C-pure:
double dot(const double *a, const double *b, unsigned long n)
{
register double res=0.0;
register unsigned long i;
for(i=(n/4)*4; i != 0; i -= 4)
{
register const double res1=a[i] * b[i];
register const double res2=a[i+1] * b[i+1];
register const double res3=a[i+2] * b[i+2];
register const double res4=a[i+3] * b[i+3];
res += res1 + res2 + res3 +res4;
}
switch(n-i)
{
case 3: res += a[n-3] * b[n-3];
case 2: res += a[n-2] * b[n-2];
case 1: res += a[n-1] * b[n-1];
}
return(res);
}
et une C/Asm (plus rapide)
double dot(const double *a, const double *b, unsigned long n)
{
double res;
__asm__ __volatile__ ("fldz\n\t"
"testl %1, %1\n\t"
"jbe .fem.dot.end\n"
".fem.dot.loop:\n\t"
"subl $1, %1\n\t"
# ifdef SSE
/*
* Theses 2 instructions do all the job!
* Whithout them, we get "only" 17% speedup
* note: 128 is an empirical value...
*/
"prefetcht2 -128(%3, %1, 8)\n\t"
"prefetcht2 -128(%2, %1, 8)\n\t"
# endif /* SSE */
"fldl (%3, %1, 8)\n\t"
"fmull (%2, %1, 8)\n\t"
"faddp %0, %0(1)\n\t"
"jne .fem.dot.loop\n"
".fem.dot.end:"
: "=%%st" (res)
: "q" (n) , "q" (a), "q" (b));
return(res);
}
Si il y a des grourous de l'optimisation de code, j'aimerai avoir vos avis!
Merci
ps. j'ai tester blas et atlas sans succès.
# et les forums ?
Posté par Juke (site web personnel) . Évalué à 10.
http://linuxfr.org/forums/19/(...)
# register ???
Posté par bastien (site web personnel) . Évalué à 2.
http://scv.bu.edu/SCV/Archive/IBM/IBMdocs/c/compiler/ref/ruclcre.ht(...)
Mais j'ai peur de ne pas avoir compris ... (ca met pas les variables dans les registres cpu quand meme ???? oO )
[^] # Re: register ???
Posté par Nicolas LAURENT . Évalué à 2.
[^] # Re: register ???
Posté par kruskal . Évalué à 3.
Enfin, ca dit plutot au compilo "écoute, tu veut bien etre gentil de mettre ca en registre ?" ensuite le compilo fait ce qu'il veut.
En général le compilo est assez intelligent pour mettre tout seul les variables qui le peuvent dans les registres, donc c'est tres peu utilisé.
[^] # Re: register ???
Posté par CoinKoin . Évalué à 4.
L'usage du mot-clef "register" n'est plus très utile à l'heure actuelle, car les compilateurs modernes sont plus à même que le programmeur d'affecter les registres aux variables les plus employées.
(De plus, il est impossible d'appeler l'opérateur & sur ces variables, mais ça, tu dois le savoir).
Bon, moi, à ta place, je chercherais plutôt à optimiser mon code avec les options de gcc... genre :
gcc -03 -march=athlon-xp -finline-limit=1000000 /* Tant pis pour la mémoire, ont veut aller vite, et en général, il y a plus qu'assez de RAM sur les machines actuelles. */ -funsafe-math-optimizations /*Risqué, ça...*/ -malign-double -m128bit-long-double ...
vive man gcc!
[^] # Re: register ???
Posté par gc (site web personnel) . Évalué à 3.
Sauf que c'est très con parce que la mémoire est devenue très lente par rapport aux processeurs, et trop inliner va seulement provoquer une famine du cache et foutre en l'air les performances.
Il faut surtout benchmarker, et les bonnes options dépendent en grande partie de l'algo dans le chemin critique.
# Vectorisation
Posté par Guillaume Knispel . Évalué à 2.
D'autant que tu as commencé le boulot avec la structure unloopée dans la version C.
Ensuite je mixerais le résultat avec du prefetching.
Ptet que l'unlooping de l'asm donnerais de bon résultats en schedulant les instru avec soin.
[^] # Re: Vectorisation
Posté par Nicolas Boulay (site web personnel) . Évalué à 1.
"La première sécurité est la liberté"
# + d'infos...
Posté par Nicolas Boulay (site web personnel) . Évalué à 2.
Si c'est "moyen gros", tu peux essayer un bloc prefetch.
genre rajouter :
for(i=0; i < n; i += 16)
{
dummy1 += a[i]; dummy2 += b[i];
}
devant la 1er boucle mais vu que tu n'y fais pas grand chose peut-être que mixer la chose pourrais faire gagner du temps :
for(i=0; i < (n/4)*4 ; i += 4){ // les prefetcher automatiques n'aiment pas les adresses descendantes
dummy1 += a[j=(j+16) mod n]; dummy2 += b[j];
res1+=a[i] * b[i];
res2+=a[i+1] * b[i+1];
res3+=a[i+2] * b[i+2];
res4 +=a[i+3] * b[i+3];
}
res += res1 + res2 + res3 +res4;
A coder en SSE si tu veux t'amuser (déroulant la boucle pareil !).
"La première sécurité est la liberté"
# optims de base
Posté par Mouns (site web personnel) . Évalué à 3.
les calculs a virgules fixes sont excessivement plus rapide que les virgules flottantes.
apres au niveau de l'archi :
sur les archis MMXisante, le MMX permet de paralleliser en prime des operations a virgules fixes la ou il n'y a qu'une operation a virgule flottante
il peut etre interessant d'utiliser certaines propriétés des pentium ( non MMX aussi ) qui ont une deuxieme UAL plus restreinte pour paralleliser les operations.
je ne connais pas les specificités des Athlon, je ne peux donc en parler.
et enfin reste une version MP du calcul.
au niveau du code :
un jmp réinitie le bus une partie du processeur ( pipeline de traitement des instructions ) donc il faut etaler les boucles.
les conditions sont couteuses.
un shift ( multiplication ou division par deux ) est bien moins couteux en cycle qu'un mul sur des entiers
un and est mieux qu'un div pour obtenir le reste ( s'arranger avec 2^x-1 )
avoir une approche differentielle du calcul permet dans une certaine mesure de se passer aussi des multiplication et division
si tout cela est impossible, selon la precision demander une logarithme bien choisi peut aussi facilité les calculs
faut aussi penser à aligner les données en memoire
avec ca, tu peux avoir des gains assez phenomenaux ... mais il faut faire du benchmark et surtout une analyse sinon cela peut ne servir a rien.
[^] # Re: optims de base
Posté par Christophe Fergeau . Évalué à 4.
>un and est mieux qu'un div pour obtenir le reste ( s'arranger avec 2^x-1 )
Dans les cas simples, j'espère que gcc (ou le compilateur) fait l'optimisation tout seul... Dans les cas plus compliqués, je sais pas si ça vaut vraiment le coup de découper une multiplication en plusieurs multiplications par 2 avec addition ?
[^] # Re: optims de base
Posté par Nicolas LAURENT . Évalué à 4.
[^] # Re: optims de base
Posté par Nicolas LAURENT . Évalué à -2.
# un sujet
Posté par Stephane Marchesin (site web personnel) . Évalué à 1.
et dec c'est pour les chiens ? ;)
"prefetcht2 -128(%3, %1, 8)\n\t"
"prefetcht2 -128(%2, %1, 8)\n\t"
Tu devrais essayer avec prefetchnta plutôt que prefetcht2
Essaye aussi un prefetch à une distance de 256, ca peut être plus rapide (tu ne donnes pas la taille moyenne de tes vecteurs).
Essaye aussi d'aller dans le sens incrémental pour parcourir ton vecteur (les chipsets sont capables de faire des prefetchs hardware uniquement dans ce sens).
Aligne ta mémoire (man memalign).
Sinon, vu comme ta boule de calcul est courte, je pense que quasiment tous les gains se feront sur les accès mémoire.
[^] # Re: un sujet
Posté par Nicolas LAURENT . Évalué à 2.
> "subl $1, %1\n\t"
et dec c'est pour les chiens ? ;)
non mais utiliser subl me fait gagner 17 % en temps....
Tu devrais essayer avec prefetchnta plutôt que prefetcht2
Essaye aussi un prefetch à une distance de 256, ca peut être plus rapide (tu ne donnes pas la taille moyenne de tes vecteurs).
j'ai fait le test avec 256 et c'est les meme resultat qu'avec 128. La taille des vecteurs varie entre 1 et 1500. Dans un meme calcul, il peut y avoir des vecteur de toute taille.
Essaye aussi d'aller dans le sens incrémental pour parcourir ton vecteur (les chipsets sont capables de faire des prefetchs hardware uniquement dans ce sens).
le parcours à l'envers m'a fait gagner quelques % sur MIPS mais effectivement sur ia32 j'y perd.
Sinon, vu comme ta boule de calcul est courte, je pense que quasiment tous les gains se feront sur les accès mémoire.
oui, c'est aussi ma conclusion...
[^] # Re: un sujet
Posté par Stephane Marchesin (site web personnel) . Évalué à 1.
Problème de scheduling. Bienvenue dans la magie de l'execution out of order :)
Essaye de bouger un peu le dec entre les instructions flottantes.
j'ai fait le test avec 256 et c'est les meme resultat qu'avec 128. La taille des vecteurs varie entre 1 et 1500. Dans un meme calcul, il peut y avoir des vecteur de toute taille.
Ah, mais 1500 c'est tout petit !
Essaye d'insérer des prefetch à intervalle de 64 avant la boucle :
prefetchtnta (...)
prefetchtnta 64(...)
Bien sûr, ne dépasse pas l'endroit où tu préfetches dans la boucle (ne mets pas un 128 si il y en a deja un dans la boucle, quoi).
# atlas
Posté par Troy McClure (site web personnel) . Évalué à 3.
ben reteste, ça marche bien, c'est portable et tu ne pourras pas faire plus rapide.
[^] # Re: atlas
Posté par Nicolas LAURENT . Évalué à 1.
ben reteste, ça marche bien, c'est portable et tu ne pourras pas faire plus rapide.
ben pourtant, mes routines (C et ASM) _sont_ plus rapides... et la première est portable.
[^] # Re: atlas
Posté par Troy McClure (site web personnel) . Évalué à 4.
(gcc -O3 t.c -lblas -L/usr/lib/atlas/sse -latlas -lm, sur un athlon-xp avec le atlas-sse de debian je ne sais pas trop pour quel proc il a été compilé)
vecteurs de taille N=500, 500000 dot:
- dot(c): 0.285s
- dot(asm): 0.554s
- dot(atlas/sse): 0.242s
N=50000, 5000 dot:
-dot(c): 4.876s
-dot(asm): 3.522s
-dot(atlas/sse): 3.580s
Voila, je m'attendais un peu à ce que atlas explose plus franchement les autres, mais quand même: au mieux tu ne gagnes que quelques pouillèmes, et uniquement pour ta machine. Note que je ne dis pas que l'exercice n'est pas interessant
# Petites doc sympa
Posté par ckyl . Évalué à 1.
Ca tombe bien l'exemple c'est a peu pres ce que tu cherches :-)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.