C ++ OpenMP Parallel For Loop – Alternative a std :: vector

Sulla base di questo thread, il vettore OpenMP e STL , quali strutture dati sono buone alternative per un vettore std :: condiviso in un ciclo parallelo? L’aspetto principale è la velocità e il vettore potrebbe richiedere il ridimensionamento durante il ciclo.

La domanda che colleghi stava parlando del fatto che “quel contenitore vettoriale STL non è thread-safe nella situazione in cui più thread scrivono su un singolo contenitore”. Questo è vero solo, come affermato correttamente, se chiamate metodi che possono causare la riallocazione dell’array sottostante che std::vector detiene. push_back() , pop_back() e insert() sono esempi di questi metodi pericolosi.

Se è necessaria la riallocazione sicura dei thread, il blocco di costruzione del thread intel della libreria offre contenitori di vettori simultanei . Non si dovrebbe usare tbb :: concurrent_vector nei programmi a thread singolo perché il tempo necessario per accedere agli elementi casuali è maggiore del tempo impiegato da std :: vector per fare lo stesso (che è O (1)). Tuttavia, i vettori simultanei chiamano push_back() , pop_back() , insert() in modo thread-safe, anche quando avviene la riallocazione.

MODIFICA 1: le diapositive 46 e 47 della seguente presentazione Intel forniscono un esempio illustrativo di riallocazione simultanea utilizzando tbb :: concurrent_vector

EDIT 2: A proposito, se inizi a utilizzare Intel Tread Building Block (è open source, funziona con la maggior parte dei compilatori ed è molto meglio integrato con le caratteristiche di C ++ / C ++ 11 rispetto a openmp), quindi non è necessario usare openmp per creare un parallel_for, Ecco un bell’esempio di parallel_per usare tbb.

Penso che tu possa usare std::vector con OpenMP la maggior parte del tempo e abbia ancora buone prestazioni. Il seguente codice, ad esempio, riempie std::vectors in parallelo e poi li combina alla fine. Finché il collo di bottiglia è la funzione di loop / fill principale, questo dovrebbe funzionare in generale e essere thread-safe.

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

Modificare:

OpenMP 4.0 consente riduzioni definite dall'utente utilizzando #pragma omp declare reduction . Il codice sopra può essere semplificato con a

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

Modifica: Ciò che ho mostrato fino ad ora non riempie il vettore in ordine. Se l'ordine è importante, questo può essere fatto in questo modo

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

Ciò evita di salvare un vettore std :: per ciascun thread e quindi di unirli in serie all'esterno dell'area parallela. Ho imparato a conoscere questo "trucco" qui . Non sono sicuro di come farlo (o se è anche ansible) per riduzioni definite dall'utente. . Non è ansible farlo con riduzioni definite dall'utente.

Mi sono appena reso conto che la sezione critica non è necessaria e ho capito da questa domanda parallela-cumulativo-prefisso-somme-in-openmp-comunicando-valori-tra-thread . Anche questo metodo ottiene l'ordine corretto

 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;