Come parallelizzare un ciclo for attraverso un C ++ std :: list usando OpenMP?

Vorrei scorrere tutti gli elementi in un elenco std :: in parallelo usando OpenMP. Il ciclo dovrebbe essere in grado di modificare gli elementi della lista. C’è una soluzione semplice per questo? Sembra che OpenMP 3.0 supporti loop paralleli quando l’iteratore è un Iterator di accesso casuale, ma non altrimenti. In ogni caso, preferirei utilizzare OpenMP 2.0 in quanto non ho il pieno controllo su quali compilatori sono disponibili per me.

Se il mio contenitore fosse un vettore, potrei usare:

#pragma omp parallel for for (auto it = v.begin(); it != v.end(); ++it) { it->process(); } 

Capisco che potrei copiare la lista in un vettore, fare il ciclo, quindi copiare tutto indietro. Tuttavia, vorrei evitare questa complessità e spese generali, se ansible.

Se decidi di utilizzare Openmp 3.0 , puoi utilizzare la funzione di task :

 #pragma omp parallel #pragma omp single { for(auto it = l.begin(); it != l.end(); ++it) #pragma omp task firstprivate(it) it->process(); #pragma omp taskwait } 

Questo eseguirà il ciclo in un thread, ma delegherà l’elaborazione di elementi ad altri.

Senza OpenMP 3.0 il modo più semplice sarebbe scrivere tutti i puntatori agli elementi della lista (o iteratori in un vettore e scorrere su quello.) In questo modo non dovresti copiare nulla ed evitare il sovraccarico di copiare gli elementi stessi, quindi non dovrebbe avere troppo overhead:

 std::vector elements; //my_element is whatever is in list for(auto it = list.begin(); it != list.end(); ++it) elements.push_back(&(*it)); #pragma omp parallel shared(chunks) { #pragma omp for for(size_t i = 0; i < elements.size(); ++i) // or use iterators in newer OpenMP elements[i]->process(); } 

Se si desidera evitare di copiare anche i puntatori, è sempre ansible creare un parallelizato per il ciclo a mano. Puoi avere i thread per accedere agli elementi interlacciati della lista (come proposto da KennyTM) o dividere l’intervallo in parti contious uguali prima di iterare e scorrere su quelli. La successiva sembra preferibile in quanto i thread evitano l’accesso a listnode attualmente elaborati da altri thread (anche se solo il prossimo puntatore), che potrebbe portare a una condivisione errata. Questo sembrerebbe più o meno come questo:

 #pragma omp parallel { int thread_count = omp_get_num_threads(); int thread_num = omp_get_thread_num(); size_t chunk_size= list.size() / thread_count; auto begin = list.begin(); std::advance(begin, thread_num * chunk_size); auto end = begin; if(thread_num = thread_count - 1) // last thread iterates the remaining sequence end = list.end(); else std::advance(end, chunk_size); #pragma omp barrier for(auto it = begin; it != end; ++it) it->process(); } 

La barriera non è strettamente necessaria, tuttavia se il process muta l’elemento elaborato (ovvero non è un metodo const), potrebbe esserci una sorta di condivisione falsa senza di essa, se i thread eseguono un’iterazione su una sequenza che è già stata modificata. In questo modo itererà 3 volte e n volte sulla sequenza (dove n è il numero di thread), quindi il ridimensionamento potrebbe essere inferiore all’ottimale per un numero elevato di thread.

