Réduction sur le tableau dans OpenMP
J'essaie de paralléliser le programme suivant, mais je ne sais pas comment réduire sur un tableau. Je sais qu'il n'est pas possible de le faire, mais est-il une alternative? Grâce. (J'ai ajouté une réduction sur m qui est fausse mais je voudrais avoir un conseil sur la façon de le faire.)
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <omp.h>
using namespace std;
int main ()
{
int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10];
time_t start_time = time(NULL);
#pragma omp parallel for private(m) reduction(+:m)
for (int n=0 ; n<10 ; ++n ){
for (int m=0; m<=n; ++m){
S[n] += A[m];
}
}
time_t end_time = time(NULL);
cout << end_time-start_time;
return 0;
}
3 réponses
Oui, il est possible de faire une réduction de tableau avec OpenMP. Dans Fortran, il a même construit pour cela. En C/C++, vous devez le faire vous-même. Voici deux façons de le faire.
La première méthode privée, la version de S pour chaque thread, les remplir en parallèle, puis les fusionne en S dans une section critique (voir le code ci-dessous). La deuxième méthode fait un tableau avec des dimensions 10 * nthreads. Remplit ce tableau en parallèle, puis le fusionne dans S sans utiliser de critique section. La deuxième méthode est beaucoup plus compliquée et peut avoir des problèmes de cache en particulier sur les systèmes multi-sockets si vous ne faites pas attention. Pour plus de détails, voir ceci remplir les histogrammes (réduction de tableau) en parallèle avec OpenMP sans utiliser une section critique
Première méthode
int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10] = {0};
#pragma omp parallel
{
int S_private[10] = {0};
#pragma omp for
for (int n=0 ; n<10 ; ++n ) {
for (int m=0; m<=n; ++m){
S_private[n] += A[m];
}
}
#pragma omp critical
{
for(int n=0; n<10; ++n) {
S[n] += S_private[n];
}
}
}
Deuxième méthode
int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10] = {0};
int *S_private;
#pragma omp parallel
{
const int nthreads = omp_get_num_threads();
const int ithread = omp_get_thread_num();
#pragma omp single
{
S_private = new int[10*nthreads];
for(int i=0; i<(10*nthreads); i++) S_private[i] = 0;
}
#pragma omp for
for (int n=0 ; n<10 ; ++n )
{
for (int m=0; m<=n; ++m){
S_private[ithread*10+n] += A[m];
}
}
#pragma omp for
for(int i=0; i<10; i++) {
for(int t=0; t<nthreads; t++) {
S[i] += S_private[10*t + i];
}
}
}
delete[] S_private;
J'ai deux remarques concernant la réponse de Zboson:
1. La méthode 1 est certainement correcte mais la boucle de réduction est réellement exécutée en série, à cause du #pragma omp critical qui est bien sûr nécessaire car les matrices partielles sont locales à chaque thread et la réduction correspondante doit être faite par le thread devant la matrice.
2. Méthode 2: la boucle d'initialisation peut être déplacée en dehors de la section unique et donc devenir parallélisable.
Le programme suivant implémente tableau de réduction de utilisation d'openMP v4.0 utilisateur défini facilité de réduction de la:
/* Compile with:
gcc -Wall -fopenmp -o ar ar.c
Run with:
OMP_DISPLAY_ENV=TRUE OMP_NUM_THREADS=10 OMP_NESTED=TRUE ./ar
*/
#include <stdio.h>
#include <omp.h>
struct m10x1 {int v[10];};
int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
struct m10x1 S = {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
int n,m=0;
void print_m10x1(struct m10x1 x){
int i;
for(i=0;i<10;i++) printf("%d ",x.v[i]);
printf("\n");
}
struct m10x1 add_m10x1(struct m10x1 x,struct m10x1 y){
struct m10x1 r ={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
int i;
for (i=0;i<10;i++) r.v[i]=x.v[i]+y.v[i];
return r;
}
#pragma omp declare reduction(m10x1Add: struct m10x1: \
omp_out=add_m10x1(omp_out, omp_in)) initializer( \
omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} )
int main ()
{
#pragma omp parallel for reduction(m10x1Add: S)
for ( n=0 ; n<10 ; ++n )
{
for (m=0; m<=n; ++m){
S.v[n] += A[m];
}
}
print_m10x1(S);
}
Ceci suit textuellement l'exemple de réduction de nombre complexe à la page 97 de fonctionnalités OpenMP 4.0.
Bien que la version parallèle fonctionne correctement, il y a probablement des problèmes de performance, que je n'ai pas étudiés:
- add_m10x1 les entrées et les sorties sont passées par valeur.
- la boucle dans add_m10x1 est exécutée en série.
Dit "problèmes de performance" sont de ma propre fabrication et il est tout à fait simple de ne pas les présenter:
- les paramètres de add_m10x1 doivent être passés par référence (via des pointeurs en C, des références en C++)
- le calcul dans add_m10x1 doit être fait en place.
- add_m10x1 doit être déclaré nul et l'instruction return supprimée. Le résultat est renvoyé par le premier paramètre.
- la déclaration le pragma de réduction doit être modifié en conséquence, le combinateur doit être juste un appel de fonction et non une affectation (spécifications v4. 0 p181 lignes 9,10).
- la boucle for Dans add_m10x1 peut être parallélisée via un parallèle omp pour pragma
- L'imbrication parallèle doit être activée (par exemple via OMP_NESTED=TRUE)
La partie modifiée du code est alors:
void add_m10x1(struct m10x1 * x,struct m10x1 * y){
int i;
#pragma omp parallel for
for (i=0;i<10;i++) x->v[i] += y->v[i];
}
#pragma omp declare reduction(m10x1Add: struct m10x1: \
add_m10x1(&omp_out, &omp_in)) initializer( \
omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} )
Si la traduction de votre code en Fortran, qui peut utiliser des tableaux dans les opérations de réduction OpenMP, ne fait pas appel, vous pouvez utiliser un tas de variables temporaires. Par exemple
int S0, S1, S2, ..., S9;
...
#pragma omp parallel for private(...) shared(S0, S1, S2, ..., S9) \
reduction(+:S0, S1, S2, ..., S9)
for ...
Cela vous laisse avec la perspective peu attrayante d'avoir à écrire une sorte d'instruction if ou case pour déterminer laquelle des temporaires doit être mise à jour. Si votre code n'est qu'un exemple que vous souhaitez utiliser pour l'apprentissage, continuez.
Mais si votre intention est vraiment d'écrire une somme de préfixe parallèle routine puis chercher autour. C'est un bon point de départ.