Calcul sur une matrice, optimisation ?

Calcul sur une matrice, optimisation ? - C - Programmation

Marsh Posté le 12-10-2004 à 15:09:49    

:hello: ,
J ai une matrice de [512]*[512],
je dois calculer la somme de chaque colone et ligne de la matrice.
 

Code :
  1. void sums_slow (int x[MAX][MAX], int colsums[MAX], int rowsums[MAX])
  2. {
  3. }


en sauvant le resultat de chaque operation dans colsums[n] ou rowsums[m].
 
Il y a t-il une methode/algo plus rapide que ce genre de chose

Code :
  1. {
  2. int j,i;
  3. int colsum = 0;
  5. for (i=0; i<MAX; i++)
  6. {
  7.  int temp = 0;
  8.  for (j=0; j<MAX; j++)
  9.  {
  10.   temp += x[j][i];  //x[0],[j]  row  x[j][0] column
  11.   //printf ("%d \n", x[0][j]);
  13.  }
  14.  //printf ("%d \n", temp);  
  15.  colsums[i] = temp;
  16. }
  17. //printf ("\n" );
  18. for (i=0; i<MAX; i++)
  19. {
  20.  int temp = 0;
  21.  for (j=0; j<MAX; j++)
  22.  {
  23.   temp += x[i][j];
  24.   //printf ("%d \n", x[0][j]);
  25.  }
  26.  //printf ("%d \n", temp);  
  27.  rowsums[i] = temp;
  28. }
  29. }


 
merci  [:alarmclock119]  

Reply

Marsh Posté le 12-10-2004 à 15:09:49   

Reply

Marsh Posté le 12-10-2004 à 15:21:07    

ta pile te dit merci

Reply

Marsh Posté le 12-10-2004 à 15:30:51    

quand tu calcul la somme d'une colonne, pour respecter l'ordre de ton code, tu peux en profiter pour ajouter la valeur courante à la ligne correspondante.
 
=> une seule boucle au lieu de 2.

Reply

Marsh Posté le 12-10-2004 à 15:31:05    

