Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1556 connectés 

 
 


 Mot :   Pseudo :  
 
 Page :   1  2  3
Page Suivante
Page Précédente
Bas de page 
Auteur Sujet :

Calcul sur une matrice, optimisation ?

n°872179
Taz
bisounours-codeur
Posté le 13-10-2004 à 10:29:28  profilanswer
 

Reprise du message précédent :

Joel F a écrit :

mon code :
 

Code :
  1. int f(int i) { return 2*i; }
  3. #define N 10000
  4. int j[N];



tu peux pas faire comme tout le monde ? si je te file du code, c'est justement pour qu'on compare ...

mood
Publicité
Posté le 13-10-2004 à 10:29:28  profilanswer
 

n°872182
pains-aux-​raisins
Fatal error
Posté le 13-10-2004 à 10:32:58  profilanswer
 

Code :
  1. int j,i;
  2. for (i=0; i<MAX; ++i) { rowsums[i] = 0; }
  3. for (i=0; i<MAX; ++i) {
  4.    colsums[i] = 0;
  5.    for(j=0; j<MAX; j++) {
  6.       colsums[i] += x[j][i];
  7.       rowsums[j] += x[j][i];
  8.    }
  9. }


:o


Message édité par pains-aux-raisins le 13-10-2004 à 10:33:25
n°872186
Taz
bisounours-codeur
Posté le 13-10-2004 à 10:36:03  profilanswer
 

# colsums[i] += x[j][i];
#       rowsums[j] += x[j][i];
 
 
ça c'est franchement génial, sauf que c'est exactement un cas où l'abstraction fuit ... n'est-ce pas Joel (On Software :o)

n°872189
pains-aux-​raisins
Fatal error
Posté le 13-10-2004 à 10:38:09  profilanswer
 

désolé, j'ai pas votre niveau en optimisation de code :sleep:

n°872190
Taz
bisounours-codeur
Posté le 13-10-2004 à 10:40:11  profilanswer
 

non, mais tu peux te rendre compte que lors du parcours par colonne plutot que par ligne d'une matrice, la distance entre les données de deux itérations est __très__ grande. bref ça fait péter tout le cache. pour rien.

n°872191
Lam's
Profil: bas.
Posté le 13-10-2004 à 10:42:31  profilanswer
 

Taz, tu es méchant, parce que pains-aux-raisins avait fait un "+1" sur ma remarque du parcours par colonne.
 
Le code qu'il vient de poster n'est qu'une "correction" de la pseudo-version du prof (qui est donc celui qui a décidé de parcourir par colonne).


Message édité par Lam's le 13-10-2004 à 10:43:12
n°872193
Taz
bisounours-codeur
Posté le 13-10-2004 à 10:47:04  profilanswer
 

mais je suis pas méchant ...

n°872196
pains-aux-​raisins
Fatal error
Posté le 13-10-2004 à 11:00:43  profilanswer
 

Y a pas de souci...

n°872217
xiluoc
un pc pour les unirs ....
Posté le 13-10-2004 à 11:24:21  profilanswer
 

j ai envoye un link cest pas une pseudo version...

n°872219
pains-aux-​raisins
Fatal error
Posté le 13-10-2004 à 11:26:44  profilanswer
 

tu veux nous dire que ton prof est nul ? :whistle:

mood
Publicité
Posté le 13-10-2004 à 11:26:44  profilanswer
 

n°872227
xiluoc
un pc pour les unirs ....
Posté le 13-10-2004 à 11:50:35  profilanswer
 

si ca vous fais plaisir.
http://www.comp.mq.edu.au/~len/

n°872229
pains-aux-​raisins
Fatal error
Posté le 13-10-2004 à 11:57:45  profilanswer
 

Je pige pas tout ; c'est le même mec d'où tu tires ton programme ?

n°872230
Lam's
Profil: bas.
Posté le 13-10-2004 à 11:58:26  profilanswer
 

Ah merde, le lien que tu as donné ne marchait pas à la maison. Je viens de le lire, et je me rend compte que tout est dit là:
http://www.comp.mq.edu.au/units/co [...] .hamey.pdf
 
Le fait que tu n'ait pas compris nos multiples allusions au déroullage de boucle et à l'ordre d'accès de la mémoire (vis à vis du cache) me montre que tu ne l'as probablement pas lu, ou du moins pas compris.  
 
Je te conseille donc vivement de te replonger dans ton cours (c'est très rare les profs qui donnent les exos sans avoir donner le cours avant), et je te conseille de relire le PDF à tête reposée, avec un grand diet coke bien frais... Si tu as des problèmes, tes collègues devraient être capables de t'aider, avec une bien meilleurs connaissance du contexte.
 

n°872235
pains-aux-​raisins
Fatal error
Posté le 13-10-2004 à 12:02:12  profilanswer
 

Lam's a écrit :

Ah merde, le lien que tu as donné ne marchait pas à la maison. Je viens de le lire, et je me rend compte que tout est dit là:
http://www.comp.mq.edu.au/units/co [...] .hamey.pdf


miam ! ça m'a l'air très bon ça :)

