3. OpenMP: Verständnisfrage zu Vektoren, Matrizen (2D, 3D) und Arrays (2D, 3D)

OpenMP: Verständnisfrage zu Vektoren, Matrizen (2D, 3D) und Arrays (2D, 3D)

  • S

    Hi COM,

    also Parallelisieren mittels OpenMP funktioniert mittlerweile wunderbar.
    Wie das Addieren, Subtrahieren, Multiplizieren und Dividieren mit Vektoren bzw. Matrizen funktioniert ist mir auch bewusst (also mathematisch). Ich glaube auch, dass ich eine erfolgreiche Vektor- bzw. auch Matrix-Addition programmiert habe, soweit so gut.

    Ich habe allerdings gerade ein Verständnisproblem zwischen Arrays, Vektoren und Matrizen.

    Hier erstmal der Code einer stinknormalen 1D-Vektoraddition (Skalare Addition):
    1DVecAdd64.cpp:

    const uint64_t NumValues = 800000000ULL;
uint64_t a[NumValues] = {0ULL}, \
         b[NumValues] = {0ULL}, \
         c[NumValues] = {0ULL};

//serielle Variante:
for(uint64_t i=0ULL;i<NumValues;++i)
{
  c[i] = a[i] + b[i];
}

//parallele Variante:
#pragma omp parallel default(none) shared(std::cout, a, b, c)
{
  #pragma omp flush
  #pragma omp for schedule(static)
  for(uint64_t j=0ULL;j<NumValues;++j)
  {
    c[j] = a[j] + b[j];
  }
}

    Funktioniert soweit auch wunderbar. Nun wollte ich aber mal in weitere Dimensionen vordringen, sprich 2D, 3D und 4D.
    Doch jetzt hab ich das Problem den Sinn und Zweck von mehrdimensionalen Arrays zu verstehen. Dazu mal ein Bsp.-Programm, wie ich eine 2D-Vektoraddition umgesetzt habe:
    2DVecAdd64_1.cpp:

    const uint64_t NVdim1 = 400000000ULL, NVdim2 = 400000000ULL;
//NVdim1: x (col)
//NVdim2: y (row)
uint64_t a[NVdim1][NVdim2] = {{0ULL}}, \
         b[NVdim1][NVdim2] = {{0ULL}}, \
         c[NVdim1][NVdim2] = {{0ULL}};

//serielle Variante:
for(uint64_t i=0ULL;i<NVdim1;++i)
{
  for(uint64_t j=0ULL;j<NVdim2;++j)
  {
    c[i][j] = a[i][j] + b[i][j];
  }
}

//parallele Variante:
#pragma omp parallel default(none) shared(std::cout, a, b, c)
{
  #pragma omp flush
  #pragma omp for schedule(static)
  for(uint64_t i=0ULL;i<NVdim1;++i)
  {
    for(uint64_t j=0ULL;j<NVdim2;++j)
    {
      c[i][j] = a[i][j] + b[i][j];
    }
  }
}

    Was ist da der Unterschied zu vorher, also zur 1D-Variante?
    Für mich passiert hier genau das selbe: Skalare Additionen,
    nur liegen hier die Skalare (Array-Elemente) nicht mehr in einem 1D-Array, sondern in einem 2D-Array vor. Tatsache ist aber, dass über die Indizes jeweils immer nur eine normale Variable (Skalar) angesteuert wird, letztendlich also das gleiche passiert, wie im obigen Programm 1DVecAdd64.
    Was ich aber möchte ist eine klassische 2D-Vektoraddition (also eine Addition von zweikomponentigen Vektoren der Form v_n(x,y)). Ich möchte also folgendes damit berechnen können:

    v1(x1,y1) + v2(x2,y2) = v3(x1+x2,y1+y2) = v3(x3,y3)