pour faire un peu plus rapide (mais surement encore optimisable, tu peux utiliser 2 iterateurs.
l'un commence au debut de ta ligne, l'autre a la fin (idem si c'est des colonne)  
Et tu les fais aller, simultanément pour qu'ils se rejoingne a MAX/2
T'as plus qu'a additioner les 2 valeurs recupéré par tour de boucle.
Ya surement mieux, mais cette amélioration divise quand meme par deux le temps de calcul.

Reply

Marsh Posté le 12-10-2004 à 15:32:14    

oui, un seul parcour suffit
 
un truc dans ce genre la
 
...
colsums[i] = 0;
rowsums[i] = 0;
for( j = 0; j < MAX; j++ )  
{  
    colsums[i] += x[j][i];  
    rowsums[i] += x[i][j];  
}  
...

Reply

Marsh Posté le 12-10-2004 à 15:32:15    

c0wb0y a écrit :

pour faire un peu plus rapide (mais surement encore optimisable, tu peux utiliser 2 iterateurs.
l'un commence au debut de ta ligne, l'autre a la fin (idem si c'est des colonne)  
Et tu les fais aller, simultanément pour qu'ils se rejoingne a MAX/2
T'as plus qu'a additioner les 2 valeurs recupéré par tour de boucle.
Ya surement mieux, mais cette amélioration divise quand meme par deux le temps de calcul.


Non.

Reply

Marsh Posté le 12-10-2004 à 15:33:17    

hu ?
Je ne comprends pas pourquoi c'est incorrect =/

Reply

Marsh Posté le 12-10-2004 à 15:35:41    

cris56 a écrit :

oui, un seul parcour suffit
 
un truc dans ce genre la
 
...
colsums[i] = 0;
rowsums[i] = 0;
for( j = 0; j < MAX; j++ )  
{  
    colsums[i] += x[j][i];  
    rowsums[i] += x[i][j];  
}  
...


 
Il y a du mieux, mais tu continues à faire 2 accès aléatoires pour chaque case visitée.  Si tu fais:
   rowsums[j] += x[j][i];
 
Ca a plus de gueule, car rowsums a plus de chance d'être en cache (il ne fait que 512 cases, contre 262144 pour la matrice x), et tu n'accèdes qu'une fois à chaque case de ta matrice (en fait, 2, mais le compilateur l'optimisera).
 

Reply

Marsh Posté le 12-10-2004 à 15:38:04    

cris56 a écrit :

oui, un seul parcour suffit
 
un truc dans ce genre la
 
...
colsums[i] = 0;
rowsums[i] = 0;
for( j = 0; j < MAX; j++ )  
{  
    colsums[i] += x[j][i];  
    rowsums[i] += x[i][j];  
}  
...

euh la tu ferais bien de mesurer, tu risques de foutre en l'air ton cache (et si la matrice est grande, faire plein de défauts de pages). prudence donc

Reply

Marsh Posté le 12-10-2004 à 15:38:23    

Code :
  1. pour i = 1 à N  -- lignes
  2.    pour j = 1 à N  -- colonnes
  3.       rowsum[i] += x[i][j]
  4.       colsum[j] += x[i][j]
  5.    fin pour
  6. fin pour


non ?

Reply

Marsh Posté le 12-10-2004 à 15:38:23   

Reply

Marsh Posté le 12-10-2004 à 15:38:57    

( hum, si mon erreur était par rapport au "temps de calcul divisé par deux" alors j'ai compris, j'ai dis n'importequoi en fait (: ya autant de calcul, c'est juste la longueur des parcours qui est réduite, m'enfin on doit y gagner un peu qd meme je pense )
Si c'était pas par rapport a ca, alors j'vois pas  :??:

Reply

Marsh Posté le 12-10-2004 à 15:39:44    

Lam's a écrit :


rowsums[j] += x[j][i];
 


 
tout a fais, j'y avais meme pensé mais la je m'etais d'abord servi du fait que la matrice etais carré, si elle ne l'etais pas ta solution s'imposait d'elle meme
 
merci
 
edit : taz > oue, je viens de voir


Message édité par cris56 le 12-10-2004 à 15:41:44
Reply

Marsh Posté le 12-10-2004 à 15:40:27    

c0wb0y a écrit :

Si c'était pas par rapport a ca, alors j'vois pas  :??:


Vi c'était ça. Mais tu peux aussi bien simplement dérouler ta boucle, sans avoir à passer par l'arrière...
 

Reply

Marsh Posté le 12-10-2004 à 15:49:03    

( j'sais pas ce que ca veut dire derouler une boucle http://hellien.free.fr/smileys/god.gif
C'est ca quand on se limite au poly de C qu'on a en cours :] http://hellien.free.fr/smileys/mad_overclocker.gif)

Reply

Marsh Posté le 12-10-2004 à 15:55:05    

loop unrolling en anglais. A mon avis, google a 2 ou 3 trucs à dire à ce propos ;)

Reply

Marsh Posté le 12-10-2004 à 23:08:20    

Merci les gas, justement cest pour nous aprendre a utiliser le cache, on doit tout dabord faire une methode la plus pourrie possible (je vais essayer de retoucher mon premier exemple), et une optimise le mieux que l on peut.
 
 le cache :
64kB, 4-way set associative, with a 32-byte cache line
 
je vais esseyer plusieurs methode et poster les temps.
 
 
 

Reply

Marsh Posté le 12-10-2004 à 23:21:31    

for(i=0;i<SIZE;i++) truc(i);
 
=>
 
for(i=0;i<SIZE/4;i++)
{
  truc(4*i);
  truc(4*i+1);
  truc(4*i+2);
  truc(4*i+3);
}
 
poru i < 300 a peu pres, vitesse x2 a x3 sur du Pentium, x4-5 sur du PPC

Reply

Marsh Posté le 12-10-2004 à 23:31:22    

t'as déjà essayé avec les __builtins de prefetch de gcc ?
 
 
bah bah bah, faut pas faire comme ça, faut faire avec i < SIZE; i += 4; tu dois au moins sauver 2/3 instructions avec ça :D

Reply

Marsh Posté le 12-10-2004 à 23:34:32    

Taz a écrit :


bah bah bah, faut pas faire comme ça, faut faire avec i < SIZE; i += 4; tu dois au moins sauver 2/3 instructions avec ça :D


 
bizzarement non :| et au moins avec ma version je ne me chie pas dednas ^^

Reply

Marsh Posté le 12-10-2004 à 23:44:26    

je te parle de traiter les quelques éléments qui restent si SIZE % 4 != 0
 
avec gcc3.3 (et 3.4), j'ai un registre de plus utilisé pour stocker le i * 4

Reply

Marsh Posté le 12-10-2004 à 23:46:25    

si SIZE%4 evidemment ^^
 
sous gcc 3.3 Apple j'ai pas ce registre en plus.

Reply

Marsh Posté le 12-10-2004 à 23:49:25    

Code :
  1. void f(int);
  3. #ifdef JOELF
  5. void g()
  6. {
  7.   const int N = 100;
  8.   int i;
  10.   for(i = 0; i < N / 4; ++i)
  11.     {
  12.       f(4 * i);
  13.       f(4 * i + 1);
  14.       f(4 * i + 2);
  15.       f(4 * i + 3);
  16.     }
  17. }
  19. #else
  21. void g()
  22. {
  23.   const int N = 100;
  24.   int i;
  26.   for(i = 0; i < N; i += 4)
  27.     {
  28.       f(i);
  29.       f(i + 1);
  30.       f(i + 2);
  31.       f(i + 3);
  32.     }
  33. }
  35. #endif // JOELF


 
en gcc -O3 -S ça te donne quoi respectivement ?


Message édité par Taz le 12-10-2004 à 23:49:50
Reply

Marsh Posté le 13-10-2004 à 01:13:29    

la matrice est de [512*512] donc multiple de 4.
voila different methodes plus leur temps.
compiler avec cc -O
bi proc ultra sparc
 
methode du premier post : 8.29 ms
seconde methode

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


11,90 ms     [:dams86]  
 
Pour celle qui utilise le 4 way associative cache,  
truc(i) est censez faire quoi ?

Reply

Marsh Posté le 13-10-2004 à 01:44:44    

déjà si tu veux faire un benchmark, il faut que ton processus tourne au moins une minute et que tu prennes un temps moyen sur au moins 3 exécutions consécutives

Reply

Marsh Posté le 13-10-2004 à 02:08:38    

j ai utilise le prog donne par le prof. :/
lequel servira amesurer nos algo.

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


 
8,77 ms
 
je comprend pas trop l exemple pour le 4 way cache assiociative, pouriez vous develope un peu ?
merci  
 :jap:


Message édité par xiluoc le 13-10-2004 à 02:29:34
Reply

Marsh Posté le 13-10-2004 à 09:19:00    

fait des vrais mesures ! tu peux pas conclure sur des durées aussi ridicules.

Reply

Marsh Posté le 13-10-2004 à 09:33:30    

Taz a écrit :


en gcc -O3 -S ça te donne quoi respectivement ?


-- truc effacé paske faux


Message édité par Joel F le 13-10-2004 à 20:18:39
Reply

Marsh Posté le 13-10-2004 à 09:50:17    

Pour la version la plus lente possible, jacced au column et row de la matrice 8 par 8 (32 byte line, 4 way associative il load 8 word a chaque fois) pour avoir un maximum de miss.
grace a ca je tombe a 14.8 m/s, c est yune moyenne apres plusieurs test.
Taz tu peus aller verifier : http://www.comp.mq.edu.au/units/co [...] nts/3.html
 
J aimerai savoir si il existe es outils montrant le nombre de miss sur le cache ? de facon a savoir ou sa coince.
 
Pourais je avoir plus dexplication sur :

Code :
  1. for(i=0;i<SIZE;i++) truc(i);
  3. =>
  5. for(i=0;i<SIZE/4;i++)
  6. {
  7.   truc(4*i);
  8.   truc(4*i+1);
  9.   truc(4*i+2);
  10.   truc(4*i+3);
  11. }


 

Reply

Marsh Posté le 13-10-2004 à 09:52:32    

Code :
  1. // JOELF
  2. g:
  3. stwu 1,-32(1)
  4. mflr 3
  5. stw 29,20(1)
  6. stw 3,36(1)
  7. stw 31,28(1)
  8. li 31,0
  9. .L6:
  10. slwi 29,31,2
  11. addi 31,31,1
  12. mr 3,29
  13. bl f
  14. addi 3,29,1
  15. bl f
  16. addi 3,29,2
  17. bl f
  18. addi 0,29,3
  19. mr 3,0
  20. bl f
  21. cmpwi 0,31,24
  22. ble+ 0,.L6
  23. lwz 3,36(1)
  24. lwz 29,20(1)
  25. lwz 31,28(1)
  26. mtlr 3
  27. addi 1,1,32
  28. blr


 
 

Code :
  1. // sans JOELF
  2. g:
  3. stwu 1,-32(1)
  4. mflr 3
  5. stw 3,36(1)
  6. stw 31,28(1)
  7. li 31,0
  8. .L6:
  9. mr 3,31
  10. bl f
  11. addi 3,31,1
  12. bl f
  13. addi 3,31,2
  14. bl f
  15. addi 3,31,3
  16. addi 31,31,4
  17. bl f
  18. cmpwi 0,31,99
  19. ble+ 0,.L6
  20. lwz 3,36(1)
  21. lwz 31,28(1)
  22. addi 1,1,32
  23. mtlr 3
  24. blr

Reply

Marsh Posté le 13-10-2004 à 09:53:50    

moi je veux savoir comment tu peux tirer des conclusions sur des laps de temps aussi ridicule ?

Reply

Marsh Posté le 13-10-2004 à 09:55:34    

comme ca

Code :
  1. /* dotest.c: Speed test module for COMP226 Assignment 3
  2. *  2004.  Copyright Leonard G C Hamey 2001-2004.  All rights reserved.
  3. * This program may only be used by COMP226 students at Macquarie
  4. * University for the purposes of developing their solution to
  5. * assignment 3.
  6. *
  7. * This is the source code version from which I compiled the object module
  8. * for the students to test their programs with.
  9. */
  11. # include "dotest.h"
  13. # if DOALIGN
  14. DATAITEM memory[NR*NC*3*MAXTEST+GAP*3*MAXTEST+ALIGN];
  15. # else
  16. DATAITEM mem[NR*NC*3*MAXTEST+GAP*3*MAXTEST];
  17. # endif
  18. DATAITEM *xp[MAXTEST], *yp[MAXTEST], *zp[MAXTEST];
  19. int xim[MAXM] = { 1, 3, 1, 3, 2, -1, 2, -1, 5, 3, 5, 3 };
  20. int xjm[MAXM] = { -1, 1, 3, -1, -1, 2, 1, -3, -1, 1, 3, -1};
  21. int yim[MAXM] = { 1, 2, 3, 4, -1, -2, -3, -4, 3, 2, 1, 4 };
  22. int yjm[MAXM] = { -3, -5, 7, 2, 8, 4, 5, 3, -3, -5, -7, 2 };
  23. int zim[MAXM] = { 0, 1, 2, 0, -1, -2, 0, 1, 2, 0, -1, -2 };
  24. int zjm[MAXM] = { 0, 0, 1, 1, 2, 2, -2, -2, -1, -1, 0, 0 };
  28. /* Routines to implement a simple timer mechanism. */
  30. # include <sys/time.h>
  31. # include <sys/timeb.h>
  32. # include <sys/resource.h>
  34. /* Static data structures used by abstract object timer. */
  36. static struct timeb wall_on, wall_off;
  37. static struct rusage user_on, user_off;
  38. static long int wall = 0L, user = 0L;
  40. /* Timer on: Start timing program execution */
  42. void timer_on ()
  43. { ftime (&wall_on);
  44.   getrusage (RUSAGE_SELF, &user_on);
  45. }
  47. /* Timer off: Stop timing program execution
  48. * Current time interval is added to accumulated time.
  49. */
  51. void timer_off ()
  52. { getrusage (RUSAGE_SELF, &user_off);
  53.   ftime (&wall_off);
  54.   wall += (wall_off.time - wall_on.time) * 1000 +
  55.       wall_off.millitm - wall_on.millitm;
  56.   user += (user_off.ru_utime.tv_sec - user_on.ru_utime.tv_sec) *
  57.       1000 + (user_off.ru_utime.tv_usec -
  58.       user_on.ru_utime.tv_usec) / 1000;
  59. }
  61. /* Timer display: Prints the current accumulated time */
  63. void timer_display (FILE *out)
  64. { fprintf (out, "wall %d.%03d  user %d.%03d\n",
  65.       wall/1000, wall % 1000, user / 1000, user % 1000);
  66. }
  68. /* timer_user_ms: Returns user CPU time in ms currently accumulated */
  70. int timer_user_ms ()
  71. { return user;
  72. }
  74. /* timer_wall_ms: Returns wall clock (true elapsed) time accumulated */
  76. int timer_wall_ms ()
  77. { return wall;
  78. }
  80. /* timer_reset: Reset timer accumulators to zero. */
  82. void timer_reset ()
  83. { wall = user = 0;
  84. }
  87. int timer_begin ()
  88. {
  89.   timer_reset ();
  90.   timer_on ();
  91. }
  93. int timer_end ()
  94. {
  95.   timer_off ();
  96.   /* timer_display (stdout); */
  97.   return user;
  98. }
  101. /* -------------------------------------------------------------- */
  104. /* The rest of this program does the timing */
  106. float exec_test (void (*op)(), int ntests, int is_test1);
  108. float do_test (char *name, void (*op)(), int is_test1)
  109. {
  110.   float time;
  111.   int ntests;
  113.   fprintf (stderr, "do_test version 3.0\n" );
  114.   fprintf (stderr, "Testing your %s operator %s\n", is_test1 ? TEST1 : TEST0, name);
  116.   alarm (15);
  118.   /* First test 3 times to estimate how many tests required for
  119.    * sufficient accuracy of measurement */
  120.   time = exec_test (op, 0, is_test1);
  121. # ifdef VERBOSE
  122.     printf ("[3]: %.5f\n", time);
  123. # endif
  125.   if (time < -0.5)
  126.     return time;  /* Execution failure - no time data recorded */
  128.   ntests = 3;
  129.   /* The estimate of number of iterations required must be based on
  130.    * at least 0.05 seconds of data */
  131.   while (time * ntests < 0.05)
  132.   {
  133.     ntests = ntests * 10;
  134.     time = exec_test (op, ntests, is_test1);
  135. # ifdef VERBOSE
  136.       printf ("[%d]: %.5f\n", ntests, time);
  137. # endif
  138.   }
  139.  
  140.   /* Absolutely must have at least 0.75 seconds of data to base estimate
  141.    * on. */
  142.   while (time * ntests < 0.75)
  143.   {
  144.     /* Estimate number of tests required for 1.2 second of data */
  145.     ntests = (int) (1.2 / time) + 1;
  146.     if (ntests > MAXTEST)
  147.       ntests = (ntests + MAXTEST - 1) / MAXTEST * MAXTEST;
  148.     time = exec_test (op, ntests, is_test1);
  149.   }
  150.    
  151. # if TIMEONLY
  152.   printf ("%8.2f", time*1000.0);
  153. # else
  154.   printf ("%s: %.2fms/operation (executed %d times)\n", name, time * 1000.0, ntests);
  155. # endif
  156.   return time * 1000.0;
  157. }
  161. void initialise (DATAITEM x[NR][NC], DATAITEM y[NR][NC], DATAITEM z[NR][NC],
  162.     int xim, int xjm, int yim, int yjm, int zim, int zjm)
  163. {
  164.   int i, j;
  166.   for (i = 0; i < NR; i++)
  167.     for (j = 0; j < NC; j++)
  168.     {
  169.       if (x != NULL)
  170.         x[i][j] = FORMULAX;
  171.       if (y != NULL)
  172.         y[i][j] = FORMULAY;
  173.       if (z != NULL)
  174.         z[i][j] = FORMULAZ;
  175.     }
  176. }
  179. float exec_test (void (*op)(), int ntests, int is_test1)
  180. {
  181.   RETURN_TYPE0 (*op0)() = 0;
  182.   RETURN_TYPE1 (*op1)() = 0;
  183. # if RETURN0
  184.     RETURN_TYPE0 result0[MAXTEST];
  185. # else
  186.     char result0[1];
  187. # endif
  188. # if RETURN1
  189.     RETURN_TYPE1 result1[MAXTEST];
  190. # else
  191.     char result1[1];
  192. # endif
  193.   int i, j;
  194.   int nrun, utime, check_correctness;
  195. # if DOALIGN
  196.   DATAITEM *mem;
  197. # endif
  198.   DATAITEM *x, *y, *z;
  200.   check_correctness = ntests == 0;
  201.   if (ntests == 0)
  202.     ntests = 5;  /* Initial test to estimate time required for testing */
  204.   /* Determine how many tests to run */
  205.   nrun = ntests;
  206.   if (nrun > MAXTEST)
  207.     nrun = MAXTEST;
  209. # if DOALIGN
  210.   /* Align memory array mem to multiple of ALIGN bytes which must be a power of 2 */
  211.   mem = memory + ALIGN;
  212.   mem = (DATAITEM *) ((int) (mem) & ~(ALIGN-1));
  213. # endif
  214.   /* Now set up the array pointers. */
  215.   for (i = 0; i < nrun; i++)
  216.   {
  217. # if XYZ
  218.     /* x, y, z, x, y, z, x, y, z order in memory
  219.      */
  220.     xp[i] = mem + i * (NR * NC + GAP) * 3;
  221.     yp[i] = xp[i] + NR * NC + GAP;
  222.     zp[i] = yp[i] + NR * NC + GAP;
  223. # else
  224.     /* x, x, x, ..., y, y, y, ..., z, z, z, ... in memory
  225.      */
  226.     xp[i] = mem + i * (NR * NC + GAP);
  227.     yp[i] = xp[i] + (NR * NC + GAP) * MAXTEST;
  228.     zp[i] = yp[i] + (NR * NC + GAP) * MAXTEST;
  229. # endif
  230.   }
  231. # if INFO
  232.   fprintf (stderr, "xp[0] = %x  xp[1] = %x  yp[0] = %x  zp[0] = %x\n",
  233.     xp[0], xp[1], yp[0], zp[0]);
  234. # endif
  236.   /* Initialise the arrays with some data. */
  237.   fprintf (stderr, "Data initialisation..." );
  238.   for (i = 0; i < nrun; i++)
  239.   {
  240.   /* casting pointers to void * prevents compiler from complaining  
  241.    * about their eventual use as 2-D arrays */
  242.     initialise ((void *) xp[i], (void *) yp[i],
  243.          (void *) zp[i], xim[i % MAXM], xjm[i % (MAXM-1)],
  244.                 yim[i % MAXM], yjm[i % (MAXM-1)],
  245.                 zim[i % MAXM], zjm[i % (MAXM-1)]);
  246.   }
  248.   /* Perform operations */
  249.   fprintf (stderr, "Executing your routine..." );
  250.   timer_begin ();
  251.   for (i = 0; i < ntests; i++)
  252.   {
  253.     x = xp[i % MAXTEST];
  254.     y = yp[i % MAXTEST];
  255.     z = zp[i % MAXTEST];
  256.     if (is_test1)
  257. {
  258.   op1 = (RETURN_TYPE1 (*)()) op;
  259. # if RETURN0
  260.   result1[i % MAXTEST] = (*op1) (ARG1);
  261. # else
  262.       (*op1) (ARG1);
  263. # endif
  264. }
  265.     else
  266. {
  267.   op0 = (RETURN_TYPE0 (*)()) op;
  268. # if RETURN0
  269.   result0[i % MAXTEST] = (*op0) (ARG0);
  270. # else
  271.       (*op0) (ARG0);
  272. # endif
  273. }
  274.   }
  275.   utime = timer_end ();
  276.   fprintf (stderr, "Execution completed.\n" );
  278.   STAFF_PROCESSING
  280.   return ((float) (utime) / 1000.0 / ((float) ntests));
  281. }

Reply

Marsh Posté le 13-10-2004 à 09:59:04    

xiluoc a écrit :


grace a ca je tombe a 14.8 m/s, c est yune moyenne apres plusieurs test.


53 km/h. C'est une vitesse raisonnable en ville. Pourquoi veux-tu aller plus vite ?  
 
Tu as fais un google sur "loop unrolling" ou bien tu veux qu'on fasse le copier/coller pour toi ?
 
Et sinon, tu es sûr du copier/coller de la solution du prof ? Ca me parrait bizarre qu'il accède à la matrice colonne par colonne...

Reply

Marsh Posté le 13-10-2004 à 10:00:29    

comment je t'ai bien eu Joelf, le gcc de MacOSX est pourri ! tu fais à chaque fois la multiplication ! alors que moi le calcul est factorisé ! (et je parle pas de tous les load pour recharger i à chaque fois)
 
ma version fait donc du code franchement meilleur ! et mon GCC rox !


Message édité par Taz le 13-10-2004 à 10:08:56
Reply

Marsh Posté le 13-10-2004 à 10:09:45    

Lam's a écrit :

[...]Et sinon, tu es sûr du copier/coller de la solution du prof ? Ca me parrait bizarre qu'il accède à la matrice colonne par colonne...


+1
et pis

Code :
  1. rowsums[j] = 0;

hors de la boucle j ca me paraît louche.

Reply

Marsh Posté le 13-10-2004 à 10:18:59    

Taz a écrit :

comment je t'ai bien eu Joelf, le gcc de MacOSX est pourri ! tu fais à chaque fois la multiplication ! alors que moi le calcul est factorisé ! (et je parle pas de tous les load pour recharger i à chaque fois)
 
ma version fait donc du code franchement meilleur ! et mon GCC rox !


 
han, na c'est moi qui est la plus grosse :o
hmmm 2sec ...
 
j'etais pas en -o3  :sweat:  
 
ma version

Code :
  1. LCFI0:
  2. mtctr r3
  3. addi r2,r1,32
  4. .p2align 4,,15
  5. L14:
  6. stw r9,0(r2)
  7. stw r11,4(r2)
  8. addi r9,r9,8
  9. addi r11,r11,8
  10. stw r10,8(r2)
  11. stw r8,12(r2)
  12. addi r10,r10,8
  13. addi r2,r2,16
  14. addi r8,r8,8
  15. bdnz L14
  16. lwz r1,0(r1)
  17. blr


Reply

Marsh Posté le 13-10-2004 à 10:21:25    

euh je bigle ou y a pas un seul f dans ton truc ?

Reply

Marsh Posté le 13-10-2004 à 10:24:05    

ben peut etre que si ta fonction f etait pas vide, -O3 la laisserrai vivre [:autobot]
 
fiel moi exactement le code que tu utilise.

Reply

Marsh Posté le 13-10-2004 à 10:26:10    

mon code :
 

Code :
  1. int f(int i) { return 2*i; }
  3. #define N 10000
  4. int j[N];
  6. void g()
  7. {
  8. int i;
  10. for(i = 0; i < N / 4; ++i)
  11. {
  12. j[4 * i] = f(4 * i);
  13. j[4 * i+1] = f(4 * i + 1);
  14. j[4 * i+2] = f(4 * i + 2);
  15. j[4 * i+3] = f(4 * i + 3);
  16. }
  17. }
  19. void h()
  20. {
  21. int i;
  23. for(i = 0; i < N; i += 4)
  24. {
  25. j[i] = f(i);
  26. j[i+1] = f(i + 1);
  27. j[i+2] = f(i + 2);
  28. j[i+3] = f(i + 3);
  29. }
  30. }
  33. int main(int,char**)
  34. {
  35. g();
  36. h();
  37. }


 
la sortie assembleur en -O3 -mcpu=ppc-g5
 

Code :
  1. .section __TEXT,__text,regular,pure_instructions
  2. .section __TEXT,__picsymbolstub1,symbol_stubs,pure_instructions,32
  3. .globl _j
  4. .data
  5. .align 2
  6. _j:
  7. .space 40000
  8. .section __TEXT,__text,regular,pure_instructions
  9. .align 2
  10. .align 2
  11. .p2align 4,,15
  12. .globl __Z1fi
  13. .section __TEXT,__text,regular,pure_instructions
  14. .align 2
  15. __Z1fi:
  16. LFB6:
  17. slwi r3,r3,1
  18. blr
  19. LFE6:
  20. .align 2
  21. .p2align 4,,15
  22. .globl __Z1gv
  23. .section __TEXT,__text,regular,pure_instructions
  24. .align 2
  25. __Z1gv:
  26. LFB7:
  27. mflr r7
  28. bcl 20,31,"L00000000001$pb"
  29. "L00000000001$pb":
  30. li r8,6
  31. li r10,4
  32. li r11,2
  33. mflr r2
  34. mtlr r7
  35. addis r6,r2,ha16(_j-"L00000000001$pb" )
  36. li r2,0
  37. la r5,lo16(_j-"L00000000001$pb" )(r6)
  38. addis r0,r5,0x1
  39. mr r9,r5
  40. subf r4,r5,r0
  41. addi r3,r4,-25536
  42. srwi r0,r3,4
  43. mtctr r0
  44. .p2align 4,,15
  45. L14:
  46. stw r2,0(r9)
  47. stw r11,4(r9)
  48. addi r2,r2,8
  49. addi r11,r11,8
  50. stw r10,8(r9)
  51. stw r8,12(r9)
  52. addi r10,r10,8
  53. addi r9,r9,16
  54. addi r8,r8,8
  55. bdnz L14
  56. blr
  57. LFE7:
  58. .align 2
  59. .p2align 4,,15
  60. .globl __Z1hv
  61. .section __TEXT,__text,regular,pure_instructions
  62. .align 2
  63. __Z1hv:
  64. LFB8:
  65. mflr r7
  66. bcl 20,31,"L00000000002$pb"
  67. "L00000000002$pb":
  68. li r8,6
  69. li r10,4
  70. li r11,2
  71. mflr r2
  72. mtlr r7
  73. addis r6,r2,ha16(_j-"L00000000002$pb" )
  74. li r2,0
  75. la r5,lo16(_j-"L00000000002$pb" )(r6)
  76. addis r0,r5,0x1
  77. mr r9,r5
  78. subf r4,r5,r0
  79. addi r3,r4,-25524
  80. srwi r0,r3,4
  81. mtctr r0
  82. .p2align 4,,15
  83. L27:
  84. stw r2,0(r9)
  85. stw r11,4(r9)
  86. addi r2,r2,8
  87. addi r11,r11,8
  88. stw r10,8(r9)
  89. stw r8,12(r9)
  90. addi r10,r10,8
  91. addi r9,r9,16
  92. addi r8,r8,8
  93. bdnz L27
  94. blr
  95. LFE8:
  96. .align 2
  97. .p2align 4,,15
  98. .globl _main
  99. .section __TEXT,__text,regular,pure_instructions
  100. .align 2
  101. _main:
  102. LFB9:
  103. mflr r2
  104. stw r2,8(r1)
  105. LCFI0:
  106. stwu r1,-80(r1)
  107. LCFI1:
  108. bl __Z1gv
  109. bl __Z1hv
  110. lwz r2,88(r1)
  111. li r3,0
  112. addi r1,r1,80
  113. mtlr r2
  114. blr
  115. LFE9:
  116. .globl _Z1fi.eh
  117. _Z1fi.eh = 0
  118. .no_dead_strip _Z1fi.eh
  119. .globl _Z1gv.eh
  120. _Z1gv.eh = 0
  121. .no_dead_strip _Z1gv.eh
  122. .globl _Z1hv.eh
  123. _Z1hv.eh = 0
  124. .no_dead_strip _Z1hv.eh
  125. .globl main.eh
  126. main.eh = 0
  127. .no_dead_strip main.eh
  128. .data
  129. .constructor
  130. .data
  131. .destructor
  132. .align 1
  133. .subsections_via_symbols

Reply

Marsh Posté le 13-10-2004 à 10:28:04    

ben je te l'ai filé !
 
c'est clair pourtant, il a pas le code de f ... et pourtant il vire les appels, mais il garde la boucle ... (alors que chez moi évidemment si void f(int i) { } g est alors vide ...
 
y a un truc qui foire terrible là ...

Reply

Marsh Posté le 13-10-2004 à 10:29:28    

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

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

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