n°872240
xiluoc
un pc pour les unirs ....
Posté le 13-10-2004 à 12:07:07  profilanswer
 

Bon j avoue je l'avais lut en survolant, j y retourne.

n°872242
Taz
bisounours-codeur
Posté le 13-10-2004 à 12:08:31  profilanswer
 

par contre vive le C++ et le template, comme l'indique la date du document, ce genre d'optimisation à la main, c'est d'un autre temps
 
edit: par contre faut bien voir que ses exemples, sur CISC ça va tout de suite moins bien marcher


Message édité par Taz le 13-10-2004 à 12:09:21
n°872243
Lam's
Profil: bas.
Posté le 13-10-2004 à 12:08:52  profilanswer
 

pains-aux-raisins a écrit :

miam ! ça m'a l'air très bon ça :)


Il est pas mal effectivement.
 
Puis-je te conseiller de le lire après avoir lu ça d'abord:
http://webster.cs.ucr.edu/AoA/Wind [...] urea2.html
 
Ca t'expliquera ce qu'est un 4-way associative cache en douceur...

n°872245
Lam's
Profil: bas.
Posté le 13-10-2004 à 12:11:16  profilanswer
 

xiluoc a écrit :

Bon j avoue je l'avais lut en survolant, j y retourne.


Mort de rire.  
 
Taz, tu peux nous expliquer ça veut dire quoi const, size_t et namespace ?  
 
J'ai pas trop compris en lisant le Stroustrup en survolant...

n°872246
xiluoc
un pc pour les unirs ....
Posté le 13-10-2004 à 12:11:25  profilanswer
 

Sympa j ai un peut de mal entre le set associative cache , l associative mapped cache et direct maped cache.


Message édité par xiluoc le 13-10-2004 à 12:12:11
n°872254
Taz
bisounours-codeur
Posté le 13-10-2004 à 12:15:41  profilanswer
 

Lam's a écrit :


 
Taz, tu peux nous expliquer ça veut dire quoi const, size_t et namespace ?  
 
J'ai pas trop compris en lisant le Stroustrup en survolant...

même pas drôle  :sweat:
 
(d'autant plus que size_t et const c'est du C :/)


Message édité par Taz le 13-10-2004 à 12:16:05
n°872324
Joel F
Real men use unique_ptr
Posté le 13-10-2004 à 13:37:57  profilanswer
 

Taz :
ton code me genere aucune boucle ni aucune evaluation cr f est vide ...
j'ai bien etait obligé d'y mettre du code [:dawa]

n°872383
Taz
bisounours-codeur
Posté le 13-10-2004 à 14:17:04  profilanswer
 

Joel F a écrit :

Taz :
ton code me genere aucune boucle ni aucune evaluation cr f est vide ...
j'ai bien etait obligé d'y mettre du code [:dawa]

mais n'importe quoi !
 
void f(int);
 
ça veut pas dire que f est vide !
 
tu prends mon truc, tu fais gcc -O3 -S dawa.c :o

n°872393
xiluoc
un pc pour les unirs ....
Posté le 13-10-2004 à 14:25:59  profilanswer
 

3  ms =)
 
4 way associative, 32 byte per cache line
8 words a la fois.
 
Dans le document ils parlent aussi d aliasing, qui permet d eviter de loader deux fois le meme chifre.
je pense a ce cas par exemple

Code :
  1. rowsums[r]+= x[r][c] + x[r][c+1] + ...
  2. colsums[c]+= x[r][c];
  3. .
  4. .
  5. .


je dois creer des pointeurs ?
d autre modifs possible pour optimiser ?

