OpenMP: Schleife parallelisieren, die auf einen vector pusht

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.

*john 0

opppppp schrieb:

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?

Gar nicht!
Abgesehen von dem korrekten Umgang mit dem Vector (reserve verwenden), ist das schlußendlich ein Stream Problem, so daß man es auf einem Nicht-NUMA-System überhaupt nicht sinnvoll parallelisieren kann. Die Geschwindigkeit hängt ausschließlich davon ab, wie schnell die Daten aus dem Speicher gelesen und wieder geschrieben werden können. Bei einem NUMA-System kann man unter ganz bestimmten Bedingungen die Sache beschleunigen, aber dazu müssen die einzelnen Speicherblöcke auf verschiedenen NUMA-Knoten liegen.

dot

Da die einzelnen Aufrufe von verarbeite(a) wohl unabhängig voneinander jeweils nur auf einem Element des vectors arbeiten, kann man zumindest die parallelisieren. Einfach den vector vorher auf die richtige Größe bringen und dann kann man theoretisch sämtliche Elemente parallel bearbeiten!?
Aus der Tatsache dass er push_back verwendet, würde ich zumindest schließen, dass es ihm sowieso nicht um die parallelisierung der Einfügeoperationen ging...

vielleicht solltet ihr mal den thread durchlesen, statt alles zu wiederholen...

*john 0

dot schrieb:

Da die einzelnen Aufrufe von verarbeite(a) wohl unabhängig voneinander jeweils nur auf einem Element des vectors arbeiten, kann man zumindest die parallelisieren.

So schnell die Antwort geschrieben, ja natürlich hast recht. Allerdings muß dann der Aufwand hinreichend groß sein.

dot

~john schrieb:

dot schrieb:

Da die einzelnen Aufrufe von verarbeite(a) wohl unabhängig voneinander jeweils nur auf einem Element des vectors arbeiten, kann man zumindest die parallelisieren.

So schnell die Antwort geschrieben, ja natürlich hast recht. Allerdings muß dann der Aufwand hinreichend groß sein.

Korrekt, davon ging ich natürlich aus, denn ansonsten würde das ganze Vorhaben diese Schleife zu parallelisieren selbstverständlich überhaupt keinen Sinn machen...

rapso

Michael E. schrieb:

Der C++98-Standard sagt was anderes:

§8.5.5 schrieb:

...

war mir nicht gelaeufig, sorry.

Michael E. schrieb:

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.

optimierte memset routinen koennen bei den meisten CPUs recht nah an die theoretische speicherbandbreite mit nur einem core kommen. hast du ausgefallene hardware z.b. einen 12core opteron 61xx NUMA speicher, wirst du vermutlich zwei cores brauchen die jeweils fuer ihren speicherbereich zustaendig sind, sonst bist du am verbindungsbus limitiert (HyperTransport).
Bei einem i7 muestest du in etwa 80-100GB/s speicherbandbreite haben, damit du core-limitiert bist (und dann liegt es am bus zwischen L2 und L1).