OpenMP: Umgang mit unsigned long long

[Schlitzauge]

Hi COM,

Folgender Fall:

------------------------------------------------------------------

Folgende Infos:

OS: Scientific Linux 6.1 x64 (up2date)

Kompiler: g++ (GCC) 4.4.5 20110214 (Red Hat 4.4.5-6)

+kompatibel zu/ab: OpenMP v3.0

Glibc - x86_x64 - v2.12-1.25.el6_1.3

OpenMP - x86_64:

libgomp.x86_64 : GCC OpenMP v3.0 shared support library

Kompilierungsaufruf (Release):

g++ -std=c++0x -m64 -fopenmp -Wall -Wextra -pedantic -pedantic-errors -O3 -s source.cpp -o dest

------------------------------------------------------------------

Das Prog soll einfach nur eine Variable hochzählen:

Quellcode:

#ifdef _OPENMP

#include <omp.h>

#endif


#include <stdlib.h>

#include <stdio.h>

#include <iostream>


using namespace std;


int main(int argc, char *argv[])

{

  unsigned long long test = 18446744073709551615;


  const unsigned long long NumValues = 18446744073709551614;

  unsigned long long NumberOfIterations = 0;


  for(unsigned long long i=1;i<=NumValues;i++)

  {

    NumberOfIterations++;

  }

  printf("Benötigte Iterationen - SERIELL: %llu\n",NumberOfIterations);

  NumberOfIterations = 0;


  #pragma omp parallel reduction(+: NumberOfIterations)

  {

    #pragma omp for

    for(unsigned long long k=1;k<=NumValues;k++)

    {

      NumberOfIterations++;

    }

  }

  printf("Benötigte Iterationen - PARALLEL: %llu\n",NumberOfIterations);

  NumberOfIterations = 0;


  printf("%llu",test);


  getchar();

  return 0;

}

Ausgabe:

Benötigte Iterationen - SERIELL: 18446744073709551614

   

Das Problem ist nun, dass die parallele Schleife entweder länger braucht als die serielle oder sich irgendwie aufgehangen hat (kann das nicht konkret sagen, da ich den Vorgang nach einer Minute abgebrochen hab. Die CPU-Last war aber immer so bei 1600%).

Es liegen 24 Kerne vor (12 physisch, 12 logische), also 24 parallele Threads.

Selbst wenn mal einige Threads nicht parallel arbeiten sollten, müsste das Ganze doch immer noch schneller ablaufen als die serielle Schleifen-Variante, oder???

Gut, den Zeitunterschied kann ich nicht wirklich ausmachen, da selbst die serielle Schleife vollständig abgearbeitet ist, wie ich das Programm gestartet hab. Fakt ist aber, dass es irgendwo einen Haken bei der parallelen OpenMP-for-Schleife geben muss, da diese einfach nicht zur Potte kommt.

Hat jemand eine Erklärung dafür? Muss man an der OpenMP-Schleife noch irgendwas machen?

Grüße

Schlitzauge :):)

[flashpixx]

Selbst wenn mal einige Threads nicht parallel arbeiten sollten, müsste das Ganze doch immer noch schneller ablaufen als die serielle Schleifen-Variante, oder???

Nein das kann man pauschal nicht sagen, es kommt drauf an, was real an Code generiert wird (z.B.: Loop Enrollment, Semaphore ...).

Allgemein gilt: Amdahlsches Gesetz bzw Gustafsons Gesetz

[Schlitzauge]

Ja gut, aber ich seh einfach nicht, wo das Problem liegt.

Das ist doch die übliche Herangehensweise, wie man eine OpenMP-for-Schleife macht oder nicht?

Nach der Theorie her, sollte grob gesagt diese Schleife doch durch die Anzahl der Threads aufgeteilt werden. Jeder Thread bekommt für seinen abzuarbeitenden Bereich, sein eigenes Exemplar der Zählvariable (in dem Fall also k) und arbeitet seinen Bereich anschließend ab. Also z.B. Thread 0 von k=1 bis k=10, Thread 1 von k = 11 bis k = 20, usw.

Durch Reduction bekommt außerdem in meinem Beispiel-Prog die OpenMP-Schleife ein eigenes Exemplar der hochzuzählenden Variable "NumberOfIterations". Schlussendlich bekommt jeder Thread also nur 1/24 an Aufgaben als ein einziger Single-Prozess. Jedes der 24 Teilergebnisse wird dann am Ende bloß zu einem Gesamtergebnis zusammenaddiert (die 24 Additionen sollten ja wohl nicht die Zeitverzögerungen erklären).

Es ist auch so, wenn ich kleinere Werte für NumValues nehme, z.B. 10000, funktioniert alles wie es soll:

Benötigte Iterationen - SERIELL: 10000

Benötigte Iterationen - PARALLEL: 10000

Wenn ich aber in den äußersten Bereichen der unsigned long long´s gehe, funktioniert´s nicht mehr (wie oben zu sehen ist).

Nur warum? Kommt OpenMP mit unsigned long long nicht klar?

Wenn ich kleinere Werte nehme, den Datentyp aber gleich lasse, funktionierts ja trotzdem.

Grüße

Schlitzauge :):)

Bearbeitet 28. September 2011 von Schlitzauge

[flashpixx]

Also z.B. Thread 0 von k=1 bis k=10, Thread 1 von k = 11 bis k = 20, usw.

Nein in Deinem Beispiel nicht. Du läuft in der Schleife von K=1 bis k==NumValues, d.h. Deine For-Schleife wird "Anzahl-Threads x NumValues" ausgeführt, jede Thread läuft somit von K=1 bis k==NumValues. Erst nachdem die Schleife beendet wurde wird das Reduce auf der Variablen NumberOfIterations ausgeführt. Du musst die Schleife von von k=1 bis k==NumValues / Anzahl-Thread + ((isLastThread) ? NumValues % AnzahlThreads : 0) laufen lassen.

Das "pragma omp parallel reduction" macht letztendlich nur einen copy-by-value für jeden Thread, der Wert ist aber für alle Threads gleich, sofern Du es nicht änderst.

Der Compiler kann nicht Deine Daten automatisch verteilen, dafür bist Du als Programmierer zuständig.

Bearbeitet 28. September 2011 von flashpixx

[Schlitzauge]

Nein in Deinem Beispiel nicht. Du läuft in der Schleife von K=1 bis k==NumValues, d.h. Deine For-Schleife wird "Anzahl-Threads x NumValues" ausgeführt, jede Thread läuft somit von K=1 bis k==NumValues. Erst nachdem die Schleife beendet wurde wird das Reduce auf der Variablen NumberOfIterations ausgeführt.

Hm. Und warum stimmt dann das Ergebnis?

Bsp.: ich lasse 2400 (NumValues) mal hochzählen. Dann steht am Ende in NumberOfIterations auch eine 2400 drinn.

Nachdem, was Du aber sagst, müsste praktisch jeder der Threads (bei mir 24) sein eigenes Exemplar von NumberOfIterations bis 2400 inkrementieren.

Gemäß diesen Artikels:

OpenMP

, würde doch dann durch meine reduction(+: NumberOfIterations)-Anweisung, die echte NumberOfIterations-Variable am Ende durch 24-Additions-Operationen zusammengesetzt: z.B.

NumberOfIterations = Thread0.NumberOfIterations + Thread1.NumberOfIterations + ... + Thread_n.NumberOfIterations;

Wobei jede Thread-Lokale dann ja 2400 groß sein müsste. Müsste dann am Ende nicht eigentlich 57600 herauskommen? Dies sagt mir doch, dass die OpenMP-for-Schleife sehr wohl auf alle bzw. viele Threads verteilt und parallel ausgeführt wird. Natürlich wird der gleiche Code parallel ausgeführt, aber jeder Thread bekommt dann halt nur - in meinem Fall - 1/24 an Iterationen (NumValues), also z.B. Thread0 iteriert von k=1 bis k<=100, Thread2 von k=101 bis k<=200 usw. Im Beispiel müsste also jeder Thread [ca.] 100 mal iterieren. Srry der Nachfrage, aber Aufgrund des Endergebnisses komme ich selber zu dieser Schlussfolgerung. Ebenso verwirrt mich das jetzt, da dieses Verhalten in vielen Tutorials und Dokumentationen so propagiert wird. Dein Argument lese / höre ich gerade zum ersten mal. Ich finde es aber auch logisch so, vorausgesetzt, OpenMP übernimmt einem wirklich nicht die Arbeit. Ich kann es nur gerade Aufgrund des immer wieder richtigen Endergebnisses nicht nachvollziehen. Ich bitte daher mal um Aufklärung. THX im Voraus.

Du musst die Schleife von von k=1 bis k==NumValues / Anzahl-Thread + ((isLastThread) ? NumValues % AnzahlThreads : 0) laufen lassen.

Ein bissl versteh ich das schon, aber irgendwas funktioniert nicht. Meintest Du das so:

for(unsigned long long k=1;[B]k==NumValues / omp_get_num_threads() + ((omp_get_thread_num()) ? NumValues % omp_get_num_threads() : 0[/B];k++)

{

  //.....

}

Bzw. woher nimmst Du "isLastThread" und ist "Anzahl-Thread" sowie "AnzahlThreads" bei Dir das Gleiche?

Grüße

Schlitzauge :):)

[flashpixx]

Hm. Und warum stimmt dann das Ergebnis?

Bsp.: ich lasse 2400 (NumValues) mal hochzählen. Dann steht am Ende in NumberOfIterations auch eine 2400 drinn.

Nachdem, was Du aber sagst, müsste praktisch jeder der Threads (bei mir 24) sein eigenes Exemplar von NumberOfIterations bis 2400 inkrementieren.

siehe OpenMP

reduction: Die Daten sind privat, werden jedoch am Ende auf einen globalen Wert zusammengefasst (reduziert). So lässt sich zum Beispiel die Summe aller Elemente eines Arrays parallel bestimmen.

, würde doch dann durch meine reduction(+: NumberOfIterations)-Anweisung, die echte NumberOfIterations-Variable am Ende durch 24-Additions-Operationen zusammengesetzt: z.B.

NumberOfIterations = Thread0.NumberOfIterations + Thread1.NumberOfIterations + ... + Thread_n.NumberOfIterations;

später wird dann auf die private Variable im Thread z.B. ein "std::max(var_thread1, var_thread2...)" gemacht ....

Wobei jede Thread-Lokale dann ja 2400 groß sein müsste. Müsste dann am Ende nicht eigentlich 57600 herauskommen?

.... und Du bekommst Deine 2400. Alleine das "reduce" sagt doch schon aus was passiert. Du hast n Werte, auf n Threads verteilt und nun wird nach irgendeiner Relation diese n Werte auf einen reduziert. Diese Relation kann z.B. das Max / Min oder sonst irgendwie etwas sein.

Dies sagt mir doch, dass die OpenMP-for-Schleife sehr wohl auf alle bzw. viele Threads verteilt und parallel ausgeführt wird. Natürlich wird der gleiche Code parallel ausgeführt, aber jeder Thread bekommt dann halt nur - in meinem Fall - 1/24 an Iterationen (NumValues), also z.B. Thread0 iteriert von k=1 bis k<=100, Thread2 von k=101 bis k<=200 usw.

Nein Du implizierst in Deinen Gedanken, dass OpenMP durch das Reduce eine Aufteilung der Daten macht und das tut es nicht. OpenMP macht genau das was Du ihm sagst:

1. mache Variable auf jedem Thread privat (der Wert der Variablen wird letztendlich per copy-by-value n-fach repliziert)

2. führe Schleife aus

3. reduziere die Variable wieder auf eine Instanz zurück

Woher soll OpenMP wissen, dass er die ersten k Elemente auf den ersten, die zweiten k Elemente auf den zweiten Thread usw. packen soll !? Man könnte auch denken, dass OpenMP vielleicht ein Round-Robin-Prinzip anwendet, also erstes Element auf ersten Thread, zweites Element auf zweiten usw (bis Elementindex % Threadanzahl) woher soll OpenMP wissen, wie Du es gerne haben möchtest? Wenn eine Abhängigkeit zwischen den Daten besteht, z.b. Element 1 muss berechnet sein, bevor 2 berechnet werden kann, dann wäre es schlecht, wenn 1 und 2 auf getrennten Threads liegen würden, im worst-case holst Du Dir dann einen Deadlock.

Bzw. woher nimmst Du "isLastThread" und ist "Anzahl-Thread" sowie "AnzahlThreads" bei Dir das Gleiche?

Das sind Größen / Variablen, die OpenMP bereitstellt (für den genauen Synatx bitte Doku ansehen). Lastthread wäre letztendlich "threadnumber == threadcount-1" OpenMP und Message Passing Interface sind sehr ähnlich bzw. in vielen Punkten identisch. Ich empfehle Dir, dass Du gerade zur Parallelisierung erst einmal Grundlagen Dir anschaust. Als Literatur wäre dafür z.B. Parallele Programmierung: Amazon.de: Thomas Rauber, Gudula Rünger: Bücher Parallele numerische Verfahren Springer-Lehrbuch Masterclass: Amazon.de: Götz Alefeld, Ingrid Lenhardt, Holger Obermaier: Bücher geeignet. Parallelisierung ist nicht trivial und naive Ansätze sind oft schlechter als ein sequentieller Code. Nur weil eine Bibliothek wie OpenMP einem viele Komponenten bereitstellt, heißt das nicht, dass es mal eben "schnell" gemacht ist. Parallele Algorithmen sind extrem schwierig und erfordern zunächst einmal entsprechendes Wissen über parallele Verarbeitung, denn neben der parallelen Ausführung ist auch der Datenfluss / -zugriff extrem relevant. Dein Code liefert beim Compileraufruf:

test.cpp:11:31: warning: integer constant is so large that it is unsigned

test.cpp:11: warning: this decimal constant is unsigned only in ISO C90

test.cpp:13:42: warning: integer constant is so large that it is unsigned

test.cpp:13: warning: this decimal constant is unsigned only in ISO C90

test.cpp: In function ‘int main(int, char**)’:

test.cpp:26: warning: iteration variable ‘k’ is unsigned

test.cpp:26: error: invalid controlling predicate

Wobei Du eben bei dem Reduce überlegen solltest, was passiert wenn Du eine Bereichsüberschreitung bekommst, sprich wenn Die Iterationsanzahl * Threadanzahl die Größe des Datentypes überschreitet

Bearbeitet 29. September 2011 von flashpixx

[Schlitzauge]

später wird dann auf die private Variable im Thread z.B. ein "std::max(var_thread1, var_thread2...)" gemacht ....

Na dann erscheints auch logisch. Nur steht das nirgends geschrieben. D.h. mir ist bisher noch keine Dokumentation oder ein Tutorial bekannt, wo das erwähnt wird (Bücher mal außen vor, da mir gerade keine zur Verfügung stehen).

Inwieweit bringt dann dieses Beispiel etwas?:

int main(){

    int n;


    printf("Geben sie eine Ganzzahl ein: ");

    scanf("%d", &n);


    // Der Initialwert von is_prime ist wichtig, da dieser auch

    // in die Berechnung einbezogen wird.

    bool is_prime = true;


    #pragma omp parallel reduction(&&: is_prime)

    {

        // jeder bekommt sein eigenes is_prime,

        // welches mit true, dem neutralen Element von &&,

        // initialisiert wurde.


        #pragma omp for

        for(int i=2; i<n; ++i)

            if(n%i == 0)

                is_prime = false;


        // Alle is_prime (auch das aus der main Funktion) werden

        // mittels && verknüpft. Im Klartext bedeutet dies, dass,

        // falls eines false ist, das Resultat false ist.

    }


    if(is_prime)

        printf("%d ist prim\n", n);

    else

        printf("%d ist nicht prim\n", n);


}

Quelle (Abschnitt "Reduction"): OpenMP Ich meine, wozu da diese OpenMP-for-Schleife, wenn doch jeder Thread das Gleiche macht? Oder hängt das damit zusammen, dass ein Unterschiedliches Verhalten (Parallelität) bei n Threads durch Kontrollstrukturen in der Schleife hervorgerufen wird (wie hier mit der IF-Abfrage)? Du hast mir ja bereits irgendwie gesagt, wie ich richtig inkrementieren muss. Aber nur mal so zum Verständnis: Ich muss nicht die Schleife an sich parallelisieren, sondern den ganzen Algorithmus der iteriert werden soll (wie in meinem Beispiel, ein simples NumberOfIterations++)? Wie genau müsste das dann ausschauen, wenn ich meine Schleife zum einfachen Hochzählen, parallelisieren möchte und das jeder Thread sich auch nur um einen Bereich von Iterationen/AnzahlThreads kümmert? Und wie veranlasst man, dass die Teilergebnisse dann nicht einfach auf ein Maximales reduziert werden, sondern auch wirklich zusammengerechnet werden? Davon ging ich bisher ja bereits aus, was die reduction()-Anweisung betrifft, was aber falsch ist, wie es sich herausstellte.

Das sind Größen / Variablen, die OpenMP bereitstellt (für den genauen Synatx bitte Doku ansehen). Lastthread wäre letztendlich "threadnumber == threadcount-1"

Ich glaube Dir ja, dass dies schon die richtige Abbruchbedingung ist. Ich kann nur nichts mit den drei bzw. nur einer Variablen anfangen. Die Doku zu OpenMP 3.0 hab ich mir nochmal angeschaut. Aber ein "isLastThread" kann ich da nicht finden, auch sonst nicht, wenn ich Google damit füttere und auch der Kompiler kennt diese Variablen trotz omp.h nicht. Meinst Du mit "isLastThread" etwa die Funktion: omp_get_thread_num(); ? AnzahlThreads wäre demnach die Funktion: omp_get_num_threads(); ? Aber wie gesagt, weiß ich jetzt nicht, ob Du einfach nur zwei Tippfehler hattest und "Anzahl-Thread" sowie "AnzahlThreads" bei Dir nun das Gleiche sind oder nicht?

Dein Code liefert beim Compileraufruf:

test.cpp:11:31: warning: integer constant is so large that it is unsigned

test.cpp:11: warning: this decimal constant is unsigned only in ISO C90

test.cpp:13:42: warning: integer constant is so large that it is unsigned

test.cpp:13: warning: this decimal constant is unsigned only in ISO C90

test.cpp: In function ‘int main(int, char**)’:

test.cpp:26: warning: iteration variable ‘k’ is unsigned

[B]test.cpp:26: [U]error[/U]: invalid controlling predicate[/B]

Kann ich nicht nachvollziehen. Ich meine, ja, die Warnungen habe ich auch, aber mein oben stehender Code, erzeugt bei mir nur diesen Output, ohne ERRORS:

NestedLoop3.cpp:13:29: warning: integer constant is so large that it is unsigned

test.cpp:13: warning: this decimal constant is unsigned only in ISO C90

test.cpp:15:40: warning: integer constant is so large that it is unsigned

test.cpp:15: warning: this decimal constant is unsigned only in ISO C90

test.cpp: In function ‘int main(int, char**)’:

test.cpp:22: warning: ISO C++ does not support the ‘ll’ gnu_printf length modifier

test.cpp:33: warning: ISO C++ does not support the ‘ll’ gnu_printf length modifier

test.cpp:36: warning: ISO C++ does not support the ‘ll’ gnu_printf length modifier

test.cpp: At global scope:

test.cpp:11: warning: unused parameter ‘argc’

test.cpp:11: warning: unused parameter ‘argv’

Zu den Warnungen wollte ich später mal noch kommen. Alles zu seiner Zeit.

Wobei Du eben bei dem Reduce überlegen solltest, was passiert wenn Du eine Bereichsüberschreitung bekommst, sprich wenn Die Iterationsanzahl * Threadanzahl die Größe des Datentypes überschreitet

Warum sollte das bei meinem Programm ein Problem darstellen, wenn doch jeder Thread - wie wir jetzt feststellten - mit eigenem Exemplar vom Datentyp "unsigned long long" das Gleiche iteriert? Im Beispiel-Code lasse ich lediglich gegen die Grenze von "unsigned long long" inkrementieren, nicht aber darüber hinaus. So, wie der Code jetzt ist, iterieren und inkrementieren Deiner Aussage nach, alle Threads doch das Gleiche. Die Reduction()-Anweisung reduziert das anschließend auf eine Instanz, wobei alle Threads am Ende in deren lokalen privaten Variable, den gleichen Wert haben drinn stehen, weshalb die Dann reduzierte Instanz natürlich den gleichen Wert erhält. Oder hab ich Dich jetzt falsch verstanden?

Grüße

Schlitzauge :):)

PS: THX für die Literatur-Tipps, werde ich mir sicherlich auch besorgen. Mir gehts aber um das Hier und Jetzt. Literatur hilft mir also @Moment nicht weiter. Ich wollte doch einfach nur mal ein paar kleine Anfänger-Beispiele, wie das Hochzählen, wo man den Effekt der Parallelisierung beobachten kann, ausprobieren. HelloWorld brachte es nicht wirklich, da letztendlich Seriellität. :upps

Bearbeitet 29. September 2011 von Schlitzauge

[flashpixx]

Inwieweit bringt dann dieses Beispiel etwas?

Ich möchte Dir hier jetzt nicht jedes Beispiel einzeln erklären, das sprengt hier jeden Rahmen.

Ich meine, wozu da diese OpenMP-for-Schleife, wenn doch jeder Thread das Gleiche macht?

Oder hängt das damit zusammen, dass ein Unterschiedliches Verhalten (Parallelität) bei n Threads durch Kontrollstrukturen in der Schleife hervorgerufen wird (wie hier mit der IF-Abfrage)?

Hier ist der Hinweis auf die Literatur eigentlich passend, denn Parallelität spielt sich nicht nur im Code ab. Man hat ggf mehrschichte Architektur z.B. arbeite ich mit Threadparallelität & Parallelität auf MPI Ebene, was letztendlich dazu führt, dass ich den Algorithmus auf einer physikalischen Maschine parallelisiere und eine Datenparallelität über mehrere physikalischen Maschinen habe.

Ich muss nicht die Schleife an sich parallelisieren, sondern den ganzen Algorithmus der iteriert werden soll (wie in meinem Beispiel, ein simples NumberOfIterations++)?

genau das, natürlich erreicht man das auch durch parallel arbeitende Schleifen, nur muss man dann auf den richtigen Datenbereichen arbeiten & die Ergebnisse die entstehen passend verbinden.

Und wie veranlasst man, dass die Teilergebnisse dann nicht einfach auf ein Maximales reduziert werden, sondern auch wirklich zusammengerechnet werden? Davon ging ich bisher ja bereits aus, was die reduction()-Anweisung betrifft, was aber falsch ist, wie es sich herausstellte.

Das steht in der OpenMP Doku

Ich glaube Dir ja, dass dies schon die richtige Abbruchbedingung ist. Ich kann nur nichts mit den drei bzw. nur einer Variablen anfangen. Die Doku zu OpenMP 3.0 hab ich mir nochmal angeschaut.

Das wäre aber mal die Mindestvoraussetzung, um anständig arbeiten zu können.

Meinst Du mit "isLastThread" etwa die Funktion: omp_get_thread_num(); ?

AnzahlThreads wäre demnach die Funktion: omp_get_num_threads(); ?

Aber wie gesagt, weiß ich jetzt nicht, ob Du einfach nur zwei Tippfehler hattest und "Anzahl-Thread" sowie "AnzahlThreads" bei Dir nun das Gleiche sind oder nicht?

Das war Pseudocode => schau in die Doku da findet sich dazu die passenden Befehle. Bei MPI heißen die Befehle "size" und "rank".

Warum sollte das bei meinem Programm ein Problem darstellen, wenn doch jeder Thread - wie wir jetzt feststellten - mit eigenem Exemplar vom Datentyp "unsigned long long" das Gleiche iteriert? Im Beispiel-Code lasse ich lediglich gegen die Grenze von "unsigned long long" inkrementieren, nicht aber darüber hinaus. So, wie der Code jetzt ist, iterieren und inkrementieren Deiner Aussage nach, alle Threads doch das Gleiche. Die Reduction()-Anweisung reduziert das anschließend auf eine Instanz, wobei alle Threads am Ende in deren lokalen privaten Variable, den gleichen Wert haben drinn stehen, weshalb die Dann reduzierte Instanz natürlich den gleichen Wert erhält. Oder hab ich Dich jetzt falsch verstanden?

Beispiel (Pseudocode)

uchar x = 0;


do parallel with x is private on each thread {

x= 253;

} 


reduce with + { x };

was hat x für einen Wert nach dem Reduce bei einem oder mehr als einem Thread !? Wenn das Reduce zu einer Bitweisen Verknüpfung wie z.B. & oder | änderst, wie sehen dann die Ergebnisse aus !?

Ich wollte doch einfach nur mal ein paar kleine Anfänger-Beispiele, wie das Hochzählen, wo man den Effekt der Parallelisierung beobachten kann, ausprobieren.

In diesem Bereich gibt es keine Anfängerbeispiele, denn sobald Du eine Schleife hast spielen auch die Daten, die Du verwendest eine Rolle. Die "beste" Parallelisierung erreicht man auf Algorithmusebene und muss man einiges an Wissen hineinstecken, um gute Lösungen zu produzieren. Alle Frameworks die existieren können dies nicht, sondern sie arbeiten rein auf Codeebene. Es liegt am Programmierer für die richtigen Daten und auch die passenden Datentypen zu sorgen.

[Schlitzauge]

Ich möchte Dir hier jetzt nicht jedes Beispiel einzeln erklären, das sprengt hier jeden Rahmen.

Wollte ich auch gar nicht. Aber bei dem Beispiel wird quasi das selbe Prinzip angewandt wie bei meinem, bloß mit reduction(&&: is_prime).

Warum sollte dort dann ein Nutzen von Parallelität sein, wenn keiner bei meinem Beispiel greift?

Das steht in der OpenMP Doku

Dann seh ich es nicht. Hab mir diese jetzt schon 8x etwas ausführlicher angeschaut.

Kann mir nicht einfach mal jemand ein kleines Beispiel für paralleles Hochzählen schreiben. Mit Code vor meiner Nase, kann ich so etwas wesentlich besser nachvollziehen. Wenns geht, bitte aber kein Pseudocode, da ich damit noch nicht so viel zu tun hatte. Direkte C/C++-Syntax sagt mir da schon mehr zu.

Doch auch andere Beispiele von anderen Seiten verwenden genau das Gleiche Prinzip wie ich oben und behaupten trotzdem, dass dabei ein Nutzen von Parallelität greift.

Hier nur mal zwei Beispiele:

Quelle 1 (Abschnitt Akkumulation): OpenMP

Code:

int accumulate(int arr[], int size){

    int sum = 0;

    #pragma omp parallel for reduction(+:sum)

    for(int i=0; i<size; ++i)

        sum += arr;

    return sum;

}

Quelle 2 (Abschnitt: Verwendung von Reduktionen): OpenMP und inkrementelle Parallelisierung - (article in german) - Intel® Software Network Code:

float DotProduct (float *a, float *b, int N)

{

  float dot = 0.0;

  #pragma omp parallel for reduction(+:sum)

  {

    for (int i = 0; i < N; i++)

    {

      dot += a[i] * b[i];

    }

  }

  return dot;

}

Ähnliche Beispiele finde ich auch auf zahlreichen anderen Seiten, Tutorials, Videos, etc. Ich habe dann mal etwas weiter probiert und mit dem was herausgekommen ist, versteh ich nun gar nichts mehr: Hier mein neuer Code (Test2.cpp):

#ifdef _OPENMP

#include <omp.h>

#endif


#include <stdlib.h>

#include <stdio.h>

#include <iostream>


using namespace std;


int main(int argc, char *argv[])

{

  unsigned long long test = 18446744073709551615;

  const unsigned long long NumValues = 24000;

  unsigned long long NumberOfIterations = 0;


  //Serielle Variante

  for(unsigned long long i=1;i<=NumValues;i++)

  {

    NumberOfIterations++;

  }

  printf("Benötigte Iterationen - SERIELL: %llu\n",NumberOfIterations);

  NumberOfIterations = 0;


  int NumThreads = 0;

  #pragma omp parallel

  {

    #pragma omp master

    {

      NumThreads = omp_get_num_threads();

      printf("Anzahl Threads: %i\n",NumThreads);

    }

  }

  int *Threads = new int[NumThreads];


  //Parallele Variante

  #pragma omp parallel reduction(+: NumberOfIterations) shared(Threads)

  {

    #pragma omp for schedule(static)

    for(unsigned long long k=1;k<=NumValues;k++)

    {

      NumberOfIterations++;

      Threads[omp_get_thread_num()]++;

    }

  }


  for(int j=0;j<NumThreads;j++)

  {

    if(j<10)

    {

      printf("Thread  %i benötigte %llu Iterationen\n",j,Threads[j]);

    }

    else

    {

      printf("Thread %i benötigte %llu Iterationen\n",j,Threads[j]);

    }

  }


  printf("Benötigte Iterationen - PARALLEL: %llu\n",NumberOfIterations);

  NumberOfIterations = 0;


  printf("Maximalgrenzwert von unsigned long long: %llu\n",test);


  delete []Threads;


  getchar();

  return 0;

}

Kompiliert mit:

g++ -std=c++0x -m64 -fopenmp -Wall -Wextra -pedantic -pedantic-errors -O3 -s Test2.cpp -o Test2

Und nun der Output:

Benötigte Iterationen - SERIELL: 24000

Anzahl Threads: 24

Thread  0 benötigte 1000 Iterationen

Thread  1 benötigte 1000 Iterationen

Thread  2 benötigte 1000 Iterationen

Thread  3 benötigte 1000 Iterationen

Thread  4 benötigte 1000 Iterationen

Thread  5 benötigte 1000 Iterationen

Thread  6 benötigte 1000 Iterationen

Thread  7 benötigte 1000 Iterationen

Thread  8 benötigte 1000 Iterationen

Thread  9 benötigte 1000 Iterationen

Thread 10 benötigte 1000 Iterationen

Thread 11 benötigte 1000 Iterationen

Thread 12 benötigte 1000 Iterationen

Thread 13 benötigte 1000 Iterationen

Thread 14 benötigte 1000 Iterationen

Thread 15 benötigte 1000 Iterationen

Thread 16 benötigte 1000 Iterationen

Thread 17 benötigte 1000 Iterationen

Thread 18 benötigte 1000 Iterationen

Thread 19 benötigte 1000 Iterationen

Thread 20 benötigte 1000 Iterationen

Thread 21 benötigte 1000 Iterationen

Thread 22 benötigte 1000 Iterationen

Thread 23 benötigte 1000 Iterationen

Benötigte Iterationen - PARALLEL: 24000

Maximalgrenzwert von unsigned long long: 18446744073709551615

Demnach hat jeder Thread wie ursprünglich angenommen, auch nur (1/AnzThreads)-tel (bei mir also 1/24 = bei 24000 Iterationen total, nur 1000 Iterationen für jeden Thread) aller Iterationen übernommen und nicht jeder Thread parallel 24000.

Da das Gesamtergebnis dennoch 24000 ist, schlussfolgere ich daraus, dass meine "reduction(+: NumberOfIterations)"-Anweisung am Ende kein std::max(,) anwendet, sondern jedes Teilergebnis (1000) zu einem Ganzen (24000) summiert. Der Ablauf war also sehr wohl parallel.

Was stimmt nun also und was nicht?

Der eine sagt das, die anderen jenes und mein neues Beispiel-Prog "Test2" meine ursprüngliche Vermutung.

Grüße

Schlitzauge :):)

[flashpixx]

Du brauchst hier keine Schriftgrößen zu verwenden, um Deinen Fragen Nachdruck zu verleihen. Ein normal geschriebener Text reicht vollkommen aus.

Es scheint so, dass OpenMP im Gegensatz zu MPI generell bei Schleifen, sofern man nichts anderes angibt, direkt wie Du richtig sagst, die Schleife auftrennt und auf die Anzahl Threads verteilt. Finde ich zwar jetzt sehr seltsam, weil das durchaus Probleme machen kann, aber es scheint so zu sein.

Dann seh ich es nicht. Hab mir diese jetzt schon 8x etwas ausführlicher angeschaut.

http://openmp.org/mp-documents/OpenMP3.1-CCard.pdf Dort sind die Operatoren, die das Reduktion verwenden kann in der Tabelle auf der zweiten Seite angegeben.

Kann mir nicht einfach mal jemand ein kleines Beispiel für paralleles Hochzählen schreiben. Mit Code vor meiner Nase, kann ich so etwas wesentlich besser nachvollziehen. Wenns geht, bitte aber kein Pseudocode, da ich damit noch nicht so viel zu tun hatte. Direkte C/C++-Syntax sagt mir da schon mehr zu.

Ich werde Dir hier keinen fertigen C++ Code schreiben, so dass Du ihn nur compilieren musst, damit Du das verstehst. Pseudocode soll das Problem verdeutlichen, die Übersetzung in die Sprache mit der Du arbeitest, musst Du selbst leisten. Wenn ich Dir hier Beispiele fertig vorkaue, dann muss ich dafür extrem viel Zeit aufwenden, die ich nicht habe. Wenn Du es so nicht verstehst, dann müsstest Du ggf mal eine Anfrage stellen, so dass man sich preislich über einen Lehrgang o.ä. einigen kann.

Demnach hat jeder Thread wie ursprünglich angenommen, auch nur (1/AnzThreads)-tel (bei mir also 1/24 = bei 24000 Iterationen total, nur 1000 Iterationen für jeden Thread) aller Iterationen übernommen und nicht jeder Thread parallel 24000.

Ich war davon ausgegangen dass der MPI und OpenMP Standard hier identisch sind, es ist aber wohl nicht so.

@topic: Schau Dir noch einmal das Beispiel an und evtl übersetzt Du es auch einmal in Deinen C++ Code

uchar x = 0;


do parallel with x is private on each thread {

x= 253;

} 


reduce with + { x };

Versuche Dir einmal für das Minibeispiel die folgenden Fragen zu beantworten:

Was hat x für einen Wert nach dem Reduce bei einem oder mehr als einem Thread !?

Wenn das Reduce zu einer Bitweisen Verknüpfung wie z.B. & oder | änderst, wie sehen dann die Ergebnisse aus !?