Bsp.:
v1(5,7) + v2(2,3) = v3(5+2,7+3) = v3(7,10)

    Also die komponentenweise Addition.

    Ich sehe in meinem 2DVecAdd64_1-Prog aber nur die gleiche Berechnung wie im 1DVecAdd64-Prog, eine Addition von Skalaren. Weshalb mich das verwirrt?:
    Gerechnet wird stets nur mit Skalaren (1D-Vektoren), was den einzelnen Komponenten mehrkomponentiger (mehrdimensionaler) Vektoren entspricht.
    Ob ich mir jetzt ein eindimensionales Array hernehme:

    1DArray[25];

    oder ein zweidimensionales Array:

    2DArray[5][5];

    ist doch egal. Das sind in meinen Augen immer noch die gleichen Daten(mengen), lediglich etwas anders angeordnet und nun anders adressierbar. Gerechnet wird beim 2DVecAdd64_1-Prog letztenendes so:

    A_ArrayElement+B_ArrayElement = C_ArrayElement;

    Der Unterschied zwischen beiden Progs ist einfach nur die Art der Adressierung der Elemente (beim 1D-Prog gibt es jeweils nur einfache Indize, beim 2D-Prog halt zweifache Indize, schlussendlich wird aber jeweils immer nur ein Element (Skalar) angesprochen).

    Damit realisiere ich aber nicht das, was ich mir vorgestellt habe (glaube ich zumindest). Also habe ich es mal mittels eigenem Datentyp realisiert:
    2DVecAdd64_2.cpp:

    struct V2D //2D-Vektor
{
  public:
    uint64_t x, y;
    V2D(uint64_t X = 0ULL, uint64_t Y = 0ULL):x(X),y(Y){}
    ~V2D(){};
};

const uint64_t Num2DVecs = 400000000ULL; //Anzahl 2D-Vektoren
struct V2D a[Num2DVecs], \
           b[Num2DVecs], \
           c[Num2DVecs];

//serielle Variante:
for(uint64_t i=0ULL;i<Num2DVecs;++i)
{
  c[i].x = a[i].x + b[i].x;
  c[i].y = a[i].y + b[i].y;
}

//parallele Variante:
#pragma omp parallel default(none) shared(std::cout, a, b, c)
{
  #pragma omp flush
  #pragma omp for schedule(static)
  for(uint64_t j=0ULL;j<Num2DVecs;++j)
  {
    c[j].x = a[j].x + b[j].x;
    c[j].y = a[j].y + b[j].y;
  }
}

    Damit kann ich genau das realisieren / so rechnen, wie eben beschrieben.
    Jetzt könnte ich das für 3D und 4D so weiter machen, doch irgendwie werde ich nicht daraus schlau.

    Meine Frage ist nun, was richtig ist, um mit 2D-Vektoren (Vektor mit zwei Komponenten x und y) zu rechnen? (und warum).
    Ich meine, die Lösung mit eigenem Datentyp funktioniert und ist richtig.
    Doch wie müsste die Lösung aussehen, wenn ich das ausschließlich mit klassischen Arrays umsetzen möchte? Um es nochmal deutlich zu machen: ich möchte keine 1D-Vektor/Skalar-Addition:

    a+b=c

    , sondern eine 2D-Vektor-Addition (wo also jeweils einzeln die [x,y] Komponenten zweier solcher 2D-Vektoren zu Ergebniskomponenten eines 2D-Ergebnisvektors errechnet werden):

    v1(x1,y1) + v2(x2,y2) = v3(x1+x2,y1+y2) = v3(x3,y3)

    Ich habe folgendes versucht:
    2DVecAdd64_3.cpp

    const uint64_t NVdim1 = 400000000ULL, NVdim2 = 400000000ULL;
//NVdim1 = x (col)
//NVdim2 = y (row)
uint64_t a[NVdim1][NVdim2] = {{0ULL}}, \
         b[NVdim1][NVdim2] = {{0ULL}}, \
         c[NVdim1][NVdim2] = {{0ULL}};

//serielle Variante:
for(uint64_t i=0ULL;i<NVdim1;++i)
{
  for(uint64_t j=0ULL;j<NVdim2;++j)
  {
    c[i][j] = a[i][j] + b[i][j];
  }
}

omp_set_nested(2);
//parallele Variante:
#pragma omp parallel default(none) shared(std::cout, a, b, c)
{
  #pragma omp flush
  #pragma omp for collapse(2) schedule(static)
  for(uint64_t i=0ULL;i<NVdim1;++i)
  {
    for(uint64_t j=0ULL;j<NVdim2;++j)
    {
      c[i][j] = a[i][j] + b[i][j];
    }
  }
}

    Der gleiche Fall wieder. Was bringt mir das, wenn doch nur wieder Skalare miteinander addiert werden???
    Meine Vermutung ist ja, dass ich etwas Grundlegendes verwechsle.
    Mittels Array kann man einen 2D-Vektor (zwei Komponenten) wie folgt darstellen:

    array[2];

    wobei das array[] der Vektor ist und das Element mit Index 0 (array[0]) die x-Komponente und das Element mit Index 1 die y-Komponente.
    An sich liegen diese Komponenten aber erst einmal gleichwertig hintereinander.

    Wäre dann ein zweidimensionales Array:

    array2D[2][2]

    quasi zwei solcher Vektoren?
    Liegt es dann an mir / am Programmierer, jeweils die richtigen Datenelemente als x- und y-Komponenten zu interpretieren (etwa bei der Ausgabe oder beim Algorithmieren)?
    Das würde dann auch einiges erklären, wobei mir der Weg mittels struct dann doch optisch ansprechender und verständlicher erscheint.

    Ich danke vielmals im Voraus.

    Grüße

    Schlitzauge 🙂 🙂 🙂 🙂

    0
  • Mod

    😕 😕 😕

    Du hattest es am Anfang richtig. Ich verstehe deine Schlussfolgerungen nicht. Du schreibst doch selber:

    (x1,y1) + (x2,y2) = (x1+x2,y1+y2)

    Was ist denn x1+x2, wenn nicht eine skalare Addition?

    Und was hat das alles mit OpenMP zu tun, außer, dass in deinem Programm OpenMP vorkommt?

    0
  • S

    Hm. Ja, das erste Prog, die 1DVecAdd64.cpp funktioniert ja auch.
    Dort ist es ja auch gewollt, dass lediglich Skalare miteinander addiert werden, immerhin ist es ja auch nur eine Addition zweier 1D-Vektoren (Vektoren mit nur einer Komponente = Skalar; 1D-Vektoraddition / Skalare Addition). Bei diesem Prog wird ja auch genau das gerechnet:

    a+b=c
Bsp.:
5+5=10

    Mir geht es aber um den Übergang zu weiteren Dimensionen, sprich 2D und später auch 3D/4D.

    Ich habe dazu zwei bzw. drei Programme vorliegen. Einmal die 2DVecAdd64_1.cpp bzw. 2DVecAdd64_3.cpp (wo ich versucht habe, das mit zweidimensionalen Arrays zu realisieren) und dann noch die 2DVecAdd64_3.cpp (wo das Ganze mittels eigenem Datentyp umgesetzt ist).
    Bei ersteren beiden genannten, rechne ich aber irgendwie auch nur wie oben bei der 1D-Variante.
    Ich möchte aber gerne 2D-Vektoren (also Vektoren mit zwei Komponenten x und y) miteinander addieren:

    v1(x1,y1) + v2(x2,y2) = v3(x1+x2,y1+y2) = v3(x3,y3)
