ZUT - Polska Rama Kwalifikacji / Rok 2022/2023 / Wydział Informatyki / Informatyka (S1) / Inżynieria oprogramowania / Sylabus przedmiotu

Wydział Informatyki - Informatyka (S1)
specjalność: Inżynieria oprogramowania

Sylabus przedmiotu Programowanie równoległe i współbieżne:

Informacje podstawowe

Kierunek studiów	Informatyka
Forma studiów	studia stacjonarne	Poziom	pierwszego stopnia
Tytuł zawodowy absolwenta	inżynier
Obszary studiów	charakterystyki PRK, kompetencje inżynierskie PRK
Profil	ogólnoakademicki
Moduł	—
Przedmiot	Programowanie równoległe i współbieżne
Specjalność	Inżynieria oprogramowania
Jednostka prowadząca	Katedra Inżynierii Oprogramowania
Nauczyciel odpowiedzialny	Włodzimierz Bielecki <Wlodzimierz.Bielecki@zut.edu.pl>
Inni nauczyciele	Marek Pałkowski <Marek.Palkowski@zut.edu.pl>
ECTS (planowane)	4,0	ECTS (formy)	4,0
Forma zaliczenia	zaliczenie	Język	polski
Blok obieralny	3	Grupa obieralna	2

Formy dydaktyczne

Forma dydaktyczna	KOD	Semestr	Godziny	ECTS	Waga	Zaliczenie
laboratoria	L	5	30	2,0	0,50	zaliczenie
wykłady	W	5	30	2,0	0,50	zaliczenie

Wymagania wstępne

KOD	Wymaganie wstępne
W-1	Programowanie 2
W-2	Architektura systemów komputerowych
W-3	Systemy operacyjne

Cele przedmiotu

KOD	Cel modułu/przedmiotu
C-1	Uksztatowanie wiedzy i umiejtnoci niezbędnych do opracowania aplikacji równolegych i współbieżnych dla komputerów równoległych
C-2	Ukształtowanie świadomego rozumowania dokształcania się i odpowiedzialności za wspólne realizowanie projektów w zakresie programowania równoległego i współbieżnego

Treści programowe z podziałem na formy zajęć

KOD	Treść programowa	Godziny
laboratoria
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.	2
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.	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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
		30
wykłady
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.	2
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	2
T-W-3	Podstawowe techniki zrównoleglenia pętli programowych. Transformacja FAN. Transformacja PAR. Transformacja FAN+PAR. Transformacja PIPE.	2
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.	4
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.	2
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.	2
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.	2
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.	4
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.	2
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.	2
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ń.	2
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.	2
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.	2
		30

Obciążenie pracą studenta - formy aktywności

KOD	Forma aktywności	Godziny
laboratoria
A-L-1	Udział w zajęciach	30
A-L-2	Przygotowanie do zajć	8
A-L-3	Pisanie programów i sprawozdań	10
A-L-4	Konsultacje	2
		50
wykłady
A-W-1	Udział w wykładach	30
A-W-2	Przygotowanie sie dozaliczenia	16
A-W-3	Udział w konsultacjach	2
A-W-4	Zaliczenie	2
		50

Metody nauczania / narzędzia dydaktyczne

KOD	Metoda nauczania / narzędzie dydaktyczne
M-1	Wykad informacyjny/konwersatoryjny
M-2	Ćwiczenia laboratoryjne

Sposoby oceny

KOD	Sposób oceny
S-1	Ocena formująca: Ocena stopnia wykonania zadań praktycznych pod koniec każdych laboratoriów
S-2	Ocena formująca: Zaliczenie końcowe poprzez sprawdzenie efektów kształcenia: przedstawienie pytań i ocena odpowiedzi

Zamierzone efekty uczenia się - wiedza

Zamierzone efekty uczenia się	Odniesienie do efektów kształcenia dla kierunku studiów	Odniesienie do efektów zdefiniowanych dla obszaru kształcenia	Odniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżyniera	Cel przedmiotu	Treści programowe	Metody nauczania	Sposób oceny
I_1A_D02.03.2_W01 Zna podstawowe metody gromadzenia i przetwarzania danych i informacji w oparciu o komputery równoległe	I_1A_W02	—	—	C-1	T-L-1, T-L-2, T-L-3, T-L-4, T-L-5, T-L-6, T-L-7, T-L-8, T-L-10, T-L-9, T-L-11, T-L-13, T-L-12, T-L-14, T-L-15, T-W-3, T-W-4, T-W-5, T-W-6, T-W-7, T-W-8, T-W-10, T-W-9, T-W-11, T-W-1, T-W-2, T-W-12, T-W-13	M-2	S-2
I_1A_D02.03.2_W02 Zna API i biblioteki do tworzenia aplikacji równoległych dla komputerów wielordzeniowych	I_1A_W02	—	—	C-1	T-W-3, T-W-4, T-W-5, T-W-6, T-W-7, T-W-8, T-W-10, T-W-9, T-W-11, T-W-1, T-W-2, T-W-12, T-W-13	M-1	S-2