Code :
  1. void sums_fast (int x[MAX][MAX], int colsums[MAX], int rowsums[MAX])
  2. {
  3.   int n;
  5.   for(n=0; n<MAX;n+=8)
  6.   {
  7.    colsums[n] = 0;
  8.    colsums[n+1] = 0;
  9.    colsums[n+2] = 0;
  10.    colsums[n+3] = 0;
  11.    colsums[n+4] = 0;
  12.    colsums[n+5] = 0;
  13.    colsums[n+6] = 0;
  14.    colsums[n+7] = 0;
  15.   }
  16.  
  17.   for(n=0; n<MAX;n+=8)
  18.   {
  19.    rowsums[n] = 0;
  20.    rowsums[n+1] = 0;
  21.    rowsums[n+2] = 0;
  22.    rowsums[n+3] = 0;
  23.    rowsums[n+4] = 0;
  24.    rowsums[n+5] = 0;
  25.    rowsums[n+6] = 0;
  26.    rowsums[n+7] = 0;
  27.   } 
  31. int c,r;
  32. for (r=0; r<MAX;r++)
  33. {
  34.   for(c=0; c<MAX;c+=8)
  35.   {
  36.    rowsums[r]+= x[r][c] + x[r][c+1] + x[r][c+2] + x[r][c+3] + x[r][c+4] + x[r][c+5] + x[r][c+6] + x[r][c+7];
  37.    colsums[c]+= x[r][c];
  38.    colsums[c+1]+= x[r][c+1];
  39.    colsums[c+2]+= x[r][c+2];
  40.    colsums[c+3]+= x[r][c+3];
  41.    colsums[c+4]+= x[r][c+4];
  42.    colsums[c+5]+= x[r][c+5];
  43.    colsums[c+6]+= x[r][c+6];
  44.    colsums[c+7]+= x[r][c+7]; 
  45.   }
  46. }

n°872397
Lam's
Profil: bas.
Posté le 13-10-2004 à 14:29:57  profilanswer
 

Non. Il y a toujours plein de cache-misses. Demandes toi: quand x[r][c] est dans le cache, quoi d'autre y est ?
 

n°872398
xiluoc
un pc pour les unirs ....
Posté le 13-10-2004 à 14:34:02  profilanswer
 

quand x[r][c] est dans le cache les 7 autres x[r][c+1...7] y sont. donc j en profite pour additioner la ligne (row) et rajouter un morceau a la somme de chaque colone concerne.
la je vois pas :/

n°872407
Joel F
Real men use unique_ptr
Posté le 13-10-2004 à 14:43:08  profilanswer
 

Taz a écrit :

mais n'importe quoi !
 
void f(int);
 
ça veut pas dire que f est vide !
 
tu prends mon truc, tu fais gcc -O3 -S dawa.c :o


 

Code :
  1. __Z1gv:
  2. LFB5:
  3. mflr r2
  4. stmw r29,-12(r1)
  5. LCFI0:
  6. stw r2,8(r1)
  7. LCFI1:
  8. li r30,0
  9. stwu r1,-80(r1)
  10. LCFI2:
  11. L6:
  12. slwi r29,r30,2
  13. mr r3,r29
  14. bl L__Z1fi$stub
  15. addi r3,r29,1
  16. bl L__Z1fi$stub
  17. addi r3,r29,2
  18. bl L__Z1fi$stub
  19. addi r30,r30,1
  20. addi r3,r29,3
  21. bl L__Z1fi$stub
  22. cmpwi cr0,r30,24
  23. ble+ cr0,L6
  24. lwz r2,88(r1)
  25. addi r1,r1,80
  26. lmw r29,-12(r1)
  27. mtlr r2
  28. blr
  29. LFE5:
  30. .align 2
  31. .globl __Z1hv
  32. .section __TEXT,__text,regular,pure_instructions
  33. .align 2
  34. __Z1hv:
  35. LFB6:
  36. mflr r2
  37. stmw r30,-8(r1)
  38. LCFI3:
  39. stw r2,8(r1)
  40. LCFI4:
  41. li r30,0
  42. stwu r1,-80(r1)
  43. LCFI5:
  44. L14:
  45. mr r3,r30
  46. bl L__Z1fi$stub
  47. addi r3,r30,1
  48. bl L__Z1fi$stub
  49. addi r3,r30,2
  50. bl L__Z1fi$stub
  51. addi r3,r30,3
  52. addi r30,r30,4
  53. bl L__Z1fi$stub
  54. cmpwi cr0,r30,99
  55. ble+ cr0,L14
  56. lwz r2,88(r1)
  57. addi r1,r1,80
  58. lmw r30,-8(r1)
  59. mtlr r2
  60. blr

n°872408
Lam's
Profil: bas.
Posté le 13-10-2004 à 14:43:36  profilanswer
 

Pardon, j'avais mal lu. Oui, c'est correct.
 
edit:  
1. utilise memset pour initialiser rowsums et colsums (la fonction est généralement optimisée pour ça)
 
2. essaye de faire plusieurs lignes en même temps, ça devrait marcher un chouia plus vite...


Message édité par Lam's le 13-10-2004 à 14:51:27
n°872413
xiluoc
un pc pour les unirs ....
Posté le 13-10-2004 à 14:50:46  profilanswer
 

A default de trouver mon ereur il y a t il des outils sous linux me permetant de visualiser les miss et hit de mon prog sur le cache ?

n°872467
xiluoc
un pc pour les unirs ....
Posté le 13-10-2004 à 15:42:48  profilanswer
 

up

n°872532
Taz
bisounours-codeur
Posté le 13-10-2004 à 17:11:48  profilanswer
 

JoelF > ben c'est la même chose alors que j'ai. Donc la version avec addition est meilleure

n°872609
Joel F
Real men use unique_ptr
Posté le 13-10-2004 à 19:12:16  profilanswer
 

Taz a écrit :

JoelF > ben c'est la même chose alors que j'ai. Donc la version avec addition est meilleure


 
ok ^^ je vais corriger mes sources :o

n°872611
Taz
bisounours-codeur
Posté le 13-10-2004 à 19:13:21  profilanswer
 

merkiki ?

n°872620
Joel F
Real men use unique_ptr
Posté le 13-10-2004 à 19:25:25  profilanswer
 

merki tazounet :bisou:

n°872626
skeye
Posté le 13-10-2004 à 19:47:17  profilanswer
 

(et si je vous en file de jolies boucles avec des calculs sur des matrices dedans vous me dites comment les améliorer aussi? [:opus dei])


---------------
Can't buy what I want because it's free -
n°872637
Joel F
Real men use unique_ptr
Posté le 13-10-2004 à 19:59:07  profilanswer
 

toute facon, hors du SIMD point de salut
 
AltiVec pwn

n°872640
Taz
bisounours-codeur
Posté le 13-10-2004 à 20:02:24  profilanswer
 

le truc c'est surtout que sur une architecture qui crie famine niveau registre, il faudrait pas se permettre de gacher bêtement des registres. L'assembleur, c'est pas terrible. Quand on voit le vrai code de JoelF, ça debient déjà chiant. Mais si on prend le temps d'étudier quelques structures, ça devient basique. Et ça paie :D
 
Il me fait bien marré le PDF de l'autre : il est bien. Mais quant il explique qu'il faut utiliser des scalaires pour favoriser les registres, il en déclare une bonne vingtaine :D

n°872646
skeye
Posté le 13-10-2004 à 20:04:35  profilanswer
 

Taz a écrit :

le truc c'est surtout que sur une architecture qui crie famine niveau registre, il faudrait pas se permettre de gacher bêtement des registres. L'assembleur, c'est pas terrible. Quand on voit le vrai code de JoelF, ça debient déjà chiant. Mais si on prend le temps d'étudier quelques structures, ça devient basique. Et ça paie :D
 
Il me fait bien marré le PDF de l'autre : il est bien. Mais quant il explique qu'il faut utiliser des scalaires pour favoriser les registres, il en déclare une bonne vingtaine :D


J'ai testé sur 1 ou 2 boucles le coup des scalaires (sur intel) pour rigoler, je perds moins que je pensais finalement... :whistle:


---------------
Can't buy what I want because it's free -
n°872659
Lam's
Profil: bas.
Posté le 13-10-2004 à 20:14:22  profilanswer
 

skeye a écrit :

J'ai testé sur 1 ou 2 boucles le coup des scalaires (sur intel) pour rigoler, je perds moins que je pensais finalement... :whistle:


Par curiosité, quel compilo, quel processeur ?  

n°872661
skeye
Posté le 13-10-2004 à 20:15:45  profilanswer
 

Lam's a écrit :

Par curiosité, quel compilo, quel processeur ?


Dev-cpp jesaispluquelleversion, sur un pentium 4.
Compilé avec les flags -O2 -march...


---------------
Can't buy what I want because it's free -
n°872663
Joel F
Real men use unique_ptr
Posté le 13-10-2004 à 20:17:10  profilanswer
 

Taz a écrit :


Quand on voit le vrai code de JoelF, ça debient déjà chiant.  


 
quel vrai code ?

n°872664
Joel F
Real men use unique_ptr
Posté le 13-10-2004 à 20:19:38  profilanswer
 

Taz a écrit :


ça c'est franchement génial, sauf que c'est exactement un cas où l'abstraction fuit ... n'est-ce pas Joel (On Software :o)


 
???

mood
Publicité
Posté le   profilanswer
 

 Page :   1  2  3
Page Suivante
Page Précédente
Haut de page 

Aller à :
Ajouter une réponse
 

Sujets relatifs
fonction html : listbox optimisation?[devcpp] options d'optimisation ne change rien
Calcul de différence entre deux dates[algo] inversion d'une matrice, cas "particulier"
Optimisation traitement d'imagesCalcul sur HH:MM:SS et centièmes de secondes
Valeur nulle et optimisationMatrice 3x10
[PHP - MYSQL] optimisation d'une requete[vba]Optimisation du code pour la rapidité (résolu)
Plus de sujets relatifs à : Calcul sur une matrice, optimisation ?

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.104 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR