IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Programmation parallèle, calcul scientifique et de haute performance (HPC) Discussion :

Paralléliser du code


Sujet :

Programmation parallèle, calcul scientifique et de haute performance (HPC)

  1. #1
    Membre du Club

    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2015
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2015
    Messages : 4
    Points : 69
    Points
    69
    Par défaut Paralléliser du code
    Bonjour,

    Je voudrais ajouter les directives OpenMP pour un algorithme de dessin basé sur les forces. Cependant, je n'ai aucune expérience en OpenMP (je n'ai jamais eu de courses ou formation d'OpenMP). Après de lire quelques courses et tutoriel que j'ai trouvés en ligne, j'ai essayé d'ajouter quelques directives selon ma compréhension; et mon programme est compilé, mais le résulta est différent par rapport à la version séquentielle.

    Vous pouvez ci-joint le code source ici:
    http://www.mediafire.com/download/3m.../drawgraph.zip

    Comme vous pouvez le constater, la portion de code je voudrais paralléliser est:

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    unsigned long graphLayout(Graph * graph, double * coords, unsigned long maxiter) {
      while(!converged && iter < maxiter) {
        for(int i = 0 ; i < graph->nvtxs ; i++) {
          double force[3];
          // 1) calculer la force répulsive
          // 2) calculer la force d'attraction
          // 3) mettre à jour la position de la force
        }
      }
    }

    Est-ce que vous pouvez m'aider à figurer où sont les problèmes avec les directives que j'ai ajouté et m'enseigner comment pour les corriger?

    Je vous remercie par avance pour votre aide!

  2. #2
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    Peux-tu directement poster le morceau de code en question avec et sans les directives OpenMP ?

  3. #3
    Membre du Club

    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2015
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2015
    Messages : 4
    Points : 69
    Points
    69
    Par défaut
    Citation Envoyé par Matt_Houston Voir le message
    Peux-tu directement poster le morceau de code en question avec et sans les directives OpenMP ?
    Bien sur, je voudrais rendre parallèle cette fonction:

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    // This code based on the article "Efficient and High-Quality Force-Directed Graph Drawing" written by Yifan Hu.
    unsigned long graphLayout(Graph * graph, double * coords, unsigned long maxiter)
    {
      assert(graph);
      assert(coords);
     
      /* main simulation loop */
      double energy = 0.0, _energy = +INFINITY;
      double maxmove = -INFINITY;
      double * _coords = malloc(graph->nvtxs*DIM*sizeof(double)); assert(_coords);
      double * position = coords;
      double * _position = _coords;
      memcpy(_position, position, graph->nvtxs*DIM*sizeof(double));
      int converged = 0;
      double step = 1.0;
      unsigned long iter = 0;
      if(maxiter == 0) maxiter = ULONG_MAX;
      if(period == 0) period = ULONG_MAX;
     
      /* time loop */
      while(!converged && iter < maxiter) { 
     
        energy = 0.0;
        maxmove = -INFINITY;
     
        /* for all particles xi, compute forces applied to it */
        for(int i = 0 ; i < graph->nvtxs ; i++) {
     
          /* position of particle i */
          double * _xi = _position+i*DIM; 
     
          /* reset force applied to particle i */
          double force[DIM];      
          for(int d = 0 ; d < DIM ; d++) force[d] = 0.0;
     
          /* compute repulsive forces (electrical: f=-C.K^2/|xi-xj|.Uij) */      
          for(int j = 0 ; j < graph->nvtxs ; j++) {    
        if(i == j) continue;
        double * _xj = _position+j*DIM;
        double dist = DISTANCE(_xi,_xj);        
        // power used for repulsive force model (standard is 1/r, 1/r^2 works well)
        // double coef = 0.0; -C*K*K/dist;       // power 1/r
        double coef = -C*K*K*K/(dist*dist); // power 1/r^2    
        for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist;
          }
     
          /* compute attractive forces (spring: f=|xi-xj|^2/K.Uij) */
          for(int k = graph->xadj[i] ; k < graph->xadj[i+1] ; k++) {
        int j =  graph->adjncy[k]; /* edge (i,j) */ 
        double * _xj = _position+j*DIM;
        double dist = DISTANCE(_xi,_xj);            
        double coef = dist*dist/K;
        for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist;    
          }     
     
          /* update particle position & energy */
          double * xi = position+i*DIM;  
          double nforce2 = NORM2(force);
          double move[DIM]; 
          for(int d = 0 ; d < DIM ; d++) move[d] = step*force[d]/sqrt(nforce2);
          for(int d = 0 ; d < DIM ; d++) xi[d] = _xi[d] + move[d];      
          double nmove = NORM(move);
     
          /* reduction */
          if(nmove > maxmove) maxmove = nmove;       // ???
          energy += nforce2;         
        }    
     
        // energy /= graph->nvtxs; // normalize energy
     
        /* update step length */
        if(energy < _energy/5.0) step /= STEPCOEF;  /* step length increased, if energy strongly reduced */
        else if(energy < _energy) step = step;      /* step length unchanged, if energy reduced */
        else step *= STEPCOEF;                      /* step length reduced, if energy increased */    
     
        /* check convergence */
        // if((energy < _energy) && ((_energy-energy)/energy < 0.0001)) converged = 1;
        if(maxmove < K*TOL) converged = 1;      
        _energy = energy;    
        if((iter % period == 0) || converged) {     
          char vtkfile[255];
          sprintf(vtkfile, "/tmp/output-%06ld.vtk", iter);
          saveVTKGraph(vtkfile, graph, position);
          printf("iter %ld: energy %.2f, maxmove %.6f\n", iter, energy, maxmove);
        }
        iter++;      
     
        /* swap former and newer position */
        double * tmp = _position; _position = position; position = tmp;
     
      } // end of while loop
     
      free(_coords);
     
      return iter;
    }

    En particulier les deux boucles:

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
          /* compute repulsive forces (electrical: f=-C.K^2/|xi-xj|.Uij) */      
          for(int j = 0 ; j < graph->nvtxs ; j++) {    
        if(i == j) continue;
        double * _xj = _position+j*DIM;
        double dist = DISTANCE(_xi,_xj);        
        // power used for repulsive force model (standard is 1/r, 1/r^2 works well)
        // double coef = 0.0; -C*K*K/dist;       // power 1/r
        double coef = -C*K*K*K/(dist*dist); // power 1/r^2    
        for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist;
          }
     
          /* compute attractive forces (spring: f=|xi-xj|^2/K.Uij) */
          for(int k = graph->xadj[i] ; k < graph->xadj[i+1] ; k++) {
        int j =  graph->adjncy[k]; /* edge (i,j) */ 
        double * _xj = _position+j*DIM;
        double dist = DISTANCE(_xi,_xj);            
        double coef = dist*dist/K;
        for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist;    
          }

    qui consomme beaucoup de ressources de calcul.

  4. #4
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    Mais où sont les directives que tu as ajouté et qui produisent un code au comportement différent ? Poste les deux versions l'une à la suite de l'autre.

  5. #5
    Membre du Club

    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2015
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2015
    Messages : 4
    Points : 69
    Points
    69
    Par défaut
    Citation Envoyé par Matt_Houston Voir le message
    Mais où sont les directives que tu as ajouté et qui produisent un code au comportement différent ? Poste les deux versions l'une à la suite de l'autre.
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    unsigned long graphLayout(Graph * graph, double * coords, unsigned long maxiter)
    {
      assert(graph);
      assert(coords);
     
      /* main simulation loop */
      double energy = 0.0, _energy = +INFINITY;
      double maxmove = -INFINITY;
      double * _coords = malloc(graph->nvtxs*DIM*sizeof(double)); assert(_coords);
      double * position = coords;
      double * _position = _coords;
      memcpy(_position, position, graph->nvtxs*DIM*sizeof(double));
      int converged = 0;
      double step = 1.0;
      unsigned long iter = 0;
      if(maxiter == 0) maxiter = ULONG_MAX;
      if(period == 0) period = ULONG_MAX;
     
      /* time loop */
      while(!converged && iter < maxiter) { 
     
        int i;
        energy = 0.0;
        maxmove = -INFINITY;
     
        /* for all particles xi, compute forces applied to it */
        #pragma omp parallel for private(i)
        for(int i = 0 ; i < graph->nvtxs ; i++) {
     
          /* position of particle i */
          double * _xi = _position+i*DIM; 
     
          /* reset force applied to particle i */
          double force[DIM];      
          for(int d = 0 ; d < DIM ; d++) force[d] = 0.0;
     
          /* compute repulsive forces (electrical: f=-C.K^2/|xi-xj|.Uij) */      
          for(int j = 0 ; j < graph->nvtxs ; j++) {    
        if(i == j) continue;
        double * _xj = _position+j*DIM;
        double dist = DISTANCE(_xi,_xj);        
        // power used for repulsive force model (standard is 1/r, 1/r^2 works well)
        // double coef = 0.0; -C*K*K/dist;       // power 1/r
        double coef = -C*K*K*K/(dist*dist); // power 1/r^2
        #pragma omp reduction (+:force)    
        for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist;
          }
     
          /* compute attractive forces (spring: f=|xi-xj|^2/K.Uij) */
          for(int k = graph->xadj[i] ; k < graph->xadj[i+1] ; k++) {
        int j =  graph->adjncy[k]; /* edge (i,j) */ 
        double * _xj = _position+j*DIM;
        double dist = DISTANCE(_xi,_xj);            
        double coef = dist*dist/K;
        for(int d = 0 ; d < DIM ; d++) force[d] += coef*(_xj[d]-_xi[d])/dist;    
          }     
     
          /* update particle position & energy */
          double * xi = position+i*DIM;  
          double nforce2 = NORM2(force);
          double move[DIM]; 
          for(int d = 0 ; d < DIM ; d++) move[d] = step*force[d]/sqrt(nforce2);
          for(int d = 0 ; d < DIM ; d++) xi[d] = _xi[d] + move[d];      
          double nmove = NORM(move);
     
          /* reduction */
          if(nmove > maxmove) maxmove = nmove;       // ???
          //#pragma omp reduction (+:energy)
          energy += nforce2;         
        }
     
        // energy /= graph->nvtxs; // normalize energy
     
        /* update step length */
        if(energy < _energy/5.0) step /= STEPCOEF;  /* step length increased, if energy strongly reduced */
        else if(energy < _energy) step = step;      /* step length unchanged, if energy reduced */
        else step *= STEPCOEF;                      /* step length reduced, if energy increased */
     
        #pragma omp single 
        /* check convergence */
        // if((energy < _energy) && ((_energy-energy)/energy < 0.0001)) converged = 1;
        if(maxmove < K*TOL) converged = 1;      
        _energy = energy;    
        if((iter % period == 0) || converged) {     
          char vtkfile[255];
          sprintf(vtkfile, "/tmp/output-%06ld.vtk", iter);
          saveVTKGraph(vtkfile, graph, position);
          printf("iter %ld: energy %.2f, maxmove %.6f\n", iter, energy, maxmove);
        }
        iter++;      
     
        /* swap former and newer position */
        double * tmp = _position; _position = position; position = tmp;
     
      } // end of while loop
     
      free(_coords);
     
      return iter;
    }

    Voilà, après d'ajouter les directives, le temps de calcul est réduit presque par dix (en exécutant sur un serveur 64 cores AMD 6276), mais le résultat est erroné

  6. #6
    Expert confirmé
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Points : 4 182
    Points
    4 182
    Par défaut
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    #pragma omp reduction (+:force)

    Tu ordonnes une réduction de la variable force qui est de type double [], honnêtement je ne sais même pas ce que ça entraîne ! Très probablement un comportement indéterminé.

    Tu peux alternativement utiliser une section critical, ou bien décomposer ton vecteur en scalaires :
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    #pragma omp reduction (+ : x, y, z)

Discussions similaires

  1. Parallélisation de code
    Par cecile38 dans le forum Général Java
    Réponses: 6
    Dernier message: 22/03/2012, 13h06
  2. [Oracle 10g] Paralléliser du code PL/SQL
    Par Yoh dans le forum Oracle
    Réponses: 3
    Dernier message: 06/05/2011, 13h07
  3. paralléliser un code en C++ ?
    Par membreComplexe12 dans le forum C++
    Réponses: 14
    Dernier message: 10/01/2011, 16h06
  4. Outils pour paralléliser du code Java
    Par LGnord dans le forum EDI et Outils pour Java
    Réponses: 3
    Dernier message: 12/07/2010, 11h01
  5. Parallélisation de code Java sur plusieurs machines
    Par Jester dans le forum API standards et tierces
    Réponses: 8
    Dernier message: 05/12/2006, 13h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo