Réécriture de code : AWK ou LEX/YACC

Réécriture de code : AWK ou LEX/YACC - C++ - Programmation

Marsh Posté le 07-06-2003 à 22:02:57    

Le topic chiant de Jojo v 2.3 :
 
voila j'ai developpé une bibliothéque basée sur les technique des Expressives Tempaltes de Veldhuizen pour générer du code utilisant les fonctions AltiVec du PPC de maniére simple et performantes. Actuellement, ca ressemble à ca :
 

Code :
  1. using namespace eve;
  3. Vector<float,256*256> v1,v2,v3;
  5. v3 = abs(v1-v2);


 
ma bibliothéque va alors générer un code qui ressemble à ca :
 

Code :
  1. using namespace eve;
  3. Vector<float,256*256> v1,v2,v3,r;
  5. for(i=0;i<256*256/4;i++)
  6. {
  7.   vec_st(vec_abs(vec_sub(vec_ld(0,v1),vec_ld(0,v2))),i,v3);
  8. }


 
les connaiseurs apprécieront.
Problémes, pour un type de donnée précis, je n'atteind que la moitié de l'accélération théorique d'AltiVec ( resp. 2,4,8 au lieu de 4,8,16). J'ai donc developpé une deuxiéme écriture :
 

Code :
  1. using namespace eve;
  3. Vector<float,256*256> v1,v2,v3;
  4. Ref<1> x;
  5. Ref<2> y;
  7. apply( abs(x-y),v1,v2,v3);


 
Cette ecriture "deplie" le code AltiVec en prenant soin de ne charger que les vecteurs necessaires, de deplier les boucles internes et d'utiliser le cache. Grace a cette version, j'atteind facilement 95 a 99% de l'accel maximale voir meme pour les flottants 100 a 120% de l'accel. maximale.
 
PROBLEME : l'ecriture avec apply est trop contraignante, celle avec les +,-,*,etc .... trop peu efficace. Je gerre donc un moyen simple de "pre-processer" un source c++ utilisant l'ecriture 1 pr le transformer en ecriture 2.
 
QUESTION : Quel outil utilisé, AWk, LEX+YACC autre chose ???
Merci d'avance pr vos réponses.

Reply

Marsh Posté le 07-06-2003 à 22:02:57   

Reply

Marsh Posté le 07-06-2003 à 23:52:59    

je connais pas ta bibliotheque mais ça me parait louche
 
vec_abs(vec_sub(vec_ld(0,v1),vec_ld(0,v2)))
 
t'es sur que ça fait pas à chaque itération le même calcul
 
perso, je vois pas pourquoi la deuxième méthode serait plus rapide ormis le coup de l'affectation. pourquoi ne pas directement initialisé v3 avec le résultat que calcul. sinon, tu touches un problème C++: on travaille par valeur. donc à moins d'avoir une impléméntation qui partage les ressources intelligemment, on bouffe de la recopie. si tu te sens abile, pour ne pas utiliser les références?

Reply

Marsh Posté le 08-06-2003 à 00:20:05    

Joel F a écrit :

QUESTION : Quel outil utilisé, AWk, LEX+YACC autre chose ???
Merci d'avance pr vos réponses.


Tu vas t'enliser, quasiment personne ne sait écrire une grammaire pour C++ (fait un petit tour dans la bas des bugs de gcc pour voir).
Donc soit tu changes de langage (d'une manière ou d'une autre) soit tu trouve une solution dans C++, mais ne tentes surtout pas de le parser, reconnaitre les structures en question et les réécrire, c'est quasi impossible.
 
Si tu peux changer de langage, o'caml avec le système P4 te permettra de le faire simplement.

Reply

Marsh Posté le 08-06-2003 à 09:33:03    

++Taz a écrit :

je connais pas ta bibliotheque mais ça me parait louche
 
vec_abs(vec_sub(vec_ld(0,v1),vec_ld(0,v2)))
 
t'es sur que ça fait pas à chaque itération le même calcul


 
hmmm, erreur de recopie désolé.
 

++Taz a écrit :


perso, je vois pas pourquoi la deuxième méthode serait plus rapide ormis le coup de l'affectation. pourquoi ne pas directement initialisé v3 avec le résultat que calcul. sinon, tu touches un problème C++: on travaille par valeur. donc à moins d'avoir une impléméntation qui partage les ressources intelligemment, on bouffe de la recopie. si tu te sens abile, pour ne pas utiliser les références?


 
Trés simplement, Dans la premiére méthode, le code générée "charge" les données dans les registres AltiVec au fur et à mesure qu'il les rencontrent dasn l'expression. Or AltiVec et plus efficaces si l'on écrit des fonctions de types 'blit', qui charge en bloc les registres au début des itérations, font le calculs et écrivent les résultats finaux. Le problème ne vient pas du C++, les fonctions vec_??? étant des routines assembleurs. En fait la deuxiéme ecriture se déplie ainsi :
 