Per ridurre il sovraccarico, potresti mettere la generazione degli intervalli al di fuori del #pragma omp parallel , tuttavia dovrai sapere quanti thread formsranno la sezione parallela. Quindi probabilmente dovresti impostare manualmente i num_threads , o usare omp_get_max_threads() e gestire il caso in cui il numero di thread creati sia inferiore a omp_get_max_threads() (che è solo un limite superiore). L’ultimo modo potrebbe essere gestito assegnando eventualmente ciascun blocco di sette pezzi in quel caso (usando #pragma omp for farlo):

 int max_threads = omp_get_max_threads(); std::vector::iterator, std::list<...>::iterator> > chunks; chunks.reserve(max_threads); size_t chunk_size= list.size() / max_threads; auto cur_iter = list.begin(); for(int i = 0; i < max_threads - 1; ++i) { auto last_iter = cur_iter; std::advance(cur_iter, chunk_size); chunks.push_back(std::make_pair(last_iter, cur_iter); } chunks.push_back(cur_iter, list.end(); #pragma omp parallel shared(chunks) { #pragma omp for for(int i = 0; i < max_threads; ++i) for(auto it = chunks[i].first; it != chunks[i].second; ++it) it->process(); } 

Ciò richiederà solo tre iterazioni sulla list (due, se è ansible ottenere la dimensione della lista senza iterare). Penso che sia il meglio che puoi fare per gli iteratori di accesso non casuale senza usare tasks o iterare su qualche datastructure fuori posto (come un vettore di puntatore).

Dubito che sia ansible dal momento che non puoi saltare nel bel mezzo di una lista senza attraversare la lista. Gli elenchi non sono archiviati nella memoria contigua e std :: list iterators non sono Random Access. Sono solo bidirezionali.

http://openmp.org/forum/viewtopic.php?f=3&t=51

 #pragma omp parallel { for(it= list1.begin(); it!= list1.end(); it++) { #pragma omp single nowait { it->compute(); } } // end for } // end ompparallel 

Questo può essere inteso come srotolato come:

 { it = listl.begin #pragma omp single nowait { it->compute(); } it++; #pragma omp single nowait { it->compute(); } it++; ... } 

Dato un codice come questo:

 int main() { std::vector l(4,0); #pragma omp parallel for for(int i=0; i 

export OMP_NUM_THREADS = 4, output come segue (notare la seconda sezione, il numero di thread di lavoro può essere ripetuto):

 th 2 = 2 th 1 = 1 th 0 = 0 th 3 = 3 th 2 = 0 th 1 = 1 th 2 = 2 th 3 = 3 

Senza usare OpenMP 3.0 hai la possibilità di avere tutti i thread che iterano sull’elenco:

 std::list::iterator it; #pragma omp parallel private(it) { for(it = list1.begin(); it!= list1.end(); it++) { #pragma omp single nowait { it->compute(); } } } 

In questo caso ogni thread ha una propria copia dell’iteratore ( privato ) ma solo un singolo thread accederà a un elemento specifico ( singolo ) mentre gli altri thread avanzeranno agli elementi successivi ( nowait )

Oppure puoi fare un ciclo una volta per build un vettore di puntatori da distribuire tra i thread:

 std::vector< T*> items; items.reserve(list.size()); //put the pointers in the vector std::transform(list.begin(), list.end(), std::back_inserter(items), [](T& n){ return &n; } ); #pragma omp parallel for for (int i = 0; i < items.size(); i++) { items[i]->compute(); } 

A seconda del caso specifico, l’uno o l’altro può essere più veloce. Testare quale ti si addice meglio è facile.

Ecco una soluzione che consente di inserire / rimuovere nuovi elementi di una lista in parallelo.

Per una lista con N elementi abbiamo prima tagliato la lista in liste di nthreads con elementi di N/nthreads all’incirca. In una regione parallela questo può essere fatto in questo modo

 int ithread = omp_get_thread_num(); int nthreads = omp_get_num_threads(); int t0 = (ithread+0)*N/nthreads; int t1 = (ithread+1)*N/nthreads; std::list l2; #pragma omp for ordered schedule(static) for(int i=0; i 

Dove l2 è l'elenco di taglio per ogni thread.

Quindi possiamo agire su ogni lista in parallelo. Ad esempio possiamo inserire -1 ogni prima posizione nella lista come questa

 auto it = l2.begin(); for(int i=(t0+4)/5; i<(t1+4)/5; i++) { std::advance(it, 5*i-t0); l2.insert(it, -1); } 

Infine, dopo aver eseguito gli elenchi in parallelo, abbiamo unito le liste per ogni thread a una lista in ordine come questo:

 #pragma omp for ordered schedule(static) for(int i=0; i 

L'algoritmo è essenzialmente.

  1. Avanzamento rapido tramite lista sequenziale che crea liste di taglio.
  2. Agisci sulle liste di taglio aggiungendo, modificando o rimuovendo gli elementi in parallelo.
  3. Unire sequenzialmente le liste di taglio modificate in sequenza.

Ecco un esempio funzionante

 #include  #include  #include  #include  int main(void) { std::list l; for(int i=0; i<22; i++) { l.push_back(i); } for (auto it = l.begin(); it != l.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; int N = l.size(); #pragma omp parallel { int ithread = omp_get_thread_num(); int nthreads = omp_get_num_threads(); int t0 = (ithread+0)*N/nthreads; int t1 = (ithread+1)*N/nthreads; //cut list into nthreads lists with size=N/nthreads std::list l2; #pragma omp for ordered schedule(static) for(int i=0; i 

Risultato

 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 -1 0 1 2 3 4 -1 5 6 7 8 9 -1 10 11 12 13 14 -1 15 16 17 18 19 -1 20 21