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

Question

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

ho capito che avrei potuto copiare l'elenco in un vettore, fare il loop, quindi copiare tutto indietro. Tuttavia, vorrei evitare questa complessità e spese generali, se possibile.

Answer 1

Se si decide di utilizzare Openmp 3.0, è possibile utilizzare la funzione 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 delegare l'elaborazione di elementi per gli altri.

Senza OpenMP 3.0 il modo più semplice sarebbe quella di scrittura tutti i puntatori a elementi della lista (o iteratori in un vettore e l'iterazione di quello. In questo modo si potrebbe non dover copiare nulla di nuovo e di evitare il sovraccarico di copiare degli elementi stessi, quindi non dovrebbe avere a molto in alto:

std::vector<my_element*> 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 vuole evitare di copiare anche i puntatori, è sempre possibile creare un ciclo for parallelized a mano è possibile avere i fili accedere agli elementi interlacciati di. l'elenco (come proposto da KennyTM) o dividere l'intervallo in parti contiue approssimativamente uguali prima di iterare e iterare su quelle. Più tardi sembra preferibile in quanto i thread evitano l'accesso a stnodi attualmente elaborati da altri thread (anche se solo il prossimo puntatore), che potrebbe portare a false condivisioni. Ciò sembra grosso modo così:

#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 necessario, se process muta l'elemento elaborato (che significa che non è un metodo const), ci potrebbe essere una sorta di falsa condivisione senza di essa, se I thread si ripetono 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, è possibile impostare la generazione degli intervalli al di fuori dello #pragma omp parallel, tuttavia è necessario sapere quanti thread formeranno la sezione parallela. Quindi probabilmente dovresti impostare manualmente il 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 da possibilmente assegnando ad ogni pezzi filo Severa in quel caso (usando #pragma omp for dovrebbe farlo):

int max_threads = omp_get_max_threads(); 
std::vector<std::pair<std::list<...>::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(); 
} 

Questo richiederà solo tre iterazioni oltre list (due, se è possibile ottenere la dimensione del elenco senza iterare).Penso che sia il meglio che puoi fare per gli iteratori di accesso non casuale senza usare tasks o iterando su qualche datastructure fuori posto (come un vettore di puntatore).

Answer 2

Dubito che sia possibile dal momento che non puoi semplicemente saltare nel 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.

Answer 3

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 intesa 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<int> l(4,0);             
     #pragma omp parallel for               
     for(int i=0; i<l.size(); ++i){           
       printf("th %d = %d \n",omp_get_thread_num(),l[i]=i);    
     }                  
     printf("\n");               
     #pragma omp parallel                
     {                  
       for (auto i = l.begin(); i != l.end(); ++i) {     
       #pragma omp single nowait              
       {              
         printf("th %d = %d \n",omp_get_thread_num(),*i); 
       }              
      }                
     }                  
     return 0;                
} 

OMP_NUM_THREADS all'esportazione = 4, uscita come segue (nota 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 

Answer 4

Senza usare OpenMP 3.0 si ha la possibilità di avere tutte le discussioni iterare sulla lista:

std::list<T>::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 la propria copia del iteratore (privato), ma solo un singolo thread accederà a un elemento specifico (single) mentre gli altri thread verranno spostati in avanti agli elementi successivi (nowait)

Oppure si può ciclo una volta per costruire un vettore di puntatori per poi essere distribuito tra le discussioni:

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 uno o l'altro può essere più veloce. Testare quale ti si addice meglio è facile.

Answer 5

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

Per un elenco con N elementi in primo luogo abbiamo tagliato la lista in nthreads liste con circa N/nthreads elementi. In una regione parallelo questo può essere fatto come questo

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<int> l2; 
#pragma omp for ordered schedule(static) 
for(int i=0; i<nthreads; i++) { 
    #pragma omp ordered 
    { 
     auto it0 = l.begin(), it1 = it0; 
     std::advance(it1, t1-t0);  
     l2.splice(l2.begin(), l2, it0, it1); 
    } 
} 

Dove l2 è la lista di taglio per ciascun thread.

Quindi possiamo agire su ogni lista in parallelo. Per 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 stiamo facendo operare sulle liste in parallelo si splice liste per ciascun filo ritorna una lista in ordine in questo modo:

#pragma omp for ordered schedule(static) 
for(int i=0; i<nthreads; i++) { 
    #pragma omp ordered 
    l.splice(l.end(), l, l2.begin(), l2.end()); 
} 

L'algoritmo è essenzialmente.

1. Avanzamento rapido dell'elenco sequenziale.
2. Agisce sugli elenchi tagliati in parallelo aggiungendo, modificando o rimuovendo elementi.
3. Unire sequenzialmente le liste di taglio modificate in sequenza.

---

Ecco un esempio di lavoro

#include <algorithm> 
#include <iostream> 
#include <list> 
#include <omp.h> 

int main(void) { 
    std::list<int> 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<int> l2; 
    #pragma omp for ordered schedule(static) 
    for(int i=0; i<nthreads; i++) { 
     #pragma omp ordered 
     { 
    auto it0 = l.begin(), it1 = it0; 
    std::advance(it1, t1-t0);  
    l2.splice(l2.begin(), l2, it0, it1); 
     } 
    } 
    //insert -1 every 5th postion 
    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); 
    } 

    //splice lists in order back together. 
    #pragma omp for ordered schedule(static) 
    for(int i=0; i<nthreads; i++) { 
     #pragma omp ordered 
     l.splice(l.end(), l, l2.begin(), l2.end()); 
    } 
    } 

    for (auto it = l.begin(); it != l.end(); ++it) { 
    std::cout << *it << " "; 
    } std::cout << std::endl; 
} 

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