[C] Vous voyez une erreur d'algo dans ce programme de calcul en // ?

Vous voyez une erreur d'algo dans ce programme de calcul en // ? [C] - C++ - Programmation

Marsh Posté le 02-03-2003 à 21:08:25    

Bonjour,
 
Je dois faire un programme basique, prenant une matrice carree, un vecteur, et calculant le vecteur resultant du produit des deux, le tout sur 4 procos.
 
Pour le vecteur, on nous a oblige a utiliser broadcast, pour la matrice, send/receive. Je sais que ce dernier est VRAIMENT pas optimal, mais c'est ce qu'on nous a demande :/
 
Mon souci est que mon programme est, tenez vous bien, plus rapide en termes de temps d'execution pour calculer une matrice 128x128 qu'une matrice 16x16...
 
Je parle pas de speedup, mais bien de temps d'execution...
 
Et ca me semble vraiment impossible... quelqu'un peux confirmer que j'ai pas fait de connerie ?
 

Code :
  1. include "mpi.h"
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <stddef.h> /* defines NULL */
  5. #include <sys/time.h>/* definition of timeval struct and protyping of gettimeofday */
  7. int main (argc,argv)
  8.      int argc;
  9.      char *argv[];
  10. {
  11.   int numprocs = 4;
  12.   int rowperproc = 32;
  13.   int n=128;
  14.   int myid;
  15.   float r;
  16.   int s;
  17.   int i,j,k;
  18.   MPI_Status status;
  19.   double t1,t2,elapsed;
  20.   struct timeval tp;
  21.   int rtn;
  23.   MPI_Init(&argc,&argv);
  24.   MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
  25.   MPI_Comm_rank(MPI_COMM_WORLD, &myid);
  27.   if (myid == 0)
  28.     {
  29.       float data[4][32][128];
  30.       float x0[128];
  31.       float x1[4][32];
  33.       //initialising the array
  34.       for(i=0;i<numprocs;i++)
  35.         for(j=0;j<rowperproc;j++)
  36.           x1[i][j]=0.0;
  39.       //create the random numbers
  40.       srand((unsigned)time(NULL));
  41.       for(i=0;i<numprocs;i++)
  42.         for (j=0;j<rowperproc;j++)
  43.           for (k=0;k<n;k++)
  44.           {
  45.             r = (float) random() / (float) 0x7fffffff;
  46.             s = random() %2;
  47.             if (s ==0)
  48.               r *= -1.0;
  49.             data[i][j][k]=r;
  50.             //printf("nb genere : %f\n", r*s);
  51.           }
  53.       for (i=0;i<n;i++)
  54.         {
  55.           r = (float) random() / (float) 0x7fffffff;
  56.           s = random() %2;
  57.           if (s ==0)
  58.             r *= -1.0;
  59.           x0[i]=r;
  60.           //printf("nb genere : %f\n", r);
  61.         }
  63.       //sending the tables to all processors
  64.       for (i=1;i<numprocs;i++)
  65.         {
  66.           MPI_Send(data[i],rowperproc*n,MPI_FLOAT,i,0,MPI_COMM_WORLD);
  67.           // MPI_Send(x0,n,MPI_FLOAT,i,0,MPI_COMM_WORLD);
  68.         }
  69.       MPI_Bcast(x0,n,MPI_FLOAT,0,MPI_COMM_WORLD);
  71.       //Here everybody has the data. Thus, we can start the timer. Cool.
  72.       rtn=gettimeofday(&tp, NULL);
  73.       t1=(double)tp.tv_sec+(1.e-6)*tp.tv_usec;
  75.       //Done sending. Now calculating our own sum
  76.       for (j=0;j<rowperproc;j++)
  77.         for(k=0;k<n;k++)
  78.           {
  79.             x1[0][j] += data[0][j][k] * x0[k];
  80.           }
  82.       //Done calculating. Now receiving the results, and finally adding them to our sum
  83.       for (i=1;i<numprocs;i++)
  84.         {
  85.           MPI_Recv(x1[i],rowperproc,MPI_FLOAT,i,MPI_ANY_TAG,MPI_COMM_WORLD,&status);
  86.         }
  88.       rtn=gettimeofday(&tp, NULL);
  89.       t2=(double)tp.tv_sec+(1.e-6)*tp.tv_usec;
  90.       elapsed=t2-t1;
  92.       printf("ELAPSED TIME : %f\n",elapsed);
  93.     }
  94.   else
  95.     {
  96.       float myx1[32];
  97.       float data[32][128];
  98.       float x0[128];
  99.       //initialising the array
  100.       for (i=0;i<rowperproc;i++)
  101.         myx1[i]=0.0;
  103.       //waiting to receive our data
  104.       MPI_Recv(data,rowperproc*n,MPI_FLOAT,0,MPI_ANY_TAG,MPI_COMM_WORLD,&status);
  105.       MPI_Bcast(x0,n,MPI_FLOAT,0,MPI_COMM_WORLD);
  107.       //got it, now we calculate  the result
  108.       for (i=0;i<rowperproc;i++)
  109.         for(j=0;j<n;j++)
  110.           {
  111.             myx1[i] += data[i][j]*x0[j];
  112.           }
  114.       // and we send it back
  115.       MPI_Send(&myx1,rowperproc,MPI_FLOAT,0,1,MPI_COMM_WORLD);
  116.     }
  118.   MPI_Finalize();
  119.   return 0;
  121. }


 
Je sais que mes tableaux sont pas beaux mais spa le probleme la :D
 
Ce que je fais, c'est qu'u lieu de dire que j'ai une matrice de 128x128 par exemple, j'ai une matrice de 4x32x128 , ce qui me permet de diviser le tout assez facilement pour l'envoi etc.
 