Bsp.:
v1(5,7) + v2(2,3) = v3(5+2,7+3) = v3(7,10)

    Wie realisiere ich dass mittels Array´s bzw. zweidimensionaler Arrays?
    Sind da meine Lösungen dazu richtig? Ich meine, die Lösung mit eigenem Datentyp (struct; 2DVecAdd64_2) ermöglicht genau das, anders als die anderen, wo lediglich Skalare miteinander addiert werden. Ich weiß auch, dass im Prog mit eigenem Datentyp letztendlich jeweils Skalare miteinander addiert werden (genauer jeweils die x -und y-Komponenten zweier 2D-Vektoren), quasi das 1DVecAdd64.cpp-Prog in einer Iteration zweimal angewandt. Ich möchte das 2DVecAdd64_2.cpp-Programm aber gerne allein mit Arrays (vorzugsweise mit zweidimensionalen Arrays) realisieren.

    Meine Vermutung ist nun, dass ich irgendwas in der Definition von Arrays / mehrdimensionalen Arrays und den mathematischen Vektoren und Matrizen verwechsle. Ich seh es nur irgendwie nicht.

    SeppJ schrieb:

    Und was hat das alles mit OpenMP zu tun, außer, dass in deinem Programm OpenMP vorkommt?

    Dazu komme ich erst noch. Ich wollte nicht gleich zu Begin mit Fragen über Fragen ankommen. Primär steht mir mich jetzt das Verständnis bzgl. mathematischer Vektoren und Matrizen und mehrdimensionalen Arrays im Vordergrund, also bei der technischen / programmierbaren Umsetzung. Die entsprechenden Fragen zu OpenMP werden gewiss noch kommen.

    Grüße

    Schlitzauge 🙂 🙂 🙂 🙂

    0
  • Mod

    Also vermutlich fehlt dir da ganz einfach gerade der mathemtische Durchblick. Eventuell suchst du auch valarrays. Jedenfalls hast du nur wiederholt, was du im ersten Beitrag gesagt hast, meine Antwort ändert sich daher nicht.

    0
  • K

    a) Die Dimension eines Arrays hat erstmal wenig mit der Dimension eines (mathematischen) Raumes (in dem Vektoren leben) zu tun.
    b) Und wie addiert man Vektoren in Mathe? Na indem sie komponentenweise addiert werden. Warum sollte beim Programmieren anders sein als in der Mathematik?

    0
  • S

    Nein nein, mathematisch kann ich das ja.
    Ich möchte es halt gerne programmiertechnisch umsetzen.

    Bzgl. meines Vorhabens, welches dieser beiden Programme realisiert das dann?:
    2DVecAdd64_2.cpp

    struct V2D //2D-Vektor
{
  public:
    uint64_t x, y;
    V2D(uint64_t X = 0ULL, uint64_t Y = 0ULL):x(X),y(Y){}
    ~V2D(){};
};

const uint64_t Num2DVecs = 400000000ULL; //Anzahl 2D-Vektoren
struct V2D a[Num2DVecs], \
           b[Num2DVecs], \
           c[Num2DVecs];

//serielle Variante:
for(uint64_t i=0ULL;i<Num2DVecs;++i)
{
  c[i].x = a[i].x + b[i].x;
  c[i].y = a[i].y + b[i].y;
}

//parallele Variante:
#pragma omp parallel default(none) shared(std::cout, a, b, c)
{
  #pragma omp flush
  #pragma omp for schedule(static)
  for(uint64_t j=0ULL;j<Num2DVecs;++j)
  {
    c[j].x = a[j].x + b[j].x;
    c[j].y = a[j].y + b[j].y;
  }
}

    oder

    2DVecAdd64_3.cpp

    const uint64_t NVdim1 = 400000000ULL, NVdim2 = 400000000ULL;
//NVdim1 = x (col)
//NVdim2 = y (row)
uint64_t a[NVdim1][NVdim2] = {{0ULL}}, \
         b[NVdim1][NVdim2] = {{0ULL}}, \
         c[NVdim1][NVdim2] = {{0ULL}};

//serielle Variante:
for(uint64_t i=0ULL;i<NVdim1;++i)
{
  for(uint64_t j=0ULL;j<NVdim2;++j)
  {
    c[i][j] = a[i][j] + b[i][j];
  }
}

omp_set_nested(2);
//parallele Variante:
#pragma omp parallel default(none) shared(std::cout, a, b, c)
{
  #pragma omp flush
  #pragma omp for collapse(2) schedule(static)
  for(uint64_t i=0ULL;i<NVdim1;++i)
  {
    for(uint64_t j=0ULL;j<NVdim2;++j)
    {
      c[i][j] = a[i][j] + b[i][j];
    }
  }
}

    ???

    Genauer gefragt: das erste Prog mit eigenem Datentyp ermöglicht genau mein Vorhaben, die Addition zwei zweikomponentiger Vektoren. Beim letzteren bin ich mir da aber nicht ganz sicher, ob das da auch so ist, da es auf den ersten Blick hin, das Gleiche macht, wie mein 1DVecAdd64.cpp-Prog (siehe ganz oben). Ich verwechsle da anscheinend etwas zwischen der Dimension eines Arrays und der Dimension eines mathematischen Raumes (*knivil). Wenn mir da zum besseren Verständnis jemand den Unterschied genauer erklären könnte, wäre das sehr hilfreich. Ich zweifle gerade daran den Sinn und Zweck mehrdimensionaler Arrays zu erkennen. Theoretisch könnte ich ja auch alles mittels eindimensionaler Arrays und / oder struct/class realisieren. Ich stelle übrigens nur fragende Schlussfolgerungen auf, mit der Hoffnung, dass jemand diese bejaht (wenn richtig) oder dementiert (wenn falsch). Ist ja nicht so, dass ich mir überhaupt keine Gedanken darüber mache. Mit mehrdimensionalen Arrays hatte ich bislang recht wenig am Hut, von daher fehlt mir jetzt das Verständnis dahingehend, mathematisch allerdings kein Problem.

    0
  • K

    Wenn mir da zum besseren Verständnis jemand den Unterschied genauer erklären könnte, wäre das sehr hilfreich.

    Array und Dimension eines Raumes haben erstmal nichts miteinander zu tun. Du koenntest auch fragen, wo der Unterschied zwischen Liebe und Volumen liegt.

    Theoretisch könnte ich ja auch alles mittels eindimensionaler Arrays [..] realisieren

    Ja, aber die Indexierung waere anders. Mache dir einfach klar, was der Unterschied zwischen int a[5][5] und int a[25] ist.

    Mit mehrdimensionalen Arrays hatte ich bislang recht wenig am Hut, von daher fehlt mir jetzt das Verständnis dahingehend, mathematisch allerdings kein Problem

    Du versuchst Konzept A auf Konzept B abzubilden, die erstmal nichts miteinander zu tun haben.

    Darueber hinaus ist das Schwachsinn:

    const uint64_t NVdim1 = 400000000ULL, NVdim2 = 400000000ULL; 
