Discussion :

[Amnael]

Salutation,

encore une question en relation avec ce problème de parallélisation.


J'ai deux questions, qui en fait font partie du même problème, mais je vais décomposer ici pour simplifier.


J'ai une boucle séquentielle qui calcule un minimum

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
for(int i=0;i<N;i++){
  if(min<val){
     val= min
  }
}

Ici, admettons que je veuille paralléliser cette boucle.

Je vais faire un pragma omp for private (min)

De cette façon chacun des threads va calculer un minimum local.

Par exemple T0 aura le min de i=0 à 5 / T1 de i=6 à N

En sortie de boucle il reste donc à récupérer le min entre T0 et T1.

Comment effectuer cette opération là ?


======================================

Seconde question, toujours lié

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
for(int i=0;i<N;i++){
  if(min<val){
     val= min
     val2=i
  }
}

Ici si je parallélise ma boucle, en admettant que la réponse à la q1 soit ok et que mes T0 et T1 se synchronise bien sur leur propre min. Ici, j'ai en plus à me synchro sur la val2 qui correspond à celle affecte en même temps que le min.


De façon globale, la question est donc, comment synchroniser toutes mes variables en sorties.

[picodev]

Bonjour,
la réponse la plus simple est évidemment : fais des tutos et réfère-toi à la doc

Ce que tu cherches à faire est une réduction, cela peut par exemple se faire ainsi :

Code :

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
#include <stdio.h>
 
int main(void)
{
  int test[]={ 10,2,3,5,7,8,8,4,1,2,3,0,20,11,8 };
  int max_val=test[0];
  int sum=0;
 
  #pragma omp parallel for reduction(max:max_val) reduction(+:sum)
  for(int i=0; i<sizeof test/sizeof *test; ++i) {
    sum+=test[i];
    if (max_val<test[i]) max_val=test[i];
  }
 
  printf("max : %d\n"
         "sum : %d\n", max_val, sum);
 
  return 0;
}

[Amnael]

En parlant de doc tu en aurais une en tête ?

Parce que je t'avoue que mes cours sont un peu pauvre sur le sujet^^

Là je vais me renseigner sur la réduction mais je ne savais même pas que le terme existait donc

[picodev]

La première source d'infos est évidemment le site d'open mp, ensuite tu peux trouver pas mal de tutos grâce à google en cherchant par exemple «open mp tutorial», …

[foetus]

De façon globale, la question est donc, comment synchroniser toutes mes variables en sorties.

Je ne connais pas OpenMP , mais, de façon classique, il y a 2 solutions:

• Soit tu mets tes variables partagées/ tes calculs dans une section critique. Le problème avec ton cas: tu vas flinguer tes performances parce que 1 seul thread va travailler à la fois
• Soit le fil d'exécution parent va donner une variable temporaire (*), attendre la fin de tous ces fils et enfin finir les calculs/ prendre les décisions

* -> Ici, je pense à un tableau d'entiers ou de structures d'entiers et chaque fils va avoir le pointeur (l'adresse) d'une case

[Amnael]

Je suis sûr que si j'avais le droit de modifier la structure de base du programme je pourrais m'en sortir avec une structure perso foetus, hors dans mon cas on me l'interdit

L'énoncé est certes un peu bête, mais c'est surtout pour nous faire bosser le langage je pense.

En bref on a un code et on doit le paralléliser au max sans modifier la structure du code en lui même, ou très peu.

=================

Bref, du site d'open mp, je retiens plus particulièrement ceci:

for [2.7.1] [2.7.1]
Specifies that the iterations of associated loops will be
executed in parallel by threads in the team in the context
of their implicit tasks.
#pragma omp for [clause[ [, ]clause] ...]
for-loops
clause:
private(list)
firstprivate(list)
lastprivate(list)
linear(list [ : linear-step])
reduction(reduction-identifier : list)
schedule( [modifier [, modifier] : ] kind[, chunk_size])
collapse(n)
ordered[ (n) ]
nowait

Je peux donc utiliser reduction pour for avec une liste de reduction-identifier


Et un reduction-identifier se déclare de la façon suivante

declare reduction [2.16] [2.15]
Declares a reduction-identifier that can be used in a
reduction clause.

#pragma omp declare reduction(reduction-identifier :
typename-list : combiner) [initializer-clause]

reduction-identifier: A base language identifer (for C),
or an id-expression (for C++), or one of the following
operators: +, -, *, &, |, ^, && and ||

typename-list: A list of type names

combiner: An expression

initializer-clause: initializer (initializer-expr) where initializer-expr is omp_priv = initializer or function-name (argument-list )

On peut donc spécifier une opération ou un nom de variable pour la reduction



Je vais donc recoller au problème en reprenant l'exemple proposé plus haut

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
 int test[]={ 10,2,3,5,7,8,8,4,1,2,3,0,20,11,8 };
  int max_val=test[0];
  int sum=0;
 
  #pragma omp parallel for reduction(max:max_val)
  for(int i=0; i<sizeof test/sizeof *test; ++i) {
    if (max_val<test[i]) max_val=test[i];
  }

Ici, je comprends que l'on spécifie la valeur max:max_val

car max est une fonction C et max_val notre variable.

Sur ce niveau là qui correspond à ma question 1, j'ai donc bien compris.

En revanche mon problème est légèrement différent car en réalité le code de ma boucle doit récupérer une seconde valeur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
 for(int i=0; i<sizeof test/sizeof *test; ++i) {
    if (max_val<test[i]) {
           max_val=test[i]; //le max/min ok on peut traiter avec la réduction
           nb=i;
    }
}

Or, ici vous comprenez bien que "nb" ne dépend d'aucune formule mathématique; je dois simplement récupérer le nb correspondant à celui du max_val.


C'est donc là que se situe mon problème désormais.

Merci pour votre aide !