Programowanie współbieżne i rozproszone 1000-218bPWR
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.
Rodzaj przedmiotu
Efekty kształcenia
Wiedza
- zna techniki synchronizacji procesów i komunikacji międzyprocesowej w scentralizowanym i rozproszonym modelu programu współbieżnego (K_W04)
- zna algorytmy wzajemnego wykluczania i uzgadniania w systemach rozproszonych (K_W05)
- zna najpopularniejsze architektury systemów równoległych i rozproszonych
- zna podstawowe podejścia do równoległego rozwiązywania problemów (np. zrównoleglenie oparte o dane / o zadania; metody zarządzania zadaniami; podstawowe równoległe algorytmy obliczeniowe)
Umiejętności
- potrafi zastosować mechanizmy synchronizacji procesów i wątków w wybranych technologiach w zależności od architektury i możliwości konkretnego systemu (K_U06)
- potrafi zastosować metody weryfikacji programów współbieżnych (K_U07)
- posługuje się nowoczesnymi technologiami rozpraszania i zrównoleglania obliczeń (K_U08)
Kompetencje
- potrafi pracować zespołowo, w tym w zespołach interdyscyplinarnych; rozumie konieczność systematycznej pracy nad wszelkimi projektami, które mają długofalowy charakter (K_K03)
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.
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"
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: