Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Informatyki - Informatyka (N1)

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

Informacje podstawowe

Kierunek studiów Informatyka
Forma studiów studia niestacjonarne Poziom pierwszego stopnia
Tytuł zawodowy absolwenta inżynier
Obszary studiów nauki techniczne, studia inżynierskie
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 dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
wykładyW5 18 2,00,50zaliczenie
laboratoriaL5 18 2,00,50zaliczenie

Wymagania wstępne

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

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Uksztatowanie wiedzy i umiejtnoci niezbędnych do opracowania aplikacji równolegych i współbieżnych dla komputerów równoległych
C-2Ukształ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ęć

KODTreść programowaGodziny
laboratoria
T-L-1Wprowadzenie 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.1
T-L-2Napisanie 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.1
T-L-3Modyfikacja 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.1
T-L-4Skompilowanie 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.1
T-L-5Wprowadzenie 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.1
T-L-6Zapoznanie 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.1
T-L-7Zapoznanie 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.1
T-L-8Wykonanie 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.1
T-L-9Zapoznanie 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.1
T-L-10Wł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.1
T-L-11Ró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-12Ró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.1
T-L-13Wł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-14Prezentacja 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.1
T-L-15Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej.2
18
wykłady
T-W-1Architektura 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.1
T-W-2Poję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ów1
T-W-3Podstawowe techniki zrównoleglenia pętli programowych. Transformacja FAN. Transformacja PAR. Transformacja FAN+PAR. Transformacja PIPE.1
T-W-4Podstawowe 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.2
T-W-5Biblioteki 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.1
T-W-6Czym 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-7OpenMP 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-8OpenMP 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.2
T-W-9OpenMP 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.1
T-W-10OpenmP 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.1
T-W-11OpenMP 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-12Co 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.1
T-W-13Kluczowe 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.1
18

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

KODForma aktywnościGodziny
laboratoria
A-L-1Udział w zajęciach18
A-L-2Przygotowanie do zajć20
A-L-3Pisanie programów i sprawozdań10
A-L-4Konsultacje2
50
wykłady
A-W-1Udział w wykładach18
A-W-2Przygotowanie sie dozaliczenia28
A-W-3Udział w konsultacjach2
A-W-4Zaliczenie2
50

Metody nauczania / narzędzia dydaktyczne

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

Sposoby oceny

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

Zamierzone efekty kształcenia - wiedza

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposó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_W02C-1T-W-1, T-W-2, T-W-3, T-W-4, T-W-5, T-W-6, T-W-7, T-W-8, T-W-9, T-W-10, T-W-11, T-W-12, T-W-13, 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-9, T-L-10, T-L-11, T-L-12, T-L-13, T-L-14, T-L-15M-2S-2
I_1A_D02.03.2_W02
Zna API i biblioteki do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
I_1A_W02C-1T-W-1, T-W-2, T-W-3, T-W-4, T-W-5, T-W-6, T-W-7, T-W-8, T-W-9, T-W-10, T-W-11, T-W-12, T-W-13M-1S-2

Zamierzone efekty kształcenia - umiejętności

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
I_1A_D02.03.2_U01
Potrafi w zakresie podstawowym projektować, implementować i testować oprogramowanie równoległe
I_1A_U06C-1T-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-9, T-L-10, T-L-11, T-L-12, T-L-13, T-L-14, T-L-15M-2S-1

Zamierzone efekty kształcenia - inne kompetencje społeczne i personalne

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposó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_K01C-1T-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-9, T-L-10, T-L-11, T-L-12, T-L-13, T-L-14, T-L-15M-2S-1

Kryterium oceny - wiedza

Efekt kształceniaOcenaKryterium oceny
I_1A_D02.03.2_W01
Zna podstawowe metody gromadzenia i przetwarzania danych i informacji w oparciu o komputery równoległe
2,0nie zna podstawowych algorytmów projektowania algorytmów równoległych
3,0zna podstawowe algorytmy projektowania algorytmów równoległych
3,5zna podstawowe algorytmy projektowania algorytmów równoległych i wie jak zastosować je do zrównoleglenia prostych algorytmów sekwencyjnych
4,0zna szczegółowo podstawowe algorytmy projektowania algorytmów równoległych i wie jak zastosować je do zrównoleglenia prostych algorytmów sekwencyjnych
4,5zna szczegółowo podstawowe algorytmy projektowania algorytmów równoległych i wie jak i zastosować je do zrównoleglenia algorytmów sekwencyjnych
5,0zna 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,0nie zna API i bibliotek do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
3,0ma wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
3,5ma wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia prostych aplikacji
4,0ma 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,5ma 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,0ma 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 kształceniaOcenaKryterium oceny
I_1A_D02.03.2_U01
Potrafi w zakresie podstawowym projektować, implementować i testować oprogramowanie równoległe
2,0nie spełnia kryteriów określonych dla oceny 3
3,0potrafi skompilować program w openmp z Pragmami parallel i for
3,5wymagania na ocenę 3 - dodatkowo: - potrafi poprawnie skonfigurować pragmy parallel i for
4,0wymagania na ocenę 3,5 - dodatkowo: - potrafi skonfigurować większość pragm OpewnMP 2.5
4,5wymagania na ocenę 4 - dodatkowo: - potrafi określić przyspieszenie programu
5,0wymagania na ocenę 4,5- dodatkowo: - potrafi określić skalowalność i efektywność programu

