Pole | KOD | Znaczenie kodu |
---|
Zamierzone efekty uczenia się | I_1A_D02.03.2_W01 | Zna podstawowe metody gromadzenia i przetwarzania danych i informacji w oparciu o komputery równoległe |
---|
Odniesienie do efektów kształcenia dla kierunku studiów | I_1A_W02 | Posiada wiedzę w zakresie projektowania, analizy i implementacji algorytmów, struktur danych oraz konstrukcji programistycznych, zna podstawowe problemy algorytmiczne występujące w obszarze informatyki. |
---|
Cel przedmiotu | C-1 | Uksztatowanie wiedzy i umiejtnoci niezbędnych do opracowania aplikacji równolegych i współbieżnych dla komputerów równoległych |
---|
Treści programowe | T-W-11 | OpenMP 2.5: Dyrektywy sieroty. Zakresy zmiennych zawartych wewnątrz sierot.Równoległość zagnieżdżona. Zmienne środowiskowe w OpenMP. Funkcje zarządzania środowiskiem wykonawczym. Funkcje synchronizacji wątków. Funkcje pomiaru czasu wykonania obliczeń. |
---|
T-W-6 | Czym jest OpenMP 2.5. Co oznacza otwarty standard. Model Fork – Join. Historia OpenMP. Składowe OpenMP.Zalety OpenMP. Blok strukturalny. Czego nie zapewnia OpenMP. Rola dyrektyw OpenMP. |
T-W-7 | OpenMP 2.5: Dyrektywa Parallel, jej klauzule. Zmienne prywatne i dzielone. Klauzula Default. Obszar statyczny i dynamiczny regionu równoległego. Klauzula IF. Zarządzanie liczbą wątków.Wątki Dynamiczne.Zagnieżdżone regiony równoległe. |
T-W-9 | OpenMP 2.5: Zasady domyślnego zakresu zmiennych. Wyjątki od zasady domyślnego zakresu zmiennych. Usuwanie/honorowanie zależności odwrotnych. Usuwanie/honorowanie zależności po wyjściu. Usuwanie zmiennych indukcji.Zrównoleglenie pętli z kilkoma gniazdami.Technika podziału pętli. Technika rozszerzenia zmiennej skalarnej. |
T-W-8 | OpenMP 2.5: Dyrektywa DO/for, jej klauzule. Ograniczenia dyrektywy DO/for. Klauzula LASTPRIVATE. Klauzula Nowait. Klauzula Reduction. Klauzula SCHEDULE, jej argumenty. Sposoby szeregowania iteracji pętli. Wybór odpowiedniego sposobu szeregowania iteracji pętli.Klauzula i dyrektywa ORDERED.Klauzula COLLAPSE. |
T-W-13 | Kluczowe czynniki wpływające na wydajność aplikacji równoległych: Minimalizacja liczby wejść do regionu równoległego. Efekt fałszywego podziału. Bilansowanie obciążenia wątków. Niewłaściwa równoległość. Jak możemy uniknąć barier? Zwiększenie granulacji zadania. |
T-W-12 | Co to jest wyścig danych. Konstrukcje do obsługi synchronizacji w OpenMP. Dyrektywa BARRIER.Dyrektywa FLUSH. Dyrektywa master.Dyrektywa CRITICAL. Dyrektywa ATOMIC. Zastosowanie funkcji obsługi zamków do implementacji sekcji krytycznej. |
T-W-2 | Pojęcie zależności w programach. Rodzaje zależności w pętlach. Tożsamość semantyczna programów. Wpływ zależności na tożsamość semantyczną programów |
T-W-10 | OpenmP 2.5: Zmienne i klauzula threadprivate. Klauzula COPYIN. Dyrektywa Sections i jej klauzule. Dyrektywa Single i jej klauzule. Dyrektywy łączone. Ograniczenia dla wszystkich dyrektyw podziału pracy. |
T-W-5 | Biblioteki i API programowania równoległego: Posix Threads. Intel Threading Building Blocks. C++ 11 Threads. OpenMP. OpenCL. OpenACC. Zrównoleglenie automatyczne za pomocą kompilatorów optymalizujących. |
T-W-1 | Architektura komputerów równoległych. Prawo Moore’a. Taksonomia Flynna. Komputer MIMD z pamięcią dzieloną. Proces, jego zasoby. Wątek, jego zasoby.
Wielozadaniowość, wielowątkowość. Modele programowania wielowątkowego. |
T-W-3 | Podstawowe techniki zrównoleglenia pętli programowych. Transformacja FAN.
Transformacja PAR. Transformacja FAN+PAR. Transformacja PIPE. |
T-W-4 | Podstawowe wskaźniki jakości aplikacji równoległych. Program deterministyczny. Ziarnistość obliczeń. Wpływ ziarnistości na czas wykonania programu równoległego. Lokalność programu jako miara. Lokalność programu jako cecha . Zasady organizacji i działania pamięci podręcznej. Przyspieszenie programu równoległego.Rodzaje przyspieszenia. Punkt złotego środka liczby wątków. Efektywność. Koszt obliczeń w środowisku równoległym. Prawo Amdahla. Prawo Gustafsona. Definicja programu skalowalnego. Skalowalność systemu równoległego. |
T-L-1 | Wprowadzenie do napisania prostych programów w języku C/C++ z OpenMP
Kompilacja, uruchomienie i testowanie aplikacji.
Wyświetlenie specyfikacji procesorów z komendy poleceń w systemie Linux.
Wyświetlenie uruchomionych procesów i użytkowników w systemie.
Mierzenie czasu wykonywania kodu za pomocą funkcji omp_get_wtime().
Wyjaśnienie kwestii nie zrównoleglania operacji wejścia/wyjścia oraz pojęć wątek, proces,
rywalizacja między wątkami oraz sekcja krytyczna. |
T-L-2 | Napisanie programu obliczającego równolegle mnożenie macierzy.
Wykorzystanie dyrektywy #pragma omp paralel.
Wykorzystanie dyrektywy #pragma omp for.
Zmierzenie czasu obliczeń dla różnej liczby wątków.
Ustawienie żądanej liczby wątków: klauzula num_thrreads(), funkcje omp_get_num_threads(),
omp_set_num_threads().
Porównanie wyników czasowych dla 1, 2, 4 oraz 8 wątków.
Porównanie wyników czasowych dla różnych rozmiarów macierzy. |
T-L-4 | Skompilowanie programu wyliczającego zbiór Mandelbrota (fraktal).
https://rosettacode.org/wiki/Mandelbrot_set#PPM_non_interactive
Zapoznanie się z formatem graficznym PPM.
Wyjaśnienie zagadnienia zrównoleglenia tego kodu.
Modyfikacja kodu:
- przesunięcie operacji zapisu plikowego poza pętle
- prywatyzacja zmiennych.
Wykorzystanie pragm omp paralel, for oraz klauzul private i shared.
Porównanie plików wyjściowych wersji sekwencyjnej i równoległej.
Zapoznanie się z pojęciami deterministyczności oraz zgodności kodu równoległego z
sekwencyjnym odpowiednikiem.
Zmierzenie czasu kodu dla wielu wątków oraz policzenie przyspieszenia. |
T-L-5 | Wprowadzenie pojęcia harmogramowania iteracji.
Zapoznanie się z klauzulą schedule i jej parametrami w pragmie omp for.
Modyfikacje parametrów schedule.
Interpretacja wyników: student ma za zadanie zrozumieć dlaczego domyślny podział nie jest
efektywny dla większej liczby wątków niż 2.
Wyjaśnienie działania kodu (tło fraktala liczy się krótko).
Zapoznanie się z pojęciami równoważenie obciążenia (load balancing) i czasy przestojów (idle-time).
Strojenie klauzuli schedule, zapoznanie się z harmonogramowaniem dynamicznym i wielkością
paczki (chunk size).
Wykonanie sprawozdania na podstawie wyników z laboratorium 4 i 5, tabele z wynikami
czasowymi i wykresy przyspieszeń, analiza porównawcza dla różnych parametrów schedule oraz
wnioski. Ocena 2. |
T-L-3 | Modyfikacja programu mnożenia macierzy – zamiana czytania kolumnami na wiersze w jednej z
macierzy wejściowej.
Wyjaśnienie pojęcia lokalności, pamięci kieszeniowej i RAM.
Wyjaśnienie pojęcie przyspieszenia, w tym liniowego i superliniowego.
Wyjaśnienie istoty lokalności dla przetwarzania równoległego.
Porównanie wyników czasowych z wynikami uzyskanymi w laboratorium 2.
Wykonanie sprawozdania na podstawie wyników z laboratorium 2 i 3, tabele z wynikami
czasowymi i wykresy przyspieszeń, analiza porównawcza oraz wnioski. Ocena 1. |
T-L-6 | Zapoznanie się z kodem obliczania fraktala BuddaBrot.
Dobranie rozmiaru obliczeń w zależności od jego parametrów wejściowych.
Zrównoleglenie kodu z wykorzystaniem pragm omp paralell i for:
- usekwencyjnienie części kodu – zmierzenie czasu tej części i szacowanie wpływu na końcowe
przyspieszenie według Prawa Amdahla.
- zamiana standardowej funkcji losującej na rand_r i wyjaśnienie dlaczego potrzebna jest
specjalna implementacja dla kodu współbieżnego.
Zaliczeniem jest program oraz aktywność w rozwiązywaniu zadań w czasie laboratorium. Ocena
3. |
T-L-11 | Równoległa implementacja rysowania trójkąta Sierpińskiego.
Format wyjściowy: PPM.
Wprowadzenie pojęcia: równoległość drobno- i gruboziarnista oraz częstość występowania
synchronizacji.
Zrównoleglenie:
- narysowanie głównego trójkąta
- wyliczenie potomnych trójkątów
- narysowanie potomnych trójkątów (równolegle)
- dla każdego potomnego trójkąta wyliczenie potomnych i dodatnie do tej samej puli
- narysowanie wszystkich potomnych trójkątów (równolegle), itd.
Zastosowanie pragm omp barrier oraz single.
Przykładowo: rysowanie jeden wątek | single obliczanie potomków 3 | rysowanie trójkątów 3
wątki, bariera | single obliczanie potomków 3*3 | rysowanie trójkątów 9 wątki, bariera, …
Zaliczeniem jest program oraz aktywność w rozwiązywaniu zadań w czasie laboratorium. Ocena
7. |
T-L-13 | Własna implementacja równoległa generatora obrazów ASCII.
Format wejściowy: PPM, format wyjściowy: plik tekstowy.
Przyporządkowanie każdemu odcieniowi innego znaku ASCII w obrębie bloku pikseli.
Zrównoleglenie kodu za pomocą pragmy omp paralell for.
Zastosowanie aplikacji na obrazach o dużych rozmiarach.
Zmierzenie czasu, przyspieszenia.
Zapoznanie się z pojęciem efektywności.
Zapoznanie się z pojęciem skalowalności.
Zaliczeniem laboratorium jest sprawozdanie, w którym należy przedstawić wynik czasowe oraz
przyspieszenie , efektywność oraz skalowalność. Ocena 9. |
T-L-15 | Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu.
Zaliczenie i oddawanie zaległych programów i sprawozdań.
Wystawienie oceny końcowej. |
T-L-9 | Zapoznanie się z algorytmami filtry graficzne bazujące na maskach (rozmywający, wyostrzający).
Implementacja aplikacji dla plików wejściowych w formacie graficznym PPM.
Zapis poszczególnych plików w formacie PPM.
Zrównoleglenie aplikacji (pragmy omp paralell for).
Zmierzenie czasu i obliczenie przyspieszenia.
Zaliczeniem jest program oraz aktywność w rozwiązywaniu zadań w czasie laboratorium. Ocena
5. |
T-L-10 | Własna implementacja pragma omp paralell for z harmonogramowaniem dynamicznym.
Zapoznanie się z sekcją krytyczną.
Wykorzystanie pragm omp paralell.
Wykorzystanie pragmy omp critical.
Zrozumienie podziału przestrzenie iteracji pomiędzy wątkami (uproszczenie zadania: liczba
iteracji jest podzielna przez liczbę wątków).
Wprowadzenie dodatkowych zmiennych wyliczających prywatne granice wątka.
Rywalizacja wątków o kolejną paczkę za pomocą omp critical.
Zastosowanie implementacji na programie z Laboratorium 2.
Zaliczeniem jest program oraz aktywność w rozwiązywaniu zadań w czasie laboratorium. Ocena
6. |
T-L-12 | Równoległa implementacja przejścia przez labirynt.
Format wyjściowy: tekstowy lub animacja.
Zrównoleglenie na tej samej zasadzie co w zadaniu nr 11.
Potomkami są tym razem nowe ścieżki gdy wątek natrafi na rozwidlenie ścieżek.
Aplikacja kończy się po odwiedzeniu wszystkich korytarzy.
Zastosowanie pragm omp barrier oraz single.
Wątki przemierzające labirynt synchronizowane są co jeden krok, jeżeli napotykany jest nowy
korytarz, dodajemy do puli kolejny wątek.
Możliwość zapętlenia: wątki natrafiają na odwiedzony korytarz, traktują go jako ścianę.
Możliwość kolizji: wątek powinien zakładać blokadę co każdy krok gdyż daną komórkę może
odwiedzać inny wątek w tym samym czasie.
Zaliczeniem laboratorium jest sprawozdanie, w którym należy wyjaśnić zastosowany model
współbieżności w tym zadaniu. Ocena 8. |
T-L-14 | Prezentacja sprawozdań:
Grupy studentów 2-3 osobowe prezentują inne narzędzia do zrównoleglania kodu, modele
współbieżności oraz programowanie koprocesorów. Tematy:
Temat 1: Intel Threading Building Blocks
Temat 2: C++ 11 Threads
Temat 3: Posix Threads
Temat 4: Intel Xeon Phi
Czas prezentacji: 20 minut.
Ocena 10. |
T-L-7 | Zapoznanie się z algorytmem Conoway’a („Gra w życie”).
Własna implementacja powyższego zadania dla jednej kolonii. Sposób wizualizacji zależny od
studenta (tekstowy, graficzny, animacja).
Przetwarzanie równoległe w wyliczeniu nowej tablicy (pragma omp paralell for).
Zastąpienie dwóch tablic jedną wykorzystując operację modulo.
Wykorzystanie klauzuli omp single, omp barier w celu wizualizacji poprzez jeden wątek. |
T-L-8 | Wykonanie implementacji dla wielu kolonii w algorytmie Conoway’a.
Student sam dobiera (modyfikuje) reguły gry dla wielu kolonii (krzyżowanie, zwalczanie).
Wprowadzenie pojęcie blokady i ich implementacja w OpenMP: funkcje omp_set_lock,
omp_unset_lock i typ omp_lock_t.
Zrównoleglenie za pomocą pragmy pragma omp paralell sections.
Każda kolonia realizowana jest poprzez osobny wątek (section).
Kolonie zaczynają od innego miejsca w tablicy.
Za pomocą funkcji blokowania wprowadzenie poprawnej implementacji rywalizacji wątków.
Każdy wątek równolegle oblicza tablicę (równoległość zagnieżdżona).
Zapoznanie się z funkcjami omp_set_nested i omp_get_nested.
Zaliczeniem jest program oraz aktywność w rozwiązywaniu zadań z laboratorium 7 i 8, a także
zrozumienie pojęć rywalizacji wątków i zagnieżdżenia. Ocena 4. |
Metody nauczania | M-2 | Ćwiczenia laboratoryjne |
---|
Sposób oceny | S-2 | Ocena formująca: Zaliczenie końcowe poprzez sprawdzenie efektów kształcenia: przedstawienie pytań i ocena odpowiedzi |
---|
Kryteria oceny | Ocena | Kryterium oceny |
---|
2,0 | nie zna podstawowych algorytmów projektowania algorytmów równoległych |
3,0 | zna podstawowe algorytmy projektowania algorytmów równoległych |
3,5 | zna podstawowe algorytmy projektowania algorytmów równoległych i wie jak zastosować je do zrównoleglenia prostych algorytmów sekwencyjnych |
4,0 | zna szczegółowo podstawowe algorytmy projektowania algorytmów równoległych i wie jak zastosować je do zrównoleglenia prostych algorytmów sekwencyjnych |
4,5 | zna szczegółowo podstawowe algorytmy projektowania algorytmów równoległych i wie jak i zastosować je do zrównoleglenia algorytmów sekwencyjnych |
5,0 | zna szczegółowo podstawowe algorytmy projektowania algorytmów równoległych i wie jak zastosować je do zrównoleglenia algorytmów sekwencyjnych oraz potrafi udowodnić i uzasadnić swoją wypowiedż |