Równoległe Iteratory

Question

Projektuję strukturę danych C++ (dla wykresów), która ma być używana przez kod równoległy (przy użyciu OpenMP).

Załóżmy, że chcę mieć metodę, która umożliwia iterację wszystkich elementów (węzłów). Oczywiście ta iteracja zostanie zrównoleglona.

Czy w tym celu można użyć iteratora? Jak powinien wyglądać taki iterator, który umożliwia równoległy dostęp? Czy w tym przypadku radzisz lub nie używasz iteratorów?

Answer 1

Pętle równoległe OpenMP nie ładnie grają z iteratorami. Będziesz chciał zaimplementować mechanizm indeksowania (operator[] przyjmujący integralny argument) na twojej klasie wykresu.

Jeśli chcesz korzystać z iteratora OpenMP 3.0, upewnij się, że masz iterator dostępu losowego. Wdrożenie go jako wskaźnika do węzła lub krawędzi jest najprostszym wyborem.

Answer 2

Jest to odmiana problemu z czytnikiem/pisarzem.

To zależy od tego, czy struktura będzie zmienna czy nie. Jeśli nie, to idź, czytaj równolegle tak, jak chcesz.

Ale jeśli będzie zmienna, to iteratory będą prawdopodobnie kolidować ze zmianami wprowadzonymi do struktury. Na przykład iterator może dotrzeć do elementu, który jest aktualnie usuwany. Jednym rozwiązaniem jest utworzenie niezmiennej, tylko do odczytu kopii struktury dla każdego iteratora, ale wtedy iterator nie zarejestruje żadnych zmian dokonanych w strukturze po utworzeniu iteratora. Drugim rozwiązaniem jest wykonanie implementacji copy-on-write, która spowoduje, że wszystkie zapisy do struktury utworzą nowy obiekt, z aktualnie uruchomionymi iteratorami działającymi na starym.

Musisz zdecydować, co zapisuje w tej strukturze dla twojego programu, zgodnie z algorytmem, a następnie odpowiednio zaimplementować blokowanie odczytu/zapisu.

Answer 3

Pozwolę sobie rozwinąć mój komentarz. Jeśli nie kierujesz się kompatybilnością między platformami i chcesz, aby twój kod również kompilował i pracował z MS Visual C++, możesz skompensować złożoność dostarczania "liniowych" iteratorów do obiektów graficznych za pomocą jawnych zadań OpenMP. Jawne zadania zostały wprowadzone w OpenMP 3.0 (stąd nie jest obsługiwany przez MSVC, który jest zgodny tylko z dużo wcześniejszą specyfikacją, nawet w 2012 roku). Zadania są blokami kodu, które można wykonywać równolegle. Są one tworzone przez task konstruktem:

... other code ... 
#pragma omp task 
{ 
    ... task code ... 
} 
... other code ... 

Kiedy przepływ wykonanie osiągnie zaznaczony obszar, tworzony jest nowy obiekt i umieścić zadanie w kolejce zadań. Następnie w określonych momentach wątki bezczynne pobierają jedno zadanie z kolejki i zaczynają je wykonywać. Zadania są bardzo podobne do sekcji OpenMP, ponieważ dziedziczą środowisko i mogą działać w innej kolejności niż w seryjnej wersji kodu.

Za pomocą zadań można implementować algorytmy rekurencyjne, a także z łatwością pracować z kontenerami C++, które nie zapewniają losowych iteratorów. Na przykład przechodzenie z binarnego drzewa mogą być wykonywane tak z zadaniami:

// Helper routine to traverse a tree and create one task for each node 
void traverse_and_make_tasks(tree_node *tn) 
{ 
    if (tn == NULL) 
     return; 

    // Create a task to process the node 
    #pragma omp task 
    { 
     very_long_computation(tn->value); 
    } 

    traverse_and_make_tasks(tn->left); 
    traverse_and_make_tasks(tn->right); 
} 

... main code ... 

// Disable dynamic teams 
omp_set_dynamic(0); 

#pragma omp parallel 
{ 
    #pragma omp single nowait 
    { 
     traverse_and_make_tasks(tree->root_node); 
    } 
} 