Zamierzone efekty uczenia się - umiejętności

Zamierzone efekty uczenia się	Odniesienie do efektów kształcenia dla kierunku studiów	Odniesienie do efektów zdefiniowanych dla obszaru kształcenia	Odniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżyniera	Cel przedmiotu	Treści programowe	Metody nauczania	Sposób oceny
I_1A_D02.03.2_U01 Potrafi w zakresie podstawowym projektować, implementować i testować oprogramowanie równoległe	I_1A_U06	—	—	C-1	T-L-1, T-L-2, T-L-3, T-L-4, T-L-5, T-L-6, T-L-7, T-L-8, T-L-10, T-L-9, T-L-11, T-L-13, T-L-12, T-L-14, T-L-15	M-2	S-1

Zamierzone efekty uczenia się - inne kompetencje społeczne i personalne

Zamierzone efekty uczenia się	Odniesienie do efektów kształcenia dla kierunku studiów	Odniesienie do efektów zdefiniowanych dla obszaru kształcenia	Odniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżyniera	Cel przedmiotu	Treści programowe	Metody nauczania	Sposób oceny
I_1A_D02.03.2_K01 Świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie programowania współbieżnego	I_1A_K01	—	—	C-1	T-L-1, T-L-2, T-L-3, T-L-4, T-L-5, T-L-6, T-L-7, T-L-8, T-L-10, T-L-9, T-L-11, T-L-13, T-L-12, T-L-14, T-L-15	M-2	S-1

Kryterium oceny - wiedza

Efekt uczenia się	Ocena	Kryterium oceny
I_1A_D02.03.2_W01 Zna podstawowe metody gromadzenia i przetwarzania danych i informacji w oparciu o komputery równoległe	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ż
I_1A_D02.03.2_W02 Zna API i biblioteki do tworzenia aplikacji równoległych dla komputerów wielordzeniowych	2,0	nie zna API i bibliotek do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
	3,0	ma wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
	3,5	ma wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia prostych aplikacji
	4,0	ma szczegółową wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia prostych aplikacji
	4,5	ma szczegółową wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia zaawansowanych aplikacji
	5,0	ma szczegółową wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia zaawansowanych aplikacji oraz potrafi udowodnić i uzasadnić odpowiedź

Kryterium oceny - umiejętności

Efekt uczenia się	Ocena	Kryterium oceny
I_1A_D02.03.2_U01 Potrafi w zakresie podstawowym projektować, implementować i testować oprogramowanie równoległe	2,0	nie spełnia kryteriów określonych dla oceny 3
	3,0	potrafi skompilować program w openmp z Pragmami parallel i for
	3,5	wymagania na ocenę 3 - dodatkowo: - potrafi poprawnie skonfigurować pragmy parallel i for
	4,0	wymagania na ocenę 3,5 - dodatkowo: - potrafi skonfigurować większość pragm OpewnMP 2.5
	4,5	wymagania na ocenę 4 - dodatkowo: - potrafi określić przyspieszenie programu
	5,0	wymagania na ocenę 4,5- dodatkowo: - potrafi określić skalowalność i efektywność programu

Kryterium oceny - inne kompetencje społeczne i personalne

Efekt uczenia się	Ocena	Kryterium oceny
I_1A_D02.03.2_K01 Świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie programowania współbieżnego	2,0	nie potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących wytwarzania aplikacji równoległych
	3,0	rozumie potrzebę dokształcania i dzielenia się wiedzą w zakresie programowania równoległego i współbieżnego
	3,5	jest w stanie zaprezentować w pełni zaimplementowane rozwiązanie w oparciu o dokształcania się
	4,0	jest w stanie zaprezentować w pełni i przedyskutować z prowadzącym zaimplementowane rozwiązanie w oparciu o dokształcania się
	4,5	na bazie kompetencji wymaganych na niższe oceny jest w stanie podzielić się wiedzą w usystematyzowany sposób z grupą
	5,0	na bazie kompetencji wymaganych na niższe oceny jest w stanie przygotować i zaprezentować własne propozycje w zakresie programowania równoległego i współbieżnego

Literatura podstawowa

Rohit Chandra et al., Parallel Programming in OpenMP, Academic Press, London, 2001
W. Bielecki, Przetwarzanie równoległe i rozproszone, Politechnika Szczecińska, Szczecin, 2007
B. Chapman, Jost, and Van Der Pas, Using OpenMP, MIT Press, Cambridge, 2008

Literatura dodatkowa

specyfikacja OpenMP 2.5, www.openmp.org, 2005

