Wydział Informatyki - Informatyka (S2)
Sylabus przedmiotu Programowanie równoległe i rozproszone - Przedmiot obieralny II:
Informacje podstawowe
| Kierunek studiów | Informatyka | ||
|---|---|---|---|
| Forma studiów | studia stacjonarne | Poziom | drugiego stopnia |
| Tytuł zawodowy absolwenta | magister | ||
| Obszary studiów | nauki techniczne | ||
| Profil | ogólnoakademicki | ||
| Moduł | — | ||
| Przedmiot | Programowanie równoległe i rozproszone - Przedmiot obieralny II | ||
| Specjalność | projektowanie i zarządzanie projektami informatycznymi | ||
| Jednostka prowadząca | Katedra Inżynierii Oprogramowania | ||
| Nauczyciel odpowiedzialny | Marek Pałkowski <Marek.Palkowski@zut.edu.pl> | ||
| Inni nauczyciele | |||
| ECTS (planowane) | 4,0 | ECTS (formy) | 4,0 |
| Forma zaliczenia | zaliczenie | Język | polski |
| Blok obieralny | 9 | Grupa obieralna | 1 |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | Zaliczone przedmioty: Programowanie w językach C, C++, Architektura komputerów, Systemy operacyjne |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Uksztatowanie wiedzy i umiejtnoci niezbędnych do opracowania aplikacji równolegych dla komputerów wielerdzeniowych |
| C-2 | Ukształtowanie świadomego rozumowania dokształcania się i odpowiedzialności za wspólne realizowanie projektów w zakresie programowania 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. 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 i for. 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 i 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 oraz pojęcia lokalności. 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). Wyjaśnienie zagadnienia zrównoleglenia tego kodu. Modyfikacja kodu: - przesunięcie operacji zapisu plikowego poza pętle - prywatyzacja zmiennych. Porównanie plików wyjściowych wersji sekwencyjnej i równoległej. 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. 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. Ocena nr 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 nr 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 Laboratorium 9 (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 automatycznie zrównoleglających kod do Openmp TRACO i Pluto. Panel ćwiczeniowy i dyskusyjny. Zaliczenie i oddawanie zaległych programów i sprawozdań. Wystawienie oceny końcowej. | 2 |
| 30 | ||
| wykłady | ||
| T-W-1 | architektura komputerów wielordzeniowych oraz jej związek z wydajnością aplikacji równoległych | 2 |
| T-W-2 | podstawowe mierniki jakości aplikacji równoległych (lokalność, granulacja, determinizm, przyspieszenie i efektywność), prawa Amdahl’a i Gustaffson’a | 2 |
| T-W-3 | Pojęcie zaleznośći, rodzaje zależności w programach | 2 |
| T-W-4 | podstawowe transformacje pętli: FAN, PAR, PIPE | 2 |
| T-W-5 | pojęcie wątku, podstawowe konstrukcje aplikacji równoległych w OpenMP: region równoległy, powołaniei zakończenia wątków, model obliczeń | 2 |
| T-W-6 | Zrównoleglenie pętli w OpenMP, szeregowanie iteracji pętli do wątków | 2 |
| T-W-7 | konstrukcje podziału pracy między wątki w OpenMP | 2 |
| T-W-8 | Mechanizmy synchronizacji w OpenMP | 2 |
| T-W-9 | Mechanizm zadań w OpenMP(tasking) | 4 |
| T-W-10 | Biblioteki i narzędzia do tworzenia aplikacji równoległych komputerów wielordzeniowych: FORTRAN, OpenMP Java, POSIX, biblioteki Microsoft, biblioteki Java, Intel TBB | 2 |
| T-W-11 | podstawowe czynniki mające wpływ na wydajność aplikacji, sposoby pozwalające na tworzenie wydajnych aplikacji | 2 |
| T-W-12 | Metodologia PCAM tworzenia algorytmów równoległych | 4 |
| T-W-13 | Modele wydajnościowe do aplikacji rónoległych | 2 |
| 30 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| laboratoria | ||
| A-L-1 | udział w laboratoriach | 30 |
| A-L-2 | przygotowanie do laboratoriów | 8 |
| A-L-3 | Udzał w konsultacjach i zaliczeniu formy zajęć | 2 |
| 40 | ||
| wykłady | ||
| A-W-1 | Udział w wykładach | 30 |
| A-W-2 | Przygotowanie do zaliczenia | 35 |
| A-W-3 | Udzał w konsultacjach i zaliczeniu formy zajęć | 2 |
| 67 | ||
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 kształcenia - wiedza
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| I_2A_D16/O3/2-3_W01 ma wiedzę w zakresie tworzenia algorytmów równoległych | I_2A_W04 | — | C-1 | T-W-2, T-W-5, T-W-10 | M-1 | S-2 |
| I_2A_D16/O3/2-3_W02 zna API i biblioteki do tworzenia aplikacji równoległych dla komputerów wielordzeniowych | I_2A_W10 | — | C-2 | T-W-2, T-W-6, T-W-9 | M-1 | S-2 |
| I_2A_D16/O3/2-3_W03 zna podstawowe metody gromadzenia i przetwarzania danych i informacji w oparciu o komputery równoległe | I_2A_W04 | — | C-1 | T-W-1, T-W-2, T-W-4, T-W-9, T-W-12 | M-1 | S-2 |
Zamierzone efekty kształcenia - umiejętności
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| I_2A_D16/O3/2-3_U01 potrafi wykorzystać narzędzia i poszukiwać wiedzy o nich | I_2A_U02, I_2A_U08 | — | C-1 | T-W-1, T-W-9, T-W-13 | M-2 | S-1 |
| I_2A_D16/O3/2-3_U02 potrafi wykorzystać dotychczasową wiedzę i dobrać nowo powstałe narzędzia | I_2A_U04 | — | C-2 | T-W-12, T-L-2, T-L-4 | M-2 | S-2 |
Zamierzone efekty kształcenia - inne kompetencje społeczne i personalne
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| I_2A_D16/O3/2-3_K01 rozumie korzyśi wynikające z przetwarzania równoległego | I_2A_K03 | — | C-2 | T-W-6, T-W-9, T-W-13, T-L-2 | M-2 | S-1 |
Kryterium oceny - wiedza
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D16/O3/2-3_W01 ma wiedzę w zakresie tworzenia algorytmów równoległych | 2,0 | nie potrrafi zdefiniować programu współbieżnego, współbieżności oraz rozróżnić równoległość od współbieżności |
| 3,0 | rozumie pojęcie współbieżności, potrafi wyjaśnić definicję programu równoległego i odróżnić go od współbieżnego | |
| 3,5 | ma więdze na 3.0 oraz umie zdefiniować trudności w tworzeniu oprogramowania współbieżnego i równoległego oraz algorytmów, potrafi przedstawić podstawowe mechanizmy synchronizacji | |
| 4,0 | ma wiedzę na 3.5 oraz umiejętnie określa trudności w tworzeniu programów współbieżnych z odpowiednim doborem metod synchronizacji | |
| 4,5 | ma wiedzę na 4.0 oraz potrafi zdefiniować zagrożenia w tworzeniu oprogramowania współbieżnego | |
| 5,0 | ma wiedzę na 4.5 i potrafi wyjaśnić trudności w testowaniu oprogramowania współbieżnego | |
| I_2A_D16/O3/2-3_W02 zna API i biblioteki do tworzenia aplikacji równoległych dla komputerów wielordzeniowych | 2,0 | nie potrafi opisać pragmy parallel i for |
| 3,0 | potrafi w podstawowym zakresie określić pragmę parallel i for | |
| 3,5 | potrafi w podstawowym zakresie określić pragmę parallel, for i sections | |
| 4,0 | potrafi w podstawowym zakresie określić pragmę parallel, for i sections oraz zna pragmy barrier i atomic | |
| 4,5 | ma wiedzę na 4.0 i zna definicje funkcji openmp | |
| 5,0 | ma wiedzę na 4.5 i zna mechanizmy lock w openmp | |
| I_2A_D16/O3/2-3_W03 zna podstawowe metody gromadzenia i przetwarzania danych i informacji w oparciu o komputery równoległe | 2,0 | nie umie wyjaśnić taksonomi Flynna |
| 3,0 | potrafi wyjaśnić taksonomię Flynna | |
| 3,5 | potrafi wyjaśnić taksonomię Flynna i podać przykładowe architektury | |
| 4,0 | ma wiedzę 3.5 i opisać rozwój architektur równoległych | |
| 4,5 | ma wiedzę 4.0 i potrafi opisać architektury ze względu na dostęp do pamięci | |
| 5,0 | ma wiedzę na 4.5 i umie opisać model PCAM |
Kryterium oceny - umiejętności
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D16/O3/2-3_U01 potrafi wykorzystać narzędzia i poszukiwać wiedzy o nich | 2,0 | nie potrafi odnaleźć informacji na temat narzędzi oraz pisania programów |
| 3,0 | zna podstawowe słowa klucz, narzędzia i źródła wiedzy o nich | |
| 3,5 | potrafi odnaleźć informacje o poszczególnych funkcjach w dokumentacji narzędzia | |
| 4,0 | potrafi odnaleźć informacje o poszczególnych funkcjach w dokumentacji narzędzia i zastosować je w własnych projektach | |
| 4,5 | potrafi odnaleźć informacje o poszczególnych funkcjach w dokumentacji narzędzia i zastosować je w własnych projektach oraz zna alternetywne rozwiązania | |
| 5,0 | potrafi odnaleźć informacje o poszczególnych funkcjach w dokumentacji narzędzia i zastosować je w własnych projektach, zna alternetywne rozwiązania i jest zdolny do wyboru najbardziej odpowiedniego | |
| I_2A_D16/O3/2-3_U02 potrafi wykorzystać dotychczasową wiedzę i dobrać nowo powstałe narzędzia | 2,0 | nie zna podstaw programowania i kompilatorów |
| 3,0 | umie skompilować program w środowisku GCC i zna podstawy openmp i tbb | |
| 3,5 | umie skompilować program w środowisku GCC i zna podstawy openmp i tbb oraz zna podstawowe funkcje języka C z zakresu programowania systemów operacyjnych | |
| 4,0 | ma wiedzę na 3.5 i potrafi wykorzystać tą wiedzę do programowania aplikacji równoległych | |
| 4,5 | ma wiedzę na 4.0 i potrafi wykorzystać tą wiedzę do programowania aplikacji równoległych z wyborem odpowiednich funkcji | |
| 5,0 | wiedza 4.5 oraz umie porównać rezultaty z różnych narzędzi i funkcji |
Kryterium oceny - inne kompetencje społeczne i personalne
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D16/O3/2-3_K01 rozumie korzyśi wynikające z przetwarzania równoległego | 2,0 | nie zna podstawowych różnic między programowaniem sekwencyjnym i równoległym |
| 3,0 | ma wiedzę na temat podstawowych różnic między programowaniem sekwencyjnym i równoległym | |
| 3,5 | ma wiedzę na temat podstawowych różnic między programowaniem sekwencyjnym i równoległym i potrafi określić problem programowania równoległego | |
| 4,0 | ma wiedzę na temat podstawowych różnic między programowaniem sekwencyjnym i równoległym i potrafi określić problem programowania równoległego oraz dobrać narzędzia do jego rozwiązania | |
| 4,5 | ma wiedzę na temat podstawowych różnic między programowaniem sekwencyjnym i równoległym i potrafi określić problem programowania równoległego oraz dobrać narzędzia do jego rozwiązania a także określić korzyści z maszyn równoległych | |
| 5,0 | ma wiedzę na 4.5 i potrafi określić jakość znajomych mu rozwiązań |
Literatura podstawowa
- W. Bielecki, Essentials of parallel and distributed computing, Politechnika Szczecińska, Szczecin, 2002
- W. Bielecki, Przetwarzanie równoległe i rozproszone, Programowanie komputerów wielordzeniowych, Szczecin, 2007, Politechnika Szczecińska, 2007
- Rohit Chandra et al., Parallel Programming in OpenMP, Programowanie komputerów wielordzeniowych, Londyn, 2001
- Chapman, Jost, and Van Der Pas, Using OpenMP, The MIT Press Cambridge, 2008