Seminarium: Systemy Rozproszone
16 października 2014, godzina 12:15, sala 4070
Piotr Wojciechowski

Optymalizacja najkrótszych ścieżek w grafach skierowanych na koprocesorach

Wiele problemów sprowadza się do policzenia minimalnych odległości pomiędzy każdymi dwoma wierzchołkami w grafie. Znalezienia najkrótszych ścieżek jest dobrze znanym w literaturze problemem. Jednak tradycyjne podejścia nie bardzo nadają się do dużych, rzadkich grafów:

• algorytm Floyda-Warshalla ma złożoność pamięciową O(V²),
• algorytm Dijkstry wykazuje ograniczone możliwości zrównoleglenia.

Jednym z podejść do umożliwienia efektywnych obliczeń na dużych grafach jest wykorzystanie akceleratorów obliczeniowych. Zwykle wiąże się to z koniecznością przeprojektowania algorytmu, aby wykorzystać w pełni potencjał urządzenia.

Chciałbym opowiedzieć skąd tak naprawdę wziął się mój temat. Pokażę z jakimi problemami stykają się najlepsze implementacje. Spróbuję również udzielić odpowiedzi na tradycyjne pytanie "co z Twoją pracą magisterską".

Zapraszam!
Piotr Wojciechowski

Bibliografia:

• Andrew Davidson, Sean Baxter, Michael Garland, John D. Owens "Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths"
• Tomasz P. Michalak, Karthik .V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings "Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality"