C ++ OpenMP Parallel For-Schleife – Alternativen zu std :: vector

Basierend auf diesem Thread, OpenMP und STL-Vektor , welche Datenstrukturen sind gute Alternativen für einen gemeinsamen std :: Vektor in einer parallelen for-Schleife? Der Hauptaspekt ist Geschwindigkeit und der Vektor muss möglicherweise während der Schleife skaliert werden.

Die Frage, die Sie verknüpfen, sprach über die Tatsache, dass “dieser STL-Vektorcontainer in der Situation, in der mehrere Threads in einen einzelnen Container schreiben, nicht Thread-sicher ist”. Dies ist nur dann richtig, wenn Sie Methoden aufrufen, die eine Neuzuordnung des zugrunde liegenden Arrays, das std::vector enthält, verursachen. push_back() , pop_back() und insert() sind Beispiele für diese gefährlichen Methoden.

Wenn Sie eine threadsichere Neuzuweisung benötigen, bietet Ihnen der Bibliothek- Intel-Thread-Baustein gleichzeitige Vektorcontainer . Sie sollten tbb :: concurrent_vector nicht in einzelnen Thread-Programmen verwenden, da die Zeit, die für den Zugriff auf zufällige Elemente benötigt wird, höher ist als die Zeit, die std :: vector benötigt, um dasselbe zu tun (was O (1) ist). Gleichzeitige push_back() , pop_back() , insert() auf threadsichere Weise, selbst wenn eine Neuzuweisung erfolgt.

EDIT 1: Die Folien 46 und 47 der folgenden Intel-Präsentation geben ein anschauliches Beispiel für die gleichzeitige Neuzuweisung unter Verwendung von tbb :: concurrent_vector

EDIT 2: Übrigens, wenn Sie anfangen, Intel Tread Building Block zu verwenden (es ist Open Source, es funktioniert mit den meisten Compilern und es ist viel besser integriert mit C ++ / C ++ 11 Features als openmp), dann brauchen Sie nicht um openmp zu verwenden, um eine Parallele zu erstellen, Hier ist ein schönes Beispiel von Parallele für die Verwendung von tbb.

Ich denke, dass Sie std::vector mit OpenMP die meiste Zeit verwenden können und immer noch gute performance haben. Der folgende Code füllt beispielsweise std::vectors parallel und kombiniert sie dann am Ende. Solange Ihre Haupt-Loop / Fill-function der Flaschenhals ist, sollte dies im Allgemeinen gut funktionieren und Thread-sicher sein.

 std::vector vec; #pragma omp parallel { std::vector vec_private; #pragma omp for nowait //fill vec_private in parallel for(int i=0; i<100; i++) { vec_private.push_back(i); } #pragma omp critical vec.insert(vec.end(), vec_private.begin(), vec_private.end()); } 

Bearbeiten:

OpenMP 4.0 ermöglicht benutzerdefinierte Reduzierungen mit #pragma omp declare reduction . Der obige Code kann mit to vereinfacht werden

 #pragma omp declare reduction (merge : std::vector : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end())) std::vector vec; #pragma omp parallel for reduction(merge: vec) for(int i=0; i<100; i++) vec.push_back(i); 

Edit: Was ich bisher gezeigt habe, füllt den Vektor nicht in der richtigen Reihenfolge. Wenn die Reihenfolge zählt, kann dies so gemacht werden

 std::vector vec; #pragma omp parallel { std::vector vec_private; #pragma omp for nowait schedule(static) for(int i=0; i 

Dies vermeidet das Speichern eines std :: -Vektors für jeden Thread und das anschließende Verschmelzen seriell außerhalb des parallelen Bereichs. Ich habe von diesem "Trick" hier erfahren. Ich bin nicht sicher, wie dies (oder wenn es überhaupt möglich ist) für benutzerdefinierte Reduktionen. . Dies ist mit benutzerdefinierten Reduzierungen nicht möglich.

Ich habe gerade gemerkt, dass der kritische Abschnitt nicht notwendig ist, was ich aus dieser Frage herausgelesen habe: parallel-kumulativ-Präfix-summiert-in-openmp-kommunizierend-Werte-zwischen-thread . Diese Methode erhält auch die richtige Reihenfolge

 std::vector vec; size_t *prefix; #pragma omp parallel { int ithread = omp_get_thread_num(); int nthreads = omp_get_num_threads(); #pragma omp single { prefix = new size_t[nthreads+1]; prefix[0] = 0; } std::vector vec_private; #pragma omp for schedule(static) nowait for(int i=0; i<100; i++) { vec_private.push_back(i); } prefix[ithread+1] = vec_private.size(); #pragma omp barrier #pragma omp single { for(int i=1; i< (nthreads+1); i++) prefix[i] += prefix[i-1]; vec.resize(vec.size() + prefix[nthreads]); } std::copy(vec_private.begin(), vec_private.end(), vec.begin() + prefix[ithread]); } delete[] prefix;