C++ OpenMP Parallel For Loop – Alternativen zu std::vector [closed]

Basierend auf diesem Thread, OpenMP und STL-Vektor, welche Datenstrukturen gute Alternativen für eine sind geteilt std::vector in einer parallelen For-Schleife? Der Hauptaspekt ist die Geschwindigkeit, und der Vektor muss möglicherweise während der Schleife in der Größe geändert werden.

Ich denke, Sie können verwenden std::vector mit OpenMP die meiste Zeit und haben immer noch eine gute Leistung. Der folgende Code füllt beispielsweise aus std::vectors parallel und kombiniert sie am Ende. Solange Ihre Hauptschleifen-/Füllfunktion der Engpass ist, sollte dies im Allgemeinen gut funktionieren und Thread-sicher sein.

std::vector<int> vec;
#pragma omp parallel
{
    std::vector<int> 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<int> : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end()))

std::vector<int> vec;
#pragma omp parallel for reduction(merge: vec)
for(int i=0; i<100; i++) vec.push_back(i);

Bearbeiten: Was ich bisher gezeigt habe, füllt den Vektor nicht in Ordnung. Wenn die Reihenfolge wichtig ist, kann dies so erfolgen

std::vector<int> vec;
#pragma omp parallel
{
    std::vector<int> vec_private;
    #pragma omp for nowait schedule(static)
    for(int i=0; i<N; i++) { 
        vec_private.push_back(i);
    }
    #pragma omp for schedule(static) ordered
    for(int i=0; i<omp_get_num_threads(); i++) {
        #pragma omp ordered
        vec.insert(vec.end(), vec_private.begin(), vec_private.end());
    }
}

Dadurch wird vermieden, dass für jeden Thread ein std::vector gespeichert und dann außerhalb der parallelen Region seriell zusammengeführt wird. Ich habe hier von diesem “Trick” erfahren. Ich bin mir nicht sicher, wie ich das für benutzerdefinierte Reduzierungen machen soll (oder ob es überhaupt möglich ist).. Dies ist mit benutzerdefinierten Reduzierungen nicht möglich.

Ich habe gerade festgestellt, dass der kritische Abschnitt nicht notwendig ist, was ich aus dieser Frage herausgefunden habe. Diese Methode erhält auch die richtige Reihenfolge

std::vector<int> 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<int> 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;

Die von Ihnen verlinkte Frage bezog sich auf die Tatsache, dass “dieser STL-Vektorcontainer in Situationen, in denen mehrere Threads in einen einzelnen Container schreiben, nicht Thread-sicher ist”. Dies gilt nur, wie dort korrekt angegeben, wenn Sie Methoden aufrufen, die eine Neuzuordnung des zugrunde liegenden Arrays verursachen können std::vector hält. push_back(), pop_back() und insert() sind Beispiele für diese gefährlichen Methoden.

Wenn Sie eine Thread-sichere Neuzuweisung benötigen, dann die Bibliothek Intel-Thread-Baustein bietet Dir gleichzeitige Vektorcontainer . Sie sollten tbb::concurrent_vector nicht in Single-Thread-Programmen verwenden, da die Zeit, die für den Zugriff auf zufällige Elemente benötigt wird, länger ist als die Zeit, die std::vector benötigt, um dasselbe zu tun (was O (1) ist). Jedoch gleichzeitige Vektoraufrufe push_back(), pop_back(), insert() auf Thread-sichere Weise, auch wenn eine Neuzuweisung erfolgt.

EDIT 1: Die Folien 46 und 47 von die folgende Intel-Präsentation Geben Sie ein anschauliches Beispiel für die gleichzeitige Neuzuweisung mit tbb::concurrent_vector

EDIT 2: Übrigens, wenn Sie anfangen, Intel Tread Building Block zu verwenden (es ist Open Source, funktioniert mit den meisten Compilern und ist viel besser in C++/C++11-Funktionen integriert als Openmp), dann brauchen Sie es nicht um openmp zu verwenden, um ein parallel_for zu erstellen, Hier ist ein nettes Beispiel für parallel_for mit tbb.