Das Beispiel setzt bevor parallel gearbeitet wird eine unsigned char Variable und weist einfach in jedem Thread dieser den Wert 253 zu und führt dann ein Reduce auf (einmal eine arithmetische Addition und einmal ein boolsches and bzw oder). Überlege Dir ganz genau was mit der Variablen bei dem Reduce passiert und wie das mit der Anzahl der Threads zusammen hängt. Vor allem schau Dir einmal an wie groß ein uchar ist (sizeof liefert diese Information). Wichtig ist, dass Du das Beispiel einmal mit einem Thread gedanklich durchgehst und einmal mit mehr als einem, zwei Threads reichen da schon aus. Es soll Dir zeigen, was bei dem Reduce passieren kann und wie sich das dann auf Deine Programmierung auswirkt.

[Schlitzauge]

Du brauchst hier keine Schriftgrößen zu verwenden, um Deinen Fragen Nachdruck zu verleihen. Ein normal geschriebener Text reicht vollkommen aus.

Sollte nur der Übersicht dienen. Damit wollt ich nur noch mal herauskristallisieren, was mir im Moment am wichtigsten ist. Aber ich weiß schon, was de meinst.

http://openmp.org/mp-documents/OpenMP3.1-CCard.pdf Dort sind die Operatoren, die das Reduktion verwenden kann in der Tabelle auf der zweiten Seite angegeben.

Ich weiß, hab das ja und die ausführliche Doku dazu, 8x bzgl. meines Problem´s durchgeschaut.

Ich werde Dir hier keinen fertigen C++ Code schreiben, so dass Du ihn nur compilieren musst, damit Du das verstehst. Pseudocode soll das Problem verdeutlichen, die Übersetzung in die Sprache mit der Du arbeitest, musst Du selbst leisten. Wenn ich Dir hier Beispiele fertig vorkaue, dann muss ich dafür extrem viel Zeit aufwenden, die ich nicht habe. Wenn Du es so nicht verstehst, dann müsstest Du ggf mal eine Anfrage stellen, so dass man sich preislich über einen Lehrgang o.ä. einigen kann.

Es war lediglich eine Bitte, kein Muss.

Da es sowieso nur ein Beispiel-Code sein soll und kein "übernehmt ma meine Aufgaben", ist das nicht soooo wichtig. Ich selber bin die ganze Zeit am Probieren. Faul bin ich da gewiss nicht.

@topic: Schau Dir noch einmal das Beispiel an und evtl übersetzt Du es auch einmal in Deinen C++ Code

Code:

uchar x = 0;


do parallel with x is private on each thread {

x= 253;

} 


reduce with + { x };

Versuche Dir einmal für das Minibeispiel die folgenden Fragen zu beantworten: Was hat x für einen Wert nach dem Reduce bei einem oder mehr als einem Thread !? Wenn das Reduce zu einer Bitweisen Verknüpfung wie z.B. & oder | änderst, wie sehen dann die Ergebnisse aus !?

Das ist mir schon bewusst, dass in diesem Fall der Wertebereich überschritten werden kann bzw. wird. Das trifft aber auf mein Beispiel nicht zu, da die Iterationen fleißig auf alle Threads verteilt werden und am Ende zu einem reduziert werden, indem die Teilergebnisse zusammenaddiert werden. Ich lasse zwar in meinem Beispiel nicht die Zählvariable zu Einem reduzieren, aber eine separate Variable, die lediglich wertmäßig die Größe der Zählvariablen annimmt. Bzgl. des Pseudocode von Dir. Der würde in C/C++ mit OpenMP doch so ausschauen:

unsigned char x = 0;


#pragma omp parallel for reduction(x)

for(int i = 0;i<omp_get_num_threads();i++)

{

  x= 253;

}

, richtig?

Grüße

Schlitzauge :):)

[flashpixx]

Das ist mir schon bewusst, dass in diesem Fall der Wertebereich überschritten werden kann bzw. wird.

Prüfe es einmal genau nach, wenn das bei Deiner "NumberOfIterations" Variablen passieren würde, wäre das ein Problem. Das würde jedenfalls erklären, warum das Programm dann nicht beendet wird, denn innerhalb eines Threads eine undefinierter Abbruch erfolgt, aber das Threadding darauf wartet, dass alle Threads korrekt beendet werden, um das Reduce durch zu führen, wird dieser Zustand nie erreicht, denn alle Threads warten und einer wurde undefiniert beendet. Die Folge das Programm hängt.

Ich lasse zwar in meinem Beispiel nicht die Zählvariable zu Einem reduzieren, aber eine separate Variable, die lediglich wertmäßig die Größe der Zählvariablen annimmt.

Sollte es, schau es Dir aber im Debugger ggf einmal nach

Bzgl. des Pseudocode von Dir. Der würde in C/C++ mit OpenMP doch so ausschauen:

unsigned char x = 0;


#pragma omp parallel for reduction(x)

for(int i = 0;i<omp_get_num_threads();i++)

{

  x= 253;

}

, richtig?

Nein, jeder Thread für exakt eine Operation aus, die Zuweisung x = 253; Von einer Schleife habe ich nichts gesagt.