Jak zrównoleglić pętlę for przez C++ std :: list używając OpenMP?

Question

Chciałbym iterować przez wszystkie elementy na liście std :: list równolegle za pomocą OpenMP. Pętla powinna mieć możliwość zmiany elementów listy. Czy istnieje proste rozwiązanie tego problemu? Wygląda na to, że OpenMP 3.0 obsługuje równoległe pętle, gdy iterator jest Iteratorem dostępu losowego, ale nie inaczej. W każdym razie wolałbym używać OpenMP 2.0, ponieważ nie mam pełnej kontroli nad dostępnymi kompilatorami.

Jeśli mój pojemnik były wektor może używać:

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

Rozumiem, że mogę skopiować listę do wektora, zrobić pętlę, a następnie skopiować wszystko z powrotem. Chciałbym jednak, jeśli to możliwe, uniknąć tej złożoności i kosztów ogólnych.

Answer 1

Jeśli użytkownik zdecyduje się użyć Openmp 3.0, można użyć task cechę:

#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 
} 

ten wykona pętlę w jednym wątku, ale delegowania przetwarzania elementów do innych.

Bez OpenMP 3.0 najprostszym sposobem byłoby zapisanie wszystkich wskaźników do elementów na liście (lub iteratorów w wektorze i iteracja nad tym, w ten sposób nie trzeba kopiować niczego z powrotem i uniknąć narzutu na kopiowanie elementów sami, więc nie powinien mieć zbyt dużo napowietrznych:

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

Jeśli chcesz uniknąć kopiowania nawet wskazówek, zawsze można stworzyć parallelized pętli ręcznie można też mieć dostęp przeplatanych nici elementy. listę (zgodnie z propozycją KennyTM) lub podziel zakres w mniej więcej równych, contious częściach przed iterowaniem i iterowaniem nad nimi. Później wydaje się, że lepiej, ponieważ nici unikają dostępu do li stnodes obecnie przetwarzane przez inne wątki (nawet jeśli tylko następny wskaźnik), co może prowadzić do fałszywego udostępniania. To będzie wyglądać mniej więcej tak:

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

Bariera nie jest bezwzględnie konieczne, jednak jeśli process mutuje przetworzonego elementu (co oznacza, że ​​nie jest to metoda const), nie może być jakiś rodzaj fałszywego dzielenia bez niej, jeśli wątki iterują po sekwencji, która jest już mutowana. W ten sposób będzie iterować 3 * n razy w sekwencji (gdzie n jest liczbą wątków), więc skalowanie może być mniejsze niż optymalne dla dużej liczby wątków.

Aby zmniejszyć obciążenie, można ustawić generowanie zakresów poza wartością #pragma omp parallel, jednak trzeba będzie wiedzieć, ile wątków utworzy sekcję równoległą. Prawdopodobnie będziesz musiał ręcznie ustawić num_threads lub użyć omp_get_max_threads() i obsłużyć wielkość liter, że liczba utworzonych wątków jest mniejsza niż omp_get_max_threads() (która jest tylko górną granicą). Ostatni sposób może być obsługiwany przez możliwie przypisując każdy kawałki nici Severa w tym przypadku (używając #pragma omp for powinien zrobić):

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

To zajmie tylko trzy iteracje nad list (dwóch, jeśli można uzyskać rozmiaru lista bez iteracji).Myślę, że chodzi o to, co najlepsze, co można zrobić dla iteratorów bez dostępu losowego, bez korzystania z tasks lub iterowania nad pewną nieaktualną strukturą danych (jak wektor wskaźnika).

Answer 2

Wątpię, że jest to możliwe, ponieważ nie można po prostu wskoczyć na środek listy bez przechodzenia przez listę. Listy nie są przechowywane w ciągłej pamięci, a iteratory std :: list nie mają dostępu losowego. Są tylko dwukierunkowe.

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 

Można to rozumieć jako rozwinął jako:

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

Biorąc kod tak:

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

eksport OMP_NUM_THREADS = 4, moc następująco (uwaga druga sekcja, numer wątku roboczego może się powtarzać):

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

Bez użyciu OpenMP 3.0 masz możliwość posiadania wszystkie wątki Iteracja nad listy:

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

W tym przypadku każdy wątek ma własną kopię iterator (prywatny), ale tylko pojedynczy wątek będzie mieć dostęp do określonego elementu (pojedynczy), podczas gdy inne wątki będą przesuwać się do następnych pozycji (nowait)

lub można pętla kiedyś zbudować wektor wskaźników być następnie dystrybuowane wśród wątków:

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

zależności od konkretnego przypadku jednej lub drugiej strony może być szybciej. Sprawdzenie, który z nich jest dla Ciebie lepszy, jest łatwe.

Answer 5

Oto rozwiązanie, które umożliwia równoległe wstawianie/usuwanie nowych elementów listy.

Listę z N elementów najpierw wyciąć listę do nthreads list z grubsza N/nthreads elementów. W obszarze równoległych można to zrobić tak

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

przypadku l2 lista cięcia dla każdej nici.

Następnie możemy działać na każdej liście równolegle. Na przykład możemy wstawić -1 każdą pierwszą pozycję na liście, jak ten

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

końcu, po robimy działa na listach równolegle my splatać wykazy dla każdego wątku z powrotem do jednej listy w kolejności jak poniżej:

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

Algorytm zasadniczo.

1. Szybkie przewijanie listy kolejnych list przez sekwencję.
2. Działać na listach wycinanych równolegle dodając, modyfikując lub usuwając elementy.
3. Łączenie zmodyfikowanych list cięcia z powrotem sekwencyjnie.

---

Oto przykład roboczych

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

Wynik

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