uint64_t a[NVdim1][NVdim2] = {{0ULL}};

    Wieviel Speicher belegt Array a in diesem Fall?

    0
  • S

    knivil schrieb:

    Ja, aber die Indexierung waere anders. Mache dir einfach klar, was der Unterschied zwischen int a[5][5] und int a[25] ist.

    Das ist es ja. Ich sehe außer in der Adressierungsart und eventuell der Speicheranordnung, keinen Unterschied. Ob ich jetzt auf a[25] einfach iteriere (mit einfacher Indexierung) oder auf a[5][5] zweifach (nested loops; mit zweifacher Indexierung), ist doch egal, letztendlich bleibt die Arbeit gleich: 25 Iterationen. Die 25 Elemente von a[25] liegen bei a[5][5]jetzt halt zeilenweise aufgeteilt im Speicher. Es geht darum, dass ich anwendungsspezifische Beispiele für Nested Loops mittels OpenMP schreiben möchte. Der Mehraufwand der dadurch aber entsteht, relativiert sich nicht, wenn ich das Ganze auch mit einem einfachen Array umsetzen kann, wo der Aufwand zur Parallelisierung mittels OpenMP sehr gering ist. Auf jeden Fall würde es mich schon interessieren, wozu mehrdimensionale Arrays dann gut bzw. gedacht sind und wie ich mehrdimensionale Vektoren eines mathematischen Raumes, mit mehrdimensionalen Arrays umsetzen kann.

    knivil schrieb:

    Darueber hinaus ist das Schwachsinn:

    const uint64_t NVdim1 = 400000000ULL, NVdim2 = 400000000ULL;
uint64_t a[NVdim1][NVdim2] = {{0ULL}};

    Wieviel Speicher belegt Array a in diesem Fall?

    ((((400000000*2)*16 Bytes):1024):1024):1024 = 11,92 GByte
    * 3 2D-Vektoren = 35,76 GByte.
    Was is daran Schwachsinn? Sicher, für die gezeigten Beispiele, ergibt das wenig Sinn. Die große Anzahl ist auch nur dazu da, um die Zeitunterschiede zwischen serieller und paralleler Ausführung deutlicher zu machen.
    Faktisch schreibe ich wissenschaftliche Anwendungen für den Astrophysikalischen Bereich. An unserer Forschungseinrichtung ist ein solch großer Input an Daten der Regelfall. CPU- und Speicher (RAM, SDD/HDD) steht mehr als genug zur Verfügung. Von daher kratzen mich die rund 36 GByte RAM-Belegung nicht.
    Natürlich könnte ich weitere Berechnungen in die Schleifen einbauen, um das ganze zu verzögern oder eine weitere Schleife drumherum kapseln, sodass das öfters ausgeführt wird, aber ich wollts so wie es ist, dabei belassen. Es dient ja nur zu Demonstrationszwecken.

    0
Anmelden zum Antworten