Algorytmy i metody skalowalnego przetwarzania danych

Podstawowe wiadomości z zakresu informatyki obejmujące bazy danych i programowanie współbieżne oraz systemy operacyjne.

przedmiot obligatoryjny

30 godz. - wykład

30 godz. - ćwiczenia

30 godz. - praca z literaturą

60 godzin - realizacja projektów zaliczeniowych

10 godzin - konsultacje

K_W04

zna zaawansowane metody projektowania i analizowania złożoności obliczeniowej algorytmów i programów sekwencyjnych, równoległych i rozproszonych

K_W12

ma wiedzę o aktualnych kierunkach rozwoju i o najnowszych odkryciach w zakresie technologii sieciowych i architektur komputerów

K_U04

projektuje i analizuje algorytmy rozproszone; potrafi uzasadnić ich poprawność i przeanalizować złożoność

K_U13

umie znajdować niezbędne informacje w literaturze fachowej, bazach danych i innych źródłach, zna podstawowe czasopisma i konferencje naukowe w swojej specjalności

K_U14

potrafi w sposób popularny przedstawić najnowsze wyniki odkryć dotyczących sieci komputerowych, systemów obliczeniowych i informatyki w ogóle

1. Kreatywność: Myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań.

2. Sumienność i dokładność: Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny.

3. Komunikatywność: Skutecznie przekazuje innym swoje myśli w zrozumiały sposób; właściwie posługuje się terminologią fachową; potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę.

4. Dążenie do rozwoju: Jest nastawiony na nieustanne zdobywanie nowej wiedzy, umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych.

5. Wytrwałość i konsekwencja: Pracuje systematycznie i posiada umiejętność pozytywnego podejścia do trudności stojących na drodze do realizacji założonego celu; dotrzymuje terminów.

Wykład i laboratorium.

- pokaz

- wykład informacyjny (konwencjonalny)

- klasyczna metoda problemowa
- laboratoryjna
- referatu

W ramach wykładu zamierzam przedstawić modele obliczeniowe Pregel i MapReduce, rozmaite sposoby wyznaczania ich złożoności, algorytmy rozwiązujące konkretne problemy obliczeniowe.

Teoria informatyki obejmuje wiedzę o algorytmach rozwiązujących problemy o dowolnej złożoności obliczeniowej i przy dowolnych poziome równoległości. Praktyczna implementacja tych algorytmów napotykała do tej pory trudności nie do pokonania, np. nikomu nie udało się w praktyce zaimplementować teoretycznie doskonale rozpracowanego modelu przetwarzania PRAM. Zmiana tego stanu rzeczy dokonała się w 2004 wraz z opublikowanie informacji o modelu obliczeniowym MapReduce i jego praktycznej implementacji. Rok 2010 to pierwsza publikacja o Pregelu, tj. modelu i implementacji obliczeń na ogromnych grafach. Choć oba te modele są dość proste i można by rzec, że znane w literaturze, jednak ich przełomowość wynika, z tego, że udało się je zaimplementować w wielkiej skali, tj, na danych o wielkości rzędu 10^12 rekordów/obiektów i na tysiącach komputerów. Do tej pory, teoretycy potrafili zbudować algorytm na dowolnego n, ale praktycy potrafili je zaimplementować jedynie dla n nie większego niż 10^9. MapReduce i Pregel przesuwają te granicę o kilka rzędów wielkości.

W ramach wykładu zamierzam przedstawić oba modele obliczeniowe, rozmaite sposoby wyznaczania ich złożoności, algorytmy rozwiązujące konkretne problemy obliczeniowe za pomocą MapReduce i Pregel.

[1] Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation - Volume 6 (OSDI'04), Vol. 6. USENIX Association, Berkeley, CA, USA, 10-10.

[2] Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (SIGMOD '10). ACM, New York, NY, USA, 135-146. DOI=10.1145/1807167.1807184 http://doi.acm.org/10.1145/1807167.1807184

[3] Semih Salihoglu, Jennifer Widom: Optimizing Graph Algorithms on Pregel-like Systems. PVLDB 7(7): 577-588 (2014)

[4] Da Yan, James Cheng, Kai Xing, Yi Lu, Wilfred Ng, Yingyi Bu: Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees, 2014

[5] Louise Quick, Paul Wilkinson, and David Hardcastle. 2012. Using Pregel-like Large Scale Graph Processing Frameworks for Social Network Analysis. In Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012) (ASONAM '12). IEEE Computer Society, Washington, DC, USA, 457-463. DOI=10.1109/ASONAM.2012.254 http://dx.doi.org/10.1109/ASONAM.2012.254

[6] Yufei Tao, Wenqing Lin, and Xiaokui Xiao. 2013. Minimal MapReduce algorithms. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD '13). ACM, New York, NY, USA, 529-540. DOI=10.1145/2463676.2463719 http://doi.acm.org/10.1145/2463676.2463719

Zaliczenie laboratorium odbywa się na podstawie 5-6 projektów zaliczeniowych wykonywanych częściowo na labach i częściowo samodzielnie.

Egzamin ustny odbywa się po zakończeniu wykładów