Algorytmy Równoległe

Zadanie 1 - dekompozycja domenowa

Celem zadania jest implementacja i eksperymentalna weryfikacja kilku wariantów algorytmu równoległego dla numerycznego problemu rozpływu ciepła.

Równanie ciepła i jego dyskretyzajca oraz warianty algorytmu równoległego są opisane tutaj.
Proszę opisać przedstawiony algorytm równoległy (dowolnie wybrany wariant) zgodnie z metodologią PCAM.
Proszę zaimplementować algorytm sekwencyjny oraz opisane 4 warianty algorytmu równoległego wykorzystując MPI.
Korzystając z dostępu do klasta Zeus, proszę eksperymentalnie wyznaczyć przyspieszenie i efektywność 4 wariantów algorytmu równoległego. Dla algorytmów z reduntantnymi obliczeniami ("Overlapped") proszę przetestować kilka wartości parametru r. Eksperymenty powinny być wykonywane dla różnych (w tym dużych!) rozmiarów problemu i różnej liczby wykorzystywanych węzłów obliczeniowych.
Proszę wybrać najefektywniejszy algorytm równoległy i dodać do niego zapisywanie danych na dysk w celach późniejszej wizualizacji. Proszę to zrobić jak najefektywniej, tak żeby wpływ na same obliczenia był jak najmniejszy. Przykładowo nie trzeba zapisywać wszystkich punktów i każdego kroku czasowego. Proszę zmierzyć przyspieszenie algorytmu z włączonym zapisem danych.
Proszę napisać prostą wizualizację (mapa kolorów, animowany gif) w celu demonstracji wyników i poprawności algorytmu.
Sprawozdanie powinno zawierać: opis algorytmu według schematu PCAM, wyniki eksperymentów (wykresy i opis), oraz interpretację tych wyników.

Terminy:

Implementację proszę wykonać w oparciu o podejście wielowątkowe w Javie.
Proszę zaimplementować dwie strategie szeregowania: work stealing i work sharing (więcej na ten temat).
Strategię work stealing proszę zaimplementować przy pomocy Fork Join framework.
Przykład wykorzystania RecursiveTask

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

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

Sprawozdanie zawierające wyniki badań proszę przesyłać w formacie PDF do dnia 26.11.2017.
Demonstracja implementacji: na zajęciach 27.11.2017.

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

Zadanie:

Uruchomić przykłady PageRank lokalnie i na Zeusie.
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
Algorytm zaimplementować w trzech wariantach:
1. Implementując graf bezpośrednio na abstrakcji RDD. W tym celu proszę przerobić przykład PageRank, m.in. dodając warunek stopu.
2. Korzystając z Pregel API biblioteki GraphX.
3. Wywołując gotową implementację algorytmu z biblioteki GraphX.
Porównać czas obliczeń wszystkich trzech implementacji testując 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
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ń: na zajęciach 15.01.2018

Przypomnienie z TPR: tutorial MPI

Bartosz Balis, balis at agh edu pl