Plan działania

Moja analiza ulepszenia algorytmu okazuje się właściwa, problem leży po innej stronie. Po kolei.

Graf można przestawić jako macierz sąsiedztwa, czyli tabelkę gdzie komórka w wierszu y i kolumnie x ma oznaczone czy wierzchołki x i y są połączone krawędzią. Jeśli nie nie, to komórka zawiera liczbę 0, a jeśli tak to wpisana jest tam waga takiej krawędzi.

W moim programie do obliczania najkrótszych ścieżek, chciałabym odseparować niepotrzebne krawędzie, czyli takie które nie poprawiają wyniku. Żeby policzyć to równolegle, należy podzielić całą macierz sąsiedztwa na k części i rozesłać je wśród k maszyn. Każda maszyna będzie analizowała czy na jej części da się pominąć jakieś krawędzie.

W tym celu chciałam użyć dwóch faz Reduce, mianowicie:

  1. Map, gdzie różne części macierzy sąsiedztwa są rozsyłane do różnych maszyn
  2. Reduce, gdzie na każdej otrzymanej części jest liczone które krawędzie można pominąć w obliczeniach,
  3. Reduce, gdzie wszystkie wyniki są gromadzone na jedną maszynę i uruchamiany jest algorytm BFS

Początkowo myślałam, że można uczyć do tego klasy ChainMapper, niestety okazało się, że pozwala ona wykonywać sekwencje Map -> Map -> Reduce. Tak samo ChainReducer, nie pozwala mi na wykonanie dwóch Reduce pod rząd, a jedynie Map -> Reduce -> Map.

Co zrobić zatem aby móc wykonać Map -> Reduce -> Reduce? Nie ma niestety takiej możliwości, muszę zaimplementować dwa wykonania, Map -> Reduce oraz Map -> Reduce, gdzie danymi wejściowymi dla tej drugiej pary będą dane wyjściowe pierwszej.Trzeba będzie korzystać z plików pośrednich zapisanych na HDFS i nie zapomnieć o ich późniejszym usunięciu.

Może się okazać, że jedna iteracja nie wystarcza, czyli w jednej fazie maszyny nie usunęły wystarczająco dużo krawędzi aby całość zmieściła się w pamięci jednej maszyny gdzie będzie można uruchomić algorytm BFS. Oznacza to, że właściwą implementacją będzie jak następuje:

Do póki macierz sąsiedztwa nie jest wystarczająco mała:
—-Podziel macierz na k części
—-Wyślij je do k maszyn
—-Usuń niepotrzebne krawędzie
Wyślij dane do jednej maszyny
Oblicz BFS

Pytanie brzmi ile będzie powtórzeń w pętli i czy nie będzie ich zbyt dużo? Badania zaprezentowane w [1], że tych powtórzeń nie jest tak dużo (tzn mniej niż liniowo), więc możemy sobie na takie powtarzania pozwolić.

Oprócz skupiania się na kodzie, czas najwyższy skupić się też wreszcie na samej pracy. Plan jest taki, aby w tym tygodniu dostarczyć opisany algorytm BFS, sposoby rozwiązania problemu oraz wykonanie go dla dużych danych. Oczywiście niezbędne będzie też porównanie z właściwymi wynikami. Uff, dużo tego.

Plan działania na teraz to:

  • Zmiana algorytmu tak żeby nie korzystał z ChainMapper tak jak robi to teraz, bo niestety ale jeden z Reducerów jest pominięty
  • Uruchomienie algorytmu dla danych z Wikipedii
  • Uruchomienie tego samego algorytmu ale w Sparku, żeby móc porównać wyniki z algorytmem bibliotecznym
  • Opisanie tego wszystkiego!

Mam 2-3 dni na to żeby to zrobić, inaczej będę utykać na tym pierwszym algorytmie. Przede mną jeszcze algorytmy obliczania najkrótszych ścieżek między każdą parą wierzchołków, Page Rank i zliczanie trójkątów. Te dwa ostatnie wydają się być łatwiejsze w obliczeniach MapReduce, ale nie chcę nic mówić zanim nie wypróbuję.

Do dzieła!

__
Literatura:

[1] – Filtering: A Method for Solving Graph Problems in MapReduce, Lattanzi, Moseley, Suri, Vassilvitskii  

 

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Connecting to %s