Wydział Informatyki - Informatyka (S2)
Sylabus przedmiotu Kompilatory optymalizujące:
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 | Kompilatory optymalizujące | ||
| Specjalność | inżynieria oprogramowania | ||
| Jednostka prowadząca | Katedra Inżynierii Oprogramowania | ||
| Nauczyciel odpowiedzialny | Włodzimierz Bielecki <Wlodzimierz.Bielecki@zut.edu.pl> | ||
| Inni nauczyciele | Piotr Błaszyński <Piotr.Blaszynski@zut.edu.pl> | ||
| ECTS (planowane) | 3,0 | ECTS (formy) | 3,0 |
| Forma zaliczenia | egzamin | Język | polski |
| Blok obieralny | — | Grupa obieralna | — |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | Zaliczone przedmioty: Programowanie w językach C, C++, Programowanie równoległe i rozproszone, metody kompilacji, Analiza matematyczna, Algebra liniowa, Architektura komputerów |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Przyswojenie wiedzy i umiejętności niezbędnych do automatycznego zrównoleglania aplikacji równoległych |
| C-2 | Ukształtowanie świadomego rozumowania dokształcania się i odpowiedzialności za wspólne realizowanie projektów w zakresie wytwarzania oprogramowania |
Treści programowe z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| projekty | ||
| T-P-1 | Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO | 15 |
| 15 | ||
| wykłady | ||
| T-W-1 | Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna | 1 |
| T-W-2 | Pętle idealnie i nieidealnie zagnieżdżone. Pętle sparametryzowane . Pętle afiniczne. Pętle drobno- i grubo-ziarniste. Pętle znormalizowane. Przestrzeń iteracji pętli. Kolejność wykonywania iteracji. Przestrzeń danych i przestrzeń procesorów. | 2 |
| T-W-3 | Matematyczna reprezentacja przestrzeni iteracji. Formalna definicja zależności danych. Zadania kompilatora optymalizującego. Wektor iteracji. Kolejność leksykograficzna. Definicja transformacji zmiany kolejności iteracji pętli. Warunek poprawności transformacji . ektor dystansu i wektor kierunku. Graf zależności danych. Zależności niezależne od pętli. Zależności przenoszone pętlą. Na czym polega wektoryzacja, warunek legalności wektoryzacji. Wyeliminowanie zmiennych indukcji. Propagacja stałej. Równania do znalezienia zależności. Reprezentacja zależności za pomocą relacji. Reprezentacja zależności jako wielościan. . Architektura kompilatora optymalizującego | 3 |
| T-W-4 | Hierarchia pamięc . Przechowywanie tablicy (kolumnami lub wierszami) a lokalność kodu. Funkcja afiniczna indeksów tablicy, postać matematyczna. Partycjonowania afiniczne : odwzorowanie iteracji na procesor/wątek, czas logiczny wykonywania iteracji, iteracje w innej przestrzeni. Rola eliminacji Fouriera-Motzkina w transformacjach afinicznych Stare i nowe wektory dystansu, obliczenie nowego wektora dystansu, jego zastosowanie celem sprawdzenia legalności transformacji. Najważniejsze transformacje oraz ich przydatność w kompilatorach optymalizujących. Podział Pętli. Scalenie Pętli. Wyrównanie dla fuzji pętli. Wymiana Pętli. Odwrócenie iteracji. Przekoszenie iteracji pętli. Blokowanie. Podział zbioru indeksów. Rozszerzenie skalara | 3 |
| T-W-5 | Równoległość pozbawiona synchronizacji. Stopień równoległości pętli. Trzy kroki w algorytmie znajdowania równoległości pozbawionej synchronizacji. Ograniczenia partycjonowania przestrzeni: definicja oraz zapis matematyczny. Struktura układu równań i nierówności do znalezienia zależności, rola poszczególnych . Równości /nierówności w tym układzie. Jak korzystamy z rozwiania układu opisującego ograniczenia partycjonowania przestrzeni(przydział iteracji pętli do procesorów). Generacja kodu reprezentującego równoległość pozbawioną synchronizacji. | 2 |
| T-W-6 | Przetwarzanie potokowe.Pętle całkowicie wymienne, ich najważniejsze cechy. Ograniczenia partycjonowania czasu: zapis matematyczny, rola poszczególnych równości /nierówności w tym układzie. Jak liczba liniowo niezależnych rozwiązań układu ograniczenia partycjonowania czasu wpływa na kod wynikowy. Lemat Farkas’a. Rozwiązania układu ograniczenia partycjonowania czasu a przetwarzanie potokowe . Pętle całkowicie wymienne a blokowanie. Fala frontowa | 2 |
| T-W-7 | Tranzytywne domknięcie grafu zależności. Znalezienie równoległości pozbawionej synchronizacji w oparciu o tranzytywne domknięcie. Znalezienie drobno-ziarnistej równoległości w oparciu o tranzytywne domknięcie. Znalezienie grubo-ziarnistej równoległosci w oaparciu o tranzytywne domknięcie. | 2 |
| 15 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| projekty | ||
| A-P-1 | udział w realizacji projektu | 15 |
| A-P-2 | przygotowanie do realizacj projektu | 15 |
| A-P-3 | Udzał w konsultacjach i zaliczeniu formy zajęć | 2 |
| 32 | ||
| wykłady | ||
| A-W-1 | Udział w wykładach | 15 |
| A-W-2 | Przygotowanie do egzaminu | 34 |
| A-W-3 | Udzał w konsultacjach i egzaminie | 4 |
| 53 | ||
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_D14/02_W01 ma wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych | I_2A_W01, I_2A_W04, I_2A_W06, I_2A_W09 | — | C-1 | T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1 | M-1 | S-2 |
| I_2A_D14/02_W02 ma rozszerzoną wiedzę dotyczącą trendów rozwoju metod automatycznego zrównoleglania aplikacji sekwencyjnych | I_2A_W10 | — | C-1 | T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1 | 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_D14/02_U01 potrafi rozwiązywać złożone problemy w oparciu o automatyczne tworzenie aplikacji równoległych i rozproszonych | I_2A_U04, I_2A_U08, I_2A_U12 | — | C-1 | T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1 | M-2 | S-1 |
| I_2A_D14/02_U02 potrafi aktywnie uczestniczyć w pracach projektowych zespołowych i indywidualnych dotyczących wytwarzania oprogramowania równoległego | I_2A_U16, I_2A_U03, I_2A_U15 | — | C-1 | T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1 | M-2 | S-1 |
| I_2A_D14/02_U03 potrafi posługiwać się literaturą i dokumentacją techniczną do tworzenia aplikacji równoległych i rozproszonych | I_2A_U02 | — | C-1 | T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1 | M-2 | S-1 |
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_D14/02_K01 ma świadomość współodpowiedzialności za wspólnie realizowane zadania dotyczące zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji równoległych | — | — | — | — | — | — |
| I_2A_D14/02_K02 świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie kompilatorów optymalizujących | I_2A_K01, I_2A_K02 | — | C-2, C-1 | T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1 | M-2 | S-1 |
Kryterium oceny - wiedza
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D14/02_W01 ma wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych | 2,0 | brak wiedzy w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych |
| 3,0 | ma podstawową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych | |
| 3,5 | ma podstawową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych oraz wie jak zastosować wiedzę do zrównoleglenia prostych pętli programowych | |
| 4,0 | ma szczegółową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych oraz wie jak zastosować wiedzę do zrównoleglenia prostych pętli programowych | |
| 4,5 | ma szczegółową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych oraz wie jak zastosować wiedzę do zrównoleglenia złożonych pętli programowych | |
| 5,0 | ma szczegółową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych oraz wie jak zastosować wiedzę do zrównoleglenia złożonych pętli programowych oraz potrafi udowodnić swoje odpowiedzi | |
| I_2A_D14/02_W02 ma rozszerzoną wiedzę dotyczącą trendów rozwoju metod automatycznego zrównoleglania aplikacji sekwencyjnych | 2,0 | brak wiedzy w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych |
| 3,0 | ma podstawową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych | |
| 3,5 | ma podstawową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych oraz wie jak zastosować wiedzę do zrównoleglenia prostych pętli programowych | |
| 4,0 | ma szczegółową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych oraz wie jak zastosować wiedzę do zrównoleglenia prostych pętli programowych | |
| 4,5 | ma szczegółową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych oraz wie jak zastosować wiedzę do zrównoleglenia złożonych pętli | |
| 5,0 | ma szczegółową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych oraz wie jak zastosować wiedzę do zrównoleglenia złożonych pętli programowych oraz potrafi udowodnić swoje odpowiedzi |
Kryterium oceny - umiejętności
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D14/02_U01 potrafi rozwiązywać złożone problemy w oparciu o automatyczne tworzenie aplikacji równoległych i rozproszonych | 2,0 | nie potrafi zastosować podstawowych metod automatycznego tworzenie aplikacji równoległych i rozproszonych |
| 3,0 | potrafi rozwiązywać podstawowe problemy w oparciu o zastosowanie narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych | |
| 3,5 | potrafi rozwiązywać złożone problemy w oparciu o zastosowanie narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych | |
| 4,0 | potrafi rozwiązywać złożone problemy w oparciu o zastosowanie narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych i dokonać analizy porównawczej uzyskanych wyników | |
| 4,5 | potrafi rozwiązywać złożone problemy w oparciu o zastosowanie własnych rozwiązań i narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych i dokonać analizy porównawczej uzyskanych wyników | |
| 5,0 | potrafi rozwiązywać złożone problemy w oparciu o zastosowanie własnych rozwiązań i alternatywnych narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych i dokonać syntez rozwiązań z wielu źródeł | |
| I_2A_D14/02_U02 potrafi aktywnie uczestniczyć w pracach projektowych zespołowych i indywidualnych dotyczących wytwarzania oprogramowania równoległego | 2,0 | nie rozumie podstawowych zagadnień i nie jest w stanie uczestniczyć w zespołowych pracach projektowych |
| 3,0 | rozumie samodzielnie wybrane podstawowe zagadnienia i potrafi uczestniczyć w zespołowych pracach projektowych | |
| 3,5 | rozumie samodzielnie wszystkie podstawowe zagadnienia i potrafi aktywnie uczestniczyć w zespołowych pracach projektowych | |
| 4,0 | rozumie samodzielnie wszystkie podstawowe zagadnienia i potrafi je stosować w trakcie aktywnego uczestnictwa w zespołowych pracach projektowych | |
| 4,5 | rozumie samodzielnie wszystkie zagadnienia i potrafi analizować proponowane rozwiązania i dodawać istotne propozycje w trakcie aktywnego uczestnictwa w zespołowych pracach projektowych | |
| 5,0 | rozumie samodzielnie wszystkie zagadnienia i potrafi ocenić ich przydatność oraz wyjaśnić innym studentom zagadnienia dotyczące budowy narzędzi umożliwiających automatyczne zrównoleglanie | |
| I_2A_D14/02_U03 potrafi posługiwać się literaturą i dokumentacją techniczną do tworzenia aplikacji równoległych i rozproszonych | 2,0 | nie potrafi zastosować dostępnej dokumentacji technicznej i literatury do tworzenia aplikacji równoległych i rozproszonych |
| 3,0 | potrafi przy pomocy prowadzącego i na podstawie dostępnej dokumentacji zaimplementować proste aplikacje równoległe i rozproszone | |
| 3,5 | potrafi samodzielnie stosować udostępnioną dokumentacje techniczna do implementacji złożonych aplikacji równoległych i rozproszonych | |
| 4,0 | potrafi analizować dostępną dokumentacje techniczna i literaturę jak również poszukiwać skutecznie dodatkowych informacji | |
| 4,5 | potrafi wszystko na ocenę 4,0, proponuje również nowe rozwiązania (np. sposób zapisu konstrukcji języka C++ w sposób zrozumiały dla narzędzia pluto) udokumentowanych rozwiązań | |
| 5,0 | potrafi wszystko na ocenę 4,5, zapoznał się z innymi narzędziami do budowy aplikacji równoległych oraz potrafi porównać stosowane na zajęciach narzędzia (pluto, stepson) z innymi dostępnymi (stepson, omega, samodzielne wykorzystanie isla, llvm) |
Kryterium oceny - inne kompetencje społeczne i personalne
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_2A_D14/02_K01 ma świadomość współodpowiedzialności za wspólnie realizowane zadania dotyczące zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji równoległych | 2,0 | Nie potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych |
| 3,0 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania z oceną 3,0 | |
| 3,5 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania z oceną 3,5 | |
| 4,0 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania z oceną 4,0 | |
| 4,5 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania z oceną 4,5 | |
| 5,0 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania z oceną 5,0 | |
| I_2A_D14/02_K02 świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie kompilatorów optymalizujących | 2,0 | nie potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych |
| 3,0 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania w oparciu o dokształcenie z oceną 3,0 | |
| 3,5 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania w oparciu o dokształcenie z oceną 3,5 | |
| 4,0 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania w oparciu o dokształcenie z oceną 4,0 | |
| 4,5 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania w oparciu o dokształcenie z oceną 4,5 | |
| 5,0 | Potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych oraz zrealizował swoją część zadania w oparciu o dokształcenie z oceną 5,0 |
Literatura podstawowa
- R. Allen, K. Kennedy, Optimizing compilers, Morgan Kaufmann Publishers, Burlington, 2004
- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Compilers: Principles, Techniques, and Tools 2nd Edition, Addison Wesley, 2006
- W. Bielecki, M . Pałkowski, Ekstrakcja drobno i gruboziarnistej równoległości w pętlach programowych, ZUT w Szczecinie, Szczecin, 2011