Kryterium oceny - inne kompetencje społeczne i personalne

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

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

Literatura dodatkowa

  1. specyfikacja OpenMP 2.5, www.openmp.org, 2005

Treści programowe - laboratoria

KODTreść programowaGodziny
T-L-1Wprowadzenie 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.1
T-L-2Napisanie 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.1
T-L-3Modyfikacja 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.1
T-L-4Skompilowanie 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.1
T-L-5Wprowadzenie 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.1
T-L-6Zapoznanie 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.1
T-L-7Zapoznanie 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.1
T-L-8Wykonanie 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.1
T-L-9Zapoznanie 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.1
T-L-10Wł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.1
T-L-11Ró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-12Ró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.1
T-L-13Wł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-14Prezentacja 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.1
T-L-15Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej.2
18

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Architektura 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.1
T-W-2Poję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ów1
T-W-3Podstawowe techniki zrównoleglenia pętli programowych. Transformacja FAN. Transformacja PAR. Transformacja FAN+PAR. Transformacja PIPE.1
T-W-4Podstawowe 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.2
T-W-5Biblioteki 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.1
T-W-6Czym 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-7OpenMP 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-8OpenMP 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.2
T-W-9OpenMP 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.1
T-W-10OpenmP 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.1
T-W-11OpenMP 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-12Co 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.1
T-W-13Kluczowe 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.1
18

Formy aktywności - laboratoria