Code :
  1. for(int i = 0; i< 256*256/(4*4);i++ )
  2. {
  3.   vector float t1,t2,t3,t4;
  4.   vector float p1,p2,p3,p4;
  6.   t1 = vec_ld(4*i,v1);
  7.   t2 = vec_ld(4*i+1,v1);
  8.   t3 = vec_ld(4*i+2,v1);
  9.   t4 = vec_ld(4*i+3,v1);
  11.   p1 = vec_ld(4*i,v2);
  12.   p2 = vec_ld(4*i+1,v2);
  13.   p3 = vec_ld(4*i+2,v2);
  14.   p4 = vec_ld(4*i+3,v2);
  16.   t1 = vec_abs(vec_sub(t1,p1));
  17.   t2 = vec_abs(vec_sub(t2,p2));
  18.   t3 = vec_abs(vec_sub(t3,p3));
  19.   t4 = vec_abs(vec_sub(t4,p4));
  20.  
  21.   vec_st( t1,4*i,v3 );
  22.   vec_st( t2,4*i+1,v3 );
  23.   vec_st( t3,4*i+2,v3 );
  24.   vec_st( t4,4*i+3,v3 );
  25. }


 
Ca parait bête mais cette version respecte plus le pipeline et le cache du PPC et a donc des perf plus importantes.
 
@nraynaud : arg ... je n'ai pas besoin de parser TOUT le source C++ juste de repérer les expressions à base de Vector<> et d'effectuer les changements ... ou suis je encore en train de m'égarer ?? La contrainte la plus forte etant evidemment que je doit RESTER en C++ :(
 
J'ai bien une ébauche de solution, mais le probléme est que je risque de devoir utiliser des specialisations partielles de templates mais apparemment je ne trouve AUCUN compilo qui sache les gérer proprement :/


Message édité par Joel F le 08-06-2003 à 09:33:25
Reply

Marsh Posté le 08-06-2003 à 10:46:03    

les templates c'est une super idée: tu peut faire de la meta programmation et t'en servir pour dérouler tes boucles. si ton compilo supporte pas ça, c'est vrai que c'est mort


Message édité par Taz le 08-06-2003 à 10:46:28
Reply

Marsh Posté le 08-06-2003 à 11:05:13    

J'utilise DEJA les templates et le smeta-programmes a fond, le probleme est que l'astuce qui me permettrait de passer de v1=v2+v3 a apply(x-y,v1,v2,v3) necessite la spec. partielle des templates ce que le Apple GCC 3.1 ne supporte pas :/
 
En fait, je gere deja la generation du code déroulé via les templates mais pas encore au point precis que je veux :D
 
D'ou mon idée de réecriture du code par une appli de parsing ...
++Taz, si tu veux vraiment voir les details de mon truc je t'enverrais ca, mais la si je commence a expliquer tt en details ca va prendre trop de place :P


Message édité par Joel F le 08-06-2003 à 11:06:30
Reply

Marsh Posté le 08-06-2003 à 11:35:10    

oui, je veux bien s'il te plait...t 'as pas moyen de mettre ton compilo à jour :sol: N

Reply

Marsh Posté le 08-06-2003 à 14:13:19    

Ok, bon en fait ca peut tenir ici :
 
J'ai utilisé les Expressions Templates de Veldhuizen pour générer du code optimisé. En clair, j'ai une classe de vecteur Vector<T,S> (T : type des elem du vecteur, S taille en nb d'éléments).
 
Lorsque que tu veux faire  
 

Code :
  1. Vector<char,10> a,b,c;
  2. c = a+b


 
le compilo fait :
 

Code :
  1. c.operator=( operator+(a,b);


 
La pas trop de probleme ... mais si tu fait des trcus du genre :
 

Code :
  1. a = (b+c+d*e)/f-h;


 
Le compilo génére une tripotée de valeurs intermédiaries. C pas cool :(
 
Donc, j'ai crée une série de classe template qui me permettent d'écrire des EXPRESSIONS basées sur les templates. En clair, y a une classe Expression, une class BinaryOp, UnaryOp et Vector.
L'operator+ par ex. devient :
 

Code :
  1. template<class T,int S>
  2. Expression<BinaryOp<T,Vector<T,S>,Vector<T,S>,OpAdd<T>>,T>
  3. operator+( const Vector<T,S>& a, const Vector<T,S>& b )
  4. {
  5.    typedef BinaryOp<T,Vector<T,S>,Vector<T,S>,OpAdd<T>> expr;
  6.    return Expression<expr>( expr(a.begin(),b.begin());
  7. }


 
L'operator= au lieu d'accepter un Vector en argument, attend un object Expression. Lorsque ce dernier est résolu, il va généreer une boucle qui va évaluer le resultat de l'expression pr chaque element.  
 

Code :
  1. template<class E>
  2. Vector<T,S>& operator=( const E& expr )
  3. {
  4.   for(int i=0;i<S;i++)
  5.   {
  6.      vec_st( expr[i],0,begin());
  7.   }
  8.   return *this;
  9. }
  11. // avec :
  13. template<class E,class T>
  14. SIMDType<T>::type Expression<T,S>::oerator[](int i)
  15. {
  16.   return mInternalExpr[i];
  17. }
  19. // et :
  20. template<class T,class O>
  21. SIMDType<T>::type BinaryOp<T,T,O>::oerator[](int i)
  22. {
  23.   return O::apply( lhs[i],rhs[i] );
  24. }
  26. template<class T>
  27. class OpAdd
  28. {
  29.   static inline SIMDType<T>::type apply( T l, T r )
  30.   {
  31.     return vec_add(l,h);
  32.   }
  33. }
  35. // Le Vector fournit aussi un operator [] qui renvoie :
  36. // vec-ld(i,begin());
  38. // Au final, a+b devient :
  39.   for(int i=0;i<S;i++)
  40.   {
  41.      vec_st( vec_add(vec_ld(i,a.begin()),vec_ld(i,a.begin())),0,begin());
  42.   }


 
Mais la classe Expression n'est pas "consciente" des vecteurs qu'elle contient, si tu fait a+a, elle va charger DEUX FOIS le contenu de a dans un vector AltiVec (ce qui n'est pas bien :P). Or cette maniére de faire génére le code que je t'ai montré si dessus.
 
Ma version avec apply utilise le même principe mais permet de charger une et une seule fois chaque vecteur de l'expression. Le code a+a va charger une fois a et utiliser ce vecteur chargée pr calculer la somme. En effet, comme l'expression passé a apply n'est qu'une representation et que les vecteurs sur lesquels seront effectués les calculs sont connus AVANT le debut des calculs, on peut préchargé le svecteurs dasn l'unité AltiVec. D'ou le gain augmenté ...
 
Actuellement, les deux versions (operator et apply) cohabitent dans ma bibliothéque. MAIS je n'arrive pas à générer le code de apply a partir de l'ecriture avec les operateurs ...


Message édité par Joel F le 08-06-2003 à 14:23:04
Reply

Marsh Posté le 08-06-2003 à 14:19:46    

ouais, je comprends, j'ai peur que ça soit sans solution facile. tu te plains du cout de recopie, ce qui evidemment je comprends. Pourquoi tu n'esssayes pas de faire de l'aggrétation pour apsser outre ce problème.
 
(vivement les prochaines evolutions du C++, on pourra définir operator = + (lvalue, lhs, rhs)

Reply

Marsh Posté le 08-06-2003 à 14:25:33    

... je crois que je m'exprime mal ...
J'ai resolu le probleme de recopie, MAIS actuellement j'ai deux versions du code qui resout se probleme chacune avec des gains différents. Ce que je veux c prendre un code qui utilise la version 'pas rapide' et la réécrire avec la version 'rapide'.
 
Toute la question se resume à comment parser un fichier C++
et remplacer
 
"a=b+c;"
en
"apply(x+y,b,c,a);"

Reply

Marsh Posté le 08-06-2003 à 14:25:33   

Reply

Marsh Posté le 08-06-2003 à 15:22:49    

ok... une super regex?

Reply

Marsh Posté le 08-06-2003 à 20:12:21    

basiquement oui, sauf qu'il tenir compte des types, des typedef des macros etc ... mais basiqueemnt l'algo c :
 
- chercher les declarations de tt les objets de types Vector<T,S>
- chercher les expressions utilisant ces variables
- les reecrire.

Reply

Marsh Posté le 09-06-2003 à 00:17:07    

ben quand t'auras résolu le problème, tu donneras un petit exemple?

Reply

Marsh Posté le 09-06-2003 à 11:29:30    

D'ou ma question ... mieux vau t il utiliser LEX/YACC ou existe il un outil plus adapté ...

Reply

Marsh Posté le 09-06-2003 à 11:47:11    

Reply

Marsh Posté le 09-06-2003 à 11:49:13    

hooo mais c'est que ca m'a l'air tres tres interresant tout ca :D
mertci du lien, je viendrais au nouvelles :P
 
Question subsidiaires au utilisateurs d'AltiVec ...
quel genre d'algos ecrivez vous avec cette fabuleuse extension ??
DSp traitement d'image ? calcul arithmetique ? autres ?


Message édité par Joel F le 09-06-2003 à 11:49:41
Reply

Marsh Posté le 10-06-2003 à 11:13:56    

Bon ben Spirit ca roxx , j'ai deja reussi a faire un lexer pour mon code, a pu qu'a traiter tous ces tokens proprement  :whistle:  
 
Juste un mot : Boost ca roxx [:alphat]

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed