Journal Optimisation de code C

Posté par  .
Étiquettes : aucune
0
19
août
2004
Bonjour,

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  (site web personnel) . Évalué à 10.

    Ce serait plus approprié de poster ici:
    http://linuxfr.org/forums/19/(...)
  • # register ???

    Posté par  (site web personnel) . Évalué à 2.

    Tu peux nous dire à quoi sert le mot clé register ? c'est la premiere fois que je le vois. J'ai cherché sur le net un peu ...
    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  . Évalué à 2.

      Ben si ! :-)
    • [^] # Re: register ???

      Posté par  . Évalué à 3.

      et bien si.
      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  . Évalué à 4.

        De mémoire, d'après le bouquin de C écrit par un de mes profs, il y a déjà quelques années :
        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  (site web personnel) . Évalué à 3.

          -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. */

          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  . Évalué à 2.

    Tu peux essayer de vectoriser ton code en SSE (je crois qu'on peut mettre 2 double dans un registre SSE)
    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.
  • # + d'infos...

    Posté par  (site web personnel) . Évalué à 2.

    Tu pourrais donner plus d'info sur la taille de a et b ?

    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  (site web personnel) . Évalué à 3.

    deja pour les calculs :

    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  . Évalué à 4.

      >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 )

      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 ?
  • # un sujet

    Posté par  (site web personnel) . Évalué à 1.

    "subl $1, %1\n\t"

    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  . É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  (site web personnel) . Évalué à 1.

        non mais utiliser subl me fait gagner 17 % en temps....
        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  (site web personnel) . Évalué à 3.

    > ps. j'ai tester blas et atlas sans succès.

    ben reteste, ça marche bien, c'est portable et tu ne pourras pas faire plus rapide.
    • [^] # Re: atlas

      Posté par  . É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  (site web personnel) . Évalué à 4.

        bon du coup je viens d'essayer pour voir:
        (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  . Évalué à 1.

    http://madchat.org/coding/c/hack_processeur_en_C.html(...)

    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.