Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Informatyki - Informatyka (S2)
specjalność: inżynieria oprogramowania

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

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
projektyP2 15 1,00,44zaliczenie
wykładyW2 15 2,00,56egzamin

Wymagania wstępne

KODWymaganie wstępne
W-1Zaliczone przedmioty: Programowanie w językach C, C++, Programowanie równoległe i rozproszone, metody kompilacji, Analiza matematyczna, Algebra liniowa, Architektura komputerów

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Przyswojenie wiedzy i umiejętności niezbędnych do automatycznego zrównoleglania aplikacji równoległych
C-2Ukształ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ęć

KODTreść programowaGodziny
projekty
T-P-1Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO15
15
wykłady
T-W-1Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna1
T-W-2Pę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-3Matematyczna 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ącego3
T-W-4Hierarchia 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 skalara3
T-W-5Ró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-6Przetwarzanie 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 frontowa2
T-W-7Tranzytywne 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

KODForma aktywnościGodziny
projekty
A-P-1udział w realizacji projektu15
A-P-2przygotowanie do realizacj projektu15
A-P-3Udzał w konsultacjach i zaliczeniu formy zajęć2
32
wykłady
A-W-1Udział w wykładach15
A-W-2Przygotowanie do egzaminu34
A-W-3Udzał w konsultacjach i egzaminie4
53

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łceniaCel przedmiotuTreści programoweMetody nauczaniaSposó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_W09C-1T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1M-1S-2
I_2A_D14/02_W02
ma rozszerzoną wiedzę dotyczącą trendów rozwoju metod automatycznego zrównoleglania aplikacji sekwencyjnych
I_2A_W10C-1T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1M-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łceniaCel przedmiotuTreści programoweMetody nauczaniaSposó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_U12C-1T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1M-2S-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_U15C-1T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1M-2S-1
I_2A_D14/02_U03
potrafi posługiwać się literaturą i dokumentacją techniczną do tworzenia aplikacji równoległych i rozproszonych
I_2A_U02C-1T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1M-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łceniaCel przedmiotuTreści programoweMetody nauczaniaSposó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_K02C-2, C-1T-W-2, T-W-1, T-W-4, T-W-3, T-W-7, T-W-6, T-W-5, T-P-1M-2S-1

Kryterium oceny - wiedza

Efekt kształceniaOcenaKryterium oceny
I_2A_D14/02_W01
ma wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych
2,0brak wiedzy w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych
3,0ma podstawową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych
3,5ma 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,0ma 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,5ma 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,0ma 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,0brak wiedzy w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych
3,0ma podstawową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych
3,5ma 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,0ma 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,5ma 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,0ma 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łceniaOcenaKryterium 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,0nie potrafi zastosować podstawowych metod automatycznego tworzenie aplikacji równoległych i rozproszonych
3,0potrafi rozwiązywać podstawowe problemy w oparciu o zastosowanie narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych
3,5potrafi rozwiązywać złożone problemy w oparciu o zastosowanie narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych
4,0potrafi 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,5potrafi 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,0potrafi 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,0nie rozumie podstawowych zagadnień i nie jest w stanie uczestniczyć w zespołowych pracach projektowych
3,0rozumie samodzielnie wybrane podstawowe zagadnienia i potrafi uczestniczyć w zespołowych pracach projektowych
3,5rozumie samodzielnie wszystkie podstawowe zagadnienia i potrafi aktywnie uczestniczyć w zespołowych pracach projektowych
4,0rozumie samodzielnie wszystkie podstawowe zagadnienia i potrafi je stosować w trakcie aktywnego uczestnictwa w zespołowych pracach projektowych
4,5rozumie samodzielnie wszystkie zagadnienia i potrafi analizować proponowane rozwiązania i dodawać istotne propozycje w trakcie aktywnego uczestnictwa w zespołowych pracach projektowych
5,0rozumie 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,0nie potrafi zastosować dostępnej dokumentacji technicznej i literatury do tworzenia aplikacji równoległych i rozproszonych
3,0potrafi przy pomocy prowadzącego i na podstawie dostępnej dokumentacji zaimplementować proste aplikacje równoległe i rozproszone
3,5potrafi samodzielnie stosować udostępnioną dokumentacje techniczna do implementacji złożonych aplikacji równoległych i rozproszonych
4,0potrafi analizować dostępną dokumentacje techniczna i literaturę jak również poszukiwać skutecznie dodatkowych informacji
4,5potrafi 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,0potrafi 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łceniaOcenaKryterium 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,0Nie potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych
3,0Potrafi 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,5Potrafi 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,0Potrafi 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,5Potrafi 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,0Potrafi 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,0nie potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych
3,0Potrafi 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,5Potrafi 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,0Potrafi 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,5Potrafi 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,0Potrafi 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

  1. R. Allen, K. Kennedy, Optimizing compilers, Morgan Kaufmann Publishers, Burlington, 2004
  2. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Compilers: Principles, Techniques, and Tools 2nd Edition, Addison Wesley, 2006
  3. W. Bielecki, M . Pałkowski, Ekstrakcja drobno i gruboziarnistej równoległości w pętlach programowych, ZUT w Szczecinie, Szczecin, 2011

