Aggiornamento di un valore massimo da più thread

Question

C'è un modo per aggiornare un massimo da più thread utilizzando le operazioni atomiche?

esempio illustrativo:

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); 
} 

Nel caso precedente, la sezione critica sincronizza accesso all'intera vettore, che abbiamo solo bisogno di sincronizzare l'accesso a ciascuno dei valori indipendentemente.

Answer 1

In seguito a un suggerimento in un commento, ho trovato una soluzione che non richiede il blocco e utilizza invece la funzionalità di confronto e scambio trovata in std :: atomic/boost :: atomic. Sono limitato a C++ 03 quindi userei boost :: atomic in questo caso.

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)); 
} 

V'è una certa boilerplate coinvolti nel mettere valori float a int, poiché sembra che galleggia atomiche non sono-Lock gratuito. Non uso al 100% l'ordine di memoria, ma il livello meno restrittivo 'rilassato' sembra essere OK, poiché la memoria non atomica non è coinvolta.

Answer 2

Che dire di dichiarare, ad esempio, uno std::vector<std::mutex> (o boost::mutex) di lunghezza 128 e quindi creare un oggetto di blocco utilizzando l'elemento j?

Voglio dire, qualcosa come:

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);  
} 

Oppure, come da 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

Non sono sicuro sulla sintassi, ma algoritmicamente, sono disponibili tre opzioni:

1. Blocca l'intero vettore per garantire l'accesso atomico (che è ciò che stai facendo al momento).

2. Blocca i singoli elementi, in modo che ogni elemento possa essere aggiornato indipendentemente dagli altri. Pro: massimo parallelismo; Contro: molte serrature richieste!

3. Qualcosa nel mezzo! Concettualmente pensa di suddividere il tuo vettore in 16 (o 32/64/...) "banchi" come segue: bank0 consiste di elementi vettoriali 0, 16, 32, 48, 64, ... bank1 consiste di elementi vettoriali 1 , 17, 33, 49, 65, ... bank2 è costituito da elementi vettoriali 2, 18, 34, 50, 66, ... Ora, utilizzare 16 blocchi espliciti prima di accedere all'elemento e si può avere fino a 16-way parallelismo. Per accedere all'elemento n, acquisire il blocco (n% 16), terminare l'accesso, quindi rilasciare lo stesso blocco.

Answer 4

solo aggiungere i miei due centesimi, prima di iniziare le ottimizzazioni più a grana fine vorrei provare il seguente approccio che elimina la necessità di omp critical:

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 

    } 
} 

Si noti che non ho compilare il frammento , quindi potrei aver lasciato qualche errore di sintassi all'interno. Comunque spero di aver trasmesso l'idea.