Voila la version "serie" de l'algo :
 

Code :
  1. include "mpi.h"
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <stddef.h>      /* definition of NULL */
  5. #include <sys/time.h>   /* definition of timeval struct and protyping of gettimeofday */
  7. void print_mat(mat, nbi, nbj)
  8.      float mat[64][64];
  9.      int nbi;
  10.      int nbj;
  11. {
  12.   int i,j,k;
  13.   for (i=0;i<nbi;i++)
  14.     for (j=0;j<nbj;j++)
  15.       {
  16.         printf(" %f", mat[i][j]);
  17.       }
  18.   printf("\n" );
  21. }
  23. void print_x(x,nb)
  24.      float x[64];
  25.      int nb;
  26. {
  27.   int i;
  28.   for (i=0;i<nb;i++)
  29.     printf( " %f",x[i]);
  30.   printf("\n" );
  31. }
  33. int main (argc,argv)
  34.      int argc;
  35.      char *argv[];
  36. {
  37.   int n=64;
  38.   float r;
  39.   int s;
  40.   int i,j,k;
  42.   float data[64][64];
  43.   float x0[64];
  44.   float x1[64];
  46.   double t1,t2,elapsed;
  47.   struct timeval tp;
  48.   int rtn;
  50.   printf("let's go\n" );
  51.   //create the random numbers
  52.   srand((unsigned)time(NULL));
  53.   for(i=0;i<n;i++)
  54.     for (j=0;j<n;j++)
  55.         {
  56.           r = (float) random() / (float) 0x7fffffff;
  57.           s = random() %2;
  58.           if (s ==0)
  59.             r *= -1.0;
  60.           data[i][j]=r;
  61.         }
  63.   for (i=0;i<n;i++)
  64.     {
  65.       r = (float) random() / (float) 0x7fffffff;
  66.       s = random() %2;
  67.       if (s ==0)
  68.         r *= -1.0;
  69.       x0[i]=r;
  70.       //printf("nb genere : %f\n", r);
  71.     }
  73.   //initialising the array
  74.   for(i=0;i<n;i++)
  75.       x1[i]=0.0;
  76.   //data generated. We start the timer. gogogo.
  77.   rtn=gettimeofday(&tp, NULL);
  78.   t1=(double)tp.tv_sec+(1.e-6)*tp.tv_usec;
  80.   //calculating
  81.   for (i=0;i<n;i++)
  82.     for(j=0;j<n;j++)
  83.       {
  84.         x1[i] = x1[i] + (data[i][j] * x0[j]);
  85.       }
  87.   rtn=gettimeofday(&tp, NULL);
  88.   t2=(double)tp.tv_sec+(1.e-6)*tp.tv_usec;
  89.   elapsed=t2-t1;
  91.   printf("ELAPSED TIME %f\n",elapsed);
  92.   return 0;
  93. }


 
Je sais qu'il fait une matrice de 64x64, mais lui il tourne bieng et j'ai deja ses resultats... c'est pas pour lui qu'il y a le souci.
 
Merci :hello:
 
 

Reply

Marsh Posté le 02-03-2003 à 21:08:25   

Reply

Marsh Posté le 02-03-2003 à 23:31:00    

J'ai pas regardé si il y a des bugs dans ton code, mais le fait que tu observes un gros ralentissement avec la version parallèle ne m'étonne pas du tout. A vrai dire je suis même surpris que la version séquentielle ne te renvoie pas un temps égal à zéro (étant donné que l'horloge a une précision de 1/100ème de sec).
 
Tout ça pour dire que le produit d'une matrice 128x128 avec un vecteur ça doit prendre un millième de seconde sur une grosse bouse. Le temps que tu mesures, c'est le temps du reste du code.
 
Si tu veux avoir des infos pertinentes, commence par mesurer le temps pour faire 1000 produits matrice-vecteur. Et essaye avec des tailles de matrices plus importantes. Et tache de faire tes tests sur une grosse bouse (une bonne vieille sparc quadri-proc à 60MHz par ex), pas un bi-athlon à 2Ghz :D

Reply

Marsh Posté le 03-03-2003 à 00:09:17    

J'ai acces a un cluster de 200 P4 xeon 2Ghz... mais la n'estpas la question.
 
La ou je me pose des questions, c'est pourquoi ca prends plus de temps a faire une matrice 16x16 qu'une matrice 128x128 ?
 
:|
 
C'est le sujet qui est comme ca, une seule multiplication de matrice carree...
 
et je peux pas aller au dela de 1024x10249 limitation compilateur).

Reply

Marsh Posté le 03-03-2003 à 00:19:29    

tetedeiench a écrit :

J'ai acces a un cluster de 200 P4 xeon 2Ghz... mais la n'estpas la question.
 
La ou je me pose des questions, c'est pourquoi ca prends plus de temps a faire une matrice 16x16 qu'une matrice 128x128 ?
 
:|
 
C'est le sujet qui est comme ca, une seule multiplication de matrice carree...
 
et je peux pas aller au dela de 1024x10249 limitation compilateur).


 
- si tu reserve ta matrice avec un malloc, t'auras pas cette limite
- comme je disais plus haut, tu ne mesures le temps d'un calcul qui dure moins d'un millième de secondes avec une horloge qui n'est précise qu'au centième de secondes. Donc mesure le temps de 1000 multiplications et divise ce temps par mille. c'est tout.
 

Reply

Marsh Posté le 03-03-2003 à 00:24:40    

je peux pas faire le calcul 1000 fois malheureusement...  
 
spa dans le sujet ;) et il va m'aligner je pense.
 
Pour la resolution j'y avait pense, mais je devrais obtenir un truc plus coherent nan ?
 

Reply

Sujets relatifs:

Leave a Replay

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