Reduzieren eines Arrays in OpenMP

Question

Ich versuche, das folgende Programm zu parallelisieren, weiß aber nicht, wie ich ein Array reduzieren kann. Ich weiß, dass es nicht möglich ist, dies zu tun, aber gibt es eine Alternative? Danke. (Ich habe die Reduktion auf m hinzugefügt, was falsch ist, würde aber gerne einen Rat dazu bekommen, wie man es machen könnte.)

#include 
#include 
#include 
#include 
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;
}

Answer 1

Ja, es ist möglich, eine Array-Reduktion mit OpenMP durchzuführen. In Fortran gibt es dafür sogar eine Konstruktion. In C/C++ müssen Sie es selbst erledigen. Hier sind zwei Methoden, um dies zu tun.

Die erste Methode erstellt eine private Version von S für jeden Thread, füllt sie parallel und fusioniert sie dann in S in einem kritischen Abschnitt (siehe den folgenden Code). Die zweite Methode erstellt ein Array mit Dimensionen 10*nthreads. Es füllt dieses Array parallel und fusioniert es dann in S ohne Verwendung eines kritischen Abschnitts. Die zweite Methode ist viel komplizierter und kann Probleme mit dem Cache haben, insbesondere bei Multi-Socket-Systemen, wenn Sie nicht vorsichtig sind. Weitere Details finden Sie unter diesem Befülle Histogramme (Array-Reduktion) parallel mit OpenMP ohne Verwendung eines kritischen Abschnitts

Erste Methode

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];
        }
    }
}

Zweite Methode

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

Answer 2

Da keine der anderen Antworten erwähnt wurde, füge ich diese Antwort hinzu.

Ich versuche, das folgende Programm zu parallelisieren, weiß aber nicht, wie man ein Array reduziert. Ich weiß, dass es nicht möglich ist, dies zu tun, aber gibt es eine Alternative?

Mit OpenMP 4.5 können Sie ein Array mit Pragmas reduzieren, nämlich:

#pragma omp parallel for reduction(+:S)

Ein vollständiges laufendes Beispiel:

#define S_SIZE 10
#include 
#include 
#include 
int main ()
{
  int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
  int S [S_SIZE] = {0};

  #pragma omp parallel for reduction(+:S[:S_SIZE])
  for (int n=0 ; n

`Ergebnis:

84
114
209
303
339
412
464
487
489
502`

Answer 3

Ich habe zwei Anmerkungen zu Zbosons Antwort:
1. Methode 1 ist sicherlich korrekt, aber die Reduzierungsschleife wird tatsächlich seriell ausgeführt, wegen des #pragma omp critical, das natürlich notwendig ist, da die Teilmatrizen lokal für jeden Thread sind und die entsprechende Reduktion vom Thread durchgeführt werden muss, der die Matrix besitzt.
2. Methode 2: Die Initialisierungsschleife kann außerhalb des Single-Abschnitts verschoben werden und somit parallelisiert werden.

Das folgende Programm implementiert die Array-Reduktion unter Verwendung der OpenMP v4.0 User Defined Reduction-Funktionen:

/* Kompilieren mit:
     gcc -Wall -fopenmp -o ar ar.c
   Ausführen mit:
     OMP_DISPLAY_ENV=TRUE OMP_NUM_THREADS=10 OMP_NESTED=TRUE ./ar
*/
#include 
#include 
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);
}

Dies folgt wortwörtlich dem Beispiel für die Reduktion von komplexen Zahlen auf Seite 97 von OpenMP 4.0 Features.

Obwohl die parallele Version korrekt funktioniert, gibt es wahrscheinlich Leistungsprobleme, die ich nicht untersucht habe:

1. Die Eingaben und Ausgaben von add_m10x1 werden per Wert übergeben.
2. Die Schleife in add_m10x1 wird sequentiell ausgeführt.

Diese "Leistungsprobleme" sind von mir selbst gemacht und es ist vollkommen unkompliziert, sie nicht einzuführen:

1. Die Parameter für add_m10x1 sollten per Referenz übergeben werden (über Zeiger in C, Referenzen in C++)
2. Die Berechnung in add_m10x1 sollte direkt durchgeführt werden.
3. add_m10x1 sollte als void deklariert und die Rückgabeanweisung gelöscht werden. Das Ergebnis wird über den ersten Parameter zurückgegeben.
4. Die declare reduction-Pragma sollte entsprechend geändert werden, der Kombinierer sollte nur ein Funktionsaufruf sein und keine Zuweisung (v4.0 Spezifikationen S. 181 Zeilen 9,10).
5. Die for-Schleife in add_m10x1 kann über ein omp parallel for-Pragma parallelisiert werden.
6. Verschachteltes Parallelisieren sollte aktiviert sein (z.B. über OMP_NESTED=TRUE)

Der modifizierte Teil des Codes sieht dann wie folgt aus:

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}} )

Answer 4

Mit einer parallelen Schleife wird jeder Thread einen bestimmten Teil der Indizes der Schleife gemäß dem Scheduler verarbeiten. Dann wird das Array S keine Reduzierung benötigen, da jeder Index n unabhängig für die äußere Schleife verarbeitet wird. Außerdem sollte es kein Problem mit einem Race Condition geben, da jeder Thread an eine andere Position S[n] schreiben wird. Somit wird der obige Code einwandfrei funktionieren, indem nur die Direktive

#pragma omp parallel for

für die äußere Schleife verwendet wird.

Answer 5

Wenn es Ihnen nicht gefällt, Ihren Code in Fortran zu übersetzen, der Arrays in OpenMP-Reduktionsoperationen verwenden kann, könnten Sie eine Menge temporärer Variablen verwenden. Zum Beispiel

int S0, S1, S2, ..., S9;
...
#pragma omp parallel for private(...) shared(S0, S1, S2, ..., S9) \
            reduction(+:S0, S1, S2, ..., S9)
for ...

Dies hinterlässt Ihnen die wenig verlockende Aussicht, eine Art if- oder case-Anweisung schreiben zu müssen, um zu bestimmen, welche der temporären Variablen aktualisiert werden soll. Wenn Ihr Code nur ein Beispiel ist, das Sie zum Lernen verwenden möchten, machen Sie weiter.

Aber wenn Ihre Absicht wirklich ist, eine parallele Präfixsummen-Routine zu schreiben, dann suchen Sie herum. Hier ist ein guter Ausgangspunkt.