Programowanie równoległe i rozproszone – opracowanie lab nr 1
OpenMP (ang. Open Multi-Processing) – wieloplatformowy interfejs programowania aplikacji (API) umożliwiający tworzenie programów komputerowych dla systemów wieloprocesorowych z pamięcią dzieloną. Może być wykorzystywany w językach programowania C, C++ i Fortran na wielu architekturach, m.in. Unix i Microsoft Windows. Składa się ze zbioru dyrektyw kompilatora, bibliotek oraz zmiennych środowiskowych mających wpływ na sposób wykonywania się programu.
Dzięki temu, że standard OpenMP został uzgodniony przez głównych producentów sprzętu i oprogramowania komputerowego, charakteryzuje się on przenośnością, skalowalnością, elastycznością i prostotą użycia. Dlatego może być stosowany do tworzenia aplikacji równoległych dla różnych platform, od komputerów klasy PC po superkomputery.
OpenMP można stosować do tworzenia aplikacji równoległych na klastrach komputerów wieloprocesorowych. W tym przypadku zwykle stosuje się rozwiązanie hybrydowe, w którym programy są uruchamiane na klastrach komputerowych pod kontrolą alternatywnego interfejsu MPI, natomiast do urównoleglenia pracy węzłów klastrów wykorzystuje się OpenMP. Alternatywny sposób polega na zastosowaniu specjalnych rozszerzeń OpenMP dla systemów pozbawionych pamięci współdzielonej (np. Cluster OpenMP Intela).
Kompilacja
Przykład kompilacji dla kompilatora Intel C++:
$ icc -openmp program.cpp -o program
Przykład kompilacji dla kompilatora GCC:
$ g++ -fopenmp program.cpp -o program
Uruchomienie programu dla czterech wątków:
$ env OMP_NUM_THREADS=4 ./program
Proces kompilacji OpenMP (https://iwomp.zih.tu-dresden.de/downloads/OpenMP-compilation.pdf – m.in. slajd 13):
Front End – odczytanie kodu źródłowego, sprawdzenie czy jest wolny od błędu, przygotowanie kodu pośredniego. (Czytanie i sprawdzanie dyrektyw OpenMP, czy dyrektywa jest w odpowiednim miejscu, czy pętla jest dozwolona, niektóre błędy mogą nie być uznane za błąd! Tworzy kod pośredni z adnotacjami OpenMP do dalszego obsłużenia).
Middle End – jak najlepsza analiza i optymalizacja kodu. (Tłumaczenie sekcji, pętli, dodawanie niejawnych barier, łączenie sąsiednich obszarów równoległych i barier [redundancja]).
Back End – przetłumaczenie konstrukcji OpenMP na wielowątkowy kod
Każdy wątek potrzebuje własnego stosu.
Konstrukcje związane ze współdzieleniem pracy:
omp for lub omp do – używane do rozdzielania iteracji pętli pomiędzy wątki, zwane także konstrukcjami pętli.
sections – przypisanie następujących po sobie, ale niezależnych bloków kodu do różnych wątków
single – wyszczególnienie bloku kodu, który będzie przetwarzany przez tylko jeden wątek, z barierą na końcu
master – podobne do single, przy czym kod jest przetwarzany tylko przez wątek główny, bez bariery na końcu
shared – dane współdzielone, co oznacza, że są widoczne i dostępne dla wszystkich wątków jednocześnie. Domyślnie wszystkie zmienne w regionie współdzielonej pracy są shared z wyjątkiem licznika iteracji pętli.
private – dane są prywatne dla każdego wątku, co oznacza, że każdy wątek posiada lokalną kopię i używa jej jako zmienną tymczasową. Prywatne zmienne nie są inicjalizowane, ich wartość nie jest udostępniana do użycia poza regionem przetwarzanym równolegle. Domyślnie liczniki iteracji pętli są prywatne.
default – pozwala programiście ustawiać domyślny zasięg zmiennych wewnątrz równolegle przetwarzanego regionu, poprzez użycie shared, private lub none. Opcja none zmusza programistę do deklarowania każdej zmiennej.
critical section – zawarty blok kodu będzie przetwarzany przez tylko jeden wątek w danym czasie, a nie jednocześnie przez kilka. Jest często używany do ochrony współdzielonych danych przed błędnym stanem.
atomic – podobne do critical section, ale informuje kompilator aby zostały użyte specjalne instrukcje sprzętowe dla zapewnienia lepszej wydajności. Kompilatory mogą zignorować tę sugestię od użytkownika i użyć critical section.
ordered – zawarty blok jest przetwarzany w porządku, w którym iteracje są uruchamiane w sekwencyjnej pętli.
barrier – każdy wątek czeka, zanim wszystkie inne wątki osiągną ten punkt. Konstrukcje współdzielące prace posiadają ukrytą synchronizację barier na końcu.
nowait – ustala, że wątek kompletujący przyporządkowaną mu pracę, może pracować bez czekania na inne wątki przed zakończeniem. W przypadku braku tej klauzuli, wątki przeprowadzają synchronizację bariery na końcu bloku pracy współdzielonej.
schedule(type, chunk) – Jest to użyteczne, jeśli konstrukcja współdzieląca prace jest pętlą do lub for. Określa sposób podziału pętli na części wykonywane równolegle. Parametr „type” określający sposób rozdziału iteracji jest obowiązkowy. Drugi parametr „chunk” jest opcjonalny. Określa on wielkość równolegle przetwarzanej części. Musi być liczbą całkowitą. Poszczególne wątki w blokach są rozmiaru „chunk”, do których przydzielane są iteracje. Typy planowania to:
static – Tutaj, każdy z wątków posiada przypisane iteracje przed uruchomieniem iteracji pętli. Domyślnie, iteracje są dzielone po równo między wątki. Określenie całkowitej wartości dla parametru „chunk” spowoduje przydzielenie tej ilości następujących po sobie iteracji do konkretnego wątku. Jeżeli programista pominie parametr „chunk”, zbiór iteracji zostanie podzielony na podzbiory o wielkości (w przybliżeniu) równej liczba_iteracji/liczba_wątków, a każdy wątek otrzyma przynajmniej jeden podzbiór.
dynamic – Tutaj, pewna ilość iteracji jest przypisywana do mniejszej ilości wątków. Gdy konkretny wątek skończy swoją iterację, pobiera następną z pozostałych wolnych iteracji. Ostatni podzbiór może mieć mniejszą wielkość niż ta określona przez parametr „chunk”. Parametr „chunk” definiuje ilość iteracji, które są przyporządkowywane do wątku za każdym razem. Gdy „chunk” nie jest określony, wówczas podzbiory są jednoelementowe.
guided – Duży fragment następujących po sobie iteracji jest przypisywany do każdego wątku dynamicznie (jak powyżej). Rozmiar fragmentu zmniejsza się wykładniczo, wraz z każdą pomyślną alokacją, do minimalnego rozmiaru zdefiniowanego w parametrze „chunk”. Jeśli programista ustawi parametr „chunk” na 1, to rozmiar każdego zbioru jest opisany algorytmem: liczba_nieprzydzielonych_iteracji/liczba_wątków. Wartość ta zmierza do 1. Adekwatnie, jeśli „chunk” ustalony zostaje na m gdzie m>1, to rozmiar porcji ustalany jest podobnie jak wyżej, lecz nie może on stać się mniejszy od m. Wyjątkiem jest jedynie ostatnia porcja. Może ona być mniejsza od zadanej wielkości. Domyślny „chunk” (gdy nie jest ustalony) jest równy 1.
auto – System samodzielnie określa podział zrównoleglenia zadania.
runtime – Ta opcja zezwala na określanie na wykorzystywanie powyższych możliwości w trakcie działania programu. Przekazywanie jest powiązane ze zmienną środowiskową OMP_SCHEDULE:
$ export OMP_SCHEDULE="dynamic" $ export OMP_SCHEDULE="guided,4"
if – Powoduje, że wątki zrównoleglają zadanie tylko wtedy gdy warunek jest spełniony. W innym wypadku blok kodu jest przetwarzany szeregowo.
firstprivate – we wszystkich wątkach przypisywane są wartości początkowe, takie jak przed wejściem do bloku równoległego.
zmiennym lastprivate po zakończeniu bloku równoległego przypisywana jest ich wartość końcowa w bloku równoległym (tak jakby był on wykonywany sekwencyjnie).
threadprivate – uczynienie ze zmiennych globalnych, zmiennych prywatnych wątków, z ich zachowaniem pomiędzy różnymi blokami równoległymi.
reduction(operator | intrinsic: list) – zmienna posiada lokalną kopię w każdym wątku, lecz wartości lokalnych kopii są podsumowywane (redukowane) do współdzielonej globalnie zmiennej. Jest to bardzo użyteczne, jeśli dana operacja (ustalona w parametrze „operator” dla tego przypadku) pracuje na interaktywnym typie danych, takim, że jego wartość podczas konkretnej iteracji zależy od jego wartości w poprzedniej. Ogólnie, kroki, które prowadzą do operacyjnej inkrementacji są zrównoleglane, ale wątki gromadzą się i czekają na zaktualizowanie danych, dzięki temu inkrementacja następuje w dobrym porządku co zapobiega błędnym stanom. Jest to wymagane na przykład, przy całkowaniu numerycznym funkcji i równaniach różniczkowych.
flush – Punkt, w którym kompilator upewnia się, że wszystkie wątki w obszarze równoległym mają takie samo pojęcie o zmiennych podanych w parametrze
master – Uruchamiane jedynie przez wątek główny (wątek zarządzający resztą podczas przetwarzania dyrektywy OpenMP) Żadna niewidoczna bariera nie występuje, inne wątki nie muszą jej osiągnąć.
Zalety
Prostota – nie ma potrzeby przejmowania się przesyłaniem wiadomości, jak w MPI
Układ danych i dekompozycja jest obsługiwana automatycznie przez dyrektywy
Równoległość inkrementacyjna – można pracować na jednej porcji programu w jednym czasie, nie są potrzebne drastyczne zmiany kodu
Zunifikowany kod dla szeregowych i równoległych aplikacji – konstrukcje OpenMP są traktowane jako komentarz podczas kompilacji przy użyciu sekwencyjnego kompilatora
Oryginalny (szeregowy) kod na ogół nie potrzebuje zmian przy jego zrównoleglaniu przy użyciu OpenMP. Redukuje to szanse nieumyślnego wprowadzenia błędów przy konwersji.
Zarówno grubo-, jak i drobnoziarnista równoległość jest możliwa.
Wady
Obecnie działa wydajnie jedynie przy platformach wieloprocesorowych z pamięcią współdzieloną (zobacz jednak Cluster OpenMP Intela).
Wymaga kompilatora wspierającego OpenMP.
Skalowalność jest limitowana przez architekturę pamięci.
Brakuje niezawodnej obsługi błędów.
Brakuje drobno-ziarnistych mechanizmów kontroli przypisania wątku do procesora.
Zasady określania ilości wątków:
ustalenie liczby wątków przy pomocy klauzuli num_threads, np.:
#pragma omp parallel num_threads(2)
wywołanie funkcji omp_set_num_threads, np.:
omp_set_num_threads(4);
ustalenie zmiennej środowiskowej OMP_NUM_THREADS, np.:
$ set OMP_NUM_THREADS = 1;
w pozostałych przypadkach liczba wątków jest ustalana przez implementację OpenMP w danym systemie – zazwyczaj liczba procesorów w komputerze,
istnieje możliwość dynamicznego ustalania liczby wątków.
Zmienne środowiskowe:
OMP_DYNAMIC [TRUE/FALSE] – dynamiczne przydzielenie liczby wątków w równoległym obszarze
OMP_NESTED [TRUE/FALSE] – zagnieżdżona współbieżność
OMP_NUM_THREADS [INT] – maksymalna liczba wątków we współbieżnym obszarze
OMP_SCHEDULE [STATIC/DYNAMIC/GUIDED/RUNTIME [, chunk]] – tylko gdy ustawiona klauzula shedule(runtime), dla dyrektyw for lub parallel for, ustala sposób podziału iteracji pomiędzy wątki
Kiedy petla się nie zrównolegli?
Komputer z jednym procesorem,
Klauzula if nie została spełniona,
Włączony jest dynamiczny przydział liczby procesorów i system zdecyduje, że tylko jeden procesor jest w stanie obsłużyć pętle,
Liczba wątków ustawiona na wartość 1.
Hyper-threading – implementacja wielowątkowości współbieżnej opracowana przez firmę Intel i stosowana w procesorach Atom, Core i3, Core i5, Core i7, Pentium 4.
Hyper-threading służy zwiększeniu wydajności obliczeń prowadzonych równolegle przez mikroprocesory. Dla każdego fizycznego rdzenia procesora system operacyjny przypisuje dwa procesory wirtualne, a następnie dzieli obciążenie obliczeniami między nimi, jeżeli jest to możliwe. Hyper-threading wymaga nie tylko wsparcia ze strony systemu operacyjnego, ale również oprogramowania zoptymalizowanego specjalnie dla obsługi tej technologii. Intel zaleca wyłączanie jej, jeżeli używany jest system operacyjny bez takiej optymalizacji.
OpenMP przydziela jeden wątek na rdzeń. Jeżeli HT jest włączony to w takim wypadku przydzielane są dwa wątki na jeden rdzeń. Trzeba pamiętać o tym, że naszym ograniczeniem jest pamięć dzielona (za https://www.msi.umn.edu/sites/default/files/OpenMP.tutorial_1.pdf – slajd 18).
PI metodą Monte Carlo
Pole kwadratu = 4r2
Pole koła = ∏*r2
więc:
i dalej, mając pole koła i kwadratu można obliczyć:
Pola można otrzymać stosując metodę MC.
Losuje się n punktów z opisanego na tym kole kwadratu - dla koła o R = 1 współrzędne wierzchołków (-1,-1), (-1,1), (1,1), (1,-1).
Po wylosowaniu każdego z tych punktów trzeba sprawdzić, czy jego współrzędne spełniają powyższą nierówność (tj. czy punkt należy do koła).
Wynikiem losowania jest informacja, że z n wszystkich prób k było trafionych, zatem pole koła wynosi
więc PI = 4 * liczba trafionych / liczba_wszystkich
Inne metody:
1.
Wzór ten, odkryty przez Leibniza, otrzymuje się po rozwinięciu w szereg Maclaurina funkcji y = arctg x i podstawieniu x = 1 ( arctg 1 = ∏/4 ).
2.
To także rozwinięcie w szereg Maclaurina, ale tym razem funkcji y = arcsin x arcsin 1 = ∏/2 ).
3.
Wzór odkryty przez Johna Wallisa
4.
To rozwinięcie, odkryte przez Eulera, otrzymuje się z teorii tzw. szeregów trygonometrycznych.
Pytania:
- co to openmp
- wady i zalety open mp
- co jest wydajniejsze zmienne prywatne czy współdzielone?
Prywatne. Chodzi o to, że nie tracimy czasu na synchronizację.
- różnice między first private oraz private
- kiedy pętla się nie z równolegli
- jak przebiega proces kompilacji Openmp
- w jaki sposób można wyznaczyć liczbę PI (nie chodzi tutaj o Monte Carlo)
- czy openMP zrównoległa na wątkach, czy procesach,
- jak określić na ilu watkach ma zrównoleglić
- jeśli nie określimy to na ilu się wykona
- co w przypadku gdy mamy hyper-threading