KODForma aktywnościGodziny
A-L-1Udział w zajęciach18
A-L-2Przygotowanie do zajć20
A-L-3Pisanie programów i sprawozdań10
A-L-4Konsultacje2
50
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Udział w wykładach18
A-W-2Przygotowanie sie dozaliczenia28
A-W-3Udział w konsultacjach2
A-W-4Zaliczenie2
50
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_D02.03.2_W01Zna podstawowe metody gromadzenia i przetwarzania danych i informacji w oparciu o komputery równoległe
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_W02Posiada 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 przedmiotuC-1Uksztatowanie wiedzy i umiejtnoci niezbędnych do opracowania aplikacji równolegych i współbieżnych dla komputerów równoległych
Treści programoweT-W-1Architektura 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-2Poję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-3Podstawowe techniki zrównoleglenia pętli programowych. Transformacja FAN. Transformacja PAR. Transformacja FAN+PAR. Transformacja PIPE.
T-W-4Podstawowe 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-5Biblioteki 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-6Czym 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-7OpenMP 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-8OpenMP 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-9OpenMP 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-10OpenmP 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-11OpenMP 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-12Co 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-13Kluczowe 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-L-1Wprowadzenie 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-2Napisanie 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-3Modyfikacja 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-4Skompilowanie 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-5Wprowadzenie 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-6Zapoznanie 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-7Zapoznanie 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-8Wykonanie 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-9Zapoznanie 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-10Wł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-11Ró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-12Ró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-13Wł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-14Prezentacja 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-15Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej.
Metody nauczaniaM-2Ćwiczenia laboratoryjne
Sposób ocenyS-2Ocena formująca: Zaliczenie końcowe poprzez sprawdzenie efektów kształcenia: przedstawienie pytań i ocena odpowiedzi
Kryteria ocenyOcenaKryterium oceny
2,0nie zna podstawowych algorytmów projektowania algorytmów równoległych
3,0zna podstawowe algorytmy projektowania algorytmów równoległych
3,5zna podstawowe algorytmy projektowania algorytmów równoległych i wie jak zastosować je do zrównoleglenia prostych algorytmów sekwencyjnych
4,0zna szczegółowo podstawowe algorytmy projektowania algorytmów równoległych i wie jak zastosować je do zrównoleglenia prostych algorytmów sekwencyjnych
4,5zna szczegółowo podstawowe algorytmy projektowania algorytmów równoległych i wie jak i zastosować je do zrównoleglenia algorytmów sekwencyjnych
5,0zna 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ż
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_D02.03.2_W02Zna API i biblioteki do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_W02Posiada 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 przedmiotuC-1Uksztatowanie wiedzy i umiejtnoci niezbędnych do opracowania aplikacji równolegych i współbieżnych dla komputerów równoległych
Treści programoweT-W-1Architektura 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-2Poję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-3Podstawowe techniki zrównoleglenia pętli programowych. Transformacja FAN. Transformacja PAR. Transformacja FAN+PAR. Transformacja PIPE.
T-W-4Podstawowe 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-5Biblioteki 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-6Czym 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-7OpenMP 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-8OpenMP 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-9OpenMP 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-10OpenmP 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-11OpenMP 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-12Co 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-13Kluczowe 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 nauczaniaM-1Wykad informacyjny/konwersatoryjny
Sposób ocenyS-2Ocena formująca: Zaliczenie końcowe poprzez sprawdzenie efektów kształcenia: przedstawienie pytań i ocena odpowiedzi
Kryteria ocenyOcenaKryterium oceny
2,0nie zna API i bibliotek do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
3,0ma wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych
3,5ma wiedzę o API i bibliotekach do tworzenia aplikacji równoległych dla komputerów wielordzeniowych i potrafi zastosować ją do tworzenia prostych aplikacji
4,0ma 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,5ma 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,0ma 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ź
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_D02.03.2_U01Potrafi w zakresie podstawowym projektować, implementować i testować oprogramowanie równoległe
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_U06Potrafi rozwiązywać podstawowe problemy algorytmiczne z uwzględnieniem ich złożoności posługując się kluczowymi językami programowania.
Cel przedmiotuC-1Uksztatowanie wiedzy i umiejtnoci niezbędnych do opracowania aplikacji równolegych i współbieżnych dla komputerów równoległych
Treści programoweT-L-1Wprowadzenie 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-2Napisanie 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-3Modyfikacja 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-4Skompilowanie 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-5Wprowadzenie 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-6Zapoznanie 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-7Zapoznanie 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-8Wykonanie 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-9Zapoznanie 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-10Wł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-11Ró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-12Ró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-13Wł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-14Prezentacja 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-15Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej.
Metody nauczaniaM-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Ocena stopnia wykonania zadań praktycznych pod koniec każdych laboratoriów
Kryteria ocenyOcenaKryterium oceny
2,0nie spełnia kryteriów określonych dla oceny 3
3,0potrafi skompilować program w openmp z Pragmami parallel i for
3,5wymagania na ocenę 3 - dodatkowo: - potrafi poprawnie skonfigurować pragmy parallel i for
4,0wymagania na ocenę 3,5 - dodatkowo: - potrafi skonfigurować większość pragm OpewnMP 2.5
4,5wymagania na ocenę 4 - dodatkowo: - potrafi określić przyspieszenie programu
5,0wymagania na ocenę 4,5- dodatkowo: - potrafi określić skalowalność i efektywność programu
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_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ówI_1A_K01Potrafi krytycznie ocenić posiadaną wiedzę informatyczną oraz dostrzega dynamikę jej zmian.
Cel przedmiotuC-1Uksztatowanie wiedzy i umiejtnoci niezbędnych do opracowania aplikacji równolegych i współbieżnych dla komputerów równoległych
Treści programoweT-L-1Wprowadzenie 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-2Napisanie 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-3Modyfikacja 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-4Skompilowanie 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-5Wprowadzenie 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-6Zapoznanie 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-7Zapoznanie 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-8Wykonanie 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-9Zapoznanie 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-10Wł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-11Ró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-12Ró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-13Wł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-14Prezentacja 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-15Prezentacja kompilatora TRACO. Panel ćwiczeniowy w zrówenoleglaniu kodu. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej.
Metody nauczaniaM-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Ocena stopnia wykonania zadań praktycznych pod koniec każdych laboratoriów
Kryteria ocenyOcenaKryterium oceny
2,0nie potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących wytwarzania aplikacji równoległych
3,0rozumie potrzebę dokształcania i dzielenia się wiedzą w zakresie programowania równoległego i współbieżnego
3,5jest w stanie zaprezentować w pełni zaimplementowane rozwiązanie w oparciu o dokształcania się
4,0jest w stanie zaprezentować w pełni i przedyskutować z prowadzącym zaimplementowane rozwiązanie w oparciu o dokształcania się
4,5na bazie kompetencji wymaganych na niższe oceny jest w stanie podzielić się wiedzą w usystematyzowany sposób z grupą
5,0na 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