Treści programowe - projekty

KODTreść programowaGodziny
T-P-1Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO15
15

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna1
T-W-2Pę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-3Matematyczna 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ącego3
T-W-4Hierarchia 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 skalara3
T-W-5Ró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-6Przetwarzanie 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 frontowa2
T-W-7Tranzytywne 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

Formy aktywności - projekty

KODForma aktywnościGodziny
A-P-1udział w realizacji projektu15
A-P-2przygotowanie do realizacj projektu15
A-P-3Udzał w konsultacjach i zaliczeniu formy zajęć2
32
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Udział w wykładach15
A-W-2Przygotowanie do egzaminu34
A-W-3Udzał w konsultacjach i egzaminie4
53
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_2A_D14/02_W01ma wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych
Odniesienie do efektów kształcenia dla kierunku studiówI_2A_W01Ma poszerzoną i pogłębioną wiedzę w zakresie wybranych działów matematyki teoretycznej oraz matematyki stosowanej
I_2A_W04Ma wiedzę z zakresu zaawansowanych technik programowania systemów informatycznych w wybranym obszarze zastosowań
I_2A_W06Posiada wiedzę o narzędziach sprzętowo-programowych wspomagających rozwiązywanie wybranych i złożonych problemów w różnych obszarach nauki i techniki
I_2A_W09Ma uporządkowaną, podbudowaną metodycznie i teoretycznie wiedzę w zakresie metod i technik projektowania systemów informatycznych
Cel przedmiotuC-1Przyswojenie wiedzy i umiejętności niezbędnych do automatycznego zrównoleglania aplikacji równoległych
Treści programoweT-W-2Pę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.
T-W-1Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna
T-W-4Hierarchia 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
T-W-3Matematyczna 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
T-W-7Tranzytywne 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.
T-W-6Przetwarzanie 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
T-W-5Ró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.
T-P-1Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO
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,0brak wiedzy w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych
3,0ma podstawową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych
3,5ma 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,0ma 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,5ma 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,0ma 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
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_2A_D14/02_W02ma rozszerzoną wiedzę dotyczącą trendów rozwoju metod automatycznego zrównoleglania aplikacji sekwencyjnych
Odniesienie do efektów kształcenia dla kierunku studiówI_2A_W10Ma poszerzoną wiedzę dotyczącą trendów rozwojowych i możliwości zastosowania informatyki w wybranych obszarach nauki i techniki
Cel przedmiotuC-1Przyswojenie wiedzy i umiejętności niezbędnych do automatycznego zrównoleglania aplikacji równoległych
Treści programoweT-W-2Pę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.
T-W-1Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna
T-W-4Hierarchia 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
T-W-3Matematyczna 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
T-W-7Tranzytywne 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.
T-W-6Przetwarzanie 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
T-W-5Ró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.
T-P-1Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO
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,0brak wiedzy w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych
3,0ma podstawową wiedzę w zakresie metod automatycznego zrównoleglenia aplikacji sekwencyjnych opartych na transformacjach afinicznych
3,5ma 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,0ma 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,5ma 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,0ma 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
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_2A_D14/02_U01potrafi rozwiązywać złożone problemy w oparciu o automatyczne tworzenie aplikacji równoległych i rozproszonych
Odniesienie do efektów kształcenia dla kierunku studiówI_2A_U04Potrafi wybrać, krytycznie ocenić przydatność i zastosować metodę i narzędzia rozwiązania złożonego zadania inżynierskiego
I_2A_U08Potrafi wykorzystywać narzędzia sprzętowo-programowe wspomagające rozwiązywanie wybranych problemów w różnych obszarach nauki i techniki
I_2A_U12Ma umiejętność stosowania zaawansowanych technik programowania i metodyki projektowania systemów informatycznych w wybranym obszarze zastosowań
Cel przedmiotuC-1Przyswojenie wiedzy i umiejętności niezbędnych do automatycznego zrównoleglania aplikacji równoległych
Treści programoweT-W-2Pę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.
T-W-1Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna
T-W-4Hierarchia 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
T-W-3Matematyczna 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
T-W-7Tranzytywne 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.
T-W-6Przetwarzanie 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
T-W-5Ró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.
T-P-1Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO
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 zastosować podstawowych metod automatycznego tworzenie aplikacji równoległych i rozproszonych
3,0potrafi rozwiązywać podstawowe problemy w oparciu o zastosowanie narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych
3,5potrafi rozwiązywać złożone problemy w oparciu o zastosowanie narzędzi do automatycznego tworzenia aplikacji równoległych i rozproszonych
4,0potrafi 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,5potrafi 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,0potrafi 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ł
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_2A_D14/02_U02potrafi aktywnie uczestniczyć w pracach projektowych zespołowych i indywidualnych dotyczących wytwarzania oprogramowania równoległego
Odniesienie do efektów kształcenia dla kierunku studiówI_2A_U16Potrafi określić kierunek dalszego uczenia się i zrealizować proces samokształcenia
I_2A_U03Potrafi aktywnie uczestniczyć w pracach projektowych indywidualnych i zespołowych przyjmując w nich różne role
I_2A_U15Ma przygotowanie niezbędne do pracy w środowisku przemysłowym oraz zna zasady bezpieczeństwa związane z tą pracą
Cel przedmiotuC-1Przyswojenie wiedzy i umiejętności niezbędnych do automatycznego zrównoleglania aplikacji równoległych
Treści programoweT-W-2Pę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.
T-W-1Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna
T-W-4Hierarchia 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
T-W-3Matematyczna 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
T-W-7Tranzytywne 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.
T-W-6Przetwarzanie 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
T-W-5Ró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.
T-P-1Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO
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 rozumie podstawowych zagadnień i nie jest w stanie uczestniczyć w zespołowych pracach projektowych
3,0rozumie samodzielnie wybrane podstawowe zagadnienia i potrafi uczestniczyć w zespołowych pracach projektowych
3,5rozumie samodzielnie wszystkie podstawowe zagadnienia i potrafi aktywnie uczestniczyć w zespołowych pracach projektowych
4,0rozumie samodzielnie wszystkie podstawowe zagadnienia i potrafi je stosować w trakcie aktywnego uczestnictwa w zespołowych pracach projektowych
4,5rozumie samodzielnie wszystkie zagadnienia i potrafi analizować proponowane rozwiązania i dodawać istotne propozycje w trakcie aktywnego uczestnictwa w zespołowych pracach projektowych
5,0rozumie 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
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_2A_D14/02_U03potrafi posługiwać się literaturą i dokumentacją techniczną do tworzenia aplikacji równoległych i rozproszonych
Odniesienie do efektów kształcenia dla kierunku studiówI_2A_U02Potrafi pozyskiwać informacje z różnych źródeł (literatura, Internet, bazy danych, dokumentacja techniczna), dokonywać ich interpretacji i oceny
Cel przedmiotuC-1Przyswojenie wiedzy i umiejętności niezbędnych do automatycznego zrównoleglania aplikacji równoległych
Treści programoweT-W-2Pę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.
T-W-1Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna
T-W-4Hierarchia 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
T-W-3Matematyczna 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
T-W-7Tranzytywne 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.
T-W-6Przetwarzanie 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
T-W-5Ró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.
T-P-1Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO
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 zastosować dostępnej dokumentacji technicznej i literatury do tworzenia aplikacji równoległych i rozproszonych
3,0potrafi przy pomocy prowadzącego i na podstawie dostępnej dokumentacji zaimplementować proste aplikacje równoległe i rozproszone
3,5potrafi samodzielnie stosować udostępnioną dokumentacje techniczna do implementacji złożonych aplikacji równoległych i rozproszonych
4,0potrafi analizować dostępną dokumentacje techniczna i literaturę jak również poszukiwać skutecznie dodatkowych informacji
4,5potrafi 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,0potrafi 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)
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_2A_D14/02_K01ma świadomość współodpowiedzialności za wspólnie realizowane zadania dotyczące zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji równoległych
Kryteria ocenyOcenaKryterium oceny
2,0Nie potrafi aktywnie uczestniczyć w pracach projektowych zespołowych dotyczących zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych
3,0Potrafi 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,5Potrafi 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,0Potrafi 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,5Potrafi 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,0Potrafi 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
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_2A_D14/02_K02świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą w zakresie kompilatorów optymalizujących
Odniesienie do efektów kształcenia dla kierunku studiówI_2A_K01Ma świadomość organizacji własnego czasu pracy i jest zdeterminowany aby osiągnąć założone cele
I_2A_K02Świadomie rozumie potrzeby dokształcania i dzielenia się wiedzą
Cel przedmiotuC-2Ukształtowanie świadomego rozumowania dokształcania się i odpowiedzialności za wspólne realizowanie projektów w zakresie wytwarzania oprogramowania
C-1Przyswojenie wiedzy i umiejętności niezbędnych do automatycznego zrównoleglania aplikacji równoległych
Treści programoweT-W-2Pę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.
T-W-1Symetryczny komputer wieloprocesorowy. Architektura NUMA. Prawo Amdahla. Ziarnistość równoległości. Kod SPMD. Lokalność czasowa. Lokalność przestrzenna
T-W-4Hierarchia 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
T-W-3Matematyczna 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
T-W-7Tranzytywne 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.
T-W-6Przetwarzanie 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
T-W-5Ró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.
T-P-1Zrealizowanie projektu dotyczącego automatycznego zownoleglenia programu sekwencyjnego w oparciu o narzebdzie PLUTO oraz narzedzie katedry KIO
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 zastosowania kompilatorów optymalizujących do automatycznego zrównoleglania aplikacji sekwencyjnych
3,0Potrafi 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,5Potrafi 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,0Potrafi 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,5Potrafi 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,0Potrafi 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