(wyłączając dynamiczne zespoły są potrzebne w celu zapobieżenia okresie czasu OpenMP od bycia zbyt inteligentna i wykonaniu region parallel pojedynczym gwintem)

Jest to bardzo powszechny wzorzec wykonywania zadań znany jako pojedynczy/seryjny producent.Ilekroć wykonanie wchodzi w region parallel, pojedynczy wątek wykonuje kod w konstrukcji single. Wywołuje traverse_and_make_tasks z węzłem głównym trzech. traverse_and_make_tasks przechodzi przez trzy i tworzy jedno zadanie dla każdego węzła. Konstrukcja task działa tylko wtedy, gdy jest używana w obszarze parallel (zakres statyczny) lub gdy jest używana w kodzie nazywanym (bezpośrednio lub pośrednio) z obszaru parallel (dynamiczne określanie zakresu). Gdy traverse_and_make_tasks przechodzi przez drzewo, generuje zadania, które stają w kolejce. Na końcu regionu parallel znajduje się niejawny punkt planowania zadań, który w przybliżeniu oznacza, że ​​wykonanie nie zostanie wznowione poza końcem regionu, dopóki wszystkie zadania nie zostaną wykonane. Można również umieścić wyraźne punkty wewnątrz równoległego regionu, używając #pragma omp taskwait. Działa to podobnie do barrier - wykonanie "blokuje", dopóki wszystkie zadania nie zostaną przetworzone.

Innym powszechnym wzorem jest równoległy producent , w którym zadania są generowane równolegle. Przykład kodu powyżej, mogą być łatwo przekształcone do równoległego producenta przez proste modyfikacje w traverse_and_make_tasks:

void traverse_and_make_tasks(tree_node *tn) 
{ 
    if (tn == NULL) 
     return; 

    #pragma omp task 
    traverse_and_make_tasks(tn->left); 
    #pragma omp task 
    traverse_and_make_tasks(tn->right); 

    // Create a task to process the node 
    very_long_computation(tn->value); 
} 

Ta wersja kodu tworzy dwa zadania, w każdym węźle - jeden do przetwarzania po potomka, a jeden do przetwarzania prawo potomek. Jeśli był to kod seryjny, przechodziłby on przez drzewo od dołu do góry. Jednak w kolejce równoległej kolejkowanie zadań powodowałoby mniej lub więcej przechodzenie od góry do dołu.

Istnieje wiele innych możliwych scenariuszy korzystania z zadań. Można też wykorzystać je w nie-rekurencyjnej przypadku przetwarzania pojemników, które nie zapewniają losowych iteratory, wymagane przez współdzielenia skonstruować for:

typedef container_type::iterator citer; 

container_type container; 
... push some values in the container ... 

#pragma omp parallel 
{ 
    #pragma omp single nowait 
    { 
     for (citer it = container.begin(); it != container.end(); it++) 
     #pragma omp task 
     process(*it); 
    } 

    #pragma omp taskwait 

    // process more 
    #pragma omp single nowait 
    { 
     for (citer it = container.begin(); it != container.end(); it++) 
     #pragma omp task 
     process_more(*it); 
    } 
} 

Ten przykład ilustruje także zastosowanie wyraźnej synchronizacji zadań wewnątrz regionu parallel.

Answer 4

Jeśli są to drzewa, prawdopodobnie będziesz chciał więcej myśleć w kategoriach skanów w Euler Tour Traversals niż "iteratory". http://en.wikipedia.org/wiki/Euler_tour_technique

Chciałbym mieć przed sobą książkę Stiepanowa. Pamiętam, jak krótko go dotykał.

Answer 5

Miałem dokładnie ten sam problem w Javie. Rozwiązanie, które zaimplementowałem, używa "hashmap of hashmaps". Nadal nie rozumiem, dlaczego standardowych bibliotek nie róbmy iteratory wielowątkowy ... Możesz przeczytać moje pytanie, wraz z moją odpowiedź (z linkiem do kodu Java) tutaj:

Scalable way to access every element of ConcurrentHashMap<Element, Boolean> exactly once