Treści programowe - laboratoria

KOD	Treść programowa	Godziny
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.	2
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.	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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
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.	2
		30

Treści programowe - wykłady

KOD	Treść programowa	Godziny
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.	2
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	2
T-W-3	Podstawowe techniki zrównoleglenia pętli programowych. Transformacja FAN. Transformacja PAR. Transformacja FAN+PAR. Transformacja PIPE.	2
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.	4
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.	2
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.	2
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.	2
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.	4
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.	2
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.	2
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ń.	2
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.	2
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.	2
		30

Formy aktywności - laboratoria

KOD	Forma aktywności	Godziny
A-L-1	Udział w zajęciach	30
A-L-2	Przygotowanie do zajć	8
A-L-3	Pisanie programów i sprawozdań	10
A-L-4	Konsultacje	2
		50

(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KOD	Forma aktywności	Godziny
A-W-1	Udział w wykładach	30
A-W-2	Przygotowanie sie dozaliczenia	16
A-W-3	Udział w konsultacjach	2
A-W-4	Zaliczenie	2
		50

(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

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-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-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-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-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-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.
	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-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-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-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-15	Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej.
	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-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-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-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-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-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-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-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-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-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-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.
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ż

Pole	KOD	Znaczenie kodu
Zamierzone efekty uczenia się	I_1A_D02.03.2_W02	Zna API i biblioteki do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
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-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-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-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-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-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-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-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-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-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-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-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.
Metody nauczania	M-1	Wykad informacyjny/konwersatoryjny
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 API i bibliotek do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
	3,0	ma wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
	3,5	ma wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia prostych aplikacji
	4,0	ma szczegółową wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia prostych aplikacji
	4,5	ma szczegółową wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia zaawansowanych aplikacji
	5,0	ma szczegółową wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia zaawansowanych aplikacji oraz potrafi udowodnić i uzasadnić odpowiedź

Pole	KOD	Znaczenie kodu
Zamierzone efekty uczenia się	I_1A_D02.03.2_U01	Potrafi w zakresie podstawowym projektować, implementować i testować oprogramowanie równoległe
Odniesienie do efektów kształcenia dla kierunku studiów	I_1A_U06	Potrafi rozwiązywać podstawowe problemy algorytmiczne z uwzględnieniem ich złożoności posługując się kluczowymi językami programowania.
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-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-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-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-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-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.
	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-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-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-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-15	Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej.
Metody nauczania	M-2	Ćwiczenia laboratoryjne
Sposób oceny	S-1	Ocena formująca: Ocena stopnia wykonania zadań praktycznych pod koniec każdych laboratoriów
Kryteria oceny	Ocena	Kryterium oceny
	2,0	nie spełnia kryteriów określonych dla oceny 3
	3,0	potrafi skompilować program w openmp z Pragmami parallel i for
	3,5	wymagania na ocenę 3 - dodatkowo: - potrafi poprawnie skonfigurować pragmy parallel i for
	4,0	wymagania na ocenę 3,5 - dodatkowo: - potrafi skonfigurować większość pragm OpewnMP 2.5
	4,5	wymagania na ocenę 4 - dodatkowo: - potrafi określić przyspieszenie programu
	5,0	wymagania na ocenę 4,5- dodatkowo: - potrafi określić skalowalność i efektywność programu

Pole	KOD	Znaczenie kodu
Zamierzone efekty uczenia się	I_1A_D02.03.2_K01	Świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie programowania współbieżnego
Odniesienie do efektów kształcenia dla kierunku studiów	I_1A_K01	Potrafi krytycznie ocenić posiadaną wiedzę informatyczną oraz dostrzega dynamikę jej zmian.
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-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-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-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-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-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.
	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-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-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-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-15	Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej.
Metody nauczania	M-2	Ćwiczenia laboratoryjne
Sposób oceny	S-1	Ocena formująca: Ocena stopnia wykonania zadań praktycznych pod koniec każdych laboratoriów
Kryteria oceny	Ocena	Kryterium oceny
	2,0	nie potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących wytwarzania aplikacji równoległych
	3,0	rozumie potrzebę dokształcania i dzielenia się wiedzą w zakresie programowania równoległego i współbieżnego
	3,5	jest w stanie zaprezentować w pełni zaimplementowane rozwiązanie w oparciu o dokształcania się
	4,0	jest w stanie zaprezentować w pełni i przedyskutować z prowadzącym zaimplementowane rozwiązanie w oparciu o dokształcania się
	4,5	na bazie kompetencji wymaganych na niższe oceny jest w stanie podzielić się wiedzą w usystematyzowany sposób z grupą
	5,0	na bazie kompetencji wymaganych na niższe oceny jest w stanie przygotować i zaprezentować własne propozycje w zakresie programowania równoległego i współbieżnego