Programowanie współbieżne i rozproszone
Informacje ogólne
Kod przedmiotu: | 1000-218bPWR |
Kod Erasmus / ISCED: |
11.304
|
Nazwa przedmiotu: | Programowanie współbieżne i rozproszone |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: | |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | obowiązkowe |
Skrócony opis: |
Platformy współbieżne i rozproszone są stosowane od wielordzeniowych procesorów w telefonach komórkowych do złożonych z dziesiątków tysięcy węzłów superkomputerów. Celem wykładu jest przedstawienie podstawowych problemów oraz technik programowania systemów równoległych i rozproszonych. Wykład zorganizowany jest wokół dwóch kluczowych zagadnień programowania współbieżnego i rozproszonego: poprawności i wydajności. |
Pełny opis: |
Platformy współbieżne i rozproszone są stosowane od wielordzeniowych procesorów w telefonach komórkowych do złożonych z dziesiątków tysięcy węzłów superkomputerów. Wykorzystanie takich zasobów to obecnie jedyna możliwość na analizę wielkich zbiorów danych (big data), czy na przeprowadzenie złożonych symulacji. Celem wykładu jest przedstawienie podstawowych problemów oraz technik programowania systemów równoległych i rozproszonych. Wykład zorganizowany jest wokół dwóch kluczowych zagadnień programowania współbieżnego i rozproszonego: poprawności i wydajności. W części dotyczącej programowania współbieżnego omówimy model obliczeń oraz podstawowe metody weryfikacji programu (dedukcyjna oraz przez model) ilustrowane na przykładzie problemu wzajemnego wykluczania. Przedstawimy model obliczeń opartych o równoległe operacje na danych (data parallel, PRAM); omówimy podstawowe algorytmy w tym modelu i miary ich złożoności. Omówimy również praktyczną realizacje modelu data parallel - programowanie urządzeń masywnie równoległych (takich jak karty graficzne, GPGPU). Pokażemy też alternatywny model programowania z dynamiczną współbieżnością (język Cilk). W części dotyczącej programowania rozproszonego przestawimy sposoby komunikacji, wzajemnego wykluczania, wyboru lidera, oraz uzgadniania stanu obliczenia. Zasygnalizujemy problematykę zapewnienia niezawodności analizując algorytm bizantyjskich generałów. Przedstawimy modele obliczeń w systemach wieloprocesorowych (pierścień i torus procesorów). Na przykładzie prostych algorytmów numerycznych pokażemy jak wyznaczać złożoność i wydajność algorytmów. Praktyczną ilustracją modelu będzie programowanie klastra z wykorzystaniem MPI. Omówimy również map-reduce, alternatywny model obliczeń wykorzystywany do przetwarzania wielkich danych. |
Literatura: |
Ben-Ari "Principles of Concurrent and Distributed Programming" Ben-Ari "Mathematical Logic for Computer Science" Herlihy, Shavit "The Art of Multiprocessor Programming" Kirk, Hwu "Programming Massively Parallel Processors" Cormen, Leiserson, Rivest "Introduction to Algorithms", 1st edition (PRAM), 3rd edition (Cilk) Casanova, Legrand, Robert "Parallel Algorithms" |
Efekty uczenia się: |
Wiedza
Umiejętności
Kompetencje
|
Metody i kryteria oceniania: |
Ocena końcowa na podstawie punktów za zadania programistyczne (40%), kolokwium (20%) i egzaminu (40%). By móc przystąpić do egzaminu, należy uzyskać co najmniej 50% punktów za zadania programistyczne oraz co najmniej 50% + 0.5 punktów za kolokwium. 3 z 4 zadań wystarczą do uzyskania maksimum. Bezpośrednio przed pierwszym terminem egzaminu można napisać kolokwium poprawkowe (punktacja z kolokwium poprawkowego anuluje punkty uzyskane w pierwszym terminie). Przystąpienie do egzaminu poprawkowego (i oddanie pracy) anuluje wynik uzyskany z egzaminu w pierwszym terminie. |
Właścicielem praw autorskich jest Uniwersytet Warszawski.