Model obliczeniowy

  • 6 min

Jak wspomniano wcześniej, narzędzie GraphLab obsługuje wiele aparatów, które umożliwiają wykonywanie funkcji wierzchołków synchronicznie lub asynchronicznie. Narzędzie GraphLab obsługuje obecnie następujące trzy aparaty:

  • synchroniczny.
  • Aparat asynchroniczny
  • asynchroniczny serializowany,

synchroniczny.

Aparat synchroniczny wykonuje kolejno fazy zbierania, stosowania i rozpraszania (Gather, Apply, Scatter — GAS) dla poszczególnych aktywnych wierzchołków przypisanych do maszyny. Gdy maszyna ukończy aktualizowanie wszystkich wierzchołków przypisanych do niej w ramach określonej iteracji, czeka na następną iterację. Wierzchołki aktywowane w każdej iteracji są zaplanowane do wykonania w następnej iteracji. W tym trybie wykonywania narzędzie GraphLab w rzeczywistości wykonuje obliczenia w modelu równoległym, zbiorczym i synchronicznym (Bulk Synchronous Parallel, BSP), podobnie do systemów, takich jak Pregel. W związku z tym obliczenia wykonywane przez aparat synchroniczny są zgodne z modelem pełnej spójności omówionym wcześniej.

Wydajność aparatu synchronicznego może być bardzo niska w przypadku wykonywania algorytmów MLDM, ponieważ faza, etap i krok nadrzędny podczas wykonywania mogą zostać zakończone dopiero po zatwierdzeniu ostatniego zadania i wierzchołka obliczenia. Czas wykonania każdej fazy, etapu i kroku nadrzędnego jest określany na podstawie najwolniejszego zadania i wierzchołka.

Aparat asynchroniczny

Przy użyciu aparatu asynchronicznego narzędzie GraphLab wykonuje aktywne wierzchołki, gdy maszyny stają się dostępne. Zmiany wprowadzone do wierzchołka i danych brzegowych w ramach funkcji stosowania i rozpraszania są natychmiast zatwierdzane do grafu i udostępniane do kolejnych obliczeń dla sąsiednich wierzchołków. Główną zaletą korzystania z aparatu asynchronicznego jest wyeliminowanie oczekiwania na kontynuowanie kolejnej iteracji, co umożliwia zwiększenie równoległości i wydajności. Aparat asynchroniczny wykonuje obliczenia wierzchołków przy użyciu modelu spójności wierzchołków, jak wspomniano wcześniej.

Mimo że aparaty asynchroniczne mogą powodować wzrosty empiryczne i algorytmiczne w wielu typowych aplikacjach MLDM, stanowią one krytyczne wyzwanie. W szczególności wykonywanie asynchroniczne zwiększa złożoność projektu i debugowania oraz może zwracać niejednoznaczne wyniki.1 Na przykład gdy symulacje statystyczne są wykonywane asynchronicznie, istnieje wysokie prawdopodobieństwo niejednoznacznych wyników. Brak uważnej kontroli tego warunku może spowodować niestabilność, a nawet rozbieżność.2 W niektórych aplikacjach zwiększona równoległość wykonywania asynchronicznego jest równoważona przez zwiększoną liczbę iteracji wymaganą do osiągnięcia zbieżności.

asynchroniczny serializowany,

Narzędzie GraphLab zapewnia zrównoważony kompromis między aparatami synchronicznymi i asynchronicznymi, umożliwiając użycie aparatu asynchronicznego serializowanego. Ten aparat narzędzia GraphLab uniemożliwia współbieżne uruchamianie funkcji GAS sąsiadujących wierzchołków przez zastosowanie szczegółowego protokołu blokowania równoległego, znanego jako schemat Chandy-Misra.3 Przy użyciu tego schematu maszyna wykonująca wierzchołek uzyskuje blokadę sąsiednich krawędzi, które istnieją na maszynie. (Jest to określane podczas chciwego partycjonowania krawędzi opisanego wcześniej). Wynikowe wykonanie jest gwarantowane do serializacji, tj. istnieje kilka szeregowych kolejności wykonywania, których wyniki są równoważne wynikam podczas wykonywania przy użyciu aparatu asynchronicznego serializowalnego. Asynchroniczne wykonywanie grafu z zastosowaniem serializacji jest równoważne z omówionym wcześniej modelem spójności krawędziowej.

Odwołania

  1. J. Gonzalez, Y. Low, H. Gu, D. Bickson i C. Guestrin (październik 2012 r.). PowerGraph: rozproszone obliczenia równoległe grafu na grafach naturalnych w ramach 10 konferencji USENIX na temat projektowania i implementacji systemów operacyjnych
  2. J. Gonzalez, Y. Low, A. Gretton i C. Guestrin (2011). Równoległe próbkowanie Gibbs: Od kolorowych Felds do cienkich drzew skrzyżowań w AISTATS, vol. 15, pp. 324-332
  3. Chandy, K. M. i Misra, J. (1984). Problem filozofów picia ACM Trans. Program. Lang. Syst. 632–646

Sprawdź swoją wiedzę

1.

Wypełnij następujące zdanie:

Narzędzie GraphLab umożliwia wykonywanie funkcji wierzchołków _______________.