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

Question

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

Answer 1

La domanda che si collega 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 si chiamano metodi che possono causare la riallocazione dell'array sottostante che contiene std::vector. push_back(), pop_back() e insert() sono esempi di questi metodi pericolosi.

Se è necessaria la riallocazione sicura dei thread, la libreria intel thread building block offre concurrent vector containers. 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.

EDIT 1: Le diapositive 46 e 47 del the following Intel presentation dare un esempio illustrativo di riallocazione concomitante con TBB :: concurrent_vector

EDIT 2: A proposito, se si inizia con 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 utilizzare openmp per creare un parallel_for, Here è un bell'esempio di parallel_for utilizzo di tbb.

Answer 2

Penso che sia possibile utilizzare std::vector con OpenMP la maggior parte del tempo e mantenere comunque buone prestazioni. Il seguente codice, ad esempio, riempie in parallelo lo std::vectors e 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<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()); 
} 

Edit:

OpenMP 4.0 consente riduzioni definiti dall'utente utilizzando #pragma omp declare reduction. Il codice di cui sopra può essere semplificata con a

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

Edit: Quello che ho mostrato finora non riempie il vettore in ordine. Se gli elementi di ordine allora questo può essere fatto come questo

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

Ciò evita salvare uno std :: vector per ogni filo e poi convergere in fuori seriale della regione parallelo. Ho saputo di questo "trucco" here. Non sono sicuro di come farlo (o se è anche possibile) per riduzioni definite dall'utente.. Non è possibile farlo con riduzioni definite dall'utente.

Mi sono appena reso conto che la sezione critica non è necessaria che ho capito da questa domanda parallel-cumulative-prefix-sums-in-openmp-communicating-values-between-thread. Anche questo metodo ottiene l'ordine corretto

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;