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 z
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
Klauzule atrybutów współdzielenia danych
" 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.
Klauzule synchronizacji
" 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.
Klauzule planowania
" 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:
1. 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.
2. 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.
3. 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.
4. auto  System samodzielnie określa podział zrównoleglenia zadania.
5. 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"
Kontrola IF
" if  Powoduje, że wątki zrównoleglają zadanie tylko wtedy gdy warunek jest spełniony.
W innym wypadku blok kodu jest przetwarzany szeregowo.
Inicjalizacja
" 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.
Redukcja
" 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.
Inne
" 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 i wady
" 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:
1. ustalenie liczby wątków przy pomocy klauzuli num_threads, np.:
#pragma omp parallel num_threads(2)
2. wywołanie funkcji omp_set_num_threads, np.:
omp_set_num_threads(4);
3. ustalenie zmiennej środowiskowej OMP_NUM_THREADS, np.:
$ set OMP_NUM_THREADS = 1;
4. w pozostałych przypadkach liczba wątków jest ustalana przez implementację OpenMP w
danym systemie  zazwyczaj liczba procesorów w komputerze,
5. 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.
1. 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).
2. 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