OpenMP: Schleife parallelisieren, die auf einen vector pusht

Ich habe eine Schleife:

vector<int> v;

for (auto a = L.begin(); a != L.end(); ++a)
{
    v.push_back(verarbeite(a));
}

Wie parallelisiere ich das mit OpenMP 3.1?

dot

Gar nicht, das macht keinen Sinn. Du kannst die Aufrufe von verarbeite() evtl. parallelisieren, aber das pushen in den vector wird immer ein Synchronisationspunkt sein, einfach weil du einen vector nicht parallel verändern kannst.

Und wenn ich #AnzahlThreads viele vector<int>'s erzeugen würde?

dot

Aber du musst doch eigentlich gar nicht pushen, du kannst den vector doch einfach vorher auf die richtige Größe resizen und dann einfach nur eine Schleife machen die in jedes Element das entsprechende Ergebnis von verarbeite() schreibt...

Hab ich gemacht, aber jetzt ist das Programm viel langsamer

Michael E.

dot schrieb:

Aber du musst doch eigentlich gar nicht pushen, du kannst den vector doch einfach vorher auf die richtige Größe resizen und dann einfach nur eine Schleife machen die in jedes Element das entsprechende Ergebnis von verarbeite() schreibt...

Welchen Sinn hat das? Auf diese Weise musst du erstmal alle Elemente auf 0 setzen, bevor ihnen der richtige Wert zugewiesen wird. Ein reserve() kann allerdings nützlich sein.

dot

Ganz einfach: Mit einem push_back kann er nicht parallel auf dem vector arbeiten. Wenn die initialisierung ein Problem ist, dann eben einfach

std::unique_ptr<int[]> v(new int[L.size()]);

rapso

Michael E. schrieb:

dot schrieb:

Aber du musst doch eigentlich gar nicht pushen, du kannst den vector doch einfach vorher auf die richtige Größe resizen und dann einfach nur eine Schleife machen die in jedes Element das entsprechende Ergebnis von verarbeite() schreibt...

Welchen Sinn hat das?

unnoetige resizes die implizit in push gemacht werden wegzulassen, sobald diese "shared" bereich weg ist, koennte man theoretisch so loesen (sofern "verarbeite" keine races hat und der iterator von L nicht langsam ist)

vector<int> v;
const size_t Size = L.end()-L.begin();
v.resize(Size);
#pragma omp parallel for
for(size_t a=0;a<Size;a++)
    v[a]=verarbeite(L.begin()+a);

Auf diese Weise musst du erstmal alle Elemente auf 0 setzen

wieso?

bevor ihnen der richtige Wert zugewiesen wird. Ein reserve() kann allerdings nützlich sein.

reserve hat das problem, dass pro iteration trotzdem auf "size" zugegriffen werden wuerde, du muesstest quasi so arbeiten

vector<int> v;
const size_t Size = L.end()-L.begin();
v.reserve(Size);
#pragma omp parallel for
for(size_t a=0;a<Size;a++)
{
    auto Tmp=verarbeite(L.begin()+a);
    #pragma omp critical
    {
      v.push_back(Tmp);
    }
}

(falls der compiler meckert, liegt es vermutlich daran, dass er size_t nicht mag, dann muss man die loop variable und begin/end int "int" umwandeln/casten)

falls die einzelnen "Verarbeite" schritte sehr unterschiedliche laufzeiten haben und man dynamisches load balancing moechte, kann man das pragma erweitern in

#pragma omp parallel for schedule(dynamic,X)

wobei X die granularitaet ist und afaik zur compiletime bekannt sein muss (sprich: trag eine zahl ein z.b. 4)

opppppp schrieb:

Hab ich gemacht, aber jetzt ist das Programm viel langsamer

Wieviele elemente sind in L?

whatsthematterwithyou schrieb:

opppppp schrieb:

Hab ich gemacht, aber jetzt ist das Programm viel langsamer

Wieviele elemente sind in L?

24

und wie lang braucht verarbeite?

Vermutlich sehr kurz.

SeppJ

Und was braucht länger: 12x verarbeite oder Thread erstellen, Aufgaben aufteilen, Ende koordinieren, Ergebnisse zusammenführen, Thread beenden? Ich glaubt, ich kenne die Antwort schon.

Vermutlich viel kürzer als Threads erzeugen/starten?

Michael E.

rapso schrieb:

Auf diese Weise musst du erstmal alle Elemente auf 0 setzen

wieso?

Weil resize neue Elemente im vector erstellt. Wenn du resize nur einen Parameter gibst, werden die neuen Elemente default-initialisiert.

Mal ne andere Frage, davon hab ich keine Ahnung: Kann es sein, dass der vector in einen schnelleren Cache getan werden kann, wenn man nur von einem Kern aus auf den vector zugreift? Denn die schnellsten Caches sind nicht shared.

Michael E. schrieb:

rapso schrieb:

Auf diese Weise musst du erstmal alle Elemente auf 0 setzen

wieso?

Weil resize neue Elemente im vector erstellt. Wenn du resize nur einen Parameter gibst, werden die neuen Elemente default-initialisiert.

http://www.cplusplus.com/reference/stl/vector/resize/

If not specified, the default constructor is used.

Wäre ja wirklich dämlichlangsam, wenn die alles auf 0 setzen.

Michael E.

Dein Link bestätigt mich doch:

finally it extends its size to 12 with their default values (for int elements this is zero).

Das ist ja dämlich. Warum machen die sowas?

rapso

Michael E. schrieb:

rapso schrieb:

Auf diese Weise musst du erstmal alle Elemente auf 0 setzen

wieso?

Weil resize neue Elemente im vector erstellt. Wenn du resize nur einen Parameter gibst, werden die neuen Elemente default-initialisiert.

default initialisierung von int bedeutet keine initialisierung (sprich: was auch immer vorher im speicher stand).
danach laeuft eine schleife die jeden wert anhand von "verarbeite" ueberschreibt.
ich versteh nicht ganz wozu da etwas mit 0 initialisiert werden muss.

Mal ne andere Frage, davon hab ich keine Ahnung: Kann es sein, dass der vector in einen schnelleren Cache getan werden kann, wenn man nur von einem Kern aus auf den vector zugreift? Denn die schnellsten Caches sind nicht shared.

ja, es ist schneller mit einem core 24werte zu schreiben als mit mehreren die um cachelines kaempfen, allerdings duerfte das schreiben von 24 int nicht das performance kritische sein.

SeppJ schrieb:

Und was braucht länger: 12x verarbeite oder Thread erstellen, Aufgaben aufteilen, Ende koordinieren, Ergebnisse zusammenführen, Thread beenden?

ja, waere echt dumm, deswegen lieber gleich openmp verwenden um den bloedsinn nicht zu machen, wie der thread starter eigentlich will.

Michael E.

rapso schrieb:

default initialisierung von int bedeutet keine initialisierung (sprich: was auch immer vorher im speicher stand).

Der C++98-Standard sagt was anderes:

§8.5.5 schrieb:

To zero-initialize storage for an object of type T means:

- if T is a scalar type (3.9), the storage is set to the value of 0 (zero) converted to T;
[...]

To default-initialize an object of type T means:
- if T is a non-POD class type [...]
- if T is an array type [...]
- otherwise, the storage for the object is zero-initialized.

§8.5.7 schrieb:

An object whose initializer is an empty set of parantheses, i.e., (), shall be default-initialized.

rapso schrieb:

ja, es ist schneller mit einem core 24werte zu schreiben als mit mehreren die um cachelines kaempfen, allerdings duerfte das schreiben von 24 int nicht das performance kritische sein.

Mal ganz unabhängig von diesem Fall, denn bei 24 Werten braucht man gar nicht zu diskutieren.