[WikiDyd] [TitleIndex] [WordIndex

UWAGA poniższe materiały są archiwalne i mogą stanowić wyłącznie uzupełnienie bieżących materiałów do przedmiotu, które znajdują się w ISODzie.

Programowanie równoległe i rozproszone (PRZEDMIOT PROWADZONY W SEMESTRZE LETNIM)

Prowadzący

Jacek Starzyński (226 GE, tel. (22) 23456 44) & Bartosz Chaber (229 GE, tel. (22) 2345 760) & Zuzanna Krawczyk (229 GE, tel. (22) 2345 760)

Zasady zaliczenia

  1. Udziału w zajęciach zostaną dopuszczone tylko osoby zapisane na przedmiot za pomocą systemu iSod

  2. Wykład kończy się pisemnym sprawdzianem ocenianym w skali 0-60 pkt.
  3. Obecność na laboratorium jest obowiązkowa.
  4. Laboratorium składa się z zajęć wprowadzających, 7 ćwiczeń i mini-projektu.
  5. Ćwiczenia wykonywane są w zespołach 2-osobowych, ale oceniane indywidualnie.
  6. Każde ćwiczenie laboratoryjne kończy się sprawdzianem ocenianym w skali 0-5 pkt.
  7. Mini-projekty wykonywane są w zespołach 3-osobowych. Każdy z członków zespołu ma ustalony zakres obowiązków.
  8. Ostateczny termin zakończenia (obrony) mini-projektów to ostatnie zajęcia w semestrze.
  9. Mini-projekty oceniane są w skali 0-25 pkt. Ocena jest indywidualna.
  10. Ostateczna ocena z przedmiotu wynika z sumy uzyskanych punktów: 0-60 = nzal, 61-72 = 3, 73-84 = 3.5, 85-96 = 4, 97-108 = 4.5, 109-120 = 5

Terminy:

Program

Wykład - wybrane czwartki (terminy niżej), 12-14, sala 226 GG

Sylabus:

Slajdy i programy przykładowe:

Temat i link do slajdów

Termin

Programy przykładowe

Wykład 1: wprowadzenie, projektowanie algorytmów

21 II

Wykład 2: Architektury maszyn, złożoność algorytmów, zysk ze zrównoleglania

28 II

Wykład 3: PR w POSIX: procesy, wątki

07 III

Programy przykładowe

Wykład 4: OpenMP

14 III

Wykład 5: gniazdka i MPI

28 III

Ćwiczenia MPI

Wykład 6: PVM

28 III

Wykład 7: RPC, RMI, CORBA

04 IV

Solver (Java wątki, bariera, RMI)

Wykład 8: GP-GPU CUDA

11 IV

Laboratorium

Uwaga! Aktualny i obowiązujący plan laboratorium od semestru 2014L znajduje się w ISOD!!! Poniższe materiały mają wyłącznie charakter archiwalny i mogą jedynie służyć jako materiał pomocniczy.

  1. Procesy w systemie Unix

  2. Sygnały w systemie Unix - ćwiczenie przygotowawcze (bez oceny)

  3. Sygnały w systemie Unix i Komunikacja z wykorzystaniem pamięci wspólnej

  4. Wątki w systemie Unix (C)

  5. MPI w Windows

  6. MPI w Linuksie

  7. PVM: Podstawy komunikacji

  8. PVM: Obliczanie liczby Pi

  9. Miniprojekty do wyboru: aplikacja wielowątkowa w C, aplikacja wielowątkowa w Javie, aplikacja Java RMI

Przykładowe dane: (cztery ładunki 1e-9 C każdy umieszczone w narożach kwadratu, rozkład od -1 do 1, w 1000 punktów)

4
0 0.1 0.1     1e-9
0 -0.1 0.1    1e-9
0 -0.1 -0.1   1e-9
0 0.1 -0.1    1e-9
-1
1
1000

Tematy projektów

  1. Rozwiązywanie układów równań liniowych - MPI, PVM, CUDA (3 projekty)
  2. Wyznaczanie i wizualizacja prądów wirowych w przewodzie o przekroju kołowym - CUDA
  3. Rozproszony algorytm genetyczny: MPI, PVM, Java (3 projekty)
  4. Rozproszony algorytm symulowanego wyżarzania: MPI, PVM, Java (3 projekty)
  5. Problem n ciał (ładunków): CUDA
  6. Adaptacyjne całkowanie numeryczne 3D: CUDA, MPI (2 projekty)
  7. Rozkład na szereg Laplace'a: MPI, CUDA (2 projekty)
  8. Rozproszony, uniwersalny system obliczeniowy: Java RMI + JINI
  9. Generacja siatek trójwymiarowych elementów skończonych: MPI, PVM (2 projekty)
  10. Generacja siatek dwuwymiarowych: CUDA
  11. Równoległa implementacja dwuwymiarowej metody elementów skończonych dla zagadnień eliptycznych: CUDA, MPI (2 projekty)
  12. Równoległa implementacja algorytmu adaptacji dwuwymiarowych siatek elementów skończonych do aktualnego rozkładu funkcji: CUDA, MPI, Java (3 projekty)
  13. Równoległa implementacja metody różnic skończonych dla zagadnień eliptycznych: CUDA, MPI, Java (3 projekty)
  14. Propagacja aktywacji w komórkach nerwowych (równoległe jednowymiarowe, dynamiczne zagadnienie różnic skończonych oraz równań różniczkowych zwyczajnych): CUDA, MPI, Java (3 projekty)
  15. Równoległe wyznaczanie tęczowych tablic ("rainbow tables") w zgadnieniach kryptografii dla haseł zaszyfrowanych algorytmem DES: CUDA, MPI, Java. (3 projekty)
  16. Równoległa implementacja wyznaczania topologii trójwymiarowych siatek elementów skończonych (sąsiedztwo węzłowe, krawędziowe, ścianowe): CUDA, MPI, PVM (3 projekty)
  17. Równoległa, realizowana w czasie rzeczywistym implementacja wykrywania ruchu i obiektów w sekwencji klatek filmowych (co najmniej 5 klatek na sekundę): CUDA, MPI, PVM (3 projekty)
  18. Równoległa implementacja algorytmu klasyfikacji nowotworowych komórek w obrazach medycznych: CUDA, MPI, PVM (3 projekty)

Literatura

  1. Marcin Engel: Programowanie współbieżne i rozproszone

  2. Piotr Gronek: Programowanie równoległe i rozproszone

  3. Jerzy Brzeziński: Przetwarzanie rozproszone

  4. Andrzej Karbowski: Podstawy Obliczeń Równoległych i Rozproszonych

  5. I. Foster: Designing and Building Parallel Programs (Online)

  6. A. Karbowski, E. Niewiadomska-Szynkiewicz, Obliczenia równoległe i rozproszone, OWPW, Warszawa, 2001.
  7. G. Karniadakis, R. Kirby, Parallel Scientific Computing in C++ and MPI, Cambridge University Press, 2003.
  8. M.K. Johnson, E.W. Troan, Oprogramowanie użytkowe w systemie Linux. WNT, Warszawa 2000.
  9. M. Rochkind, Programowanie w systemie Unix dla zaawansowanych. WNT, Warszawa 1997.
  10. M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego. WNT, Warszawa 1996.

Pytania do testu zaliczeniowego:

  1. Co to jest programowanie równolegle, rozproszone, współbieżne
  2. Proszę objaśnić skrót PCAM, znaczenie litery (P|C|A|M) w skrócie PCAM
  3. Dlaczego w fazie podziału należy dążyć do uzyskania jak największej ziarnistości
  4. Proszę omówić znane rodzaje dekompozycji
  5. Proszę omówić znane schematy komunikacji
  6. Co to jest balansowanie obciążenia?
  7. Proszę omówić znane algorytmy kolejkowania zadań
  8. Proszę omówić prawo Ahmdala
  9. Dlaczego współczynnik przyspieszenia jest mniejszy od liczby procesorów
  10. Co to jest udział części sekwencyjnej programu (algorytmu) i jak zależy od niego współczynnik przyspieszenia
  11. Jak zmienia się współczynnik przyspieszenia przy stałej liczbie procesorów i wzroście rozmiarów zadania? Dlaczego?
  12. Co to jest metryka Karpa-Flatta? Do czego służy?
  13. Co to jest sprawność programu?
  14. Proszę omówić taksonomię Flynna
  15. Co to jest SISD, SIMD, MISD, MIMD
  16. Proszę omówić znane architektury pamięci w komp. równoległych
  17. Czym różni się system SM-MIMD, DM-MIMD?
  18. Jak realizuje się dostęp do pamięci w komputerach SM-MIMD?
  19. Czym różni się proces od wątku?
  20. Proszę omówić funkcję fork
  21. Proszę wymienić sposoby komunikacji między procesami, wątkami?
  22. W jaki sposób obsługuje się sygnały?
  23. Do czego służą zamki (pthread_mutex)?
  24. W jaki sposób można synchronizować wykonywanie wątków?
  25. W jaki sposób można synchronizować wykonywanie procesów?
  26. Czym są gniazdka (socket)?
  27. Do czego służy biblioteka OpenMP?
  28. Proszę narysować model programu zgodny z OpenMP
  29. Do czego służy biblioteka MPI?
  30. Proszę opisać model programu w MPI
  31. Czym różni się komunikacja synchroniczna od asynchronicznej?
  32. Jakie funkcje służą do komunikacji (a)synchronicznej w MPI?
  33. Na czym polega i do czego służy mapowanie identyfikatorów procesów w przestrzeń użytkownika?
  34. Czy w MPI występuje mechanizmu zamków? Dlaczego?
  35. Jakie znasz mechanizmy komunikacji grupy procesów MPI?
  36. Co to jest konsola PVM? DO czego służy?
  37. Czy wirtualna maszyna PVM może składać się z różnych węzłów, czy wszystkie maszyny muszą być identyczne?
  38. Co to jest namiastka (stub)?
  39. Co to jest XDR?
  40. Co to jest i do czego służy rejestr serwerów?
  41. Proszę narysować schemat komunikacyjny Java RMI
  42. Jakie warunki musi spełniać klasa, aby mogła być serwerem Java RMI?
  43. Czy klient RMI musi znać implementację serwera?
  44. Proszę opisać technologię CORBA


CategoryCourse


2015-09-23 06:45