Aktualisieren eines Maximalwerts aus mehreren Threads

Question

Gibt es eine Möglichkeit, ein Maximum aus mehreren Threads mit atomaren Operationen zu aktualisieren?

erläuterndes Beispiel:

std::vector<float> coord_max(128); 
#pragma omp parallel for 
for (int i = 0; i < limit; ++i) { 
    int j = get_coord(i); // can return any value in range [0,128) 
    float x = compute_value(j, i); 
    #pragma omp critical (coord_max_update) 
    coord_max[j] = std::max(coord_max[j], x); 
} 

Im obigen Fall wird der kritische Abschnitt synchronisiert den Zugriff auf den gesamten Vektor, wohingegen wir nur unabhängig Zugriff auf jeden der Werte synchronisieren müssen.

Answer 1

Nach einem Vorschlag in einem Kommentar, fand ich eine Lösung, die keine Sperre erfordert und stattdessen die Compare-and-Exchange-Funktionalität in std :: atomic/boost :: atomic verwendet. Ich bin auf C++ 03 beschränkt, also würde ich in diesem Fall boost :: atomic verwenden.

BOOST_STATIC_ASSERT(sizeof(int) == sizeof(float)); 
union FloatPun { float f; int i; }; 

std::vector< boost::atomic<int> > coord_max(128); 
#pragma omp parallel for 
for (int i = 0; i < limit; ++i) { 
    int j = get_coord(i); 
    FloatPun x, maxval; 
    x.f = compute_value(j, i); 

    maxval.i = coord_max[j].load(boost::memory_order_relaxed); 
    do { 
     if (maxval.f >= x.f) break; 
    } while (!coord_max[j].compare_exchange_weak(maxval.i, x.i, 
     boost::memory_order_relaxed)); 
} 

Es gibt einige Boilerplate beteiligt Float Werte in Ints, da es scheint, dass atomare Schwimmer sind nicht frei von Sperren. Ich verwende die Speicherordnung nicht zu 100%, aber die am wenigsten restriktive Ebene "entspannt" scheint in Ordnung zu sein, da nicht-atomarer Speicher nicht beteiligt ist.

Answer 2

Wie wäre es, sagen wir, ein std::vector<std::mutex> (oder boost::mutex) der Länge 128 und dann ein Lock-Objekt mit dem j th Element erstellen?

Ich meine, so etwas wie:

std::vector<float> coord_max(128); 
std::vector<std::mutex> coord_mutex(128); 
#pragma omp parallel for 
for (int i = 0; i < limit; ++i) { 
    int j = get_coord(i); // can return any value in range [0,128) 
    float x = compute_value(j, i); 
    std::scoped_lock lock(coord_mutex[j]); 
    coord_max[j] = std::max(coord_max[j], x);  
} 

Oder wie pro Rahul Banerjee's suggestion #3:

std::vector<float> coord_max(128); 
const int parallelism = 16; 
std::vector<std::mutex> coord_mutex(parallelism); 
#pragma omp parallel for 
for (int i = 0; i < limit; ++i) { 
    int j = get_coord(i); // can return any value in range [0,128) 
    float x = compute_value(j, i); 
    std::scoped_lock lock(coord_mutex[j % parallelism]); 
    coord_max[j] = std::max(coord_max[j], x);  
} 

Answer 3

Nicht sicher über die Syntax, aber algorithmisch, haben Sie drei Möglichkeiten:

1. Sperren Sie den gesamten Vektor, um atomaren Zugriff zu gewährleisten (was Sie gerade tun).

2. Sperren Sie einzelne Elemente, so dass jedes Element unabhängig von anderen aktualisiert werden kann. Vorteile: maximale Parallelität; Nachteile: viele Schlösser erforderlich!

3. Etwas dazwischen! Stellen Sie sich konzeptionell die Partitionierung Ihres Vektors in 16 (oder 32/64/...) "Bänke" wie folgt vor: bank0 besteht aus Vektorelementen 0, 16, 32, 48, 64, ... bank1 besteht aus Vektorelementen 1 , 17, 33, 49, 65, ... bank2 besteht aus Vektorelementen 2, 18, 34, 50, 66, ... ... Verwenden Sie jetzt 16 explizite Sperren, bevor Sie auf das Element zugreifen und Sie können haben bis zu 16-Wege-Parallelität. Um auf Element n zuzugreifen, akquiriere die Sperre (n% 16), beende den Zugriff und gib dann die gleiche Sperre frei.

Answer 4

Nur meine zwei Cent hinzufügen, bevor feinkörnige Optimierungen beginnen würde ich den folgenden Ansatz versuchen, dass die Notwendigkeit für omp critical entfernt:

std::vector<float> coord_max(128); 
float    fbuffer(0); 
#pragma omp parallel 
{ 
    std::vector<float> thread_local_buffer(128); 

    // Assume limit is a really big number 
    #pragma omp for  
    for (int ii = 0; ii < limit; ++ii) { 
    int jj = get_coord(ii); // can return any value in range [0,128) 
    float x = compute_value(jj,ii); 
    thread_local_buffer[jj] = std::max(thread_local_buffer[jj], x); 
    } 
    // At this point each thread has a partial local vector 
    // containing the maximum of the part of the problem 
    // it has explored 

    // Reduce the results 
    for(int ii = 0; ii < 128; ii++){ 
    // Find the max for position ii 
#pragma omp for schedule(static,1) reduction(max:fbuffer) 
    for(int jj = 0; jj < omp_get_thread_num(); jj++) { 
     fbuffer = thread_local_buffer[ii]; 
    } // Barrier implied here 
    // Write it in the vector at correct position 
#pragma omp single 
    { 
     coord_max[ii] = fbuffer; 
     fbuffer = 0; 
    } // Barrier implied here 

    } 
} 

Beachten Sie, dass ich nicht die Schnipsel kompilieren habe , also habe ich vielleicht einen Syntaxfehler drin gelassen. Jedenfalls hoffe ich, dass ich die Idee vermittelt habe.