Algorytmy Równoległe


Zadanie 1 - dekompozycja domenowa

Etap 1: implementacja sekwencyjna i projekt algorytmu równoleglego

Opis zadania

Do wykonania:

  1. Proszę rozpisać formułę iteracyjnego obliczania temperatury i na jej podstawie zaimplementować algorytm sekwencyjny. Sprawdzić jego działanie dla zadanych warunków początkowych i brzegowych (np. na początku temperatura całej płytki oraz na jej brzegach wynosi zero, z wyjątkiem górnego brzegu, gdzie wynosi 100. Z czasem temperatura powinna się wyrównywać na całej powierzchni płytki i dążyć do zera.

  2. Proszę zaprojektować algorytm równolegly zgodnie z metodologią PCAM.

Na adres balis at agh edu pl proszę przysłać sprawozdanie w formacie PDF zawierające:

  • iteracyjny wzór na temperaturę,
  • opis algorytmu równoległego zgodnie z metodologią PCAM. W szczególności proszę zwrócić uwagę na pytania "checklist".
Termin nadsyłania sprawozdania: 24.10.2016.

Termin demonstracji implementacji sekwencyjnej: na zajęciach 25.10.2016.

Etap 2

Opis zadania

Oddawanie 2 etapu:

  • Sprawozdanie rozszerzone o wyniki pomiarow wskaznikow wydajnosci prosze przeslac w formacie PDF do 7.11.2016.
  • Demonstracja koncowej implementacji i wizualizacji: na zajeciach 8.11.2016.

Zadanie 2 - dekompozycja funkcjonalna

Opis zadania

Implementacja

  • Implementację proszę wykonać w oparciu o podejście wielowątkowe w Javie. Można też wykorzystać Cilk (C++).
  • Proszę zaimplementować dwie strategie szeregowania: work stealing i work sharing (więcej na ten temat).
  • Strategię work stealing proszę zaimplementować przy pomocy ForkJoin Pool (lub mechanizmy Cilk).

Testowanie

Do testowania proszę wykorzystać dostępne w sieci zbiory danych, np.:

Badanie algorytmu

Proszę porównwać obydwie strategie szeregowania: work sharing i work stealing. Dalsze szczegóły w pliku PDF.

Oddawanie zadania

  • Prezentacja implementacji sekwencyjnej i konsultacje: na zajęciach 22.11.2016.
  • Sprawozdanie zawierające wyniki badań proszę przesyłać w formacie PDF do dnia 5.12.2016.
  • Demonstracja implementacji: na zajęciach 6.12.2016.

Zadanie 3 - algorytmy grafowe (Page Rank i spójna składowa)

Wstęp do Page Rank oraz systemu Apache Spark: slajdy oraz notatki

Scalability? At what COST?

Zadanie:

  1. Uruchomić przykłady PageRank lokalnie i na Zeusie.
  2. Zaimplementować algorytm obliczania spójnej składowej (connected components) zgodnie z modelem Pregel.

    Zasada działania algorytmu:

    1. Na początku każdy wierzchołek oznaczamy innym znacznikiem (liczbą).
    2. Każdy wierzchołek wysyła swój znacznik do wszystkich sąsiadów.
    3. Jeżeli minimum z otrzymanych zniaczników jest mniejsze od własnego, wierzchołek zastępuje swój znacznik przez minimum otrzymanych.
    4. Powtarzamy krok 2 aż przestaną zachodzić zmiany
  3. Przetestować na dużych grafach:
    1. rzeczywistych: https://snap.stanford.edu/data/index.html#web
    2. wygenerowanych losowo (przykład z użyciem org.apache.spark.graphx.util.GraphGenerators) https://spark.apache.org/docs/latest/graphx-programming-guide.html
  4. Przetestować jaki wpływ ma sposób podziału danych http://ampcamp.berkeley.edu/wp-content/uploads/2012/06/matei-zaharia-amp-camp-2012-advanced-spark.pdf (przykład od slajdu 22).
Termin oddawania zadań: 10.01.2017


Linki

Dostęp do infrastruktury PL-Grid (klaster Zeus)

Platforma vCluster

Przypomnienie z TPR: tutorial MPI



Bartosz Balis, balis at agh edu pl